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:
- Pickup (+): A request is "picked up" when the traversal first enters its corresponding node.
- Delivery (-): A request is "delivered" when the traversal leaves the node for the last time, after visiting all its descendants.
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.
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