Decentralized multi-agent approach based on A* algorithm for on-demand transport problem

The on-demand transport (ODT) systems have developed worldwide as they have significant social, environmental, and economic benefits. Even with those benefits, it’s still important to gain popular acceptance. The acceptance key is the reactivity of the system in providing fast and reliable solutions whilst respecting vehicles’ and clients’ constraints. This paper presents a decentralized multi-agent approach to model and solve the ODT problem in a static road network. The agents interact with each other using the A* algorithm to find an optimal solution for each transport demand. The optimal solution is expressed by the fastest trajectory taken by the cheapest vehicles. We utilize factual data from a Lebanese city to do experiments evaluating the proposed approach.

A multi-agent approach for on-demand transportation problem in cities

On-demand transportation (ODT) systems have proliferated in diverse cities worldwide due to their social, economic and environmental advantages. Despite those advantages, it is vital to get public approval. The approval key is the system’s reactivity in supplying speedy and reliable solutions that consider clients’ and vehicles’ constraints. Those solutions have to reflect actual life conditions to optimize the quality of service. The most regarded challenge in studying the ODT problem in cities is the stochastic time-dependent travel speed that varies due to traffic fluctuations. To deal with an actual ODT problem, a system has to represent the traffic on its scale. Hence, estimating the travel speed at a specific time and affording a solution based on reliable traffic data. Accordingly, the passengers are served better. This work contributes to the study by solving the ODT problem in cities with a massive multi-agent system that considers historical traffic data and unpredictable events disrupting the typical traffic. We evaluate the proposed approach by experiments with instances based on actual data for a city in the north of Lebanon. The results reveal that the quality of service increases when the stochastic time-dependent travel speed is considered. 50% to 100% of affected clients by an unpredictable event are satisfied when this event is considered by the system.