This paper addresses the dial-a-ride problem (DARP) using private vehicles and alternative nodes (DARP-PV-AN). The DARP consists of creating vehicle routes in order to ensure a set of users’ transportation requests. Each request corresponds to a client needing to be transported from his/her origin to his/her destination. Routing costs have to be minimized while respecting a set of constraints like time windows and maximum route length. In the classical DARP, vehicles have to start from a depot and come back to it at the end of their route. In the DARP-PV-AN, the on-demand transportation service can be done either by a public fleet or by clients that use their private vehicles. The use of these vehicles adds more flexibility and unclog the public transportation fleet by allowing clients to organize their own transportation. However, it also raises some privacy concerns. The DARP-PV-AN addresses these concerns and focuses on location privacy, i.e., the ability to prevent the third parties from learning clients’ locations, by keeping both original and final locations private. This is addressed by setting several pickup/delivery nodes for the transportation requests, thus masking the private address. A compact mixed integer linear model is presented, and an evolutionary local search (ELS) is proposed to compute solutions of good quality for the problem. These methods are benchmarked on a modified set of benchmark instances. A new set of realistic instances is also provided to test the ELS in a more realistic way.
A dial-a-ride problem using private vehicles and alternative nodes / Brevet, D.; Duhamel, C.; Iori, M.; Lacomme, P.. - In: JOURNAL ON VEHICLE ROUTING ALGORITHMS. - ISSN 2367-3605. - 2:1-4(2019), pp. 89-107. [10.1007/s41604-019-00014-5]
A dial-a-ride problem using private vehicles and alternative nodes
Iori, M.Membro del Collaboration Group
;Lacomme, P.Membro del Collaboration Group
2019
Abstract
This paper addresses the dial-a-ride problem (DARP) using private vehicles and alternative nodes (DARP-PV-AN). The DARP consists of creating vehicle routes in order to ensure a set of users’ transportation requests. Each request corresponds to a client needing to be transported from his/her origin to his/her destination. Routing costs have to be minimized while respecting a set of constraints like time windows and maximum route length. In the classical DARP, vehicles have to start from a depot and come back to it at the end of their route. In the DARP-PV-AN, the on-demand transportation service can be done either by a public fleet or by clients that use their private vehicles. The use of these vehicles adds more flexibility and unclog the public transportation fleet by allowing clients to organize their own transportation. However, it also raises some privacy concerns. The DARP-PV-AN addresses these concerns and focuses on location privacy, i.e., the ability to prevent the third parties from learning clients’ locations, by keeping both original and final locations private. This is addressed by setting several pickup/delivery nodes for the transportation requests, thus masking the private address. A compact mixed integer linear model is presented, and an evolutionary local search (ELS) is proposed to compute solutions of good quality for the problem. These methods are benchmarked on a modified set of benchmark instances. A new set of realistic instances is also provided to test the ELS in a more realistic way.File | Dimensione | Formato | |
---|---|---|---|
BDIL-preprint.pdf
Open Access dal 02/01/2022
Descrizione: Versione pre print
Tipologia:
Versione originale dell'autore proposta per la pubblicazione
Dimensione
891.85 kB
Formato
Adobe PDF
|
891.85 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris