A Dispatching Algorithm with Application to Fleets of Shared Autonomous Vehicles

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/252190
Download file(s):
File Description SizeFormat 
252190.pdfFulltext1.58 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: A Dispatching Algorithm with Application to Fleets of Shared Autonomous Vehicles
Authors: Hellsten, Erik
Abstract: 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.
Keywords: Grundläggande vetenskaper;Matematik;Basic Sciences;Mathematics
Issue Date: 2017
Publisher: Chalmers tekniska högskola / Institutionen för matematiska vetenskaper
Chalmers University of Technology / Department of Mathematical Sciences
URI: https://hdl.handle.net/20.500.12380/252190
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.