Hybrid pointer networks for traveling salesman problems optimization.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• The Travelling Salesman Problem (TSP) is a complex combinatorial optimization challenge.
• Existing deep learning approaches, like graph pointer networks, have shown promise but can be improved.

Purpose of the Study:

• To introduce and evaluate a novel Hybrid Pointer Network (HPN) architecture for solving the TSP.
• To demonstrate the superiority of HPN over existing Graph Pointer Networks (GPN) in terms of solution quality and efficiency.

Main Methods:

• Developed an end-to-end deep reinforcement learning architecture, HPN, integrating graph embedding layers with transformer encoders.
• Compared HPN against the established GPN using identical experimental settings and benchmark TSP instances of varying sizes.

Main Results:

• HPN demonstrated statistically significant improvements in solution quality compared to GPN across small and large-scale TSP instances.
• For TSP with 50 cities (TSP50), HPN reduced the cost from 5.959 to 5.706 without post-processing heuristics like 2opt.
• Analysis using Linear mixed effect models confirmed HPN's superior performance in minimizing total trip cost.

Conclusions:

• The proposed Hybrid Pointer Network (HPN) offers a significant advancement in solving the Travelling Salesman Problem.
• HPN provides a more effective deep reinforcement learning approach for combinatorial optimization tasks.
• The study makes code, data, and models publicly available to facilitate further research.