License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2018.9
URN: urn:nbn:de:0030-drops-97148
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9714/
Go to the corresponding OASIcs Volume Portal

Petig, Thomas ; Schiller, Elad M. ; Suomela, Jukka

Changing Lanes on a Highway

pdf-format:
OASIcs-ATMOS-2018-9.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{petig_et_al:OASIcs:2018:9714,
  author =	{Thomas Petig and Elad M. Schiller and Jukka Suomela},
  title =	{{Changing Lanes on a Highway}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation  Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{9:1--9:15},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Ralf Bornd{\"o}rfer and Sabine Storandt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9714},
  URN =		{urn:nbn:de:0030-drops-97148},
  doi =		{10.4230/OASIcs.ATMOS.2018.9},
  annote =	{Keywords: Collaborative agents, vehicle scheduling, traffic optimization, approximation algorithms}
}

Keywords: Collaborative agents, vehicle scheduling, traffic optimization, approximation algorithms
Collection: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Issue Date: 2018
Date of publication: 28.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI