Mathematica教學：Solving the Traveling Salesman Problem using Gurobi solver

You can download Gurobi solver from https://www.gurobi.com/academia/academic-program-and-licenses/ .

(* Step 1: Register for an academic license on the Gurobi website and install the Gurobi engine. *)

(* Step 2: Append the Gurobi license path if needed *)
AppendTo[$Path, "your full path to the gurobi.lic directory"]

(* Step 3: Restart Mathematica before continuing *)

(* Generate test data: random 2D points *)
{pts, dist, n} = {#, DistanceMatrix[#], Length[#]} &@RandomReal[{0, 100}, {40, 2}];

(* Define decision variables *)
{xVars, uVars} = {
  Flatten@Table[x[i, j], {i, n}, {j, n}] // DeleteCases[x[i_, i_]],
  Table[u[i], {i, 2, n}]
};

(* Objective function: minimize total distance *)
obj = Total[Flatten[Table[x[i, j], {i, n}, {j, n}]*dist]];

(* Flow constraints: each city must be entered and exited exactly once *)
flow = Flatten@{
  Table[Sum[If[i != j, x[i, j], 0], {j, n}] == 1, {i, n}],
  Table[Sum[If[i != j, x[j, i], 0], {j, n}] == 1, {i, n}]
};

(* Miller-Tucker-Zemlin (MTZ) subtour elimination constraints *)
MTZ=Flatten[Table[If[i!=j&&i>1&&j>1,u[i]-u[j]+n*x[i,j]<=n-1,
Nothing],{i,n},{j,n}]];

(* Variable domains and integrality conditions *)
vardomain=Flatten@{
Thread[0<=xVars<=1],
u[1]==1,Thread[2<=uVars<=n],
xVars∈Integers,uVars∈Integers};

(* Solve the model using Gurobi *)
{optDist,sol}=NMinimize[
Flatten@{obj,flow,MTZ,vardomain},
Join[xVars,uVars],
Method->"Gurobi"];

(* Extract path from the binary decision variables *)
edges=Cases[sol,(x[i_,j_]->1):>{i,j}];
path=NestList[
Cases[edges,{#[[2]],_}][[1]]&,
edges[[1]],
Length@edges-1];

(* Visualization of the solution *)
Graphics[{
  {Red, PointSize[Large], Point@pts},
  {Blue, Thick, Line[pts[[#]] & /@ path]},
  {Green, PointSize[.02], Point@pts[[1]]},
  {Arrowheads[.02], Arrow[pts[[#]] & /@ path]}},
 Frame -> True,
 PlotLabel -> Row[{"TSP: n=", n, ", distance=", optDist}]
]

Tags:

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有0 意見