Algorithms for Flows over Time with Scheduling Costs

DOI10.1007/978-3-030-45771-6_11MaRDI QIDQ5041740zbMATH OpenOpenAlexFDO

Authors Dario Frascaria, Neil Olver

Publication date 14 October 2022

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.00082

zbMATH Keywords

flows over timetollstraffic

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Stochastic network models in operations research (90B15) Traffic problems in operations research (90B20) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Games involving graphs (91A43)

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.

Recommendations

• Algorithms for flows over time with scheduling costs
• Algorithms for minimizing weighted flow time
• scientific article; zbMATH DE number 3906196
• SCHEDULING TO MINIMIZE MAX FLOW TIME: OFF-LINE AND ON-LINE ALGORITHMS
• Algorithms for cost-aware scheduling
• Algorithms for a realistic variant of flowshop scheduling
• A FLOWSHOP SCHEDULING ALGORITHM TO MINIMIZE TOTAL FLOWTIME
• Scheduling to minimize max flow time: offline and online algorithms.
• Approximation algorithms for time constrained scheduling
• Approximability of flow shop scheduling

Cites work

• A bad network problem for the simplex method and other minimum cost flow algorithms
• Algorithmic Game Theory
• An Algorithm for Universal Maximal Dynamic Flows in a Network
• An introduction to network flows over time
• Combinatorial optimization with rational objective functions
• Constructing maximal dynamic flows from static flows
• Duality in infinite dimensional linear programming
• Dynamic equilibria in fluid queueing networks
• Efficient continuous-time dynamic network flow algorithms
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 6783389 (Why is no real title available?)
• Infinite Horizon Programs
• Long term behavior of dynamic equilibria in fluid queuing networks
• Maximal, Lexicographic, and Dynamic Network Flows
• Nash equilibria and the price of anarchy for flows over time
• Nash flows over time with spillback
• Note—Some Equivalent Objectives for Dynamic Network Flow Problems
• On the price of anarchy for flows over time
• Traffic Networks and Flows over Time
• Transient flows in networks

Cited in

(4)

• Algorithms for flows over time with scheduling costs
• scientific article; zbMATH DE number 3906196 (Why is no real title available?)
• The Complexity of Scheduling for p-Norms of Flow and Stretch
• Algorithms for minimizing weighted flow time

This page was built for publication: Algorithms for Flows over Time with Scheduling Costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041740)