A Comparison of Anticipatory Algorithms for the Dynamic and Stochastic Traveling Salesman Problem

Together with ever-growing amounts of data, advances in information technology and telecommunications offer opportunities for transportation companies to improve the quality of the service that they provide to their customers. Two methods motivated by the opportunity that the availability of data and technology gives to improve on current practice are compared in this paper. The two solution approaches are explored, in particular, in the context of a dynamic and stochastic routing problem in which a single, uncapacitated vehicle serves a set of known customers locations. Sample-scenario planning, one approach, offers the potential for higher-quality solutions, but at the expense of greater computational effort. Anticipatory insertion, on the other hand, offers reduced computation and increased managerial ease, but with the potential for reduced solution quality due to restrictions on solution structure. The authors' results show that, particularly when the degree of dynamism is low, anticipatory insertion can often match the quality of sample-scenario planning.

• Record URL:
  • https://doi.org/10.1287/trsc.1110.0374
• Record URL:
  • http://transci.journal.informs.org/content/46/3/374.abstract
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Authors:
  • Ghiani, Gianpaolo
  • Manni, Emanuele
  • Thomas, Barrett W
• Publication Date: 2012-8

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 374-387
• Serial:
  • Transportation Science
  • Volume: 46
  • Issue Number: 3
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Advanced driver information systems; Dynamic programming; Forecasting; Routing; Stochastic processes; Traveling salesman problem
• Uncontrolled Terms: Anticipatory optimization; Scenario planning; Vehicle routing problem
• Subject Areas: Highways; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01446209
• Record Type: Publication
• Files: TRIS
• Created Date: Sep 14 2012 11:15AM