An improved Tabu Search heuristic Algorithm for the Coach Trip with Shuttle Service Problem

Oualid Guemri (1) , Abdelghani Bekrar (2)

1 University of Oran
2 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

In this work we present a Tabu Search (TS) heuristic algorithm for the Coach Trip with Shuttle Service Problem (CTSSP). The CTSSP, which is a personal-transportation problem, consists of the collection of passengers from their origin stop to a final hub; this is done using some coaches and additional shuttle vehicles if needed. To solve the CTSSP, we develop a TS method. First, the initial solution is generated using Greedy Insertion Technique. Then, at each iteration, our TS generate the current solution neighborhoods using several operators. During the research, we use a repair heuristic in order to improve the overall cost. To evaluate the performance of our algorithm, 4 test instances are used. On average, the TS reports results with a gap of 5.01 % to the best known solution. Regarding this results, the improved TS is successfully qualified to the final round by the international challenge jury.

Domaines: Automatique / Robotique

Oualid Guemri, Abdelghani Bekrar. An improved Tabu Search heuristic Algorithm for the Coach Trip with Shuttle Service Problem. 4th Meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization, Jun 2015, Vienne, Austria. ⟨hal-03421623⟩