A penalty function heuristic for the resource constrained shortest path problem |
| |
| Institution: | 1. Facoltà di Ingegneria, Università del Sannio, Corso Garibaldi 107, 82100 Benevento, Italy;2. Dipartimento di Informatica e Sistemistica, Università degli Studi di Napoli “Federico II”, Via Claudio 21, 80125 Napoli, Italy;1. EDF (Électricité de France) R&D, 6 Quai Watier, 78400 Chatou, France;2. Institut de Mécanique des Fluides de Toulouse, IMFT, Université de Toulouse, CNRS – Toulouse, France;1. Faculty of Applied Economics, Department of Engineering Management, University of Antwerp, Belgium;2. Faculty of Bioscience Engineering, Department of Biosystems, KU Leuven, Belgium;1. INFN Sezione di Perugia, Italy;2. INFN Sezione di Pisa, Italy;3. LPNHE, Paris, France;4. DIEI, Perugia, Italy;5. Università di Pisa, Pisa, Italy;6. UNIMORE, Modena, Italy;7. IHEP, China |
| |
| Abstract: | The resource constrained shortest path problem (RCSP) consists of finding the shortest path between two nodes of an assigned network, with the constraint that traversing an arc of the network implies the consumption of certain limited resources. In this paper we propose a new heuristic for the solution of the RCSP problem in medium and large scale networks. It is based on the extension to the discrete case of the penalty function heuristic approach for the fast ε-approximate solution of difficult large-scale continuous linear programming problems. Computational experience on test instances has shown that the proposed penalty function heuristic (PFH) is very effective in the solution of medium and large scale RCSP instances. For all the tests reported it provides very good upper bounds (in many cases the optimal solution) in less than 26 iterations, where each iteration requires only the computation of a shortest path. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
