Premium
A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
Author(s) -
Ioachim Irina,
Gélinas Sylvie,
Soumis François,
Desrosiers Jacques
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199805)31:3<193::aid-net6>3.0.co;2-a
Subject(s) - computer science , shortest path problem , dynamic programming , mathematical optimization , discretization , linear programming , node (physics) , scheduling (production processes) , time complexity , path (computing) , algorithm , mathematics , theoretical computer science , graph , engineering , mathematical analysis , structural engineering , programming language
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 which takes into account the linear node costs. This problem has numerous applications: Two examples are job‐shop scheduling and aircraft routing and scheduling. To underline the efficiency of the proposed method, we compare it with an approach based on partial discretization of the time windows. It clearly outperformed the discretization approach on test problems with wide time windows and many nodes with negative costs. © 1998 John Wiley & Sons, Inc. Networks 31: 193–204, 1998