Algorithms for Flows over Time with Scheduling Costs

Dario Frascaria; Neil Olver

doi:10.1007/978-3-030-45771-6_11

Algorithms for Flows over Time with Scheduling Costs

Dario Frascaria^*
, Neil Olver

^*Corresponding author for this work

Operations Analytics

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization
Subtitle of host publication	21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings
Editors	Daniel Bienstock, Giacomo Zambelli
Publisher	Springer
Pages	130-143
Number of pages	14
ISBN (Electronic)	9783030457716
ISBN (Print)	9783030457709
DOIs	https://doi.org/10.1007/978-3-030-45771-6_11
Publication status	Published - 2020
Event	21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 - London, United Kingdom Duration: 8 Jun 2020 → 10 Jun 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12125 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
Country/Territory	United Kingdom
City	London
Period	8/06/20 → 10/06/20

Funding

Partially supported by NWO TOP grant 614.001.510 and NWO Vidi grant 016.Vidi.189.087. A version of this manuscript containing omitted proofs can be found on arXiv:1912.00082.

Keywords

Flows over time
Tolls
Traffic

Access to Document

10.1007/978-3-030-45771-6_11

Persistent URL (handle)

Persistent link

Cite this

Frascaria, D., & Olver, N. (2020). Algorithms for Flows over Time with Scheduling Costs. In D. Bienstock, & G. Zambelli (Eds.), Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings (pp. 130-143). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12125 LNCS). Springer. https://doi.org/10.1007/978-3-030-45771-6_11

Frascaria, Dario ; Olver, Neil. / Algorithms for Flows over Time with Scheduling Costs. Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings. editor / Daniel Bienstock ; Giacomo Zambelli. Springer, 2020. pp. 130-143 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5891a61c64a540bb8e1c18110d3be5af,

title = "Algorithms for Flows over Time with Scheduling Costs",

abstract = "Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.",

keywords = "Flows over time, Tolls, Traffic",

author = "Dario Frascaria and Neil Olver",

year = "2020",

doi = "10.1007/978-3-030-45771-6\_11",

language = "English",

isbn = "9783030457709",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "130--143",

editor = "Daniel Bienstock and Giacomo Zambelli",

booktitle = "Integer Programming and Combinatorial Optimization",

note = "21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 ; Conference date: 08-06-2020 Through 10-06-2020",

}

Frascaria, D & Olver, N 2020, Algorithms for Flows over Time with Scheduling Costs. in D Bienstock & G Zambelli (eds), Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12125 LNCS, Springer, pp. 130-143, 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020, London, United Kingdom, 8/06/20. https://doi.org/10.1007/978-3-030-45771-6_11

Algorithms for Flows over Time with Scheduling Costs. / Frascaria, Dario; Olver, Neil.
Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings. ed. / Daniel Bienstock; Giacomo Zambelli. Springer, 2020. p. 130-143 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12125 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Algorithms for Flows over Time with Scheduling Costs

AU - Frascaria, Dario

AU - Olver, Neil

PY - 2020

Y1 - 2020

N2 - Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.

AB - Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.

KW - Flows over time

KW - Tolls

KW - Traffic

UR - https://www.scopus.com/pages/publications/85083991383

UR - https://www.scopus.com/pages/publications/85083991383#tab=citedBy

U2 - 10.1007/978-3-030-45771-6_11

DO - 10.1007/978-3-030-45771-6_11

M3 - Conference contribution

AN - SCOPUS:85083991383

SN - 9783030457709

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 130

EP - 143

BT - Integer Programming and Combinatorial Optimization

A2 - Bienstock, Daniel

A2 - Zambelli, Giacomo

PB - Springer

T2 - 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020

Y2 - 8 June 2020 through 10 June 2020

ER -

Frascaria D, Olver N. Algorithms for Flows over Time with Scheduling Costs. In Bienstock D, Zambelli G, editors, Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings. Springer. 2020. p. 130-143. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2020 Apr 14. doi: 10.1007/978-3-030-45771-6_11

Algorithms for Flows over Time with Scheduling Costs

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this