Integer Programming — AGV Round-Trip Routing: 23-Ind-A1 Operations Research, December 2013, Q5

Question 5: Integer Programming — AGV Round-Trip Routing (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Mailroom $M=(0,0)$ and five departments $D_1(10,30)$, $D_2(10,50)$, $D_3(30,10)$, $D_4(40,40)$, $D_5(50,60)$; the AGV moves only along horizontal/vertical aisles, so travel distance between two points is rectilinear (Manhattan): $d(i,j)=|x_i-x_j|+|y_i-y_j|$.

Arc	$d$ (m)	Arc	$d$ (m)	Arc	$d$ (m)
M–D1	40	D1–D3	40	D2–D5	50
M–D2	60	D1–D4	40	D3–D4	40
M–D3	40	D1–D5	70	D3–D5	70
M–D4	80	D2–D3	60	D4–D5	30
M–D5	110	D2–D4	40	D1–D2	20

Find. An Integer Program whose optimal solution is the round-trip route (starting and ending at $M$, visiting each department exactly once) that minimizes total rectilinear travel. Do not solve.

Approach. This is a Traveling Salesman Problem on 6 nodes (mailroom + 5 departments) with rectilinear arc costs — formulate it with binary arc-selection variables, in/out degree-1 constraints at every node, and Miller–Tucker–Zemlin (MTZ) constraints to eliminate sub-tours.

Mailroom + 5 departments on the aisle grid; the dashed route is one feasible tour shown for illustration — the IP below is not solved for the optimal ordering.

Nodes and arc costs. Nodes $N=\{0,1,\dots,5\}$ (0=mailroom, 1–5=departments); cost $d_{ij}$ = rectilinear distance between nodes $i,j$ (tabulated above).
Decision variables. $x_{ij}\in\{0,1\}$ = 1 if the AGV travels directly from node $i$ to node $j$ ($i\ne j$); auxiliary continuous $u_i\ge0$ for $i=1,\dots,5$ (MTZ position/order variables, node 0 excluded).
Degree constraints. Every node is entered once and left once: $$\sum_{j\ne i}x_{ij}=1\ \ \forall i\in N,\qquad \sum_{i\ne j}x_{ij}=1\ \ \forall j\in N.$$
Sub-tour elimination (MTZ). Prevents the model from returning two or more disjoint mini-loops instead of one full circuit: $$u_i-u_j+5\,x_{ij}\le4,\qquad 1\le i\ne j\le5,\qquad 1\le u_i\le5.$$
Objective. Minimize total rectilinear travel distance for the closed tour: $$\boxed{\min Z=\sum_{i\in N}\sum_{j\ne i}d_{ij}\,x_{ij}}$$ subject to Steps 3–4 and $x_{ij}\in\{0,1\}$.

Element	Formulation
Variables	$x_{ij}\in\{0,1\}$ (6×5=30 arcs), $u_i\in[1,5]$ (5 MTZ variables)
Objective	$\min\sum d_{ij}x_{ij}$, $d_{ij}$ rectilinear
Degree	12 constraints (in=1, out=1 × 6 nodes)
Sub-tour elimination	20 MTZ constraints, $1\le i\ne j\le5$

Concept & Theory

Topic. Integer-programming (MTZ) formulation of the Traveling Salesman Problem on a rectilinear-distance network.

Key relations. Manhattan distance $d(i,j)=|\Delta x|+|\Delta y|$ for aisle-constrained movement; degree-1 in/out constraints alone permit disconnected sub-tours, so the Miller–Tucker–Zemlin inequalities impose a consistent visiting order that rules them out.

Why this works. $u_i-u_j+5x_{ij}\le4$ is vacuous when $x_{ij}=0$ but forces $u_j\ge u_i+1$ whenever arc $i\to j$ is used, so any cycle not containing node 0 would need a strictly increasing $u$ sequence that returns to its own start — a contradiction, which is exactly what excludes sub-tours.

Common pitfall. Using straight-line (Euclidean) distance instead of rectilinear — the question explicitly restricts the AGV to horizontal/vertical aisle movement, so $d_{ij}=|\Delta x|+|\Delta y|$, not $\sqrt{\Delta x^2+\Delta y^2}$.

Source. Hillier & Lieberman, Introduction to Operations Research, ch. 12 (Integer Programming) — TSP formulations and sub-tour elimination.

Question 5 of 10: Integer Programming — AGV Round-Trip Routing

Question 5: Integer Programming — AGV Round-Trip Routing (20 marks)