A deep reinforcement learning algorithm framework for solving multi-objective traveling salesman problem based on...

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• The multi-objective traveling salesman problem (MOTSP) is a complex optimization challenge with significant real-world applications.
• Existing methods struggle with solution space complexity and objective conflicts, leading to long computation times.
• Developing efficient algorithms for MOTSP is crucial for fields like transportation and robotics.

Purpose of the Study:

• To propose a novel end-to-end deep reinforcement learning (DRL) algorithm framework for solving the MOTSP.
• To enhance the efficiency and solution diversity of MOTSP algorithms.
• To provide a single model capable of solving multiple subproblems without explicit weight input.

Main Methods:

• The proposed framework decomposes MOTSP into single-objective subproblems using specific strategies.
• Linear transformation combines MOTSP features with objective function weights.
• A modified graph pointer network (GPN) solves the decomposed subproblems, generating diverse solutions for each weight.
• The algorithm was validated against four evolutionary and two DRL algorithms on various MOTSP instances.

Main Results:

• The proposed DRL framework successfully solves MOTSP by decomposing it into manageable subproblems.
• The modified GPN model efficiently handles subproblems without requiring weight information as input features.
• The algorithm demonstrated superior performance compared to classical evolutionary and existing DRL algorithms.
• Key improvements were observed in both reduced training time and enhanced quality of the obtained solutions.

Conclusions:

• The developed end-to-end DRL framework offers a significant advancement in solving the MOTSP.
• The approach provides a more efficient and effective method for generating diverse, high-quality solutions.
• This research paves the way for improved applications of MOTSP in practical domains.