Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Traveling salesman problem with a center.

Adam Lipowski1, Dorota Lipowska

  • 1Faculty of Physics, Adam Mickiewicz University, 61-614 Poznań, Poland.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|August 11, 2005
PubMed
Summary

This study explores the traveling salesman problem, optimizing paths by considering both length and distance from the graph center. A transition point was discovered, revealing distinct phases in path scaling, simulated annealing efficiency, and minimal path shapes.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Efficacy and safety of new direct oral anticoagulants in chronic kidney disease: AHA 2019 updated guidelines and review of the literature.

Kardiochirurgia i torakochirurgia polska = Polish journal of cardio-thoracic surgery·2025
Same author

Mean-field approximation and phase transitions in an Ising-voter model on directed regular random graphs.

Physical review. E·2025
Same author

Heat-Bath and Metropolis Dynamics in Ising-like Models on Directed Regular Random Graphs.

Entropy (Basel, Switzerland)·2023
Same author

Ising Model: Recent Developments and Exotic Applications.

Entropy (Basel, Switzerland)·2022
Same author

Fluctuation relations in a nonequilibrium system: Surface tension and effective temperature in an Ising-doped voter model.

Physical review. E·2022
Same author

Equilibrium behavior in a nonequilibrium system: Ising-doped voter model on complete graph.

Physical review. E·2022

Area of Science:

  • Computational complexity
  • Graph theory
  • Optimization algorithms

Background:

  • The traveling salesman problem (TSP) is a classic NP-hard problem in optimization.
  • Standard TSP focuses on minimizing path length.
  • This study introduces a novel cost function incorporating graph centrality.

Purpose of the Study:

  • To investigate the impact of including graph centrality in the TSP cost function.
  • To identify and characterize phase transitions in this modified TSP.
  • To analyze the scaling behavior and efficiency of optimization algorithms under this new objective.

Main Methods:

  • The simulated annealing (SA) algorithm was employed for path optimization.
  • A cost function combining path length (L) and distance from the graph's geometrical center (C) was utilized.

Related Experiment Videos

  • Analysis focused on the transition point separating different scaling behaviors.

    • Main Results:

    • A distinct transition point was identified in the modified TSP.
    • Two phases were observed, differing in the scaling of L and C.
    • The efficiency of simulated annealing and the shape of minimal paths varied between these phases.

    Conclusions:

    • The inclusion of graph centrality significantly alters the nature of the TSP.
    • Phase transitions offer new insights into the problem's complexity and solution landscape.
    • Simulated annealing performance is demonstrably affected by the centrality-aware cost function.