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 / 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.
| Original language | English |
|---|---|
| Pages (from-to) | 31-37 |
| Number of pages | 7 |
| Journal | Networks |
| Volume | 44 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Aug 2004 |
| Externally published | Yes |
Keywords
- Asymmetric traveling salesman problem
- Construction algorithm
- Improvement procedure
- Periodic constraints
ASJC Scopus subject areas
- Software
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications