Problème de collectes et livraisons avec fenêtres de temps et flotte homogène.

Résumé : Nous nous intéressons dans ce travail au problème de collectes et livraisons avec fenêtres de temps et flotte hétérogène (HVRPPDTW : Heterogeneous Vehicule Routing Problem Pickup and Delivery with Time Windows). Dans cette variante du problème de tournées de véhicules (VRP : Vehicle Routing Problem), nous avons un ensemble de véhicules de coût et de capacités différentes. L’objectif est de trouver un sous-ensemble de véhicules et un ensemble de tournées satisfaisant l’ensemble des requêtes à moindre coût. Chaque requête est caractérisée par un couple de demandes (une demande de collecte et une demande de livraison). A chaque demande est associée une quantité de marchandises à collecter (ou à livrer) sur un site donné et un intervalle de temps où la collecte (ou la livraison) doit être effectué. Etant donné une requête, le couple collecte et livraison correspondant est effectué dans la même tournée. Toute livraison n’est pas obligatoirement effectuée après la collecte correspondante. Une modélisation de ce problème sous forme de programme linéaire à variables mixtes (MILP : Mixed Integer Linear Program) est développée. Des méthodes de réduction de l’espace de recherche, un ensemble de coupes valides et un algorithme basé sur la décomposition de Benders sont également proposés. Ces approches permettent de résoudre à l’optimalité les instances réelles fournies par le Centre Hospitalier de Troyes (France) et certaines instances de la littérature pour le cas d’une flotte homogène.