Tools
ToolsFerone, Daniele, Festa, Paola, Fugaro, Serena and Pastore, Tommaso (2020) A dynamic programming algorithm for solving the k-Color Shortest Path Problem. Optimization Letters, 15 (6). pp. 1973-1992. ISSN 1862-4472
Preview |
PDF (s11590-020-01659-z)
- Published Version
Available under License Creative Commons Attribution. Download (425kB) | Preview |
Abstract
Several variants of the classical Constrained Shortest Path Problem have been presented in the literature so far. One of the most recent is the k-Color Shortest Path Problem (k-CSPP), that arises in the field of transmission networks design. The problem is formulated on a weighted edge-colored graph and the use of the colors as edge labels allows to take into account the matter of path reliability while optimizing its cost. In this work, we propose a dynamic programming algorithm and compare its performances with two solution approaches: a Branch and Bound technique proposed by the authors in their previous paper and the solution of the mathematical model obtained with CPLEX solver. The results gathered in the numerical validation evidenced how the dynamic programming algorithm vastly outperformed previous approaches.
| Item Type: | Article |
|---|---|
| Additional Information: | Publisher Copyright: © 2020, The Author(s). |
| Uncontrolled Keywords: | constrained shortest path,dynamic programming,edge-colored network,network optimization,control and optimization ,/dk/atira/pure/subjectarea/asjc/2600/2606 |
| Faculty \ School: | Faculty of Social Sciences > Norwich Business School |
| Related URLs: | |
| Depositing User: | LivePure Connector |
| Date Deposited: | 12 May 2026 10:36 |
| Last Modified: | 12 May 2026 10:38 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/102961 |
| DOI: | 10.1007/s11590-020-01659-z |
Downloads
Downloads per month over past year
Actions (login required)
 |
View Item |