Authors : Amina El Yaagoubi, Ahmed El Hilali Alaoui and Jaouad Boukachour
Abstract: This study introduces the Shifting Traveling Salesman Problem (ShTSP) which is a new variant of the transportation problems that combines the well-known traveling salesman problem and the shifting problem. The ShTSP arises naturally in the transportation of large, heavy, hazardous or fragile products in a single vehicle with a single stack where all products are stowed in a predefined order according to their weight, fragility and stability. The stack has a single access point for the unloading of freight which means, the unloading of each product is performed according to the "Last In First Out" (LIFO) policy such that a number of products must be removed in order to reach products below them. In other words, shifting products within the vehicle becomes necessary if the target product is located below other ones. Our goal is to seek an optimal tour that takes account of the shifting cost which represents the temporary removal of frights in the vehicle caused by the unloading and reloading operations at each client of the tour. We propose a mathematical model as a mixed nonlinear program and then we solve it by proposing two methods: the first one consists on adapting the ant colony metaheuristic and the second one introduces a new parallel-ant colony adaptation, the two algorithms are tested on a number of problem instances of varying problem characteristics from the TSPLIB benchmark sets. Computational results show the efficiency of the improved version of the algorithm which is based on the parallel concept, for small and large sized instances.
Amina El Yaagoubi, Ahmed El Hilali Alaoui and Jaouad Boukachour, 2018. The Shifting Traveling Salesman Problem: From Modeling to Resolution. Journal of Engineering and Applied Sciences, 13: 5911-5925.