22. Sequencing problems: the Traveling Salesperson Problem

A sequencing problem arises when the decision maker needs to choose the “best” ordering for a set of objects or in which sequence to perform a set of operations. The problem consists in determining a permutation among all feasible ones; to each permutation a cost is associated, and the problem, in its basic formulation, consists in the search for the least cost feasible permutation.

There exist various formulations for sequencing problems, the most common of which corresponds to the case where the cost of a permutations is given by the sum of costs associated to contiguous pairs in the sequence. To be more concrete, a typical sequencing problem is often encountered in transport logistics from where the model got the name of traveling salesperson, or TSP: a driver needs to visit a set of destinations. This situation arises, e.g., in parcel delivery or collection, or when some service tasks, like maintenance or gas meter reading, are to be performed in various locations. There are in general no capacity constraints; the only requirement is that every destination is visited once and, at the end of the tour, the driver returns to the starting base station. Thus the problem can be seen as that of sequencing the visits, in order to spend as little as possible in the overall travel. The total cost in this case is the sum of the cost incurred in moving from one destination node (or from the base station) to the following one in the sequence, or back to the base station when the tour is terminated.

This is perhaps one of the best known and most studied research problem in Operations Research. The interest in this problem arises both from the fact that it is a problem which is very simple to describe, but considerably complex to solve, and from the fact that the applications of the traveling salesperson problem are many and not limited to delivery and / or collection of goods.

A possible formalization of the problem can be obtained in following way. Consider a directed graph whose nodes are cities (or customers) to be visited. We assume that the graph is complete, which means that there exists an arc connecting each pair of nodes. Sometimes this is not the case: in a road network, as an example, only some pairs of cities are connected directly by a road. In graphs which are not complete, a path which goes through each node once and only once might not exist:

Figure made with TikZ

It is evident that, in this figure, no path exists which, starting from node 0, goes through nodes 1-5 and back to 0 without passing more than once over a node. A path which satisfies this requirement would be called an Hamiltonian path. In some applications the constraint of not passing more than once through a node might be relaxed. In the traveling example, it is important to visit each location to deliver or collect parcels; however, it not forbidden to pass again through an already visited node, on the way to a different destination. We may thus create a complete graph in which the arc between two nodes represents a “shortest path” between the nodes itself. In other words, a minimum cost path problem (see chapter Shortest (Minimum Cost) Path Problems) is repeatedly solved to find the least cost route from each node to each different node in the graph. Then, if the graph is connected, a complete graph can be defined in which arcs, representing optimal paths, connect each pair of nodes. Thus it is always possible to find hamiltonian paths.

From now on, let us assume that the graph is complete, and that costs associated to each arc are non negative. In order to formulate the optimization problem we associate an indicator variable to each arc: \(\mathvar{\delta}_{ij}\). Constraints need to be defined in such a way that this variable is equal to 1 if and only if the route prescribes to visit node \(j\) immediately after having visited node \(i\). Assuming the constraints have been formulated, the objective function is simply written, exactly in the same way as in the minimum cost path problem:

\begin{align*} \min \sum_{(i,j) \in E} \param{c}_{ij} \mathvar{\delta}_{ij} \end{align*}

In the above objective, \(E\) is the set of arcs in the graph. If nodes are denoted by \(V = \{0,1, \ldots, n\}\), then \(E = \{(i,j) \in V \times V : i \ne j\}\).

For what concerns the constraints, first observe that the tour must touch each node once; thus, referring to a network flow problem, the total flow in and out of each node should be equal to 1. That is, one and only one arc of a feasible tour will enter each node and one and only one arc will exit from it. In formulae:

\begin{align*} \sum_{i \in V, i \ne j } \mathvar{\delta}_{ij} & = 1 & \forall \, j \in V\\ \sum_{j \in V, j \ne i} \mathvar{\delta}_{ij} & = 1 & \forall \, i \in V \end{align*}

It is easily recognized that the structure of these two groups of constraints is that of matching constraints (on a graph which, however, is not bipartite like in chapter Assignment or bi-partite matching). Generic (non bipartite) weighted matching problems are easily solvable, and efficient algorithms do exist (see, e.g., [17]). Unfortunately these constraints, although necessary for a feasible solution, are not sufficient to force the indicator variables to identify a single closed tour. The following example shows the situation: