×

A penalty function heuristic for the resource constrained shortest path problem. (English) Zbl 1082.90572

Summary: 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 \(\epsilon\)-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.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Software:

XPRESS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aneja, Y. P.; Aggarwal, V.; Nair, K. P.K., Shortest chain subject to side conditions, Networks, 13, 295-302 (1983) · Zbl 0516.90028
[2] Beasley, J. E.; Christofides, N., An algorithm for the resource constrained shortest path problem, Networks, 19, 4, 379-394 (1989) · Zbl 0673.90085
[3] Bienstock, D., 1998. Experiments with a network design algorithm using \(ε\); Bienstock, D., 1998. Experiments with a network design algorithm using \(ε\)
[4] Bienstock, D., 1999. Approximately solving large-scale linear programs. I. Strengthening lower bounds and accelerating convergence, Technical Report, Columbia University; Bienstock, D., 1999. Approximately solving large-scale linear programs. I. Strengthening lower bounds and accelerating convergence, Technical Report, Columbia University
[5] Boccia, M., Sforza, A., 1999. Path design for the fleet of low emission vehicles of the ATENA Project, Technical Report, University of Naples; Boccia, M., Sforza, A., 1999. Path design for the fleet of low emission vehicles of the ATENA Project, Technical Report, University of Naples
[6] Dijkstra, E. W., A note on two problems in connection with graphs, Numerical Mathematics, 1, 269-271 (1959) · Zbl 0092.16002
[7] Elimam, A. A.; Kohler, D., Two engineering applications of a constrained shortest-path model, European Journal of Operational Research, 103, 426-438 (1997) · Zbl 0926.90061
[8] Garg, N.; Vazarini, V. V.; Yannakakis, M., Approximate max-flow min-(multi)cut theorems and their applications, (Proceedings of the 25th STOC (1993)), 698-707 · Zbl 1310.05198
[9] Goldberg, A., Oldham, J., Plotkin, S., Stein, C., 1998. An implementation of a combinatorial approximation algorithm for minimum multicommodity flow, IPCO; Goldberg, A., Oldham, J., Plotkin, S., Stein, C., 1998. An implementation of a combinatorial approximation algorithm for minimum multicommodity flow, IPCO · Zbl 0911.90153
[10] Grigoriadis, M. D.; Khachiyan, L. G., Fast approximate schemes for convex programs with many blocks and coupling constraints, SIAM Journal on Optimization, 4, 86-107 (1994) · Zbl 0808.90105
[11] Grigoriadis, M. D.; Khachiyan, L. G., An exponential-function reduction method for block-angular convex programs, Networks, 26, 59-68 (1995) · Zbl 0856.90089
[12] Grigoriadis, M. D.; Khachiyan, L. G., Approximate minimum-cost multicommodity flows in \(O(ε^{−2} KNM )\) time, Mathematical Programming, 75, 477-482 (1996) · Zbl 0874.90085
[13] Handler, G. Y.; Zang, I., A dual, algorithm for the constrained shortest path problem, Networks, 10, 293-310 (1980)
[14] Jaffe, J. M., Algorithms for finding paths with multiple constraints, Networks, 14, 95-116 (1984) · Zbl 0532.68068
[15] Jensen, P.A., Berry, R.C., 1971. A constrained shortest path algorithm, Paper presented at the 39th National ORSA Meeting, Dallas, TX, USA. Abstract given in ORSA Bulletin 19, B-139; Jensen, P.A., Berry, R.C., 1971. A constrained shortest path algorithm, Paper presented at the 39th National ORSA Meeting, Dallas, TX, USA. Abstract given in ORSA Bulletin 19, B-139
[16] Joksch, H. C., The shortest route problem with constraints, Journal of Mathematical and Analytical Applications, 14, 191-197 (1966) · Zbl 0135.20506
[17] Leighton, T.; Makedon, F.; Plotkin, S.; Stein, C.; Tragoudas, S.; Tardos, E., Fast approximation algorithms for multicommodities flow problems, (Proceedings of the 23th STOC (1991)), 101-111
[18] Perko, A., Implementation of algorithms for \(k\)-shortest loopless paths, Networks, 16, 149-160 (1986) · Zbl 0642.90097
[19] Plotkin, S.; Karger, D., Adding multiple cost constraints to combinatorial optimization problems, (Proceedings of the 27th Annual ACM Symposium on Theory of Computing (1995)), 18-25 · Zbl 0922.90065
[20] Witzgall, C., Goldman, A.J., 1965. Most profitable routing before maintenance. Paper presented at the 27th National ORSA Meeting, Boston, MA, USA. Abstract given in ORSA Bulletin 13, B-82; Witzgall, C., Goldman, A.J., 1965. Most profitable routing before maintenance. Paper presented at the 27th National ORSA Meeting, Boston, MA, USA. Abstract given in ORSA Bulletin 13, B-82
[21] XPRESS-MP, 2000. Optimisation Subroutine Library, XOSL, Reference Manual, Release 12, Dash Associates; XPRESS-MP, 2000. Optimisation Subroutine Library, XOSL, Reference Manual, Release 12, Dash Associates
[22] Yen, J. Y., Finding the \(k\)-shortest, loopless paths in a network, Management Science, 17, 712-716 (1971) · Zbl 0218.90063
[23] ZIB, MP-TESTDATA, 1988. Maximum Flow Problem. Instances available from http://elib.zib.de/pub/mp-testdata/maxflow/index.html; ZIB, MP-TESTDATA, 1988. Maximum Flow Problem. Instances available from http://elib.zib.de/pub/mp-testdata/maxflow/index.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.