Skip to Main content Skip to Navigation
Journal articles

A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints

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.
Document type :
Journal articles
Complete list of metadata

https://hal-utt.archives-ouvertes.fr/hal-02476070
Contributor : Daniel Gavrysiak Connect in order to contact the contributor
Submitted on : Wednesday, February 12, 2020 - 2:43:53 PM
Last modification on : Friday, August 27, 2021 - 3:14:07 PM

Identifiers

Collections

UTT | CNRS

Citation

Zhihai Xiang, Chengbin Chu, Haoxun Chen. A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints. European Journal of Operational Research, Elsevier, 2006, 174 (2), pp.1117-1139. ⟨10.1016/j.ejor.2004.09.060⟩. ⟨hal-02476070⟩

Share

Metrics

Record views

69