Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Travelling Salesman Problem Constraint Representation

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!

like image 226
alex25 Avatar asked Apr 14 '10 07:04

alex25


People also ask

What are the constraints for travelling salesman problem?

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.

What is travelling salesman problem explain with example?

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.

Which method is used in traveling salesman problem?

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.

What is travelling salesman problem and how is it modeled as a graph problem?

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.


1 Answers

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 )

like image 100
Oliver Michels Avatar answered Sep 28 '22 11:09

Oliver Michels