INSERTION HEURISTIC FOR A DYNAMIC DIAL-A-RIDE PROBLEM USING GEOGRAPHICAL MAPS Report as inadecuate




INSERTION HEURISTIC FOR A DYNAMIC DIAL-A-RIDE PROBLEM USING GEOGRAPHICAL MAPS - Download this document for free, or read online. Document in PDF available to download.

1 Haute Ecole de Gestion de Genève 2 Independant consultant

Abstract : We present an insertion heuristic for a dynamic Dial-a-Ride Problem, applied to a real world application on taxi sharing. The application relies on city-sized geographical maps and location coordinates for taxis and customers. A customer sends a ride request to a taxi call center, which assigns to it in quasi real-time the most appropriate taxi, with respect to capacity and time constraints: maximum waiting time before pick up and maximum drive duration for each passenger-s request. Passengers may share a taxi along some part of their journey. Our methodology relies on the computation of four shortest paths, followed by an insertion algorithm with a validity check. Each new request is so tentatively inserted into a taxi route. Experiments on real data shows the viability of our methods.

Keywords : Dynamic DARP Taxi sharing Real time Geographical maps





Author: Sacha Varone - Vytenis Janilionis -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents