Skip to content

Formulations of routing problems

Part 2 · Formulations and their properties · Chapter 13 · Lecture notes, volume 2 (PDF) · Slides · Exercises: Routing problems

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • write the ILP model of the Travelling Salesman Problem with the position variables of Miller-Tucker-Zemlin (MTZ) and explain how they eliminate subtours;

  • write the ILP model with the subtour elimination constraints of Dantzig-Fulkerson-Johnson (DFJ), and prove that it is correct;

  • count the variables and the constraints of the two models;

  • compare the LP relaxations of the two models on the same instance;

  • write the ILP model of the asymmetric TSP, and explain why the metric TSP has the same models as the TSP.

13.1 Overview of the family

  • Given the set \(\mathscr{V}=\{1,2,\dots,n\}\) of cities, the models of this chapter use the set of directed arcs

    \[ A=\{(i,j):i,j\in\mathscr{V},~i\neq j\}. \]

    Each edge \(\{i,j\}\) of the symmetric problem is represented by the two opposite arcs \((i,j)\) and \((j,i)\), which have the same cost \(d_{ij}=d_{ji}\).

  • The ILP models of the routing problems use one binary arc variable \(x_{ij}\) for each arc \((i,j) \in A\), equal to \(1\) if the tour goes from city \(i\) to city \(j\).

  • The degree constraints impose that exactly one arc leaves and exactly one arc enters each city; the models differ in the constraints that eliminate the subtours.

The routing models are assignment models on the arcs, with the degree constraints, plus constraints that forbid the subtours. The objective function minimizes the total distance \(\sum_{(i,j) \in A} d_{ij}\,x_{ij}\).

  • The table lists the members of the family, with the names of their ILP models and the sections that write them.
Problem Model Subtour elimination Section
TSP \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) position variables \(u_i\) 13.3
TSP \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) one constraint per subset of cities 13.4
metric TSP \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\), \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) the models of the TSP 13.6
ATSP \(\mathrm{ILP}_{\mathrm{ATSP}}\) the constraints of the TSP models 13.6

  • Overview

    Overview of the family

    Open

  • 13.2 ILP models for the Travelling Salesman Problem

    The assignment relaxation · The relaxation of the MTZ model · The relaxation of the DFJ model

    Open

  • 13.6 ILP models for the metric and asymmetric TSP

    In summary

    Open

Next: 13.2 ILP models for the Travelling Salesman Problem

Exercises on this chapter: Routing problems