Thomas Petig · Elad M. Schiller · Jukka Suomela

Changing lanes on a highway

ATMOS 2018 · 18th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Helsinki, Finland, August 2018 · doi:10.4230/OASIcs.ATMOS.2018.9

authors’ version publisher’s version

Abstract

We study a combinatorial optimization problem that is motivated by the scenario of autonomous cars driving on a multi-lane highway: some cars need to change lanes before the next intersection, and if there is congestion, cars need to slow down to make space for those who are changing lanes. There are two natural objective functions to minimize: (1) how long does it take for all traffic to clear the road, and (2) the total number of maneuvers. In this work, we present an approximation algorithm for solving these problems in the two-lane case and a hardness result for the multi-lane case.

Publication

Ralf Borndörfer and Sabine Storandt (Eds.): 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), volume 65 of OpenAccess Series in Informatics (OASIcs), pages 9:1–9:15, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018

ISBN 978-3-95977-096-5

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.