A filtering system to solve the large-scale shared autonomous vehicles Dial-a-Ride Problem

Sie sind hier: Homepage > Suche

A filtering system to solve the large-scale shared autonomous vehicles Dial-a-Ride Problem

Liu, Chijia / Quilliot, Alain / Toussaint, Hélène / Feillet, Dominique

Abstract Shared autonomous vehicles are rapidly becoming one of the most popular topics in the fields of transportation and operations research. This paper studies a prospective transportation system in which shared autonomous vehicles (SAVs) providing Dial-a-Ride services in urban and rural areas must meet a large number of passenger requests (at least $1 0^{5}$ per day). We consider those SAVs likely to replace, in the future, most of the individual vehicles inside urban areas. We address this very large-scale problem with a greedy insertion heuristic that involves a specific filtering system design in order to speed up the decision process and relies on an original network-driven encoding of the routes. Experimental results show that en-route vehicles can be drastically reduced by such systems using a fleet of SAVs of capacity 10, decreasing the vehicle number by more than 98%, compared to a situation where all travel demands would rely on personal vehicles. In addition, thanks to the filtering system, the total execution time can be reduced by almost 97% compared to the classic best-fit insertion heuristic, while maintaining the quality of the solution. This opens the way to the adaptation of our algorithms to a dynamic real-time context.