Solving the shortest path tour problem. Festa, P., Guerriero, F., Laganà, D., & Musmanno, R. European Journal of Operational Research, 230(3):464-474, Elsevier B.V., 11, 2013. Paper Website abstract bibtex In this paper, 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. © 2013 Elsevier B.V. All rights reserved.
@article{
title = {Solving the shortest path tour problem},
type = {article},
year = {2013},
identifiers = {[object Object]},
keywords = {Labeling method,Network flows,Shortest path,Structure path constraints},
pages = {464-474},
volume = {230},
websites = {http://linkinghub.elsevier.com/retrieve/pii/S0377221713003433},
month = {11},
publisher = {Elsevier B.V.},
id = {990f8c4f-84da-39be-93f5-2dedb4a4e2bd},
created = {2015-03-23T18:50:23.000Z},
accessed = {2014-09-12},
file_attached = {true},
profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8},
group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7},
last_modified = {2017-03-14T11:36:44.206Z},
read = {true},
starred = {false},
authored = {false},
confirmed = {true},
hidden = {false},
citation_key = {Festa2013},
private_publication = {false},
abstract = {In this paper, 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. © 2013 Elsevier B.V. All rights reserved.},
bibtype = {article},
author = {Festa, P. and Guerriero, F. and Laganà, D. and Musmanno, R.},
journal = {European Journal of Operational Research},
number = {3}
}
Downloads: 0
{"_id":"2Kg8mLhADdRFTwEw3","bibbaseid":"festa-guerriero-lagan-musmanno-solvingtheshortestpathtourproblem-2013","downloads":0,"creationDate":"2018-03-26T07:07:40.614Z","title":"Solving the shortest path tour problem","author_short":["Festa, P.","Guerriero, F.","Laganà, D.","Musmanno, R."],"year":2013,"bibtype":"article","biburl":null,"bibdata":{"title":"Solving the shortest path tour problem","type":"article","year":"2013","identifiers":"[object Object]","keywords":"Labeling method,Network flows,Shortest path,Structure path constraints","pages":"464-474","volume":"230","websites":"http://linkinghub.elsevier.com/retrieve/pii/S0377221713003433","month":"11","publisher":"Elsevier B.V.","id":"990f8c4f-84da-39be-93f5-2dedb4a4e2bd","created":"2015-03-23T18:50:23.000Z","accessed":"2014-09-12","file_attached":"true","profile_id":"756a70ce-605d-3e50-9cbb-a99c29afcbe8","group_id":"1f5b486a-d8ac-3a35-9104-56111360dab7","last_modified":"2017-03-14T11:36:44.206Z","read":"true","starred":false,"authored":false,"confirmed":"true","hidden":false,"citation_key":"Festa2013","private_publication":false,"abstract":"In this paper, 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. © 2013 Elsevier B.V. All rights reserved.","bibtype":"article","author":"Festa, P. and Guerriero, F. and Laganà, D. and Musmanno, R.","journal":"European Journal of Operational Research","number":"3","bibtex":"@article{\n title = {Solving the shortest path tour problem},\n type = {article},\n year = {2013},\n identifiers = {[object Object]},\n keywords = {Labeling method,Network flows,Shortest path,Structure path constraints},\n pages = {464-474},\n volume = {230},\n websites = {http://linkinghub.elsevier.com/retrieve/pii/S0377221713003433},\n month = {11},\n publisher = {Elsevier B.V.},\n id = {990f8c4f-84da-39be-93f5-2dedb4a4e2bd},\n created = {2015-03-23T18:50:23.000Z},\n accessed = {2014-09-12},\n file_attached = {true},\n profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8},\n group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7},\n last_modified = {2017-03-14T11:36:44.206Z},\n read = {true},\n starred = {false},\n authored = {false},\n confirmed = {true},\n hidden = {false},\n citation_key = {Festa2013},\n private_publication = {false},\n abstract = {In this paper, 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. © 2013 Elsevier B.V. All rights reserved.},\n bibtype = {article},\n author = {Festa, P. and Guerriero, F. and Laganà, D. and Musmanno, R.},\n journal = {European Journal of Operational Research},\n number = {3}\n}","author_short":["Festa, P.","Guerriero, F.","Laganà, D.","Musmanno, R."],"urls":{"Paper":"https://bibbase.org/service/mendeley/756a70ce-605d-3e50-9cbb-a99c29afcbe8/file/211325ae-ec5d-b2a3-2646-65505081bfb6/2013-Solving_the_shortest_path_tour_problem.pdf.pdf","Website":"http://linkinghub.elsevier.com/retrieve/pii/S0377221713003433"},"bibbaseid":"festa-guerriero-lagan-musmanno-solvingtheshortestpathtourproblem-2013","role":"author","keyword":["Labeling method","Network flows","Shortest path","Structure path constraints"],"downloads":0},"search_terms":["solving","shortest","path","tour","problem","festa","guerriero","laganà","musmanno"],"keywords":["labeling method","network flows","shortest path","structure path constraints"],"authorIDs":[]}