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

Fast marching methods for the continuous traveling salesman problem.

June Andrews1, J A Sethian

  • 1Department of Mathematics, University of California, Berkeley, CA 94720, USA.

Proceedings of the National Academy of Sciences of the United States of America
|January 16, 2007
PubMed
Summary
This summary is machine-generated.

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

Assisted dying legislation: challenges and considerations for community nurses.

British journal of community nursing·2024
Same author

Family dynamics and caring for older people.

British journal of community nursing·2022
Same author

Community nurses supporting carers of older people.

British journal of community nursing·2022
Same author

Joint iterative reconstruction and 3D rigid alignment for X-ray tomography.

Optics express·2022
Same author

Perspectives: Courage in nursing leadership and innovation.

Journal of research in nursing : JRN·2021
Same author

Numerical study on electrohydrodynamic multiple droplet interactions.

Physical review. E·2020

This study introduces algorithms for a variant of the traveling salesman problem (TSP) with a continuous domain and unknown paths. It presents both heuristic and optimal solutions for finding the cheapest closed path visiting all cities.

Area of Science:

  • Computational Mathematics
  • Operations Research
  • Computer Science

Background:

  • The traveling salesman problem (TSP) is a classic optimization challenge.
  • This work addresses a TSP variant with a continuous domain and a cost function dependent on spatial position.
  • The shortest paths between cities are not known a priori, requiring novel algorithmic approaches.

Purpose of the Study:

  • To develop algorithms for solving a continuous domain TSP with unknown inter-city path costs.
  • To determine the most cost-effective closed path that visits a specified set of cities exactly once.
  • To provide both heuristic and optimal solutions for this complex optimization problem.

Main Methods:

  • Development of a heuristic algorithm with a worst-case complexity of O(M*N log N).

Related Experiment Videos

  • Implementation of an optimal solution algorithm for the continuous domain TSP variant.
  • Utilizing a computational mesh of size N to approximate shortest path solutions.

    • Main Results:

    • The heuristic algorithm demonstrates an average runtime linear in the number of cities (M) and O(N log N) in mesh size (N).
    • The proposed algorithms effectively address the challenge of unknown shortest paths in a continuous domain.
    • Both heuristic and optimal solutions are presented for practical and theoretical applications.

    Conclusions:

    • Efficient algorithms, both heuristic and optimal, have been developed for a novel TSP variant.
    • The heuristic approach offers a practical solution with manageable computational complexity.
    • This research contributes to the field of combinatorial optimization and route planning.