A metaheuristic for the double traveling salesman problem with partial last-in-first-out loading constraints

This paper addresses the double traveling salesman problem with partial last-in-first-out (LIFO) loading constraints. A vehicle picks up items in the pickup area and loads them into its container, a horizontal stack. Once all the pickup operations are done, the vehicle can deliver the items to the delivery area because pickup-and-delivery areas are geographically separated. Additionally, the loading and unloading operations also follow a partial LIFO policy. The aim is to find a Hamiltonian cycle that satisfies the loading and unloading policy described above in order to minimize the distance traveled by the vehicle in both areas and the cost of the rearrangements that are performed across the routes. The state-of-the-art algorithm finds good solutions to the existing instances. However, finding good-quality solutions in large instances requires longer computing times. Therefore, we propose an iterated local search that considers two additional components to the classical components, the intensification and restart procedure. The first helps in a more thorough examination of promising neighborhoods, while the second helps in the complete diversity of the solutions in the hopes of escaping the local optima. Moreover, a new unique decoding approach for the solution representation is proposed to effectively generate feasible solutions. The proposed algorithm's performance is evaluated on an existing set of instances and in two new additional sets of larger instances that are proposed. The computational results obtained on the three test sets show that the proposed algorithm outperforms the state-of-the-art algorithm in terms of computing time required to find good-quality solutions.