×

Solving the shortest path tour problem. (English) Zbl 1317.90065

Summary: We study the shortest path tour problem in which a shortest path from a given origin node to a given destination node must be found in a directed graph with non-negative arc lengths. Such path needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be different-sized. A polynomial-time reduction of the problem to a classical shortest path problem over a modified digraph is described and two solution methods based on the above reduction and dynamic programming, respectively, are proposed and compared with the state-of-the-art solving procedure. The proposed methods are tested on existing datasets for this problem and on a large class of new benchmark instances. The computational experience shows that both the proposed methods exhibit a consistent improved performance in terms of computational time with respect to the existing solution method.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks

Software:

Algorithm 97; NETGEN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aneja, Y. P.; Aggarwal, V.; Nair, K. P.K., Shortest chain subject to side constraints, Networks, 13, 2, 295-302 (1983) · Zbl 0516.90028
[2] Bertsekas, D. P., Dynamic Programming and Optimal Control, vol. I (2005), Athena Scientific · Zbl 1125.90056
[3] Bertsekas, D. P., Linear Network Optimization: Algorithms and Codes (1991), M.I.T. Press: M.I.T. Press Cambridge, Massachusettes · Zbl 0754.90059
[4] Bertsekas, D. P., A simple and fast label correcting algorithm for shortest paths, Networks, 23, 7, 703-709 (1993) · Zbl 0801.90111
[5] Cherkassky, B. V.; Goldberg, A. V.; Radzik, T., Shortest path algorithms: theory and experimental evaluation, Mathematical Programming, 73, 129-174 (1996) · Zbl 0853.90111
[6] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), The MIT Press · Zbl 1047.68161
[7] Dijkstra, E., A note on two problems in connexion with graphs, Numerical Mathematics, 1, 269-271 (1959) · Zbl 0092.16002
[9] Di Puglia Pugliese, L.; Guerriero, F., Dynamic programming approaches to solve the shortest paths problem with forbidden paths, Optimization Methods and Software, 28, 2, 221-255 (2013) · Zbl 1271.90093
[10] Dumitrescu, I.; Boland, N., Algorithms for the weight constrained shortest path problem, International Transactions in Operational Research, 8, 1, 15-29 (2001) · Zbl 1003.90037
[11] Dumitrescu, I.; Boland, N., Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem, Networks, 42, 3, 135-153 (2003) · Zbl 1031.68144
[12] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems, Networks, 44, 3, 216-229 (2004) · Zbl 1056.90014
[13] Festa, P., Complexity analysis and optimization of the shortest path tour problem, Optimization Letters, 6, 1, 163-175 (2012) · Zbl 1259.90151
[15] Floyd, R. W., Algorithm 97: shortest path, Communications of the ACM, 5, 6, 345 (1962)
[16] Guerriero, F.; Lacagnina, V.; Musmanno, R.; Pecorella, A., A class of label-correcting methods for the K shortest paths problem, Operations Research, 49, 3, 423-429 (2001) · Zbl 1163.90771
[17] Hunt, G. C.; Michael, M. M.; Parthasarathy, S.; Scott, M. L., An efficient algorithm for concurrent priority queue heaps, Information Processing Letters, 60, 151-157 (1996) · Zbl 0900.68171
[18] Klingman, D.; Napier, A.; Stutz, J., NETGEN-A program for generating large scale (un)capacitated assignment, transportation and minimum cost flow network problems, Management Science, 20, 814-822 (1974) · Zbl 0303.90042
[19] Muhandiramge, R.; Boland, N., Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem, Networks, 53, 4, 358-381 (2009) · Zbl 1207.05201
[20] Righini, G.; Salani, M., New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks, 51, 3, 155-170 (2008) · Zbl 1144.90514
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.