VRP Variants

The Traveling Salesman Problem (TSP)

Intuitively, the TSP is the problem of a salesman who, starting from his home town, wants to find the shortest possible trip through a given set of customer cities and return home, visiting each city exactly once. More formally, it can be represented by a complete weighted graph G = (V, E), with V the set of nodes representing the cities and E the set of edges fully connecting them.

Each edge is assigned a value $d_ij$ , the length of edge $(i, j) ∈ E$ — that is, the distance between cities i and j, with $i, j ∈ V$ . The TSP is the problem of finding a minimum-length Hamiltonian cycle of the graph. In symmetric TSPs the distance between two cities is independent of the direction of traversal, that is, $d_ij = d_ji$ for every pair of nodes.

An arc set $T ⊆ E$ is a solution of the TSP if it is a simple cycle of length $|V|$ in G.

The objective function of the TSP is

$min sum of d_ij x_ij$ , where

$x_ij = 1 if the tour includes (i,j), 0 otherwise$

subject to the degree constraints and subtour-elimination constraints:

$degree constraints = 2 for every node; subtour elimination over all proper subsets Z$

The figure below shows a typical TSP input (a set of cities) and its optimal tour.

Left: a set of cities as TSP input. Right: the corresponding optimal tour — Figure 1: Typical input for the TSP (left) and its output (right).

The TSP is the special case of the VRP with a single uncapacitated vehicle, and every VRP route is a TSP tour over the depot plus its assigned customers — which is why TSP methods (2-opt, 3-opt, Lin–Kernighan) are at the core of most VRP improvement heuristics.