Fourier descriptors for 2-Opt and 3-Opt heuristics for traveling salesman problem

Abstract

This study provides speedup of the 2-Opt and 3-Opt processes by a new method based on Fourier descriptors (FDs) for the planar traveling salesman problem. By treating the planar tour as a closed contour, the proposed FD-based method, which is used as a potential swap identification function (PSIF), can limit the search space of 2-Opt/3-Opt by identifying the potential swap points/cities. In this article, approximate versions of the 2-Opt and 3-Opt procedures are adopted to investigate the performance of proposed PSIF. The experimental results using the proposed PSIF to reinforce the 3-Opt procedure show that the proposed method provides good quality solutions and faster computation.

摘要

本研究運用傅立葉述元建構啟發式2-Opt和3-Opt演算法以求解平面上之對稱型TSP問題。各種啟發式2-Opt和3-Opt演算法為求解TSP非常重要且運用頻繁的路程改善方法。 在本研究中 ， 傅立葉述元第一次被用來建構啟發式2-Opt和3-Opt演算法。 將平面上的旅行路徑視為一封閉的線型輪廓 ， 以傅立葉述元建構的潛在互換線段辨識法可以縮減2-Opt和3-Opt方法的搜尋空間 ， 加快運算速度。 經由五個實驗案例所得到的上千個實驗結果顯示 ，本研究所提出的方法可強化啟發式2-Opt和3-Opt演算法的速度。

(*聯絡人: [email protected])

Keywords:

• traveling salesman problem
• 2-Opt
• 3-Opt
• Fourier descriptors

Keywords:

• 關鍵字: 銷售員旅行問題 ， 2-Opt ， 3-Opt ， 傅立葉述元

Notes

(*聯絡人: [email protected])