|Table of Contents|

Saving algorithm of multi-vehicle routing problem with pickup-delivery and soft time window(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2010年02期
Page:
99-103，109
Research Field:
交通运输规划与管理
Publishing date:
2010-04-20

Info

Title:
Saving algorithm of multi-vehicle routing problem with pickup-delivery and soft time window
Author(s):
QI Wen-xiang;  LU Zhi-qiang;  SUN Xiao-ming
School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200240, China
Keywords:
multi-vehicle routing problem;  pickup and delivery;  heuristic saving algorithm;  soft time window
PACS:
U492.3
DOI:
-
Abstract:
Multi-vehicle routing problem with pickups and deliveries was studied, and soft time window constraint was considered by adding time punishment cost. The mathematical model was built, and its optimized object was the minimum of combination with vehicle rent cost, transportation cost and time punishment cost, and the model was solved by using heuristic saving algorithm. Time punishment cost and transpiration cost were calculated respectively, and the relation between direct and indirect deliveries was compared to obtain best routes. Test result indicates that when the times of pickups and deliveries reach 50, the average loading rate of freight car still achieves above 80%, so the heuristic saving algorithm can reduce the distance without loadage and rent times, and optimize total cost. 2 tabs, 4 figs, 11 refs.

References:

[1] CLARKE G, WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581.
[2] GILLETT B E, MILLER L R. A heuristic algorithm for the vehicle-dispatch problem[J]. Operations Research, 1974, 22(2):340-349.
[3] MONTANE F A T, GALVAO R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computers & Operations Research, 2006, 33(3): 595-619.
[4] NAGY G, SALHI S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research, 2005, 162(1): 126-141.
[5] 李 军.有时间窗的车辆路线安排问题的启发式算法[J].系统工程,1996, 14(5): 45-50. LI Jun. A heuristic algorithm for vehicle routing scheduling problem with time windows[J]. Systems Engineering, 1996, 14(5): 45-50.(in Chinese)
[6] 唐 勇,刘峰涛.新型遗传模拟退火算法求解带VRPTW问题[J].计算机工程与应用,2006,42(7):7-9. TANG Yong, LIU Feng-tao. New genetic simulated annealing algorithm for vehicle routing problem with time window[J]. Computer Engineering and Applications, 2006, 42(7): 7-9.(in Chinese)
[7] 霍佳震,张 磊.有时间窗的集货送货一体化车辆路径规划启发式算法研究[J].物流技术,2004,23(5):64-66. HUO Jia-zhen, ZHANG Lei. Study on heuristic algorithm for picking-delivery problem with time window constraint[J].Logistics Technology, 2004, 23(5): 64-66.(in Chinese)
[8] 张 燕,周支立,翟 斌.集货送货一体化的物流配送车辆路线问题的标号算法[J].运筹与管理,2007,16(3):12-19. ZHANG Yan, ZHOU Zhi-li, ZHAI Bin. Multi-attribute label matching algorithm for vehicle routing problems with time windows and backhauls[J]. Operations Research and Management Science, 2007, 16(3): 12-19.(in Chinese)
[9] 屈 援,汪 波,钟石泉.单车场集送一体化车辆路径问题及其混合算法研究[J].武汉理工大学学报:交通科学与工程版,2007,31(5):811-814. QU Yuan, WANG Bo, ZHONG Shi-quan. Research on single-depot integrated vehicle routing problem and its hybrid algorithm[J]. Journal of Wuhan University of Technology: Transportation Science and Engineering, 2007, 31(5): 811-814.(in Chinese)
[10] 赵鲁华.城市多网点配送车辆调度模型与算法研究[J].物流技术,2007,26(8):91-93. ZHAO Lu-hua. Study on vehicle scheduling model and algorithm for city multi-node delivery[J]. Logistics Technology, 2007, 26(8): 91-93.(in Chinese)
[11] 郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学,2002,10(5):51-56. LANG Mao-xiang, HU Si-ji. Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm[J]. Chinese Journal of Management Science, 2002, 10(5): 51-56.(in Chinese)

Memo

Memo:
-
Last Update: 2010-04-20