TY  - JOUR
T1  - The Shifting Traveling Salesman Problem: From Modeling to Resolution
AU - El Yaagoubi, Amina AU - El Hilali Alaoui, Ahmed AU - Boukachour, Jaouad 
JO  - Journal of Engineering and Applied Sciences
VL  - 13
IS  - 14
SP  - 5911
EP  - 5925
PY  - 2018
DA  - 2001/08/19
SN  - 1816-949x
DO  - jeasci.2018.5911.5925
UR  - https://makhillpublications.co/view-article.php?doi=jeasci.2018.5911.5925
KW  - Traveling salesman problem
KW  -unloading
KW  -reloading
KW  -shiftings
KW  -mathematical programming
KW  -optimization
KW  -metaheuristic
KW  -parallel-ant colony algorithm
AB  - 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.
ER  -