Exact and heuristic solutions to the Double TSP with Multiple Stacks

The double travelling salesman problem with multiple stacks (DTSPMS) is a pickup and delivery problem where pickups and deliveries are separated, such that all pickup operations are performed before the first delivery takes place. All operations are carried out by one vehicle and no reloading is allowed. The vehicle provides several separated (horizontal) stacks/rows for the transportation of the orders, such that each stack is accessed using a LIFO principle, independently of the other stacks. In a real-life setting the dimensions of the problem is 33 orders each consisting of one euro-pallet, which can be loaded in 3 stacks in a standard 40 foot container. Different exact and heuristic solution approaches to the DTSPMS have been implemented and tested. The exact approaches are based on different mathematical formulations of the problem which are solved using branch-and-cut. One formulation leads to a decomposition approach, consisting of a routing master problem and a loading feasibility subproblem, which generates infeasible paths for the master problem. The latter is the most promising of the tested approaches, and solves all tested problems with up to 15 orders, as well as some larger instances. The implemented heuristics include tabu search, simulated annealing and large neighbourhood search. Particularly the LNS approach shows promising results. It finds the known optimal solution of smaller instances (15 orders) within 10 seconds in most cases, and in 3 minutes it finds solutions to 33 order instances that are on average within 1% of the best known solutions.