带多软时间窗VRP及其禁忌搜索算法
|
摘要
分析了带多软时间窗VRP实际应用背景和特点,以使用的车辆数、行驶费用和偏离时间窗的惩罚费用为优化目标,结合车辆载重、最大路长等限制,建立该问题的数学模型,并设计求解该问题的自适应禁忌搜索算法。为增强算法的全局寻优能力,设计了多邻域结构并在算法中嵌入一种有限地接受不可行解的自适应机制。分别用文献中的算例和以Solomon标准算例为基础构建的新算例测试该算法,并将结果与其他方法进行对比分析。对比结果表明,所提出的算法性能较好,能在可接受的时间内求出运输成本更少、满意度更高的解。
The practical application background and characteristics of the Vehicle Routing Problem with Multiple Soft Time Windows(VRPMSTW)are analyzed. Taking the number of vehicles required, total travel cost and time window deviation as the optimization objective, combined with constraints such as vehicle capacity, maximum route length, a corresponding mathematical model is constructed. An adaptive tabu search algorithm is designed to solve the problem. In order to enhance the optimization ability of the algorithm, a multi neighborhood structure is designed and an adaptive mechanism is embedded in the algorithm to accept the infeasible solution. The algorithm is tested with examples in the literature and new instances based on the Solomon benchmark problems. Computational results are compared with other methods in the literature. The comparison results show that the algorithm proposed in this paper has better performance,and it can get the solution with less transportation cost and higher satisfaction in acceptable time.
The practical application background and characteristics of the Vehicle Routing Problem with Multiple Soft Time Windows(VRPMSTW)are analyzed. Taking the number of vehicles required, total travel cost and time window deviation as the optimization objective, combined with constraints such as vehicle capacity, maximum route length, a corresponding mathematical model is constructed. An adaptive tabu search algorithm is designed to solve the problem. In order to enhance the optimization ability of the algorithm, a multi neighborhood structure is designed and an adaptive mechanism is embedded in the algorithm to accept the infeasible solution. The algorithm is tested with examples in the literature and new instances based on the Solomon benchmark problems. Computational results are compared with other methods in the literature. The comparison results show that the algorithm proposed in this paper has better performance,and it can get the solution with less transportation cost and higher satisfaction in acceptable time.
引文
[1]Dantzig G,Ramser J.The track dispatching problem[J].Management Science,1959,10(6):80-91.
[2]宾松,符卓.求解带软时间窗的车辆路径问题的改进遗传算法[J].系统工程,2003,21(6):12-15.
[3]何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践,2013,33(5):1255-1261.
[4]王君,李波.带时间窗车辆路径问题的文化基因算法[J].计算机工程与应用,2012,48(7):26-29.
[5]Archetti C,Bianchessi N,Speranza M G.Branch-and-cut algorithms for the split delivery vehicle routing problem[J].European Journal of Operational Research,2014,238(3):685-698.
[6]潘立军,符卓.求解带时间窗取送货问题的遗传算法[J].系统工程理论与实践,2012,32(1):120-126.
[7]Favaretto D,Moretti E,Pellegrini P.Ant colony system for a VRP with multiple time windows and multiple visits[J].Journal of Interdisciplinary Mathematics,2007,10(2):263-284.
[8]Belhaiza S.A game theoretic approach for the real-life multiple-criterion vehicle routing problem with multiple time windows[J].IEEE Systems Journal,2016.
[9]李珍萍,赵菲,刘洪伟.多时间窗车辆路径问题的智能水滴算法[J].运筹与管理,2015,24(6):1-10.
[10]闫芳,王媛媛.多模糊时间窗车辆路径问题的建模及求解[J].交通运输系统工程与信息,2016,16(6):182-188.
[11]朱玲玲,杨爱琴,吴宽仁.基于协同自适应禁忌的多时窗VRP算法实现[J].计算机应用研究,2012,29(12):4542-4545.
[12]彭碧涛,周永务.多时间窗车辆路径问题的混合蚁群算法[J].计算机工程与应用,2010,46(31):28-31.
[13]马华伟,叶浩然,夏维.允许分割配送的多时间窗车辆路径问题的改进蚁群算法[J].中国管理学,2012(S1):43-47.
[14]刘光远,贺一,温万惠.禁忌搜索算法及应用[M].北京:科学出版社,2014.
[15]Fu Z,Eglese R,Li L Y O.A new tabu search heuristic for the open vehicle routing problem[J].Journal of the Operational Research Society,2005,56(3):267-274.
[16]Gendreau M,Hertz A,Laporte G.A tabu search heuristic for the vehicle routing problem[J].Management Science,1994,40(10):1276-1290.
[17]Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987,35:254-265.
[2]宾松,符卓.求解带软时间窗的车辆路径问题的改进遗传算法[J].系统工程,2003,21(6):12-15.
[3]何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践,2013,33(5):1255-1261.
[4]王君,李波.带时间窗车辆路径问题的文化基因算法[J].计算机工程与应用,2012,48(7):26-29.
[5]Archetti C,Bianchessi N,Speranza M G.Branch-and-cut algorithms for the split delivery vehicle routing problem[J].European Journal of Operational Research,2014,238(3):685-698.
[6]潘立军,符卓.求解带时间窗取送货问题的遗传算法[J].系统工程理论与实践,2012,32(1):120-126.
[7]Favaretto D,Moretti E,Pellegrini P.Ant colony system for a VRP with multiple time windows and multiple visits[J].Journal of Interdisciplinary Mathematics,2007,10(2):263-284.
[8]Belhaiza S.A game theoretic approach for the real-life multiple-criterion vehicle routing problem with multiple time windows[J].IEEE Systems Journal,2016.
[9]李珍萍,赵菲,刘洪伟.多时间窗车辆路径问题的智能水滴算法[J].运筹与管理,2015,24(6):1-10.
[10]闫芳,王媛媛.多模糊时间窗车辆路径问题的建模及求解[J].交通运输系统工程与信息,2016,16(6):182-188.
[11]朱玲玲,杨爱琴,吴宽仁.基于协同自适应禁忌的多时窗VRP算法实现[J].计算机应用研究,2012,29(12):4542-4545.
[12]彭碧涛,周永务.多时间窗车辆路径问题的混合蚁群算法[J].计算机工程与应用,2010,46(31):28-31.
[13]马华伟,叶浩然,夏维.允许分割配送的多时间窗车辆路径问题的改进蚁群算法[J].中国管理学,2012(S1):43-47.
[14]刘光远,贺一,温万惠.禁忌搜索算法及应用[M].北京:科学出版社,2014.
[15]Fu Z,Eglese R,Li L Y O.A new tabu search heuristic for the open vehicle routing problem[J].Journal of the Operational Research Society,2005,56(3):267-274.
[16]Gendreau M,Hertz A,Laporte G.A tabu search heuristic for the vehicle routing problem[J].Management Science,1994,40(10):1276-1290.
[17]Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987,35:254-265.