Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Dynamic Vehicle Routing Based on Online Traffic Information

Published: 01 November 2004 Publication History

Abstract

With the increasing availability of real-time information and communication systems in logistics, the need for appropriate planning algorithms, which make use of this technology, arises. Customers in transport markets increasingly expect quicker and more flexible fulfillment of their orders, especially in the electronic marketplace. This paper considers a dynamic routing system that dispatches a fleet of vehicles according to customer orders arriving at random during the planning period. Each customer order requires a transport from a pickup location to a delivery location in a given time window. The system disposes of online communication with all drivers and customers and, in addition, disposes of online information on travel times from a traffic management center. This paper presents a planning framework for this situation which, to our knowledge, has not yet been addressed in the literature. It then describes three routing procedures for event-based dispatching, which differ in the length of the planning horizon per event. We focus on the use of dynamic travel time information, which requires dynamic shortest path calculations. The procedures are tested and compared using real-life data of an urban traffic management center and a logistics service provider.

References

[1]
Ahuja, R. K., T. L. Magnanti, J. B. Orlin. 1993. Network Flows. Prentice Hall, Englewood Cliffs, NJ.
[2]
Ascheuer, N., M. Grötschel, N. Kamin, J. Rambau. 1998. Combinatorial online optimization in practice. OPFIMA 57 1-6.
[3]
Bierwirth, C. 2000. Adaptive Search and the Management of Logistics Systems. Kluwer Academic Publishers, Boston, MA/Dordrecht, The Netherlands/London, U.K.
[4]
Dial, R., F. Glover, D. Karney, D. Klingman. 1979. A computational analysis of alternative algorithms and labelling techniques for finding shortest path trees. Networks 9 215-248.
[5]
Fleischmann, B., M. Gietz, S. Gnutzmann. 2004. Time-varying travel times in vehicle routing. Transportation Sci. 38(2) 160-173.
[6]
Gendreau, M., J.-Y. Potvin. 1998. Dynamic vehicle routing and dispatching. T. G. Crainic, G. Laporte, eds. Fleet Management and Logistics. Kluwer Academic Publishers, Boston, MA/Dordrecht, The Netherlands/London, U.K., 115-126.
[7]
Gendreau, M., F. Guertin, J.-Y. Potvin, E. Taillard. 1999. Parallel tabu search for real-time vehicle routing and dispatching. Transportation Sci. 33 381-390.
[8]
Gronalt, M., R. F. Hartl, M. Reimann. 2003. Time-constrained pickup and delivery of full truckloads. Eur. J. Oper. Res. 151(3) 520-535.
[9]
Günther, H.-O., H. Krüger, A. Schrecker. 2001. Einsatzplanung fahrerloser Transportsysteme-Untersucht an einem praxisfall aus dem spezialmaschinenbau. Logistik Management 3 33-42.
[10]
Horn, E. T. 2000. Efficient modelling of travel in networks with time-varying link speeds. Networks 36 80-90.
[11]
Ichoua, S., M. Gendreau, J.-Y. Potvin. 2003. Vehicle dispatching with time-dependent travel times. Eur. J. Oper. Res. 144 379-396.
[12]
Jonker, R., A. Volgenant. 1987. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38 325-340.
[13]
Madsen, O., H. Ravn, J. Rygaard. 1995. A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities and multiple objectives. Ann. Oper. Res. 60 193-208.
[14]
Or, I. 1976. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Doctoral thesis, Northwestern University, Evanston, IL.
[15]
Philipps, F. 2000. Methoden der dynamischen Tourenplanung. Master thesis, University of Augsburg, Germany.
[16]
Powell, W., W. Snow, R. Cheung. 2000. Adaptive labeling algorithms for the dynamic assignment problem. Transportation Sci. 34 50-66.
[17]
Psaraftis, H. N. 1988. Dynamic vehicle routing problems. B. L. Golden, A. A. Assad, eds. Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, The Netherlands, 223-248.
[18]
Psaraftis, H. N. 1995. Dynamic vehicle routing: Status and prospects. Ann. Oper. Res. 61 143-164.
[19]
Savelsbergh, M. W. P., M. Sol. 1998. DRIVE: Dynamic routing of independent vehicles. Oper. Res. 46 474-490.
[20]
Solomon, M. 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 254-265.
[21]
Wilson, N. H. M., N. J. Colvin. 1977. Computer control for the Rochester dial-a-ride system. Technical Report TR-77-22, Massachusetts Institute of Technology, Cambridge, MA.
[22]
Wilson, N. H. M., H. Weissberg. 1976. Advanced dial-a-ride algorithms research project: Final report. Technical Report TR-76-20, Massachusetts Institute of Technology, Cambridge, MA.
[23]
Wilson, N. H. M., J. M. Sussmann, H. K. Wong, T. Higonnet. 1971. Scheduling algorithms for dial-a-ride systems. Urban Systems Laboratory Report USL TR-70-13, Massachusetts Institute of Technology, Cambridge, MA.
[24]
Yang, J., P. Jaillet, H. Mahmassani. 1999. On-line algorithms for truck fleet assignment and scheduling under real-time information. Transportation Res. Record 1667 107-113.

Cited By

View all
  • (2023)Simulation-Based Cost Modeling to Measure the Effect of Automated Trucks in Inter-Terminal Container TransportationProceedings of the Winter Simulation Conference10.5555/3643142.3643273(1593-1604)Online publication date: 10-Dec-2023
  • (2020)A periodic optimization approach to dynamic pickup and delivery problems with time windowsJournal of Scheduling10.1007/s10951-020-00650-x23:6(711-731)Online publication date: 1-Dec-2020
  • (2017)Incremental Rerouting Algorithm for single-vehicle VRPPDProceedings of the 18th International Conference on Computer Systems and Technologies10.1145/3134302.3134326(44-51)Online publication date: 23-Jun-2017
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Transportation Science
Transportation Science  Volume 38, Issue 4
November 2004
140 pages

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 November 2004

Author Tags

  1. assignment problem
  2. dynamic travel times
  3. pickup and delivery problem
  4. real-time routing

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 04 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Simulation-Based Cost Modeling to Measure the Effect of Automated Trucks in Inter-Terminal Container TransportationProceedings of the Winter Simulation Conference10.5555/3643142.3643273(1593-1604)Online publication date: 10-Dec-2023
  • (2020)A periodic optimization approach to dynamic pickup and delivery problems with time windowsJournal of Scheduling10.1007/s10951-020-00650-x23:6(711-731)Online publication date: 1-Dec-2020
  • (2017)Incremental Rerouting Algorithm for single-vehicle VRPPDProceedings of the 18th International Conference on Computer Systems and Technologies10.1145/3134302.3134326(44-51)Online publication date: 23-Jun-2017
  • (2016)Optimization for Service Routes of Pallet Service Center Based on the Pallet Pool ModeComputational Intelligence and Neuroscience10.1155/2016/56917352016(2)Online publication date: 1-Mar-2016
  • (2016)Solving the Dynamic Vehicle Routing Problem Under Traffic CongestionIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2016.252177917:8(2367-2380)Online publication date: 29-Jul-2016
  • (2016)Dynamic vehicle routing problemsNetworks10.1002/net.2162867:1(3-31)Online publication date: 1-Jan-2016
  • (2015)City Vehicle Routing Problem (City VRP): A ReviewIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2015.239553616:4(1654-1666)Online publication date: 31-Jul-2015
  • (2015)Time-dependent routing problemsComputers and Operations Research10.1016/j.cor.2015.06.00164:C(189-197)Online publication date: 1-Dec-2015
  • (2015)Dynamic milk-run OEM operations in over-congested traffic conditionsComputers and Industrial Engineering10.1016/j.cie.2015.07.01088:C(326-340)Online publication date: 1-Oct-2015
  • (2015)Customer satisfaction in dynamic vehicle routing problem with time windowsApplied Soft Computing10.1016/j.asoc.2015.06.03535:C(423-432)Online publication date: 1-Oct-2015
  • Show More Cited By

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media