Journal article
Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines
Computers & operations research, Vol.36(4), pp.1231-1248
04/01/2009
DOI: 10.1016/j.cor.2008.01.006
Abstract
The probabilistic traveling salesman problem with deadlines (PTSPD) is an extension of the well-known probabilistic traveling salesman problem in which, in addition to stochastic presence, customers must also be visited before a known deadline. For realistically sized instances. the problem is impossible to solve exactly, and local-search methods struggle due to the time required to evaluate the objective function. Because computing the deadline violations is the most time consuming part of the objective. we focus on developing approximations for the computation of deadline violations. These approximations can be imbedded in a variety of local-search methods, and we perform experiments comparing their performance using a I-shift neighborhood. These computational experiments show that the approximation methods lead to significant runtime improvements without loss in quality. (C) 2008 Elsevier Ltd. All rights reserved.
Details
- Title: Subtitle
- Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines
- Creators
- Ann Melissa Campbell - University of IowaBarrett W. Thomas - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Computers & operations research, Vol.36(4), pp.1231-1248
- Publisher
- Elsevier
- DOI
- 10.1016/j.cor.2008.01.006
- ISSN
- 0305-0548
- eISSN
- 1873-765X
- Number of pages
- 18
- Grant note
- 0237726 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 04/01/2009
- Academic Unit
- Bus Admin College; Business Analytics
- Record Identifier
- 9984380400102771
Metrics
2 Record Views