tsp.py File Reference

solve the traveling salesman problem More...

Go to the source code of this file.

Functions
def	solve_tsp (V, c)
def	distance (x1, y1, x2, y2)
def	make_data (n)

Variables
int	n = 200
int	seed = 1
	V
	c
	x
	y
	obj
	edges

Detailed Description

solve the traveling salesman problem

Definition in file tsp.py.

Function Documentation

def tsp.distance	(		x1,
			y1,
			x2,
			y2
	)

distance: euclidean distance between (x1,y1) and (x2,y2)

Definition at line 95 of file tsp.py.

def tsp.make_data

(

n

)

make_data: compute matrix distance based on euclidean distance

Definition at line 99 of file tsp.py.

def tsp.solve_tsp	(		V,
			c
	)

solve_tsp -- solve the traveling salesman problem
   - start with assignment model
   - add cuts until there are no sub-cycles
Parameters:
    - V: set/list of nodes in the graph
    - c[i,j]: cost for traversing edge (i,j)
Returns the optimum objective value and the list of edges used.

Definition at line 19 of file tsp.py.