The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are commonly represented by vertex lists. However, when the TSPPD is required to follow a policy that loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a novel variable neighborhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Extensive experiments suggest that our VNS heuristic is superior to the current best heuristics for the TSPPDL in terms of solution quality, while requiring no more computing time as the size of the problem increases.
The traveling salesman problem with pickup and delivery (TSPPD) has been extensively studied by a large number of researchers (e.g., Kalantari et al., 1985, Healy and Moll, 1995, Renaud et al., 2000, Renaud et al., 2002 and Dumitrescu et al., 2009). In the TSPPD, there is a set of n requests, denoted by R = {1, …, n}, each of which is composed of a pickup vertex and a delivery vertex. Let P = {1+, …, n+} be the set of pickup vertices and D = {1−, …, n−} be the set of delivery vertices. Vertices 0+ and 0− represent the exit from and the entrance to the depot, respectively. The TSPPD is defined on a complete and undirected graph G = (V, E, d), where V = P ∪ D ∪ {0+, 0−} is the vertex set; E = {(x, y):x, y ∈ V, x ≠ y} is the edge set; and d(x, y) denotes the non-negative distance between vertices x and y. The objective of the TSPPD is to find a shortest Hamiltonian tour on G, starting from vertex 0+ and ending at vertex 0−, for a vehicle with unlimited capacity, subject to the precedence constraints that each pickup vertex is visited before its associated delivery vertex. In most of the existing literature on the TSPPD, feasible solutions are represented by lists (or sequences) of vertices complying with the precedence constraints.
This study addresses a variant of the TSPPD in which loading and unloading operations must be performed in a last-in-first-out (LIFO) manner; this problem is referred to as the TSPPD with LIFO loading (TSPPDL). It models the fact that the storage units of most transport vehicles have only a single door located at the rear, and therefore the goods that are first picked up must be stored towards the front of the vehicle (away from the door). As a consequence, the last goods picked up should be the first ones unloaded. The LIFO constraints are especially applicable when transporting bulky items, or when the amount of handling must be minimized during the transport of hazardous materials.
The TSPPDL has been considered a more complex problem than the TSPPD because in order to judge whether a solution that is represented as a vertex list is feasible, we have to check not only the precedence constraints, but also the LIFO constraints. In this paper, we show that there is a one-to-one correspondence between feasible solutions of the TSPPDL and tree representations of such solutions. This tree data structure embodies the nature of the TSPPDL solutions and greatly simplifies this seemingly complicated problem. As a result, we were able to build upon the Variable Neighbourhood Search (VNS) heuristic proposed by Carrabs et al. (2007b), which is the best existing approach for the TSPPDL at the time of this writing, by both reproducing five of the original operators using the tree representation as well as introducing three new operators. Extensive experiments show that our new heuristic outperforms the original one in terms of solution quality, and it also requires comparatively less computation time as the number of requests in the problem increases.
The main contribution of this study is the tree representation of feasible solutions for the pickup and delivery TSP with LIFO loading. By using this data structure, the feasibility of the solution is automatically guaranteed, which aids greatly in both the design and implementation of search operators for the problem. We designed a new VNS heuristic for the problem, called VNS-Tree, which reproduced the basic search operators of the previous best approach VNS-List and includes several new operators based on the tree representation. The experimental results for VNS-Tree revealed that it outperforms VNS-List in terms of both the quality of the solutions found and computation time for large instances. Furthermore, the quality of the initial solution is not a major factor in its performance.
This work opens up new directions of research for the TSPPDL. A major failing of the vertex representation is the need to ensure the feasibility of the solution. This makes the implementation of certain techniques, for example genetic algorithms or simulated annealing, difficult or impossible. In contrast, the tree representation naturally lends itself to approaches of this type; in fact, the crossover operator used in VNS-Tree can be employed for the same purpose in an evolutionary algorithm.
The application of the tree data structure can also be considered for other problems involving pickup and delivery with the LIFO constraints. Variants for this problem include the addition of capacity constraints, multiple vehicles and time windows. It may also be worth investigating the use of a tree representation for problems where the vehicle can load goods in multiple stacks, such as the double traveling salesman problem with multiple stacks.
