需求可拆分车辆路径问题(SDVRP)是一类有待深入研究的车辆路径问题, 其求解方法与需求不可拆分的VRP问题有较大的区别. 针对该类问题, 本文提供了一种新的求解思路——基于双层规划模型的三阶段禁忌算法. 首先, 将目标函数设定为大TSP路径成本加上切割增加路径成本, 构建了SDVRP的双层规划数学模型; 然后, 根据双层规划的思路设计了三阶段禁忌启发式算法: 先求包括车场和所有顾客的大TSP路径, 再对大TSP进行切割和拆分, 接着对备选方案进行子路径优化; 最后, 通过实验仿真, 将所提出的三阶段禁忌算法与其他算法进行比较, 结果表明了所提出的算法可以比较有效地求得需求可拆分车辆路径问题的优化解, 是解决需求可拆分车辆路径问题的有效方法.
Abstract
The split delivery vehicle routing problem (SDVRP) is a kind of vehicle routing problem need to be further studied. And its solving method is much different with the traditional VRP's. This paper provides a new heuristic to solve the SDVRP called three-phase tabu algorithm, which is based on the bi-level programming model of SDVRP. First, the bi-level programming mathematical model of the SDVRP is given, which set the cost of a big TSP path and the increased cost of cutting and split as the objective function. Then, based on bi-level programming model, a three-phase tabu heuristic algorithm is designed. First phase, a big TSP path including the distribution depot and all the customers is constructed. Second phase, the big TSP is cut and split. And in the third phase, the sub-paths get from the second phase are re-optimization. Finally, through the experimental simulation, the proposed three-stage tabu algorithm compared with other algorithms. And the results showed that the proposed algorithm can really solve the SDVRP effectively. And they also proved that the three-phase tabu algorithm is really a good method of SDVRP.
关键词
车辆路径问题 /
需求可拆分 /
双层规划模型 /
禁忌算法
{{custom_keyword}} /
Key words
vehicle routing problem /
the split delivery /
bi-level programming model /
tabu algorithm
{{custom_keyword}} /
中图分类号：
U492.3
TP311
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Dror M, Trudeau P. Split delivery routing[J]. Naval Research Logistics (NRL), 1990, 37(3): 383-402.
[2] Dror M, Trudeau P. Savings by split delivery routing[J]. Transportation Science, 1989, 23(2): 141-145.
[3] 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.
[4] 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.
[5] 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.
[6] Archetti C, Mansini R, Speranza M G. Complexity and reducibility of the skip delivery problem[J]. Transportation Science, 2005, 39(2): 182-187.
[7] 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.
[8] 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.
[9] 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, 2013: 1-21.
[10] Campos V, Corberán A, Mota E. A scatter search algorithm for the split delivery vehicle routing problem[M]// Advances in Computational Intelligence in Transport, Logistics, and Supply Chain Management, Springer Berlin Heidelberg, 2008: 137-152.
[11] 孟凡超, 陆志强, 孙小明. 需求可拆分车辆路径问题的禁忌搜索算法[J]. 计算机辅助工程, 2010, 19(1): 78-83.Meng Fanchao, Lu Zhiqiang, Sun Xiaoming. Taboo search algorithm of split delivery vehicle routing problem[J]. Computer Aided Engineering, 2010, 19(1): 78-83.
[12] Wilck IV J H, Cavalier T M. A genetic algorithm for the split delivery vehicle routing problem[J]. American Journal of Operations Research, 2012, 2(2): 207-216.
[13] Wilck IV J H, Cavalier T M. A construction heuristic for the split delivery vehicle routing problem[J]. American Journal of Operations Research, 2012, 2(2): 153-162.
[14] Boudia M, Prins C, Reghioui M. An effective memetic algorithm with population management for the split delivery vehicle routing problem[M]// Hybrid Metaheuristics, Springer, 2007: 16-30.
[15] Jin M, Liu K, Eksioglu B. A column generation approach for the split delivery vehicle routing problem[J]. Operations Research Letters, 2008, 36(2): 265-270.
[16] Chen S, Golden B, Wasil E. The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results[J]. Networks, 2007, 49(4): 318-329.
[17] 刘旺盛, 杨帆, 李茂青, 等. 需求可拆分车辆路径问题的聚类求解算法[J]. 控制与决策, 2012, 27(4): 535-541.Liu Wangsheng, Yang Fan, Li Maoqing, et al. Clustering algorithm for split delivery vehicle routing problem[J]. Control and Decision, 2012, 27(4): 535-541.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(71461007,71461006);中国博士后科学基金(2014M560653);中南大学博士后基金(126227)
{{custom_fund}}
PDF(551 KB)
