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

Gianpaolo Ghiani (), Emanuele Manni () and Barrett W. Thomas ()
Additional contact information
Gianpaolo Ghiani: Dipartimento di Ingegneria dell'Innovazione, Università del Salento, 73100 Lecce, Italy
Emanuele Manni: Dipartimento di Ingegneria dell'Innovazione, Università del Salento, 73100 Lecce, Italy
Barrett W. Thomas: Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242

Transportation Science, 2012, vol. 46, issue 3, 374-387

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

Keywords: vehicle routing; dynamic; stochastic (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0374 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:46:y:2012:i:3:p:374-387

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().