Abstract
We consider the online version of the traveling salesman problem, where instances are not known in advance. Requests are released over time regardless whether the server is en route or not. This problem has been described as online TSP. Current literature about online TSP assumes that each request becomes known at its release time and will always remain active. We model the customers' waiting psychology and service preparation time into the online TSP with the objective to serve as many requests as possible. More specifically, each request has a disclosure time before accepting service at its release time, and a deadline, which is no bigger than its release time plus the travel time from origin to its position. We give lower bounds for the competitive ratios, online algorithms, and quantify the influence of advanced information on competitive ratios.
| Original language | English |
|---|---|
| Pages (from-to) | 1048-1053 |
| Number of pages | 6 |
| Journal | Computers and Industrial Engineering |
| Volume | 63 |
| Issue number | 4 |
| DOIs | |
| State | Published - Dec 2012 |
| Externally published | Yes |
Keywords
- Advanced information
- Competitive ratio
- Deadlines
- Online routing problems
Fingerprint
Dive into the research topics of 'Online traveling salesman problem with deadline and advanced information'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver