Changing lanes on a highway

Thomas Petig; Elad M. Schiller; Jukka Suomela

doi:10.4230/OASIcs.ATMOS.2018.9

Changing lanes on a highway

Thomas Petig, Elad M. Schiller, Jukka Suomela

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

1 Sitaatiot (Scopus)

37 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018
Kustantaja	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut	1-15
ISBN (painettu)	9783959770965
DOI - pysyväislinkit	https://doi.org/10.4230/OASIcs.ATMOS.2018.9
Tila	Julkaistu - 1 elok. 2018
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - Helsinki, Suomi Kesto: 23 elok. 2018 → 24 elok. 2018 Konferenssinumero: 18

Julkaisusarja

Nimi	OASIcs
Kustantaja	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Vuosikerta	65
ISSN (elektroninen)	2190-6807

Workshop

Workshop	Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Lyhennettä	ATMOS
Maa/Alue	Suomi
Kaupunki	Helsinki
Ajanjakso	23/08/2018 → 24/08/2018

Pääsy asiakirjaan

10.4230/OASIcs.ATMOS.2018.9

OASIcs-ATMOS-2018-9Final published version, 495 KBLisenssi: CC BY

OpenUrl-saatavuus

Koko teksti

Muut tiedostot ja linkit

Link to publication in Scopus

Siteeraa tätä

@inproceedings{5ad9986f6e0c48bba7e16672f77ea4be,

title = "Changing lanes on a highway",

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.",

keywords = "Approximation algorithms, Collaborative agents, Traffic optimization, Vehicle scheduling",

author = "Thomas Petig and Schiller, {Elad M.} and Jukka Suomela",

year = "2018",

month = aug,

day = "1",

doi = "10.4230/OASIcs.ATMOS.2018.9",

language = "English",

isbn = "9783959770965",

series = "OASIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--15",

booktitle = "18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018",

address = "Germany",

note = "Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS ; Conference date: 23-08-2018 Through 24-08-2018",

}

Petig, T, Schiller, EM & Suomela, J 2018, Changing lanes on a highway. julkaisussa 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018., 9, OASIcs, Vuosikerta 65, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Sivut 1-15, Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Helsinki, Suomi, 23/08/2018. https://doi.org/10.4230/OASIcs.ATMOS.2018.9

Changing lanes on a highway. / Petig, Thomas; Schiller, Elad M.; Suomela, Jukka.
18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. s. 1-15 9 (OASIcs; Vuosikerta 65).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

TY - GEN

T1 - Changing lanes on a highway

AU - Petig, Thomas

AU - Schiller, Elad M.

AU - Suomela, Jukka

N1 - Conference code: 18

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Collaborative agents

KW - Traffic optimization

KW - Vehicle scheduling

UR - http://www.scopus.com/inward/record.url?scp=85053263287&partnerID=8YFLogxK

U2 - 10.4230/OASIcs.ATMOS.2018.9

DO - 10.4230/OASIcs.ATMOS.2018.9

M3 - Conference contribution

AN - SCOPUS:85053263287

SN - 9783959770965

T3 - OASIcs

SP - 1

EP - 15

BT - 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems

Y2 - 23 August 2018 through 24 August 2018

ER -

Changing lanes on a highway

Abstrakti

Julkaisusarja

Workshop

Pääsy asiakirjaan

OpenUrl-saatavuus

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä