A Dispatching Algorithm with Application to Fleets of Shared Autonomous Vehicles
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2017
Författare
Hellsten, Erik
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Fleets of shared autonomous vehicles have been predicted to dominate the transport sector within a near future. For this to work efficiently—including the handling of spontaneous requests—the associated routing problems need to be modelled dynamically and solved efficiently. We formulate and model the problem of routing a fleet of shared autonomous vehicles over a period of time. For each vehicle and each moment in time, it must be decided which customers to serve and which routes to take. The resulting model is solved using a rolling horizon optimisation methodology together with an insertion heuristic for new requests. The optimisation problems resulting from the rolling horizon methodology are solved using column generation, where the subproblems, being elementary shortest path problems with side constraints, are solved using both a local-search heuristic and a dynamic programming algorithm. Our computational experiments show that real-world sized problem instances can be solved to near-optimality within a reasonable computing time.
Beskrivning
Ämne/nyckelord
Grundläggande vetenskaper , Matematik , Basic Sciences , Mathematics