An Effective Heuristic for the M-Tour Traveling Salesman Problem with Some Side Conditions

Abstract

This note presents a heuristic for determining very good solutions for the symmetric M-tour traveling salesman problem with some side conditions. These side conditions pertain to load, distance and time, or sequencing restrictions. The heuristic is an extension of the highly successful one of Lin and Kernighan for the single traveling salesman problem. Computational experience with widely tested vehicle dispatch problems indicates that the proposed heuristic consistently yields better solutions than existing heuristics that have appeared in the literature. Run times grow approximately as N2 3, where N is the number of cities. The heuristic is generally slower than the modified SWEEP heuristic except on problems having a large number of points per route. THIS NOTE presents a heuristic algorithm that generates very good solutions to the symmetric M-tour traveling salesman problem with some side conditions. The specific problem is: Given an n by n symmetric matrix of distances between n cities, m salesmen, and a associated with each city, find M tours of minimum total length that leave a depot, visit each city only once, return to the depot, and satisfy certain side conditions. These side conditions pertain to an upper bound on the total load or distance associated with each tour. We also consider time or sequencing restrictions in which individual cities may have due dates or interval constraints requiring that they be visited only during certain time intervals. The above node routing problem is a generalization of the well-known vehicle dispatch problem [9]. Exact optimization techniques exist [4, 17] for vehicle dispatch problems but are severely limited by the size of the problem that can be solved. Good solutions to this class of combinatorial