# Re: TSP formulation

From: Mark Wallace <mgw_at_icparc.ic.ac.uk>
Date: Thu 02 Jan 2003 04:36:57 PM GMT
Message-ID: <3E146AA9.5911973A@icparc.ic.ac.uk>
```Hi Jesper,
It isn't the most efficient formulation, but it is expressible in ECLiPSe, viz:

:- lib(ic), lib(ic_global), lib(propia), lib(branch_and_bound).

tsp(N,List,Cost) :-
init_cities(N,List),
constrain_dists(N,List,Dists),
search_min(List,Dists,Cost).

init_cities(N,List) :-
length(List,N),
M is N-1,
List::0..M,
ic:alldifferent(List).

constrain_dists(N,List,Dists) :-
List = [Home|_],
append(List,[Home],Circuit),
Cities =.. [cities|Circuit],
( for(I,1,N),
foreach(Dist,Dists),
param(Cities)
do
dist(Cities[I],Cities[I+1],Dist)
).

dist(City1,City2,D) :-
X is City1,
Y is City2,
( c(X,Y,D) ; c(Y,X,D) ) infers ac.

search_min(List,Dists,Cost) :-
Cost #= sum(Dists),
minimize(labeling(List), Cost).

%%%%%%%%%   Testing   %%%%%%%%%%%%

% Data

c(0,1,30).
c(0,2,60).
c(0,3,41).
c(0,4,17).
c(0,5,70).
c(1,2,58).
c(1,3,46).
c(1,4,46).
c(1,5,48).
c(2,3,21).
c(2,4,59).
c(2,5,40).
c(3,4,38).
c(3,5,50).
c(4,5,78).

% Goal
test(List,Cost) :-
tsp(6, List, Cost).
--
_______________________________________________________________
Dr. Mark Wallace, IC-Parc,		Phone  +44 (0)20 7594 8434
William Penney Laboratory, 		Fax    +44 (0)20 7594 8432
Imperial College, London SW7 2AZ, UK.	Email: mgw@icparc.ic.ac.uk
```
Received on Thu Jan 02 16:37:05 2003

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:20 PM GMT GMT