Résolution du problème de cueillette et livraison avec fenêtres de temps à un seul véhicule par des méta-heuristiques

Abstract

Le VRP est un problème classique qui consiste à construire des routes visitant un ensemble de clients en minimisant le coût de transport, en satisfaisant les demandes de ces derniers et en respectant les différentes capacités des véhicules. Nous nous intéressons à une importante variante du VRP qui est le PDPTW. Dans ce mémoire nous avons traité un problème de collecte et de distribution avec fenêtres de temps à un seul véhicule 1-PDPTW. Dans ce problème, le véhicule doit servir un ensemble de demandes de biens à transporter à partir d’un ensemble de fournisseurs vers des clients, tout en respectant des contraintes de capacité et des contraintes de temps. Nous avons résolu ce problème en utilisant un algorithme évolutionniste avec des opérateurs génétiques spécifiques (la 1ère heuristiques) et notre approche de colonie de fourmis adaptés pour fournir un ensemble de solutions viables. Ces approches de résolution minimisent le compromis entre la distance totale parcourue, le temps total d’attente et le retard total. The VRP is a classical problem that consists on building routes visiting a set of customers minimizing the transportation cost, while satisfying their demands and the different vehicles capacities. We are interested in an important variant of the VRP which is the PDPTW. In the present work we have dealt with the problem of collecting and delivery with time windows for a single vehicle 1-PDPTW. In this problem, a vehicle has to serve a set of customers from a set of suppliers, while satisfying their demands, under some given capacity requirements. This problem has been solved using an evolutionary algorithm with a special genetic operator in one hand, and by an adapted ant colony approach to provide a set of viable solutions on the other hand. By these approaches we minimize the trade-off between the total distance trip, the total waiting time and the total delay.