Abstract
The Dial-a-Ride Problem (DARP) consists of planning vehicle routes and schedules to transport many users, who make pickup and delivery requests. In this paper, we consider the DARP with a single depot, a homogeneous fleet of vehicles and a multi-objective function that minimizes transportation costs and user inconveniences. To solve the problem, we propose a hybrid metaheuristic called ILS-RVND that combines Iterated Local Search (ILS) and Variable Neighborhood Descent with a Random neighborhood ordering (RVND). Computational experiments are performed on the benchmark instances of the literature. The results show that compared to the state-of-the-art methods, ILS-RVND is an effective alternative to solve the multi-objective DARP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Beaudry, A., Laporte, G., Melo, T., Nickel, S.: Dynamic transportation of patients in hospitals. OR Spectr. 32(1), 77–107 (2010)
Braverman, A., Dai, J.G., Liu, X., Ying, L.: Empty-car routing in ridesharing systems. Oper. Res. 67(5), 1437–1452 (2019)
Cordeau, J.F., Laporte, G.: A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp. Res. Part B Methodol. 37(6), 579–594 (2003)
Cordeau, J.F., Laporte, G.: The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153(1), 29–46 (2007)
Cubillos, C., Urra, E., Rodríguez, N.: Application of genetic algorithms for the darptw problem. Int. J. Comput. Commun. Control 4(2), 127–136 (2009)
Daganzo, C.F., Ouyang, Y.: A general model of demand-responsive transportation services: from taxi to ridesharing to dial-a-ride. Transp. Res. Part B Methodol. 126, 213–224 (2019)
Gschwind, T., Drexl, M.: Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transp. Sci. 53(2), 480–491 (2019)
Ho, S.C., Szeto, W., Kuo, Y.H., Leung, J.M., Petering, M., Tou, T.W.: A survey of dial-a-ride problems: literature review and recent developments. Transp. Res. Part B Methodol. 111, 395–421 (2018)
Jorgensen, R.M., Larsen, J., Bergvinsdottir, K.B.: Solving the dial-a-ride problem using genetic algorithms. J. Oper. Res. Soc. 58(10), 1321–1331 (2007)
Luo, Z., Liu, M., Lim, A.: A two-phase branch-and-price-and-cut for a dial-a-ride problem in patient transportation. Transp. Sci. 53(1), 113–130 (2019)
Mauri, G.R., Lorena, L.A.N.: Customers’ satisfaction in a dial-a-ride problem. IEEE Intell. Transp. Syst. Mag. 1(3), 6–14 (2009)
Parragh, S.N., Doerner, K.F., Hartl, R.F., Gandibleux, X.: A heuristic two-phase solution approach for the multi-objective dial-a-ride problem. Netw. Int. J. 54(4), 227–242 (2009)
Saeed, K., Kurauchi, F.: Enhancing the service quality of transit systems in rural areas by flexible transport services. Transp. Res. Procedia 10, 514–523 (2015)
Savelsbergh, M.W.: The vehicle routing problem with time windows: minimizing route duration. ORSA J. Comput. 4(2), 146–154 (1992)
Urra, E., Cubillos, C., Cabrera-Paniagua, D.: A hyperheuristic for the dial-a-ride problem with time windows. Math. Probl. Eng. 2015, 1–12 (2015)
Zidi, I., Mesghouni, K., Zidi, K., Ghedira, K.: A multi-objective simulated annealing for the multi-criteria dial a ride problem. Eng. Appl. Artif. Intell. 25(6), 1121–1131 (2012)
Acknowledgments
This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001 and the Fundação de Amparo à Pesquisa e Inovação do Espírito Santo (FAPES).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Campos, A.A., Amaral, A.R.S. (2021). An Iterated Local Search for the Multi-objective Dial-a-Ride Problem. In: Abraham, A., Piuri, V., Gandhi, N., Siarry, P., Kaklauskas, A., Madureira, A. (eds) Intelligent Systems Design and Applications. ISDA 2020. Advances in Intelligent Systems and Computing, vol 1351. Springer, Cham. https://doi.org/10.1007/978-3-030-71187-0_121
Download citation
DOI: https://doi.org/10.1007/978-3-030-71187-0_121
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71186-3
Online ISBN: 978-3-030-71187-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)