Improvd Hungarian Algorithm for Solving Problem of Travel Providers

Yu LIANG , Ming-ming CHEN , Fan LIU

Science Technology and Engineering ›› 2024, Vol. 24 ›› Issue (14) : 5920 -5927.

PDF
Science Technology and Engineering ›› 2024, Vol. 24 ›› Issue (14) : 5920-5927 DOI: 10.12404/j.issn.1671-1815.2303914
research-article
Improvd Hungarian Algorithm for Solving Problem of Travel Providers
Author information +
History +
PDF

Abstract

To address the issue of multiple closed circuits arising from applying the traditional Hungarian algorithm to the travelling salesman problem (TSP), a breaking mechanism was proposed, leading to the development of the Break-Cycle Hungarian Algorithm. By adopting the description method of the assignment problem for modeling the TSP and establishing the conversion relationship between them, it is demonstrated that a sufficient and necessary condition for a feasible solution to the TSP is that the feasible solution of the corresponding assignment problem, combined with auxiliary edges, contains only one cycle. The effectiveness of the algorithm was verified through testing and comparative analysis on six standard travelling salesmen, showing that the improved Hungarian algorithm can effectively solve the TSP across various datasets.

Cite this article

Download citation ▾
Yu LIANG, Ming-ming CHEN, Fan LIU. Improvd Hungarian Algorithm for Solving Problem of Travel Providers. Science Technology and Engineering, 2024, 24(14): 5920-5927 DOI:10.12404/j.issn.1671-1815.2303914

登录浏览全文

4963

注册一个新账户 忘记密码

References

Funding

PDF (2066KB)

16

Accesses

0

Citation

Detail

Sections
Recommended

/

〈 〉