带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法

doi:10.16381/j.cnki.issn1003-207x.2017.05.010

摘要/Abstract

摘要： 需求可拆分车辆路径问题是车辆路径问题中的重要类型，又可分为需求可任意（按计量单位）拆分和需求依订单拆分两种子类型，在配送车辆路径优化等实际问题中有着广泛的应用背景。综合考虑客户需求依订单拆分和客户对于被服务时间的要求，本文针对带软时间窗的需求依订单拆分车辆路径问题及其优化算法进行研究。建立了问题的数学模型，设计了求解的禁忌搜索算法，以Solomn标准算例为基础构造算例对算法进行测试，并将求解结果与相关文献中的结果进行比较。结果表明，算法收敛性较好，为解决该类问题提供了一种方法。

关键词: 车辆路径问题, 需求依订单拆分, 软时间窗, 禁忌搜索算法

Abstract: As an important type of vehicle routing problem, split delivery vehicle routing problem, which can be divided into two subtypes, split deliveries without restriction (by unit) and split deliveries by order, has broad applications such as distribution vehicle routing optimization and so on. In most of the present research of split delivery vehicle routing problem, customers' demands can be split without restrictions. However, in practical, sometimes a customer order consists of several cargos and could not be split during deliveries. So the cargos in the same order can only be delivered by the same vehicle. In that condition, customers' demands can be split in orders while a specific order could not be split. In addition, more and more customers have time window requirement during the distribution process. Considering this two respects, the vehicle routing problem with soft time windows and split deliveries by the order and its optimization algorithm are presented. The problem allows that the same customer can be serviced by multiple vehicles and the customer demand can be split but not split a specific order. Customers can be served either in the specified time windows or out of the time windows with according punishment. A mixed integer programming model for the problem is constructed and a tabu search algorithm for the model is proposed. The proposed algorithm was coded and tested on the problems which are based on the benchmark problems generated by Solomn. The computational results are compared with the ones in related literatures. It shows that the algorithm converges well and effectively solves the problem.

Key words: vehicle routing problem, split deliveries by order, Soft time windows, tabu search algorithm

中图分类号:

O221
F253.4

符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 中国管理科学, 2017, 25(5): 78-86.

FU Zhuo, LIU Wen, QIU Meng. A Tabu Search Algorithm for the Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order[J]. Chinese Journal of Management Science, 2017, 25(5): 78-86.

参考文献

[1] Dror M, Trudeau P. Savings by split delivery routing[J]. Transportations Science, 1989, 23(2):141-145.
[2] Fu Zhuo, Eglese R, Li L Y O. A unified tabu search algorithm for vehicle routing problems with soft time windows[J]. Journal of the Operational Research Society, 2008, 59(5):663-673.
[3] Dror M, Trudeau P. Split delivery routing[J]. Naval Research Logistics, 1990, 37(3):383-402.
[4] Archetti C, Savelsbergh M W, Grazia Speranza M. To split or not to split:That is the question[J]. Transportation Research Part E:Logistics and Transportation Review, 2008,44(1):114-123.
[5] Archetti C, Savelsbergh M W, Speranza M G. Worst-case analysis for split delivery vehicle routing problems[J]. Transportation Science, 2006, 40(2):226-234.
[6] Archetti C, Feillet D, Gendreau M, et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C:Emerging Technologies, 2011,19(5):741-750.
[7] Archetti C, Mansini R, Speranza M G. Complexity and reducibility of the split delivery problem[J]. Transportation Science, 2005,39(2):182-187.
[8] Jin Mingzhou, Liu Kai, Eksioglu B. A column generation approach for the split delivery vehicle routing problem[J]. Operations Research Letters, 2008, 36(2):265-270.
[9] Chen S8, Golden B, Wasil E. The split delivery vehicle routing problem:Applications, algorithms, test problems, and computational results[J]. Networks, 2007,49(4):318-329.
[10] Salani M, Vacca I. Branch and price for the vehicle routing problem with discrete split deliveries and time windows[J]. European Journal of Operational Research, 2011, 213(3):470-477.
[11] 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.
[12] Archetti C, Speranza M G, Hertz A. A tabu search algorithm for the split delivery vehicle routing problem[J]. Transportation Science, 2006, 40(1):64-73.
[13] Aleman R E, Hill R R. A tabu search with vocabulary building approach for the vehicle routing problem with split demands[J]. International Journal of Metaheuristics, 2010, 1(1):55-80.
[14] Berbotto L, García S, Nogales F J. A randomized granular tabu search heuristic for the split delivery vehicle routing problem[J]. Annals of Operations Research, 2014, 222(1):153-173.
[15] Campos V, Corberán A, Mota E. A scatter search algorithm for the split delivery vehicle routing problem[M]//Fin R A,Rothlauf F. Advances in Computational Intelligence in Transport, Logistics, and Supply Chain Management,Berlin-Heidelberg:Springer,2008:137-152.
[16] 谢毅. 需求可拆分的物流车辆路线问题研究[D]. 上海:同济大学,2006.
[17] 孟凡超,陆志强,孙小明. 需求可拆分车辆路径问题的禁忌搜索算法[J]. 计算机辅助工程,2010, 9(1):78-83.
[18] 陆琳. 不确定信息车辆路径问题及其智能算法研究[M]. 北京:科学出版社,2010.
[19] 李三彬,柴玉梅,王黎明. 需求可拆分的开放式车辆路径问题的研究[J]. 计算机工程,2011, 37(6):168-171.
[20] 刘旺盛,杨帆,李茂青,等. 需求可拆分车辆路径问题的聚类求解算法[J]. 控制与决策,2012, 27(4):535-540.
[21] 刘旺盛,黄娟. 需求可拆分的车辆路径问题的分段求解[J]. 集美大学学报,2011, 16(1):38-44.
[22] 杨亚璪,靳文舟,郝小妮,等. 求解集送货可拆分车辆路径问题的启发式算法[J]. 华南理工大学学报,2010, 38(3):58-62.
[23] Pankratz G. A grouping genetic algorithm for the pickup and delivery problem with time windows[J].OR Spectrum,2005,27(1):21-41.
[24] Frizzell P W, Gi In J W. The split delivery vehicle scheduling problem with time windows and grid network distances[J]. Computers & Operational Research, 1995, 22(6):655-667.
[25] Solomn M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2):254-265.
[26] 侯立文,谭家美,赵元. 求解带时间窗的客户需求可分条件下的车辆路径问题[J]. 中国管理科学,2007, 15(6):78-83.
[27] 马华伟, 叶浩然, 夏维. 允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解[J]. 中国管理科学,2012, 20(S1):43-47.
[28] 李宁,邹彤,孙德宝. 带时间窗车辆路径问题的粒子群算法[J]. 系统工程理论与实践,2004, 24(4):134-140.
[29] 吴耀华,张念志. 带时间窗车辆路径问题的改进粒子群算法研究[J]. 计算机工程与应用,2010, 46(15):345-349.
[30] 马炫,彭芃,刘庆. 求解带时间窗车辆路径问题的改进粒子群算法[J]. 计算机工程与应用,2009, 45(27):679-684.
[31] 汪勇,丁凡,吴志华. 协同进化遗传算法求解带时间窗的车辆路径问题[J]. 统计与决策,2010, (10):76-87.
[32] 潘立军,符卓. 求解带时间窗取送货问题的遗传算法. 系统工程理论与实践, 2012, 32(1):120-126.
[33] 潘立军,符卓. 求解带时间窗车辆路径问题的时差插入检测法. 系统工程理论与实践, 2012, 32(2):319-322.
[34] 宾松,符卓. 求解带软时间窗的车辆路径问题的改进遗传算法[J]. 系统工程,2003, 21(6):79-85.
[35] 祁文祥,陆志强,孙小明. 带软时间窗的集货与送货多车辆路径问题节约算法[J]. 交通运输工程学报,2010, 10(2):99-103.
[36] Dror M, Laporte G, Trudeau P. Vehicle routing with split deliveries[J]. Discrete Applied Mathematics,1994, 50(3):239-254.
[37] Archetti C, Mansini R, Speranza M G. Complexity and reducibility of the skip delivery problem[J]. Transportation Science, 2005, 39(2):182-187.
[38] Gendreau M, Laporte G, Potvin J Y. Metaheuristics for the Capacitated VRP[M]//Toth P, Vigo D. The vehicle routing problem. Philadelphia, PA:SIAM Monographs on Discrete Mathematics and Applications, 2002:129-154.
[39] Cordeau J F, Gendreau M, Laporte G, et al. A guide to vehicle routing heuristics[J]. Journal of the Operational Research Society, 2002, 53(5):512-522.
[40] Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004, 31(12):1947-1964.
[41] 刘光远,贺一,温万惠. 禁忌搜索算法及应用[M]. 北京:科学出版社,2014.
[42] 傅少川,胡梦飞,唐方成. 禁忌搜索算法在单分配多枢纽辐射式物流网络中的应用[J]. 中国管理科学,2012, 20(3):145-151.
[43] 李进,傅培华,李修琳,等. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学,2015, 23(10):98-106.
[44] Fu Zhuo, 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.