Changing lanes on a highway

Thomas Petig, Elad M. Schiller, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

16 Downloads (Pure)

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.

Original languageEnglish
Title of host publication18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-15
ISBN (Print)9783959770965
DOIs
Publication statusPublished - 1 Aug 2018
MoE publication typeA4 Article in a conference publication
EventWorkshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - Helsinki, Finland
Duration: 23 Aug 201824 Aug 2018
Conference number: 18

Publication series

NameOASIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume65
ISSN (Electronic)2190-6807

Workshop

WorkshopWorkshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Abbreviated titleATMOS
CountryFinland
CityHelsinki
Period23/08/201824/08/2018

Keywords

  • Approximation algorithms
  • Collaborative agents
  • Traffic optimization
  • Vehicle scheduling

Fingerprint Dive into the research topics of 'Changing lanes on a highway'. Together they form a unique fingerprint.

  • Cite this

    Petig, T., Schiller, E. M., & Suomela, J. (2018). Changing lanes on a highway. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018 (pp. 1-15). [9] (OASIcs; Vol. 65). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/OASIcs.ATMOS.2018.9