Ant Colony Optimization With an Improved Pheromone Model for Solving MTSP With Capacity and Time Window Constraint

Abstract

The optimization of logistics distribution can be defined as the multiple traveling salesman problem (MTSP). The purpose of existing heuristic algorithms, such as Genetic Algorithm (GA), Ant Colony Algorithm (ACO), etc., is to find the optimal path in a short time. However, two important factors of logistics distribution optimization, including work time window and the carrying capacity of the vehicle in distribution system, have been ignored. In this paper, we consider the influences of time limitation of modern commercial logistics and carrying capacity of the vehicle on the logistics optimization, and then propose a MTSP with constraints of time window and capacity of each salesman. We design a novel hybrid algorithm by combining the minimum spanning 1-tree with ACO to find the optimal solution. In addition, we improve the pheromone update rules to increase the search efficiency of ACO algorithm. The experiments show that the novel hybrid algorithm achieves a shorter path than the other algorithms.

Keywords

• Multiple traveling salesman problem
• ant colony optimization
• time window
• capacity