Reinsertion Algorithm Based on Destroy and Repair Operators for Dynamic Dial a Ride Problems
| Autor: | Wahiba Ramdane Cherif-Khettaf, Ammar Oulamara, Sven Vallée |
|---|---|
| Přispěvatelé: | OPTImisation Methods for Integrated SysTems (OPTIMIST), Department of Networks, Systems and Services (LORIA - NSS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Service (business)
Computer science Dial a ride 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] 01 natural sciences InsertionandReinsertionHeuristics 010305 fluids & plasmas Set (abstract data type) Ask price 0103 physical sciences 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Online algorithm Computational experiments Algorithm DynamicDARP |
| Zdroj: | Lecture Notes in Computer Science book series Lecture Notes in Computer Science book series, 11536, springer, pp.81-95, 2019, Computational Science – ICCS 2019 19th International Conference, Faro, Portugal, June 12–14, 2019, Proceedings, Part I, ⟨10.1007/978-3-030-22734-0_7⟩ International Conference on Computational ScienceICCS 2019: Computational Science Proceedings, Part I – ICCS 2019 International Conference on Computational Science ICCS 2019: Computational Science Proceedings, Part I – ICCS 2019, pp.81-95, 2019, ⟨10.1007/978-3-030-22734-0_7⟩ Lecture Notes in Computer Science ISBN: 9783030227333 ICCS (1) |
| DOI: | 10.1007/978-3-030-22734-0_7⟩ |
| Popis: | International audience; The Dial-a-Ride Problem (DARP) consists in serving a set of customers who specify their pickup and drop-off locations using a fleet of vehicles. The aim of DARP is designing vehicle routes satisfying requests of customers and minimizing the total traveled distance. In this paper, we consider a real case of dynamic DARP service operated by Padam (www.padam.io.) in which customers ask for a transportation service either in advance or in real time and get an immediate answer about whether their requests are accepted or rejected. A fleet of fixed number of vehicles is available during a working period of time to provide a transportation service. The goal is to maximize the number of accepted requests during the service. In this paper, we propose an original and novel online Reinsertion Algorithm based on destroy/repair operators to reinsert requests rejected by the online algorithm used by Padam. The proposed algorithm was implemented in the optimization engine of Padam and extensively tested on real hard instances up to 1011 requests and 14 vehicles. The results show that our method succeeds in improving the number of accepted requests. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|