Vehicle Routing Planning in Dynamic Transportation Network Based on Floating Car Data

Abstract:

The traditional research on vehicle routing planning was mostly on the assumption that link travel time is constant, but the traffic conditions in real road network are often fluctuant. In order to meet the requirements of fast and efficient delivery, it is necessary to study vehicle routing planning in dynamic transportation network. In recent years, time dependent vehicle routing problem (TDVRP) which considers traffic conditions attracted more and more scholar's attention. However, most studies on TDVRP are based on simple test network, and assumed all vehicles depart from the depot at a fix time. In this paper, we studied TDVRP based on floating car data. We gave a mathematical model for TDVRP, and represented the dynamic network as a first in first out (FIFO) network by time dependent function of travel speed. Then, we designed a routing construction algorithm named DTO-NNC algorithm for TDVRP. Moreover, we constructed a test instance of 100 customers based on floating car data in the road network of Shanghai, and solved it in the case of fixed departure time and variable departure time. Through the instance, DTO-NNC algorithm has been proven efficient in real road network.

• Periodical: Applied Mechanics and Materials (Volumes 209-211)
• Pages: 707-716
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.209-211.707
• Online since: October 2012
• Authors: Zheng Yu Duan, Dong Yuan Yang
• Keywords: Floating Car Data, Routing Construction Algorithm, Time Dependent Vehicle Routing Problem (TDVRP)

References

[1] G. B. Dantzig, K. B. Ramser: Management Science Vol. 6, No. 1 (1959), pp.80-89

[2] Soojung Jung: A genetic algorithm for the vehicle routing problem with time dependent travel times. Dissertation of Ph.D. University of Maryland, College Park, USA (2000)

[3] Zengmin Xiao: Research on vehicle routing problem with dynamic networks. Dissertation of master. Southwest Jiaotong University, Chengdu, China (2005) (In Chinese)

[4] E. H. Bowman: Operations Research Vol. 4, No. 1 (1956), pp.100-103

[5] J. C. Picard, M. Queyranne: Operations Research Vol. 26, No. 1 (1978), pp.87-110

[6] Chryssi Malandraki, Mark S. Daskin: Transportation Science Vol. 26, No. 3 (1992), pp.185-200

[7] Soumia Ichoua, Michel Gendreau and Jean-Yves Potvin: Discrete Optimization Vol. 144 (2003), pp.379-396

[8] Alberto V. Donati, Luca Maria Gambardella, Andrea E. Rizzoli, Norman Casagrande and Roberto Montemanni: Time Dependent Vehicle Routing Problem with an Ant Colony System. Technical Report (2002)

DOI: 10.1016/j.ejor.2006.06.047

[9] Alberto V. Donati, Roberto Montemanni, Norman Casagrande, Andrea E. Rizzoli and Luca M. Gambardella: European Journal of Operational Research Vol. 185 (2008), pp.1174-1191

DOI: 10.1016/j.ejor.2006.06.047

[10] Alberto V. Donati, Roberto Montermanni, Luca M. Gambardella and Andrea E. Rizzoli: Integration of a Robust Shortest Path Algorithm with a Time Dependent Vehicle Routing Model and Applications. International Symposium on Computational Intelligence for Measurement Systems and Applications (CIMSA 2003), Lugamo, Switzerland (2003), pp.26-31

DOI: 10.1109/cimsa.2003.1227196

[11] Shang-Chun Lu: To solve the vehicle routing problem with time dependent road network. Dissertation of master. National Kaohsiung First University of Science and Technology, Taiwan (2005) (In Chinese)

[12] Bin Wu: Particle swarm optimization for vehicle routing problem and its application. Dissertation of Ph.D. Zhejiang University of Technology, Hangzhou, China (2007) (In Chinese)

[13] Yanwei Zhao, Bin Wu, Wanliang Wang and Jingling Zhang: Particle Swarm Optimization for Open Vehicle Routing Problem with Time Dependent Travel Time. Proceedings of the 17th World Congress, The International Federation of Automatic Control, Seoul, Korea (2008), pp.12843-12848

DOI: 10.3182/20080706-5-kr-1001.02172

[14] Marius M. Solomon: Operations Research Vol. 35 (1987), pp.254-265

[15] Marius M. Solomon: VRPTW Benchmark Problems. http://w.cba.neu.edu/~msolomon/ problems.htm

[16] Zhengyu Duan, Dongyuan Yang and Shang Wang: Control Theory and Applications Vol. 27, No. 11 (2010), pp.1157-1163 (In Chinese)