Question

A salesman will visit all the cities in the table below from Cincinnati and returned to Cincinnati. Your help is needed to determine the route to be taken this salesman for a minimum total mileage.

Answer 1

travelling salesman problem... is this from graph theory ?

Answer 2

yes this is travelling salesman problem, but i just need the linear programming, not the solution

Answer 3

the decision variable, objective function and constraints

Answer 4

okay.. . this is heavy for me. i hope someone else would answer this,..

@TuringTest @experimentX @Outkast3r09 @zzr0ck3r

Answer 5

n = 12
c_ij= distance from city i to city j
x_ij = 1, if a tour includes travelling from city i to city j
0, otherwise
from here i don't know

Answer 6

the objective function would be the sum of all the miles for route
\[O = \sum_{i=1}^{12}\sum_{j=1}^{12} x_{ij} *c_{ij}\]
as far as the programming, not sure, it seems there are 11! possible routes so the goal is to use a bunch of loops to assign all 11! combinations to x_ij
then evaluate each sum and determine the route that yields the minimum value

Answer 7

i read the final model for TSP, but in the decision variable there is y_ij=flow from node i to node j, should i use this too?

Answer 8

yes probably, the decision variable y_ij will tell the program what to assign to x_ij
sorry i haven't done too much with linear programming or graph theory

Answer 9

do you have any references, e-book or ever find the similarly question?

Answer 10

http://www.tsp.gatech.edu/index.html

Answer 11

thank you

Answer 12

I'm sorry but this would take a bit too much detail for me to investigate right now.
I am also quite tired (it's almost 3am here) so I afraid I'll have to pass you off
@Zarkon @myininaya @Callisto @KingGeorge
most of them are online right now, hopefully one comes and helps

Good luck!

Answer 13

@asnaseer @experimentX @satellite73

Answer 14

thank you turing