Modélisation et méthode de résolution
Outil d'optimisation pour le transport des personnes handicapées mentales

4.1 Modélisation et état de l’art

• Le problème de confection des plans de transport relève du domaine de l’Optimisation discrète (pour une introduction à ce domaine, vous pouvez consulter le dossier sur ce sujet ). Il appartient à la classe des « Problèmes de tournées de véhicules » (VRP : Vehicle Routing Problem).

  Le problème étudié présente plusieurs particularités : il peut comporter à la fois des tournées ouvertes (les taxis qui effectuent un aller ou un retour vers l’établissement), et des tournées fermées (les véhicules de l'établissement qui effectuent une boucle complète). Le problème est contraint par l'existence de fenêtres horaires. Les véhicules peuvent être de capacités différentes les uns des autres. De plus, un ensemble de contraintes pratiques compliquent le problème :

  • limitation de la durée des trajets ;

  • personnes en fauteuil roulant ;

  • incompatibilités entre personnes, etc.

    Sur l’optimisation discrète

    Optimisation discrète  de M.C. Portmann et A. Oulamara

• Le problème comprenant uniquement des tournées ouvertes est appelé «  open-VRP » et appartient à la classe des problèmes NP-difficiles. De manière étonnante, l'open-VRP n'a donné lieu qu'à très peu de travaux jusqu'à ces dernières années. En 2004, Brandão  ne mentionne l'existence que de trois articles antérieurs, datés de 1981, 1983 et 2000. Letchford  propose une résolution exacte de l'open-VRP avec des véhicules identiques et sans contraintes de fenêtres de temps. Le temps de résolution dépasse une heure pour des instances de quelques dizaines de sites.

  Les articles  et  décrivent des modèles mathématiques d’open-VRP avec des contraintes de fenêtres de temps. Fu  intègre la notion de flotte hétérogène. Enfin, Pisinger  décrit un algorithme adaptable à un grand nombre de variantes du VRP, dont l'open-VRP avec fenêtres horaires. En revanche, l'open-VRP avec flotte hétérogène et fenêtres horaires, ou le VRP combinant tournées fermées et ouvertes, n'ont, à notre connaissance,...