On a many-to-one shortest paths for a taxi service

Varone, Sacha

Real application involving routing algorithms for moving vehicles needs accurate information, especially for micro mobility. In this note, we describe a reverse bounding Dijkstra algorithm using geographical maps, geographical coordinates of vehicles and pick-up point for a taxi fleet application. The problem that is solved consists in a customer request received by a taxi company, which has to... More

Add to personal list
    Résumé
    Nous décrivons un algorithme de type Dijkstra appliqué à des cartes géographiques, nécessaire à une application à temps réel pour une compagnie de taxis. Le problème qui est résolu consiste en une demande de client reçu par une société de taxi, qui doit répondre à cette demande en affectant l'un de ses taxis, tel qu'un temps d'attente maximal ne soit pas dépassé pour prendre en charge le client. La sélection du taxi est basée sur des plus courts chemins, calculés à partir de l'emplacement de la demande jusqu'au taxis. La méthode peut être appliquée à d'autres algorithmes de plus courts chemins que l'algorithme de Dijkstra. Les avantages de cette approche comprennent la possibilité d'intégrer facilement des informations de trafic en temps réel, ainsi que la rapidité d'exécution de l'algorithme.
    Summary
    Real application involving routing algorithms for moving vehicles needs accurate information, especially for micro mobility. In this note, we describe a reverse bounding Dijkstra algorithm using geographical maps, geographical coordinates of vehicles and pick-up point for a taxi fleet application. The problem that is solved consists in a customer request received by a taxi company, which has to satisfy this request with one of his nearby taxi, restricted to a maximal waiting time for the customer. The selection of the taxi to be assigned to this request is based on many-to-one shortest paths, computed reversly from the location of the request. The methodology can be applied to other shortest paths algorithms than the Dijkstra algorithm. Benefits from this approach include real time information associated with the underlying geographical data to get accurate estimated time to pick-up.