𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Continuous-time shortest path problems with stopping and starting costs

✍ Scribed by A.B. Philpott; A.I. Mees

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
344 KB
Volume
5
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

We describe a general solution method for the problem of finding the shortest path between two vertices of a graph in which each edge has some transit time, costs can vary with time, and stopping and parking (with corresponding costs) are allowed at the vertices.

πŸ“œ SIMILAR VOLUMES

Time-varying shortest path problems with
Time-varying shortest path problems with constraints
✍ Cai, X.; Kloks, T.; Wong, C. K. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 159 KB

We study a new version of the shortest path problem. Let G Γ… (V, E) be a directed graph. Each arc e √ E has two numbers attached to it: a transit time b(e, u) and a cost c(e, u), which are functions of the departure time u at the beginning vertex of the arc. Moreover, postponement of departure (i.e.

A dynamic programming algorithm for the
A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
✍ Ioachim, Irina; GοΏ½linas, Sylvie; Soumis, FranοΏ½ois; Desrosiers, Jacques πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 154 KB πŸ‘ 3 views

This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time windows and additional linear costs on the node service start times. To optimally solve this problem, we propose a new dynamic programming algorithm w