Skip to content

Routing problems

Part 1 · Combinatorial optimization problems · Chapter 6 · Lecture notes, volume 1 (PDF) · Slides · Exercises: Routing problems

Prerequisites

  • From this module, Chapter 1 «Combinatorial optimization problems»: what a combinatorial optimization problem is, how the number of solutions explodes, and the notions of primal bound, dual bound and gap.

  • From the same chapter, the reference TSP instance with \(5\) cities, which this chapter studies in detail.

Objectives

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

  • state the TSP, the asymmetric TSP and the metric TSP, and describe an instance and a tour;

  • compute the length of a tour, and count the tours of an instance;

  • explain why listing all the tours is hopeless already for \(20\) cities;

  • build a first tour by hand with the nearest neighbour rule;

  • compute a lower bound on the optimal length from the two shortest edges of every city, and measure the gap with a tour.

6.1 Overview of the family

  • The routing problems of this chapter share the same data: a set \(\mathscr{V} = \{1,2,\dots,n\}\) of \(n\) cities and, for each pair of distinct cities \(i,j \in \mathscr{V}\), a distance \(d_{ij} \in \Z_{\ge 1}\).

  • A solution is a tour, a permutation \(\sigma\) of the cities read as a closed route that visits every city exactly once; its length \(L(\sigma)\) is the sum of the distances travelled.

  • The objective is to minimize the length of the tour.

A routing problem finds a shortest tour through all the cities. The members of the family differ in the properties of the distances: symmetric, metric or asymmetric.

  • The table lists the members of the family, with the section that defines each of them.
Problem Acronym Distances Section
travelling salesman problem TSP symmetric, \(d_{ij} = d_{ji}\) 6.2
metric travelling salesman problem metric TSP symmetric, with the triangle inequality 6.6
asymmetric travelling salesman problem ATSP \(d_{ij}\) may differ from \(d_{ji}\) 6.6

  • Overview

    Overview of the family

    Open

  • 6.2 The travelling salesman problem

    Counting the tours · A first tour by hand · A combinatorial lower bound

    Open

  • 6.6 Variants: metric and asymmetric TSP

    The asymmetric travelling salesman problem · Remarks · Typical mistakes · In summary

    Open

Next: 6.2 The travelling salesman problem

Exercises on this chapter: Routing problems

In depth: what the course does on this problem