%% ======================================================== %% Auteur: Jean-Michel Richer %% email: jean-michel.richer@univ-angers.fr %% ======================================================== %% %% Problème du voyageur de commerce %% (Travelling Salesman Problem) : %% %% Etant donné N villes pour lesquels on connait les %% distances les séparant, trouver un chemin qui ne passe %% qu'une seule fois par chaque ville et qui est le plus %% court possible. %% %% Le plus court chemin pour cet exemple est 7293. %% %% ======================================================== include "globals.mzn"; %% -------------------------- %% Variables %% -------------------------- int: N = 13; array[1..N, 1..N] of int: distances; % cities = [ "1. New York, NY", % "2. Los Angeles, CA", % "3. Chicago, IL", % "4. Minneapolis, MN", % "5. Denver, CO", % "6. Dallas, TX", % "7. Seattle, WA", % "8. Boston, MA", % "9. San Francisco, CA", % "10. St. Louis, MI", % "11. Houston, TX", % "12. Phoenix, AZ", % "13. Salt Lake City" ] distances = array2d(1..N,1..N, [ 0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972, 2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579, 713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260, 1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987, 1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371, 1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999, 2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701, 213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099, 2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600, 875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162, 1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200, 2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504, 1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0 ]); array[1..N] of var 1..N: x; int: min_val = min([distances[i,j] | i,j in 1..N where distances[i,j] > 0]); int: max_val = max([distances[i,j] | i,j in 1..N]); array[1..N] of var min_val..max_val: d; %% -------------------------- %% Constraints %% -------------------------- constraint alldifferent(x); constraint circuit(x); constraint forall(i in 1..N) ( distances[i,x[i]] = d[i] ); %% -------------------------- %% Search %% -------------------------- var int: distance = sum(d); solve :: int_search(d, max_regret, indomain_split, complete) minimize distance; %% -------------------------- %% Result %% -------------------------- output [ "x: ", show(x), "\n", show(distance) ];