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

Gianpaolo Ghiani; Emanuele Manni; Barrett W. Thomas

doi:10.1287/trsc.1110.0374

Back

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

Journal article

Peer reviewed

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

Gianpaolo Ghiani, Emanuele Manni and Barrett W. Thomas

Transportation science, Vol.46(3), pp.374-387

08/01/2012

DOI: 10.1287/trsc.1110.0374

View Online

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.

Operations Research & Management Science

Science & Technology

Technology

Transportation

Transportation Science & Technology

Details

Title: Subtitle: A Comparison of Anticipatory Algorithms for the Dynamic and Stochastic Traveling Salesman Problem
Creators: Gianpaolo Ghiani - University of Salento
Emanuele Manni - University of Salento
Barrett W. Thomas - University of Iowa
Resource Type: Journal article
Publication Details: Transportation science, Vol.46(3), pp.374-387
Publisher: Informs
DOI: 10.1287/trsc.1110.0374
ISSN: 0041-1655
eISSN: 1526-5447
Number of pages: 14
Grant note: Ministero dell'Istruzione, dell'Universita e della Ricerca (MIUR) of Italy; Ministry of Education, Universities and Research (MIUR)
Language: English
Date published: 08/01/2012
Academic Unit: Bus Admin College; Business Analytics
Record Identifier: 9984380496302771

Metrics

10 Record Views

47 Times Cited - Web of Science

See more details