|
|||||
|
|
The tree representation for the pickup and delivery traveling salesman problem with LIFO loading |
|
| Authors: | Yongquan Li Dejian Tu |
| Institution: | a School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China b Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong c Department of Computer Science, School of Information Science and Technology, Sun Yat-Sen University, Guangzhou, Guangdong, China |
| Abstract: | The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are commonly represented by vertex lists. However, when the TSPPD is required to follow a policy that loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a novel variable neighborhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Extensive experiments suggest that our VNS heuristic is superior to the current best heuristics for the TSPPDL in terms of solution quality, while requiring no more computing time as the size of the problem increases. |
| Keywords: | Traveling salesman Pickup and delivery Last-in-first-out loading Tree data structure Variable neighborhood search |
| 本文献已被 ScienceDirect 等数据库收录！ | |