Menu
I read a couple of articles and sample code about how to solve TSP with Genetic Algorithms and Ant Colony Optimization etc. But everything I found didn't include time (window) constraints, eg. "I have to be at customer x before 12am)" and assumed symmetry.
Can somebody point me into the direction of some sample code or articles that explain how I can add constraints to TSP and how I can represent those in code.
Thanks!
226
The Cost- Constrained Traveling Salesman Problem requires both selection and sequencing of tasks, while the Traveling Salesman Problem requires sequencing only. In the Traveling Salesman Problem, the goal is not to select and sequence tasks to make optimal use of a limited resource.
Travelling Salesman Problem (TSP) : Given a set of cities and distances between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Note the difference between Hamiltonian Cycle and TSP.
The Brute Force approach, also known as the Naive Approach, calculates and compares all possible permutations of routes or paths to determine the shortest unique solution. To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes.
The traveling nalesman problem (TSP) is to find a tour of minimal cost. The TSP can be modeled as a graph problem by considering a complete graph G = /V, E), and assigning each edge uu E E the cost o., A tour is then a circuit in G that meets every node. In this context, tours are sometimes called Eamiltonian c~rcuits.
Professor Reinelt at university of heidelburg in germany is one of the leading experts for the TSP. He has a collection of papers on the various variants of the TSP.
see http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
I think your variant is called Vehicle Routing Problem with Time Windows. ( http://en.wikipedia.org/wiki/Vehicle_routing_problem )
100
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
