更新时间：2023-01-05 01:02
重复运输是指一种货物本可以直达目的地，但由于某种原因而在中途停卸重复装运的不合理运输现象。简言之就是，本来可以直接将货物运到目的地，但是在未达目的地之处，或目的地之外的其它场所将货卸下，再重复装运送达目的地，这是重复运输的一种形式。另一种形式是，同品种货物在同一地点一面运进，同时又向外运出。重复运输的最大毛病是增加了非必要的中间环节，这就延缓了流通速度，增加了费用，增大了货损。
物流作为第三利润源泉, 已经越来越引起人们的重视。降低物流成本成为人们考虑物流的一个重要方面,而在物流成本中运输成本占据着很大的比重。物流产业一直缺乏现代运输及物流配送的路径优化系统, 车辆在进行运输配送集货的时候,不得不行驶更多的路, 需要更多的车辆, 这就导致了货运的空载率过高及空载行驶里程过大, 极大地浪费了物流资源,带来了很大的物流运输成本。
路径优化问题是指行驶尽量少的路程来完成所有的任务。通过载重量一定的车辆对每一个结点完成集货或配送等任务, 其中每一个结点都有一定量货物的供给或需求任务。它要求不能超出车辆的载重限制,同时尽量使车辆行驶距离最短。国内外对路径优化的研究主要集中在启发式算法, 遗传算法、模拟退火算法、禁忌搜索算法和蚁群算法几个方面。传统的启发式算法多把重点放在路程的节约上面, 因此有众多的学者对它提出了改进。如首先对车辆进行初始的估计, 将车辆出车费用和行驶费用共同考虑在一起, 而不是把节约路程作为唯一的指标, 以及以车辆载重约束分组, 然后在组内进行路线的设计。节约启发式算法还被应用于集送一体化问题。新的智能算法也被广
泛应用于VRP问题,如用遗传算法解决不确定车辆数的车辆路径问题, 用混合遗传算法来解决物流配送路径的优化问题。另外, 基于模糊可能性的混合遗传算法,研究了决策者的主观嗜好对决策目标的影响。改变编码的方式, 用隐含编码方式进行计算以及双种群遗传算法也用来解决这一问题。各类蚁群算法也被广泛应用于这一问题。为提高搜索效率, 提出了几种结合算法, 如将粒子群优化算法与模拟退火算法结合,以及运用多初始解和全局禁忌表等各种措施来减小解的不稳定性和扩大搜索范围。
国内外大部分的研究将注意力放在不可重复运输上,即每项任务只能有某一辆车来完成, 这样虽然降低了研究的复杂度,但同时也可能会造成需要更多的车辆来完成运输配送的任务。由于出动一辆车的固定成本远远大于车辆的一定里程内的行驶成本,对于一个具体的问题,寻求能完成任务的最少车辆数是减少成本的有效方法。实际上有的时候一个任务点在被两个车辆服务时,不但会减少车辆的使用数目,并且可能还会使总路程减少,进而降低总的运输费用。因此,寻求在最少车辆的情况下,来降低行车距离就是本文将要研究的内容。
假设有一个物流集货中心,编号为0, 拥有多台载重量为q的车辆。有m项货物运输任务需要完成, 以1, 2, …, i, …, m表示,已知任务i的货运量为gi(i=1, 2, …, m),且gi (1)所有任务都是事先安排的, 调度问题是静态的。 (2)每辆车在执行任务完毕后必须再回到原来所在位置,即再回到集货中心。 (3)成本分为运输成本(与路径有关)和出车成本(与出车数量有关)。 (4)车辆的运营费用权数大于运输成本的权数。启发式算法是一种简单的、易实现的算法,它主要是从节约算法(Clarke-Wright算法)出发而得到的一种算法。由于VRP问题是NP问题,精确求解非常困难,启发式算法具有快速求解NP难题、对初值要求不严格等优点,便于计算机系统的实现。因此,研究启发式算法不失为一种可行的方向。本文将在节约算法的基础上解决可重复运输的路径优化问题,通过合理的算法,以总成本最低为目标来实现。以cij表示车辆从点i行驶到点j的距离,得到点i和点j连接在一条线路上的费用节约值sij=c0i+c0j-cij。把cij排列成序,在安排路线时,尽量首先安排节约值大的,这样使总路程最少。若超出车辆的行驶里程或者超出车辆的载重限制,则结束这条路线,重新进行选择。在传统节约算法搜索合并中,每次都是取M内的第一项sij, 即节约值最大的那个, 考察它们的货程中的局部最优性,没有考虑到整体最优性。为降低这种局部最优性, 我们在实施车辆合并后, 考察其车辆的剩余载重量与总任务的、尚不满足一辆车的货物量, 根据大小, 确定是否进行下一步的货物收集任务来进一步完善路径,降低空载率。 本文以节约式算法为基础, 构造了路径优化的可重复运输数学模型, 并给出了有效解决这一问题的方法,实现了降低运输总成本的目的, 具有很强的现实意义。最后通过算例证明了该做法是可行性, 结果也比以前的解决办法需要更低的成本。在实际应用中, 如何在实现路径优化的同时, 解决企业运输的时效性, 即时间窗问题, 是路径优化问题研究的难点,也是必须要解决的问题。特别是在允许等待和延迟的情况下, 如何建立一套模糊规则来衡量上述惩罚或损失来解决模糊时间窗问题是今后研究的一个方向。