A new approach to solving the multiple traveling salesperson problem using genetic algorithms

A new approach to solving the multiple traveling salesperson problem using genetic algorithms

0.00 Avg rating0 Votes
Article ID: iaor20084164
Country: Netherlands
Volume: 175
Issue: 1
Start Page Number: 246
End Page Number: 257
Publication Date: Nov 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics: genetic algorithms
Abstract:

The multiple traveling salesperson problem (MTSP) involves scheduling m > 1 salespersons to visit a set of n > m locations so that each location is visited exactly once while minimizing the total (or maximum) distance traveled by the salespersons. The MTSP is similar to the notoriously difficult traveling salesperson problem (TSP) with the added complication that each location may be visited by any one of the salespersons. Previous studies investigated solving the MTSP with genetic algorithms (GAs) using standard TSP chromosomes and operators. This paper proposes a new GA chromosome and related operators for the MTSP and compares the theoretical properties and computational performance of the proposed technique to previous work. Computational testing shows the new approach results in a smaller search space and, in many cases, produces better solutions than previous techniques.

Reviews

Required fields are marked *. Your email address will not be published.