In this article we describe a heuristic algorithm to solve the asymmetrical traveling salesman problem with periodic constraints over a given m-day planning horizon. Each city i must be visited ri times within this time horizon, and these visit days are assigned to i by selecting one of the feasible combinations of ri visit days with the objective of minimizing the total distance traveled by the salesman. The proposed algorithm is a heuristic that starts by designing feasible tours, one for each day of the m-day planning horizon, and then employs an improvement procedure that modifies the assigned combination to each of the cities, to improve the objective function. Our heuristic has been tested on a set of test problems purposely generated by slightly modifying known test problems taken from the literature. Computational comparisons on special instances indicate encouraging results.
Solving the Asymmetric Traveling Salesman Problem with Periodic Constraints
TRIKI, CHEFI
2004-01-01
Abstract
In this article we describe a heuristic algorithm to solve the asymmetrical traveling salesman problem with periodic constraints over a given m-day planning horizon. Each city i must be visited ri times within this time horizon, and these visit days are assigned to i by selecting one of the feasible combinations of ri visit days with the objective of minimizing the total distance traveled by the salesman. The proposed algorithm is a heuristic that starts by designing feasible tours, one for each day of the m-day planning horizon, and then employs an improvement procedure that modifies the assigned combination to each of the cities, to improve the objective function. Our heuristic has been tested on a set of test problems purposely generated by slightly modifying known test problems taken from the literature. Computational comparisons on special instances indicate encouraging results.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
