A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints |
| |
| Institution: | 1. LIMOS CNRS 6158, Labex IMOBS3, Blaise Pascal University, 63000 Clermont-Ferrand, France;2. DEI “Guglielmo Marconi” – University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy;1. The Key Laboratory of Road and Traffic Engineering, Ministry of Education, Tongji University, Cao''an Road No.4800, Jiading District, Shanghai, 201804, China;2. College of Transportation Engineering, Tongji University, Cao''an Road No.4800, Jiading District, Shanghai, 201804, China;3. Department of Urban Management, Kyoto University, Kyoto, 615-8246, Japan;4. Research and Development Center of Transport Industry of Self-driving Technology, China Merchants Chongqing Communications Research & Design Institute Co. Ltd., Xuefu Avenue No.33, Nan''an District, Chongqing, 400067, China;1. Urban Transport Systems Laboratory, School of Architecture, Civil and Environmental Engineering, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne CH-1015, Switzerland;2. Department of Industrial Engineering, Tel-Aviv University, Tel-Aviv 69978, Israel |
| |
| Abstract: | This paper presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints. In this heuristic, a properly organized local search strategy and a diversification strategy are used to improve initial solutions. Then the improved solutions can be refined further by an intensification strategy. The performance of this heuristic was evaluated by intensive computational tests on some randomly generated instances. Small gaps to the lower bounds from the column generation method were obtained in very short time for instances with no more than 200 requests. Although the result is not sensitive to the initial solution, the computational time can be greatly reduced if some effort is spent to construct a good initial solution. With this good initial solution, larger instances up to 2000 requests were solved in less than 10 hours on a popular personal computer. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
