Method of solving vehicle routing problem with customers' dynamic requests

Li Bing; Zheng Si-fa; Cao Jian-dong; Yang Yang; Geng Hua; Lian Xiao-min

Volume 7 Issue 1

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2007 > 7(1): 106-110

Next Previous

Li Bing, Zheng Si-fa, Cao Jian-dong, Yang Yang, Geng Hua, Lian Xiao-min. Method of solving vehicle routing problem with customers' dynamic requests[J]. Journal of Traffic and Transportation Engineering, 2007, 7(1): 106-110.

Citation:

Li Bing, Zheng Si-fa, Cao Jian-dong, Yang Yang, Geng Hua, Lian Xiao-min. Method of solving vehicle routing problem with customers' dynamic requests[J]. Journal of Traffic and Transportation Engineering, 2007, 7(1): 106-110.

Citation:

PDF( 292 KB)

Method of solving vehicle routing problem with customers' dynamic requests

State Key Laboratory of Automotive Safety and Energy, Tsinghua University, Beijing 100084, China

More Information

Author Bio:
Li Bing(1981-), male, doctoral student, +86-10-62771667, libing00@mails.tsinghua.edu.cn

Lian Xiao-min(1955-), male, professor, +86-10-62795405, lianxm@tsinghua.edu.cn
Received Date: 2006-10-30
Publish Date: 2007-02-25

Abstract

Abstract

A real-time vehicle routing problem(VRP) with customers' dynamic requests in logistics collection was decomposed into a set of static VRPs, in which vehicles were not at depot. Static VRPs were equally converted into general static VRPs by adding virtual customers and relative restrictions, and they were solved by static problem algorithm. With the solving VRP method, a dynamic VRP with 20 customers was solved by using improved saving algorithm. The result shows that the method is feasible, it takes 0.49 s to get the reoptimized route.
- traffic planning,
- vehicle routing,
- saving algorithm,
- dynamic routing

FullText(HTML)

References(11)

References

[1]	Dantzig G B, Ramser R H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. doi: 10.1287/mnsc.6.1.80
[2]	Song Hou-bing, Cai Yuan-li. Hybrid genetic algorithm of vehicle routing withti me windows[J]. Journal of Traffic and Transportation Engineering, 2003, 3(4): 112-115. (in Chinese) http://transport.chd.edu.cn/article/id/200304009
[3]	Thangiah S R, Osman I H, Sun T. Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with ti me windows[R]. Slipery Rock: Slippery Rock University, 1994.
[4]	Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J]. Annals of Operations Research, 1993, 41(1): 421-451.
[5]	Zhang Bo, Ye Jia-wei, Hu Yu-cong. Application of optimizing the path by simulated annealing[J]. China Journal of Highway and Transport, 2004, 17(1): 79-81. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200401019.htm
[6]	Hu Da-wei, Hu Yong, Zhu Zhi-qiang. Solving location-routing problem based on space filling curve and dynamic programming[J]. Journal of Chang an University: Natural Science Edition, 2006, 26(3): 80-83. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200603021.htm
[7]	Clarke G, Wright J W. Scheduling of vehicles froma central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581.
[8]	Yang Rui-chen, Zhou Yong-fu, Yun Qing-xia. Hybrid algorithm for vehicle's optimal route[J]. Journal of Traffic and Transportation Engineering, 2005, 5(1): 102-105. (in Chinese) doi: 10.3321/j.issn:1671-1637.2005.01.024
[9]	Psaraftis H N. Vehicle Routing: Methods and Studies[M]. Amstersam: North-Holland Press, 1988.
[10]	Ghiani G, Guerriero F, Laporte G, et al. Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies[J]. European Journal of Operational Research, 2003, 151(1): 1-11.
[11]	李军, 郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京: 中国物资出版社, 2001.