Solution for Multiple Traveling Salesman Problem with Balanced Workload

The Multiple Traveling Salesman Problem with Balanced Workload (mTSP-BW) is an extended version of the classic Traveling Salesman Problem, which requires simultaneous optimization of task allocation and route planning for multiple salesmen while ensuring balanced workloads among them. This problem has significant applications in logistics distribution, drone inspections, multi-robot coordination, and similar scenarios.

Solving this challenge typically involves balancing two core objectives: Total path cost minimization (traditional TSP objective) Workload balancing among salesmen (load balancing objective)

Typical solution approaches can be divided into three categories:

1. Exact Algorithms Suitable for small-scale problems. Branch and bound methods systematically search the solution space to find optimal solutions, while integer linear programming establishes mathematical models for precise solving. However, these methods suffer from exponential computational complexity growth as problem size increases.

2. Classical Heuristic Algorithms Two-stage approach: First cluster tasks for allocation, then optimize individual salesman routes Improved genetic algorithm: Design fitness functions incorporating load balancing factors Optimized ant colony algorithm: Consider workload disparity penalties during pheromone updates

3. Intelligent Optimization Methods Reinforcement learning framework: Model task allocation as a Markov decision process Graph neural networks: Learn spatial features of city nodes for pre-allocation Hybrid strategies: Combine tabu search and simulated annealing for local optimization

Practical applications often employ hierarchical optimization strategies: upper layer uses clustering-based task allocation to ensure load balancing, while lower layer applies traditional TSP algorithms to optimize individual salesman routes. Recent research trends focus on combining machine learning to predict task distribution characteristics, thereby assisting heuristic algorithms in achieving faster convergence.

The key challenge lies in balancing two conflicting objectives: overemphasizing load balancing may increase total path costs, while solely optimizing routes can lead to uneven task distribution. Effective solutions typically require adjusting objective weights according to specific business scenarios.