article

A dynamic vehicle routing problem based on real-time traffic information

Authors:

Gilles Goncalves,

Remy DupasAuthors Info & Claims

International Journal of Innovative Computing and Applications, Volume 2, Issue 4

Pages 215 - 225

https://doi.org/10.1504/IJICA.2010.036809

Published: 01 November 2010 Publication History

Abstract

We treat the dynamic vehicle routing problem with time windows (DVRPTW) in the context of real-time traffic information. We integrate traffic information obtained in real time to change the speed profile according to the accidents on the road network (congestion, etc.). The travel times are based on a time-dependent model in which the travel speeds are step functions. This model is enriched with an exponential smoothing function able to calculate the forecasted speed. The analysis of the results of these experiments shows that our method with real-time traffic information provides a good performance, a better robustness against a simple model with time dependent travel time.

References

[1]

Bianchi, L. (2000) 'Notes on dynamic vehicle routing - the state of the art', Technical report, IDSIA-05-01.

[2]

Chen, H-K., Hsueh, C-F. and Chang, M-S. (2006) 'The real-time time-dependent vehicle routing problem', Transportation Research Part E: Logistics and Transportation Review, Vol. 42, pp.383-408.

[3]

Dantzig, G. and Ramser, J. (1959) 'The truck dispatching problem', Operations Research, Management Sciences, Vol. 6, No. 1, pp.80-91.

Digital Library

[4]

Gendreau, M., Guertin, F., Potvin, J-Y. and Taillard, E. (1999) 'Parallel tabu search for real-time vehicle routing and dispatching', Transportation Science, Vol. 33, pp.381-390.

Digital Library

[5]

Goldberg, D. and Lingle, R. (1985) 'Alleles, loci, and the tsp', in Proceedings of the First International Conference on Genetic Algorithms, pp.154-159.

[6]

Goncalves, G., Hsu, T., Dupas, R. and Housroum, H. (2007) 'Une plate-forme de simulation pour la gestion dynamique de tournées de véhicule', Journal Européen des Systémes Automatisés, Vol. 41, No. 5, pp.515-539.

[7]

Gourieroux, C. and Monfort, A. (1995) 'Séries temporelles et modéles dynamiques', Economica.

[8]

Grefenstette, J., Gopal, R., Rosmaita, R. and Gucht, D. (1985) 'Genetic algorithms for the traveling salesman problem', in Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Eribaum Associates, Mahwah, NJ, pp.160-165.

[9]

Housroum, H. (2005) 'Une approche génétique pour la résolution du probléme VRPTW dynamique', PhD thesis, Université d'Artois.

[10]

Ichoua, S., Gendreau, M. and Potvin, J-Y. (2003) 'Vehicle dispatching with time-dependent travel times', European Journal of Operational Research, Vol. 144, pp.379-396.

[11]

Or, I. (1976) 'Travelling salesman-type combinatorial problems and their relation to the logistics of blood banking', PhD thesis, Department of Industrial Engineering and Management Sciences, North Western University, Evanston, Il.

[12]

Séguin, R., Potvin, J-Y., Gendreau, M., Crainic, T.G. and Marcotte, P. (1997) 'Real-time decision problems: an operations research perspective', Journal of the Operational Research Society, Vol. 48, pp.162-174.

[13]

Solomon, M. (1987) 'Algorithms for the vehicle routing and scheduling problems with time window constraints', Operations Research, Vol. 35, pp.254-265.

Digital Library

[14]

Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J-Y. (1997) 'A tabu search heuristic for the vehicle routing problem with soft time windows', Transportation Science, Vol. 31, pp.170-186.

Digital Library

[15]

Woensel, T.V., Kerbacheb, L., Peremansc, H. and Vandaeled, N. (2008) 'Vehicle routing with dynamic travel times: a queueing approach', European Journal of Operational Research, Vol. 186, No. 3, pp.990-1007.

[16]

Woensel, T.V., Peremans, H. and Vandaele, N. (2002) 'A vehicle routing problem with stochastic travel times', in Forthcoming Proceedings of the 4th Aegean International Conference on Design and Analysis of Manufacturing Systems, Samos, Greece.

[17]

Zhao, X., Goncalves, G. and Dupas, R. (2008) 'A genetic approach to solving the vehicle routing problem with time-dependent travel times', in 16th Mediterranean Conference on Control and Automation, 25-27 June 2008, Congress Centre, Ajaccio, France.

[18]

Zhu, K.Q. (2000) 'A new genetic algorithm for vrptw', International Conference on Artificial Intelligence, Las Vegas, USA.

Cited By

Petters ARomero JAyala HFacon J(2012)Moving license plate segmentation by region and corner-based approachInternational Journal of Innovative Computing and Applications10.1504/IJICA.2012.0500554:3/4(149-162)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1504/IJICA.2012.050055

A dynamic vehicle routing problem based on real-time traffic information
1. Computer systems organization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Online vehicle routing and scheduling with dynamic travel times

The developments in mobile communication technologies are a strong motivation for the study of dynamic vehicle routing and scheduling problems. In particular, the planned routes can be quickly modified to account for the occurrence of new customer ...
Restricted dynamic heterogeneous fleet vehicle routing problem with time windows
IWANN'13: Proceedings of the 12th international conference on Artificial Neural Networks: advences in computational intelligence - Volume Part II

This paper tackles a Restricted Dynamic Heterogeneous Fleet Vehicle Routing Problem with Time Windows as a real-world application of a courier service company in the Canary Islands, Spain. In this particular application of the Vehicle Routing Problem ...
Passenger Condition Based Route-Planning for Cognitive Vehicle System

This article proposes a route-planning method for an environment in which self-driving vehicles are widely used. Such vehicles generate a new route to avoid traffic congestion when it occurs. Through the self-developed traffic simulator, the author was ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Innovative Computing and Applications

International Journal of Innovative Computing and Applications Volume 2, Issue 4

November 2010

50 pages

ISSN:1751-648X

EISSN:1751-6498

Issue’s Table of Contents

Publisher

Inderscience Publishers

Geneva 15, Switzerland

Publication History

Published: 01 November 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Petters ARomero JAyala HFacon J(2012)Moving license plate segmentation by region and corner-based approachInternational Journal of Innovative Computing and Applications10.1504/IJICA.2012.0500554:3/4(149-162)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1504/IJICA.2012.050055

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents