Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints |
| |
Authors: | Brenda Cheang Xiang Gao Andrew Lim Hu Qin Wenbin Zhu |
| |
Affiliation: | 1. School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China;2. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave., Kowloon Tong, Kowloon, Hong Kong;3. Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong |
| |
Abstract: | We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem. |
| |
Keywords: | Traveling salesman Pickup and delivery Last-in-first-out loading Distance constraint Metaheuristic |
本文献已被 ScienceDirect 等数据库收录! |
|