Statements (74)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:mathematical_concept
mathematical optimization NP-hard problem |
| gptkbp:abbreviation |
gptkb:TSP
|
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:decision |
NP-complete
|
| gptkbp:describedBy |
gptkb:Graph_theory
|
| gptkbp:field |
gptkb:Mathematics
Computer science Operations research |
| gptkbp:formedBy |
1930s
|
| gptkbp:goal |
Find shortest possible route visiting each city exactly once and returning to origin
|
| gptkbp:hasApplication |
gptkb:robot
Genome sequencing Telecommunications Supply chain management Route planning PCB manufacturing Network design Logistics optimization Astronomical observation scheduling Circuit design Data clustering Delivery optimization Drone path planning Food delivery routing Inspection route planning Inspection tours Manufacturing automation Medical sample collection routing Meter reading routing Ride-sharing route planning Sales route optimization Scheduling maintenance School bus routing Snow plow routing Taxi dispatch optimization Tour planning Vehicle routing Warehouse picking Waste collection routing |
| gptkbp:hasVariant |
gptkb:Asymmetric_TSP
gptkb:Bottleneck_TSP gptkb:Euclidean_TSP gptkb:Generalized_TSP gptkb:Metric_TSP gptkb:Multiple_TSP gptkb:Open_TSP gptkb:Prize-collecting_TSP gptkb:Stochastic_TSP gptkb:Time-dependent_TSP |
| https://www.w3.org/2000/01/rdf-schema#label |
Traveling salesman problem
|
| gptkbp:notableFor |
gptkb:Concorde_TSP_Solver
gptkb:Branch_and_bound gptkb:Christofides_algorithm gptkb:Nearest_neighbor_algorithm Dynamic programming |
| gptkbp:relatedTo |
gptkb:Hamiltonian_cycle_problem
gptkb:Traveling_purchaser_problem gptkb:Vehicle_routing_problem |
| gptkbp:solvedBy |
Approximation algorithms
Heuristic algorithms Exact algorithms |
| gptkbp:usedIn |
gptkb:Logistics
Astronomy Manufacturing Genetics DNA sequencing Scheduling Planning Microchip design |
| gptkbp:bfsParent |
gptkb:Hamiltonian_cycle_problem
gptkb:Hamiltonian_path_problem |
| gptkbp:bfsLayer |
5
|