建立了同时送取货的随机旅行时间车辆路径问题(STT-VRPSPD)的机会约束规划模型,构建了分散搜索算法求解策略.分散搜索算法中,针对STT-VRPSPD问题的复杂特性,构造了解的改进策略、组合策略,并采用改进的节约算法构造分散搜索算法初始解,从而使文中设计的分散搜索算法更加适应STT-VRPSPD问题特有的负载波动性.仿真实验中,首先对分散搜索算法的参数设置进行分析,确定了最优参数组合;然后基于经典的Dethloff算例数据,构造了STT-VRPSPD的测试算例,并对分散搜索算法和遗传算法进行了对比分析,结果表明,分散搜索算法对于STT-VRPSPD的求解质量优于遗传算法.
Abstract
This paper set up a chance-constrained programming model for STT-VRPSDP (stochastic traveling time vehicle routing problem with simultaneous pick-up and delivery), designed respectively a scatter search algorithm applicable to this problem. In response to the complexity of STT-VRPSDP, this paper constructed innovatively an improvement method and a combination method derived from the basic theory of scatter search algorithm. Moreover, with C-W algorithm as an approach to get the initial solution to scatter search algorithm, the scatter search algorithm designed in this paper catered better to the loading floating feature particular to STT-VRPSDP and therefore could better the quality of solution. The simulation experiment firstly analyzed the parameters setting of scatter search algorithm, after which several sets of instances were chosen for the purpose of comparing and analyzing scatter search algorithm and genetic algorithm. The computation results show that solutions of scatter search algorithm are better than those of genetic algorithm.
关键词
随机旅行时间车辆路径问题 /
同时送取货车辆路径问题 /
混合整数规划 /
分散搜索算法
{{custom_keyword}} /
Key words
vehicle routing with stochastic traveling time /
vehicle routing with simultaneous pick-up and delivery /
mixed integer programming /
scatter search
{{custom_keyword}} /
中图分类号：
O223
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Min H. The multiple vehicle routing problems with simultaneous delivery and pick-up points[J]. Transportation Research A, 1989, 23(5): 377-386.
[2] Dethloff J. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up[J]. OR Spektrum, 2001, 23(1): 79-96.
[3] Tang F A, Galvão R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computer and Operations Research, 2006, 33(3): 595-619.
[4] Kao E P C. A preference order dynamic program for a stochastic traveling salesman problem[J]. Operations Research, 1978, 26(6): 1033-1045.
[5] Laporte G, Louveaux F, Mercure H. The vehicle routing problem with stochastic travel times[J]. Transportation Science, 1992, 26(3): 161-170.
[6] Park Y B, Song S. Vehicle scheduling problems with time-varying speed[J]. Computers & Industrial Engineering, 1997, 33(3/4): 853-856.
[7] 谢秉磊. 随机车辆路径问题研究[D]. 西南交通大学, 2003. Xie B L. Research on stochastic vehicle routing problems[D]. Xinan Jiaotong University, 2003.
[8] Anily S. The vehicle-routing problem with delivery and back-haul options[J]. Naval Research Logistics, 1996, 43(3): 415-434.
[9] Dethloff J. Relation between vehicle routing problems: An insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls[J]. Journal of the Operational Research Society, 2002, 53(1): 115-118.
[10] Campos V, Laguna M, Mart R. Scatter Search for the Linear Ordering Problem[M]//Corne D, Dorigo M, Glover F. New Ideas in Optimization, McGraw-Hill, UK, 1999: 331-341.
[11] Campos V, Laguna M, Mart R. Context-independent scatter and tabu search for permutation problems[J]. INFORMS Journal on Computing, 2005, 17(1): 111-122.
[12] Glover F, Laguna M, Mart R. Scatter Search[M]//Ghosh A, Tsutsui S. Advances in Evolutionary Computing: Theory and Applications, New York: Springer-Verlag , 2003: 519-537.
[13] Laguna M, Mart R. Experimental testing of advanced scatter search designs for global optimization of multimodel functions[J]. Journal of Global Optimization, 2005, 33(2): 235-255.
[14] Russell R, Chiang W. Scatter search for the vehicle routing problem with time windows[J]. European Journal of Operational Research, 2006, 169(2): 606-622.
[15] Keskin B B, Uster H. A scatter search-based heuristic to locate capacitated transshipment points[J]. Computers & Operations Research, 2007, 34(10): 3112-3125.
[16] Gonzalez B, Adenso-Diaz B. A scatter search approach to the optimum disassembly sequence problem[J]. Computers & Operations Research, 2006, 33(6): 1776-1793.
[17] 张涛,田文馨,张玥杰,等.带车辆行程约束的VRPSPD问题的模型与改进蚁群算法[J].系统工程理论与实践, 2008, 28(1): 132-140. Zhang T, Tian W X, Zhang Y J, et al. The improved ant colony algorithm for the VRPSPD with maximum distance constraint[J]. Systems Engineering — Theory & Practice, 2008, 28(1): 132-140.
[18] Glover F. Heuristics for integer programming using surrogate constraints[J]. Decision Sciences, 1977, 8: 156-166.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(71171126, 61170095); 上海市自然科学基金(09ZR1420400); 上海市哲学社会科学规划(2011 BGL015)
{{custom_fund}}
PDF(686 KB)
