Keywords

1 Introduction

The Probabilistic Traveling Salesman Problem (PTSP) is an NP-hard problem [6] introduced by Jaillet [10]. It is a variant of the Traveling Salesman Problem (TSP), where each city has an assigned probability of requiring a visit. We search for an a-priori tour through all cities that minimizes the expected length of the real tour, where some cities might not have to be visited. The real tour, also called realization of the a-priori tour, then follows this a-priori tour and skips cities which do not have to be visited. A real world application for the PTSP would be, e.g., a postman who delivers mails on a fixed assigned route every day. From historical data the probability of each address requiring a visit is known. After each delivery he checks which address he has to visit next and proceeds accordingly.

Formally we are given a complete graph \(G = \langle V, E \rangle \) with V being a vertex set containing n nodes and E being an edge set containing m edges. Each edge \((i,j) \in E\) is assigned a cost \(d_{ij}\) and each node \(v \in V\) has a probability \(p_v\) of requiring a visit. If the probabilities \(p_v\) are equal for every node, the problem is called homogeneous and otherwise it is heterogeneous [9]. A solution \(T = \langle v_1, \dots , v_n \rangle \) is an a-priori tour, represented by a permutation of the n nodes, where the first and last nodes are implicitly assumed to be connected. In this paper we concentrate on the homogeneous PTSP with symmetric distances due to comparability with other papers.

The expected costs of a tour T are defined as

$$\begin{aligned} c(T) = \sum _{i = 1}^{2^n} p(R_i) L(R_i) \end{aligned}$$
(1)

where \(R_i\) is a possible realization, i.e., one possible a-posteriori tour, \(p(R_i)\) its occurrence probability, and \(L(R_i)\) the resulting length of the tour. Since there are \(O(2^n)\) different realizations, it is not convenient to compute the objective value in such a way. Therefore Jaillet [10] showed that the expected length can be calculated in \(O(n^2)\) time using the following closed form expression:

$$\begin{aligned} \begin{aligned} c(T)&= \sum _{i = 1}^{n} \sum _{j = i+1}^n d_{v_i v_j} p_{v_i} p_{v_j} \prod _{k = i+1}^{j-1} (1 - p_{v_k})\\&\quad +\sum _{j = 1}^{n} \sum _{i = 1}^{j-1} d_{v_j v_i} p_{v_i} p_{v_j} \prod _{k = j+1}^{n} (1 - p_{v_k}) \prod _{k = 1}^{i-1} (1-p_{v_k}) \end{aligned} \end{aligned}$$
(2)

This formula represents the most general form for heterogeneous PTSPs. As we concentrate on the homogeneous problem, we will use the following, simplified objective function:

$$\begin{aligned} c(T) = p^2 \sum _{r = 1}^{n-1} (1-p)^{r-1} \sum _{i = 1}^n d_{v_i v_{i+r}} \end{aligned}$$
(3)

The PTSP is a well studied problem in the literature. Bertsimas et al. [4, 6] contributed theoretical properties of the PTSP such as bounds and asymptotic analyses. Bianchi et al. [7, 8] proposed metaheuristic approaches based on ant colony optimization and local search with exact delta evaluation. Balaprakash et al. [1, 2] analyzed sampling and estimation-based approaches. Weyland et al. [14, 15] considered new sampling and ad-hoc approximation methods for local search and ant colony system. Marinakis and Marinaki [11] proposed a hybrid swarm optimization approach. The most promising results were obtained by using not the exact objective function as stated in Eq. 3, but either a restricted depth approximation or a sampling approach. In contrast, our approach is based on an efficient exact evaluation.

In Sect. 2 we apply several TSP construction heuristics to the PTSP, consider Jaillet’s Almost Nearest Neighbor Heuristic [10], and introduce two new construction heuristics derived for the PTSP: Probabilistic Farthest Insertion and Probabilistic Nearest Insertion. In Sect. 3 we propose a Variable Neighborhood Descent Framework embedded in a Variable Neighborhood Search to improve constructed solutions. Section 4 presents experimental results and Sect. 5 concludes this work.

2 Construction Heuristics

For generating an initial solution for the subsequent VND/VNS we consider several different construction heuristics. First we investigate construction heuristics having already been used for the TSP and then we improve upon them by taking also the probabilities into account.

2.1 TSP Construction Heuristics on PTSP

To construct a reasonable tour for PTSP we first investigate how well TSP construction heuristics perform. We evaluate the following construction heuristics:

Nearest Neighbor (NN): Starting from a first node \(v_0\in V\), we iteratively append an unvisited node that is nearest to the previously inserted one. The resulting computational complexity is in \(O(n^2)\).

Nearest Insertion (NI): Starting with a simple tour T containing only one node \(v_0 \in V\), we insert the nearest node to the previously inserted one at the best fitting position. Let \(v_j\) be the node to be inserted next, then we calculate the best fitting position by determining

$$\begin{aligned} \min \limits _{v_i, v_{i+1} \in T} (d_{v_i v_j} + d_{v_j v_{i+1}} - d_{v_i v_{i+1}}) \end{aligned}$$
(4)

The computational complexity is in \(O(n^2)\).

Farthest Insertion (FI): This heuristic is similar to NI. The only difference is that we choose the farthest node to the previously inserted one is chosen for insertion instead of the nearest one.

Space Filling Curve (SFC): SFC was introduced by Bartholdi et al. [3]. The heuristic constructs a Sierpiński curve over all cities and visits them as they appear on this curve. The computational complexity is in \(O(n \log n)\).

Radial Sorting (RS): We construct a new virtual city which can be seen as the center of mass of all cities. The cities are then sorted and visited by their angle relative to this center. For TSP this heuristic usually yields poor results, but for stochastic vehicle routing problems with low probabilities it can perform really well [5]. The computational complexity is dominated by the sorting, and thus, is in \(O(n \log n)\).

2.2 Construction Heuristics for PTSP Using Probabilities

To take probabilities into account we adapt the first three heuristics from Sect. 2.1.

Almost Nearest Neighbor Heuristic (ANN): ANN was mentioned by Jaillet [10] in his dissertation, but it did not gain much attention until now. It appends the city with the lowest change of expected length from the last inserted city to the tour. The cost of inserting city \(v_j\) can be computed the following way for heterogeneous problems:

$$\begin{aligned} \min \limits _{v_j \in (V - T)} \left( \sum _{i = 1}^{|T|} p_{v_i} p_{v_j} d_{v_i v_j}\prod _{k = i+1}^{|T|} (1 - p_{v_k})\right) \end{aligned}$$
(5)

For the homogeneous problem we can simplify the formula:

$$\begin{aligned} \min \limits _{v_j \in (V - T)} \left( \sum _{i = 1}^{|T|} d_{v_i v_j} (1 - p)^{(|T|-i)}\right) \end{aligned}$$
(6)

Note that we omitted the \(p^2\) in the homogeneous formula because we try to find a minimum and therefore scaling by \(p^2\) does not matter. The resulting computational complexity is in \(O(n^3)\) because we insert each city in the tour and evaluate Eq. 6 on each position in the tour.

Probabilistic Nearest Insertion (PNI): PNI is a new heuristic derived from NI where we insert the node nearest to the last inserted node into the tour and evaluate the objective function on each possible position. This naive approach results in a computational complexity of \(O(n^4)\). We use Bianchi et al.’s delta 1-shift [8] local search procedure to solve this heuristic more efficiently: Bianchi showed that 1-shift local search is possible in time \(O(n^2)\) using delta evaluation. Therefore we insert the node at the first position in the tour and then perform one iteration of the delta 1-shift procedure. Therefore we are able to reduce the complexity to \(O(n^3)\).

Probabilistic Farthest Insertion (PFI): PFI is a new heuristic similar to PNI. The only difference is that the farthest node to the previously inserted one is chosen for insertion instead of the nearest one.

3 Variable Neighborhood Search

Variable Neighborhood Descent (VND) and Variable Neighborhood Search (VNS) were introduced by Mladenović and Hansen in 1997 [12]. VND uses the fact that if a solution is at a local optimum in some neighborhood it is not necessarily locally optimal in another neighborhood. We use delta 2-opt and delta 1-shift neighborhood structures by Bianchi et al. [8] to combine them within a VND framework because they showed that it is possible to exactly evaluate them using delta evaluation formulations. Therefore, we compute a solution that is locally optimal with respect to both neighborhoods.

Via a general VNS we repetitively randomize the tour by applying shaking, and locally improving it again with VND. In the i-th shaking neighborhood we perform 2i random shift moves. Our VNS terminates after 20 iterations without improvement.

4 Computational Results

The algorithms were implemented in C++99 and compiled with GNU GCC 4.6.4. As test environment we used an Intel Xeon E5649, 2.53 GHz Quad Core, running on Ubuntu 12.04.5 LTS (Precise Pangolin). For a comparison with the literature we use test instances from the TSPLIB [13]. Homogeneous visiting probabilities were assumed to be \(p\in \{0.1,0.2,\dots ,0.5\}\).

Table 1. Results of construction heuristics.
Full size table
Table 2. Variable neighborhood descent/search comparison.
Full size table

Table 1 summarizes our evaluation of the construction heuristics. Generally the probabilistic versions generate better results than their deterministic counterparts but at the price of much higher runtimes. From the deterministic ones, FI performs best, but also SFC performs well. Overall, PFI performs best but PNI is close.

Table 2 shows our Variable Neighborhood Search results compared to results from the literature. Weyland et al. [15] only published results of their EACS for instances att532 and rat783 with \(p=0.1\) and \(p=0.2\), and therefore, we performed additional tests using their code and published parameters for the other instances. For the VNS we apply FI and PFI as construction heuristic because FI offers the best tradeoff between efficiency and runtime and PFI performs best. Therefore we only include FI+VND, FI+VNS, and PFI+VNS in our results. In many cases our VND yields good solutions in short time, but VND alone cannot keep up with Weyland et al.’s EACS [15] or Marinakis’ HybPSO [11]. However, our VNS is able to achieve new best solutions in 11 cases. We further observe that EACS performs excellent especially on the larger instances but the VNS is typically better on smaller instances. When comparing FI and PFI in combination with the VNS we see that they find solutions of similar quality but for larger instances the runtime of PFI+VNS increases more than the runtime of FI+VNS.

5 Conclusions and Future Work

In this paper the PTSP was discussed and the most important properties were shown. We focused on five TSP construction heuristics to generate an initial solution, namely Radial Sorting, Farthest Insertion, Nearest Insertion, Space Filling Curve, Nearest Neighbor, and compared them on several TSPLIB instances. Overall, Farthest Insertion performed best, followed by Space Filling Curve. Then we derived new construction heuristics to take probabilities into account: Almost Nearest Neighbor, Probabilistic Nearest Insertion and Probabilistic Farthest Insertion. They all significantly improve on their deterministic counterparts but are much more time-consuming. To improve these solutions we introduced a VNS framework with embedded VND based on 1-shift and 2-opt neighborhood structures and exact delta evaluation. Results show that FI+VNS and PFI+VNS typically yield the best solutions out of our tested configurations and they are even able to find new best-known solutions for 11 instances.

The major reason why our VNS performs so well is the usage of efficient, exact delta evaluation approaches for 1-shift and 2-opt originally proposed by Bianchi et al. [8]. Future work should consider further neighborhood structures for the PTSP for which exact delta evaluations are possible. In particular we are currently considering Or-opt.