An efficient exact approach for the constrained shortest path tour problem. (English) Zbl 1433.90177
Summary: Given a directed graph with non-negative arc lengths, the constrained shortest path tour problem \((\mathcal{CSPTP})\) is aimed at finding a shortest path from a single-origin to a single-destination, such that a sequence of disjoint and possibly different-sized node subsets are crossed in a given fixed order. Moreover, the optimal path must not include repeated arcs. In this paper, for the \(\mathcal{CSPTP}\) we propose a new mathematical model and a new efficient branch & bound method. Extensive computational experiments have been carried out on a significant set of test problems in order to evaluate empirically the performance of the proposed approach.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Bajaj, C. P., Some constrained shortest-route problems, Math. Methods Oper. Res., 15, 1, 287-301 (1971) · Zbl 0228.90049 · doi:10.1007/BF01939836 |
| [2] | Beasley, J. E.; Christofides, N., An algorithm for the resource constrained shortest path problem, Networks, 19, 4, 379-394 (1989) · Zbl 0673.90085 · doi:10.1002/net.3230190402 |
| [3] | Bérubé, J.-F.; Potvin, J.-Y.; Vaucher, J., Time-dependent shortest paths through a fixed sequence of nodes: Application to a travel planning problem, Comput. Oper. Res., 33, 6, 1838-1856 (2006) · Zbl 1087.90015 · doi:10.1016/j.cor.2004.11.021 |
| [4] | Bhat, S. and Rouskas, G.N., Service-concatenation routing with applications to network functions virtualization, 2017 26th International Conference on Computer Communication and Networks (ICCCN), , pp. 1-9, July 2017. |
| [5] | Di Puglia Pugliese, L.; Guerriero, F., A survey of resource constrained shortest path problems: Exact solution approaches, Networks, 62, 3, 183-200 (2013) · Zbl 1338.90432 · doi:10.1002/net.21511 |
| [6] | Dijkstra, E., A note on two problems in connexion with graphs, Numer. Math., 1, 1, 269-271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390 |
| [7] | 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 · doi:10.1002/net.20033 |
| [8] | Feo, T.; Resende, M., A probabilistic heuristic for a computationally difficult set covering problem, Oper. Res. Lett., 8, 2, 67-71 (1989) · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3 |
| [9] | Feo, T.; Resende, M., Greedy randomized adaptive search procedures, J. Global Optim., 6, 109-133 (1995) · Zbl 0822.90110 · doi:10.1007/BF01096763 |
| [10] | Ferone, D.; Festa, P.; Guerriero, F.; Laganá, D., The constrained shortest path tour problem, Comput. Oper. Res., 74, 64-77 (2016) · Zbl 1349.90812 · doi:10.1016/j.cor.2016.04.002 |
| [11] | Ferone, D.; Festa, P.; Resende, M. G.C., Hybridizations of GRASP with path relinking for the far from most string problem, Int. Trans. Oper. Res., 23, 3, 481-506 (2016) · Zbl 1342.90161 · doi:10.1111/itor.12167 |
| [12] | Festa, P., Complexity analysis and optimization of the shortest path tour problem, Optim. Lett., 6, 163-175 (2012) · Zbl 1259.90151 · doi:10.1007/s11590-010-0258-y |
| [13] | 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 · doi:10.1016/j.ejor.2013.04.029 |
| [14] | Festa, P. and Pallottino, S., A pseudo-random networks generator, Tech. Rep. Department of Mathematics and Applications “R. Caccioppoli”, University of Napoli FEDERICO II, Italy, 2003. |
| [15] | Festa, P. and Resende, M., GRASP: An annotated bibliography, in Essays and Surveys on Metaheuristics, Hansen, P. and Ribeiro, C.C. eds., Kluwer Academic Publishers, Dordrecht, 2002, pp. 325-367. · Zbl 1017.90001 |
| [16] | Handler, G. Y.; Zang, I., A dual algorithm for the constrained shortest path problem, Networks, 10, 4, 293-309 (1980) · Zbl 0453.68033 · doi:10.1002/net.3230100403 |
| [17] | Heegaard, P. E.; Trivedi, K. S., Network survivability modeling, Comput. Networks, 53, 8, 1215-1234 (2009) · Zbl 1162.68329 · doi:10.1016/j.comnet.2009.02.014 |
| [18] | Lim, C.; Smith, J., Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Trans., 39, 1, 15-26 (2007) · doi:10.1080/07408170600729192 |
| [19] | Marinakis, Y.; Migdalas, A.; Sifaleras, A., A hybrid particle swarm optimization – variable neighborhood search algorithm for constrained shortest path problems, Eur. J. Oper. Res., 261, 3, 819-834 (2017) · Zbl 1403.90642 · doi:10.1016/j.ejor.2017.03.031 |
| [20] | Matic, I., A Parallel Algorithm for the Constrained Shortest Path Problem on Lattice Graphs, 1-26 (2018), Springer International Publishing: Springer International Publishing, Cham · doi:10.1007/978-3-319-77510-4_1 |
| [21] | Matsumoto, M.; Nishimura, T., Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul., 8, 1, 3-30 (1998) · Zbl 0917.65005 · doi:10.1145/272991.272995 |
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.
