×

The constrained shortest path tour problem. (English) Zbl 1349.90812

Summary: In this paper, we study the constrained shortest path tour problem. Given a directed graph with non-negative arc lengths, the aim is to find a single-origin single-destination shortest path, which needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be of different size. In addition, it is required that the path does not include repeated arcs. Theoretical properties of the problem are studied, proving that it belongs to the complexity class NP-complete. To exactly solve it, a Branch & Bound method is proposed. Given the problem hardness, a Greedy Randomized Adaptive Search Procedure is also developed to find near-optimal solutions for medium to large scale instances. Extensive computational experiments, on a significant set of test problems, are carried out in order to empirically evaluate the performance of the proposed approaches. The computational results show that the Greedy Randomized Adaptive Search Procedure is effective in finding optimal or near optimal solutions in very limited computational time.

MSC:

90C35 Programming involving graphs or networks
05C20 Directed graphs (digraphs), tournaments
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

GRASP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertossi, A. A., The edge Hamiltonian path problem is np-complete, Inf Process Lett, 13, 4, 157-159 (1981) · Zbl 0495.68058
[2] Bertsekas, D. P., Dynamic programming and optimal control, vol. I (2005), Athena Scientific: Athena Scientific Boston, MA, USA · Zbl 1125.90056
[3] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer Math, 1, December (1), 269-271 (1959) · Zbl 0092.16002
[4] Feo, T. A.; Resende, M. G.C., A probabilistic heuristic for a computationally difficult set covering problem, Oper Res Lett, 8, 2, 67-71 (1989) · Zbl 0675.90073
[5] Feo, T. A.; Resende, M. G.C., Greedy randomized adaptive search procedures, J Glob Optim, 6, 109-133 (1995) · Zbl 0822.90110
[6] Festa, P., Complexity analysis and optimization of the shortest path tour problem, Optim Lett, 6, 163-175 (2012) · Zbl 1259.90151
[7] Festa, P.; Guerriero, F.; Laganà, D.; Musmanno, R., Solving the shortest path tour problem, Eur J Oper Res, 230, 464-474 (2013) · Zbl 1317.90065
[9] Festa, P.; Resende, M. G.C., GRASPan annotated bibliography, (Hansen, P.; Rebeiro, C. C., Essays and surveys on metaheuristics (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA, USA), 325-367 · Zbl 1017.90001
[10] Festa, P.; Resende, M. G.C., An annotated bibliography of GRASP - part Ialgorithms, Int Trans Oper Res, 16, 1, 1-24 (2009) · Zbl 1153.90553
[11] Festa, P.; Resende, M. G.C., An annotated bibliography of GRASP - part IIapplications, Int Trans Oper Res, 16, 2, 131-172 (2009) · Zbl 1168.90582
[12] Gabow, H. N.; Maheswari, S. N.; Osterweil, L. J., On two problems in the generation of program test paths, IEEE Trans Softw Eng, 2, 227-231 (1976)
[13] Heegaard, P. E.; Trivedi, K. S., Network survivability modeling, Comput Netw, 53, 8, 1215-1234 (2009), Performance Modeling of Computer Networks: Special Issue in Memory of Dr. Gunter Bolch · Zbl 1162.68329
[14] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of computer computations (1972), Plenum Press: Plenum Press New York, NY, USA), 85-103 · Zbl 1467.68065
[15] Lim, C.; Smith, J. C., Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Trans, 39, 1, 15-26 (2007)
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.