Abstract
Based on the turn restriction of network and the situation in which requests could not be serviced until its release time, this paper introduces the advanced information into online traveler salesman problem, proposes the online routing of express pick-up vehicles with advanced information on the turn restriction network. WBR-dd algorithm, REP-dd algorithm and PAH-dd algorithm are presented on halfpath, path and general metric space. Competitive analysis is given respectively. The lower bounds are given. The results indicate that the more advanced information, the better online algorithms perform.
| Original language | English |
|---|---|
| Pages (from-to) | 2394-2402 |
| Number of pages | 9 |
| Journal | Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice |
| Volume | 37 |
| Issue number | 9 |
| DOIs | |
| State | Published - 1 Sep 2017 |
Keywords
- Advanced information
- Competitive ratio
- Online algorithm
- Online travelling salesman problem
- Turn restriction network
Fingerprint
Dive into the research topics of 'Online routing of express pick-up vehicles with advanced information on the turn restriction network'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver