Optimisation Heuristique

Le problme de ramassage et de livraison (pick-up and delivery problem) est l'un des problmes dont une grande partie des chercheurs s'y est intresse. Il s'agit de dterminer un circuit de plusieurs vhicules, de faon servir cot minimal un ensemble de clients et de fournisseurs rpartis dans un rseau, satisfaisant certaines contraintes relatives aux vhicules, leurs capacits et des prcdences entre les nuds. Ces travaux de recherche portent sur le PDPTW (Pickup and Delivery Problem with Time Windows) plusieurs vhicules (m-PDPTW). Ce dernier a t trait dans les deux cas : statique et dynamique. Plusieurs approches de rsolution du m-PDPTW ont t proposes, bases sur les algorithmes gntiques, l'optimisation multicritre et le calcul des bornes infrieures, et ceci pour minimiser un certain nombre de critres comme : le nombre de vhicules utiliss, la somme des retards ou le cot total de transport. Ces approches ont donn de bons rsultats, principalement au niveau de la minimisation de la somme des retards,o l'obtention dans plusieurs cas, un retard nul avec un cot de transport tolrable.