Optimum departure times for commuters in congested networks

DOI10.1007/BF02283700MaRDI QIDQ2277160zbMATH OpenOpenAlexFDO

Authors André de Palma, Pierre Hansen

Publication date 1990

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02283700

zbMATH Keywords

congested networkgeneralized shortest path algorithmNP-hardone-sided Lipschitz functionoptimum departure time

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Transportation, logistics and supply chain management (90B06) Programming involving graphs or networks (90C35)

Review text

A mathematical model for a commuter to find his optimum departure time and path in a congested network is presented, in which the objective function is the sum of the fixed costs for use of arcs, cost functions of travel time depending on exogenous congestion and schedule delay. It can be shown that this problem is NP-hard. This paper presents an algorithm for solving the problem. The idea of the algorithm is based on the generalized shortest path algorithm given by the authors and \textit{M. Labbé} [Transp. Sci. 24, No.4, 276-286 (1990; Zbl 0724.90075)] and an algorithm of \textit{S. A. Piyavskij} [U.S.S.R. Comput. Math. Math. Phys. 12 (1972), No.4, 57-67 (1973); translation from Zh. Vychisl. Mat. Mat. Fiz. 12, 888-896 (1972; Zbl 0249.65046)] for the case of a one-sided Lipschitz function.

Recommendations

• Commuters' Paths with Penalties for Early or Late Arrival Time
• Optimal Time-Varying Flows on Congested Networks
• Time-dependent shortest paths with discounted waits
• Computation of the optimal value function in time-dependent networks
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length

Cites work

• A Sequential Method Seeking the Global Maximum of a Function
• An algorithm for finding the absolute extremum of a function
• Commuters' Paths with Penalties for Early or Late Arrival Time
• Global optimization of univariate Lipschitz functions. I: Survey and properties
• Global optimization of univariate Lipschitz functions. II: New algorithms and computational comparison
• Min-max heaps and generalized priority queues

Cited in

(2)

• Global optimization of univariate Lipschitz functions. I: Survey and properties
• Commuters' Paths with Penalties for Early or Late Arrival Time

This page was built for publication: Optimum departure times for commuters in congested networks

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