期刊
NETWORKS
卷 78, 期 1, 页码 17-31出版社
WILEY
DOI: 10.1002/net.22010
关键词
GRASP; network optimization; shortest path problems
This paper discusses the Constrained Forward Shortest Path Tour Problem, presenting a mathematical formulation, reduction procedure, and a GRASP algorithm for solving large instances. Computational tests confirm the effectiveness of the reduction procedure and the efficiency of GRASP, which often finds optimal solutions and provides high-quality sub-optimal solutions quickly.
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 T-1, horizontal ellipsis , T-N, 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据