View article

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 r_i times within this time horizon, and these visit days are assigned to i by selecting one of the feasible combinations of r_i 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. © 2004 Wiley Periodicals, Inc …