The Tree Representation of Feasible Solutions for the TSP with Pickup and Delivery and LIFO Loading

Dejian Tu, Songshan Guo, Hu Qin, Wee-Chong Oon, Andrew LimAAAI 2010 · DOI

Introduction

The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization, tasking a solver with finding the shortest route to visit a set of nodes exactly once. Real-world logistics often introduce complex constraints, such as the Pickup and Delivery variant (TSPPD), where each request consists of a pickup location that must be visited before its corresponding delivery location.

This paper addresses a particularly challenging version: the TSP with Pickup and Delivery and LIFO (Last-In-First-Out) Loading (TSPPDL). In this scenario, items are loaded into a stack-like compartment; an item can only be delivered if it is at the top of the stack. This implies that if item A is picked up before item B, B must be delivered before A. Traditional list-based representations of routes struggle with these constraints, as most local search moves (like swapping two stops) result in infeasible solutions that are computationally expensive to repair.

Innovation: The TSPPDL Tree

The core contribution of this work is a novel tree-based representation for feasible TSPPDL solutions. Instead of representing a route as a linear sequence of vertices, the authors encode it as an ordered tree.

Structure and Mapping

In this representation, each node in the tree (excluding the root) represents a specific request. The root node represents the depot. The physical route is generated through a modified preorder traversal of the tree:

  1. Pickup (+): A request is "picked up" when the traversal first enters its corresponding node.
  2. Delivery (-): A request is "delivered" when the traversal leaves the node for the last time, after visiting all its descendants.
The TSPPDL tree structure (a) and its mapping to a feasible route (b) via traversal.

Feasibility by Design

This structural approach ensures that both precedence (pickup before delivery) and LIFO constraints are satisfied by default. Because a node's delivery only occurs after its children (representing nested requests) have been processed, the LIFO property is naturally maintained. This "feasibility by design" eliminates the need for costly feasibility checks during the optimization process, allowing the search algorithm to focus entirely on minimizing route cost.

Search Strategy: VNS-Tree

Leveraging this tree structure, the authors developed a Variable Neighbourhood Search (VNS-Tree) heuristic. The algorithm utilizes several operators to explore the solution space:

  • Standard Operators: Adapted versions of node swapping and subtree relocation.
  • ATSP Operator: Uses an exact TSP solver to optimize the ordering of children for a given node.
  • Crossover and Perturbation: Mechanisms to combine features from different solutions and escape local optima by re-inserting subtrees.

Experimental Results

The authors evaluated VNS-Tree against the previous state-of-the-art, VNS-List, using 96 benchmark instances. These included standard TSPLIB instances and a specialized set where the optimal solution is known (Type 2).

As shown in the table below, VNS-Tree significantly outperforms the list-based approach. On Type 2 instances, VNS-Tree identified the optimal solution in 40 out of 48 cases, compared to only 20 for VNS-List. Furthermore, VNS-Tree demonstrated superior scalability, often running twice as fast as VNS-List on large 1001-node instances while maintaining higher solution quality.

Comparison of VNS-List and VNS-Tree on Type 2 instances where the optimal solution is known.

Conclusion

By shifting from a linear to a hierarchical tree representation, this research effectively "hides" complex LIFO constraints within the data structure itself. This structural elegance leads to a more efficient search space and a highly performant heuristic. Future work may extend this tree-based logic to handle additional real-world constraints such as vehicle capacity limits, time windows, and multi-vehicle fleets.

Summary updated

BibTeX
@inproceedings{tu2010tree,
  author = {Dejian Tu and Songshan Guo and Hu Qin and Wee-Chong Oon and Andrew Lim},
  title = {{The Tree Representation of Feasible Solutions for the TSP with Pickup and Delivery and LIFO Loading}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7532},
}
Figure