随机性路径优化问题综述

杨其芝

((重庆交通大学，重庆 400074)

引言

我国经历了40年的改革开放，市场经济不断繁荣，公路网的基本全面覆盖。物流配送的费用、时间等直接影响着生产的成本和企业的发展。配送的路径优化是物流配送中的重要环节，它直接影响着物流配送的效率及质量。所以路径优化问题是当前物流研究的重要内容。

车辆路径问题(VRP)问题最早于1959年由Dantzig和Fulkerson提出。路径优化问题在早期主要研究的是确定性问题，确定性问题就是指所有的信息如：客户信息、交通状况、车辆信息都是确定的。在这些确定的信息下对路径进行优化，得到满足这些信息的最优解或者满意解。

然而，实际问题中，路径优化中的信息存在很大的不确定性。因此，人们把研究方向转向了随机性路径优化问题。本文主要从随机客户需求，随机时间和随机用户三个方面进行路径优化综述。

1 随机客户需求

1992年Bertsimas以车辆行驶距离最短为目标，进行了不确定客户需求的研究，其中假设客户的需求按照一定的概率分布[1]。Lei在2011年提出了有时间约束的不确定需求的车辆路径优化问题。并用启发式算法对问题进行求解，并通过实验证实算法的准确性。Yang在2000年讨论了在运输途中有补货点的问题，车辆如果缺货可以提前在途中的补货点进行补给，不需要再返回出发点补给，这是一种带有中途补货的客户随机需求问题。作者使用启发式算法以运输成本最小为目标进行了求解最优路径。

国内对不确定客户需求问题也有许多的研究。2015年，管峰，钟铭等，基于随机顾客需求，采用鲁棒优化模型解决有容量限制的车辆路径优化问题。实例证明该模型能够保证路径再需求波动下的可行性。2016年，薛祥，朱小林探究危险品运输终端需求不确定对运输总成本和安全性的影响，结果显示对路径运输稳定性有影响。

2 随机时间

运输车辆行驶过程中的不确定性，导致车辆的旅行时间和对客户的服务时间是不确定的。1992年，Laporet对于含有不确定旅行时间和不确定服务时间的路径优化问题进行了研究。提出了三种模型,并设计了一种适合三种模型的branch-and-cut算法，并通过实验验证了可行性[2]。2003年Kenyon和Morton对上述问题也进行了研究，提出了两种数学模型。2013年，Tas就讨论了关于软时间窗和随机旅行时间的路径优化，并且通过以成本最小为目的建立了数学模型，通过禁忌搜索算法进行求解，并不断改进优化结果。

国内也有不少学者进行了相应的研究。2006年，张建勇，李军创建了具有模糊行驶时间的VRP问题的数学模型，并通过一种混合遗传算法对该模型进行求解[3]。2009年，李相勇和田澎研究了带时间窗的随机时间问题，建立了模型并用启发式算法进行求解。同年，俞峰考虑了时间以及网络状态的最短路径问题，并对影响算法化简结果的一些因素以及算法的复杂性进行了分析[4]。2011年，张涛等建立了同时去送货的不确定时间路径优化问题，并用分散搜索的方法进行求解。2014年，李锋，魏莹综合考虑车辆在运输过程中的时间和距离，通过多目标混合遗传算法对该问题求解，通过求解验证了算法的有效性[5]。

3 随机客户

1988年，Bertsimas对概率性路径问题进行了研究，其中讨论了概率最小生成树问题，概率性旅行商问题以及对应的选址问题。次年，Waters假设客户对服务的需求存在一定的概率.1995年,Gendreau对随机需求和随机用户同时存在的问题进行研究，作者通过精确算法进行了求解。2004年，Bent和Van Hentenryck研究了动态的具有随机客户和时间窗的问题，目标为最大服务客户量。2006年，Hvattum研究了客户信息未知的动态、随机的车辆路径优化问题，提出了解决该问题的启发式算法。

2012年，曾华在其博士论文中探讨了客户需求存在性和需求量为不确定因素时的概率优化问题，并建立了随机顾客和需求的车辆路径问题的数学模型，分析模型数学特征，给出解决该模型的启发式算法。

4 结论

针对上述研究，可以看出在随机性路径优化研究方面国内外都取得了显著的成果。不过还存在着下述不足：

(1)对不确定性信息的随机路径优化中考虑的不确定性信息比较单一。

(2)虽然通过建立的模型能够求出车辆的最优路径，但是随着路网规模的不断扩大，对问题的求解会变得困难。

(3)缺少对车辆的动态管理和处理运输过程中出现异常信息的快速反应机制的研究。

参考文献：

[1] Bertsimas DJ.A vehicle routing problem with stochastic demand[J].Operation Research,1992,40(3):574-585.

[2] Laporte G.1992.The vehicle routing problem:An overview of exact and approximate algorithms[J].European journal of operational Research,59(3):345-358.

[3] 张建勇,李军.具有模糊旅行时间的VRP的一种混合遗传算法[J].管理工程学报,2006,20(4):13-16.

[4] 李相勇,田澎.带时间窗和随机时间车辆路径问题:模型和算法[J].系统工程理论与实践,2009,29(8),81-90.

[5] 李锋,魏莹.求解随机旅行时间的CVRP问题的混合遗传算法[J].系统管理学报.2014,23(6):819-825.