Research on traveling salesman problem based on diffusion Monte Carlo method

Yuwei Jiao; Wei Li; Zilin Luo; Lu Yang; Liuxu Fu; Tao Song; Shifa Wang; Wendan Yuan

doi:10.1117/12.3024179

14 February 2024 Research on traveling salesman problem based on diffusion Monte Carlo method

Yuwei Jiao, Wei Li, Zilin Luo, Lu Yang, Liuxu Fu, Tao Song, Shifa Wang, Wendan Yuan

Proceedings Volume 13018, International Conference on Smart Transportation and City Engineering (STCE 2023); 130184D (2024) https://doi.org/10.1117/12.3024179
Event: International Conference on Smart Transportation and City Engineering (STCE 2023), 2023, Chongqing, China

Abstract

Within the realm of intelligent transportation systems, the crux of optimizing traffic routs to reduce congestion, enhance transit efficiency, and lower transit costs lies in devising superior methods to solve the Traveling Salesman Problem (TSP). This article established a Schrödinger equation for the TSP based on quantum theory and employs the Diffusion Monte Carlo method (DMC) to solve for the ground state wave function. The study further investigates the impact of the DMC method on solving the TSP under various annealing curves, presenting an optimal annealing curve. Through the analysis of experimental results from multiple test datasets, the efficacy of this method in addressing the TSP is validated. This research presented herein holds significant implications for solving the TSP and offers insights for the application of the Diffusion Monte Carlo method in other combinatorial optimization problems.

(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.

Citation Download Citation

Yuwei Jiao, Wei Li, Zilin Luo, Lu Yang, Liuxu Fu, Tao Song, Shifa Wang, and Wendan Yuan "Research on traveling salesman problem based on diffusion Monte Carlo method", Proc. SPIE 13018, International Conference on Smart Transportation and City Engineering (STCE 2023), 130184D (14 February 2024); https://doi.org/10.1117/12.3024179

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available