This paper deals with the Constrained Forward Shortest Path Tour Problem, an NP-complete variant of the Forward Shortest Path Tour Problem. Given a directed weighted graph G = (V, A), where the set of nodes V is partitioned into clusters T1, …, TN, the aim is determining a shortest path between two given nodes, s and d, with the properties that clusters must be visited according to a given order, and each arc can be crossed at most once. We introduce a mathematical formulation of the problem, and a reduction procedure to reduce the number of variables involved in the model. Furthermore, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm to solve large instances of the problem. Computational tests show that the reduction procedure is very effective and its application significantly speeds up the resolution of the model. Moreover, the computational results certify the effectiveness of GRASP that often finds the optimal solution and, in general, provides quickly high-quality sub-optimal solutions.
The constrained forward shortest path tour problem: Mathematical modeling and GRASP approximate solutions
Carrabs, Francesco
;D'Ambrosio, Ciriaco;Laureana, Federica
2021-01-01
Abstract
This paper deals with the Constrained Forward Shortest Path Tour Problem, an NP-complete variant of the Forward Shortest Path Tour Problem. Given a directed weighted graph G = (V, A), where the set of nodes V is partitioned into clusters T1, …, TN, the aim is determining a shortest path between two given nodes, s and d, with the properties that clusters must be visited according to a given order, and each arc can be crossed at most once. We introduce a mathematical formulation of the problem, and a reduction procedure to reduce the number of variables involved in the model. Furthermore, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm to solve large instances of the problem. Computational tests show that the reduction procedure is very effective and its application significantly speeds up the resolution of the model. Moreover, the computational results certify the effectiveness of GRASP that often finds the optimal solution and, in general, provides quickly high-quality sub-optimal solutions.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
