HYBRID EVOLUTIONNARY APPROACHES AND NEW BENCHMARKS FOR THE 1-PDPTW

In This paper we present an improved tabu search in an hybrid evolutionary approach for the single-vehicle Pickup and Delivery Problem with Time Windows (1- PDPTW). In the 1-PDPTW a vehicle must serve a collection of transportation requests by taking loads from providers to customers satisfying precedence, capacity and time constraints. This paper purposes a brief state of the art on the 1-PDPTW and hybrid evolutionary approaches to solve it. It also presents new benchmarks by giving a complexity level for each treated problem, and shows some results for the 1-PDPTW. Our hybrid evolutionary approach use evolutionary algorithm, with special genetic operators, tabu search, construction heuristics, Pareto dominance method to provide a set of satisfying and feasible solutions to the 1-PDPTW minimizing total travelled distance, total waiting time and total tardiness time.