Large Neighborhood Search pour le problème de DARP avec fenêtres de temps : application au transport intra-hospitalier de patients

Abstract

Ce projet traite du probl`eme de transport bipoint intra-hospitalier avec fenˆetres de temps (DARPTW). L’objectif est de r´eduire les temps d’attente des patients, de diminuer les distances parcourues et d’´equilibrer la charge de travail des porteurs. Pour r´esoudre ce probl`eme NP-difficile, deux approches ont ´et´e propos´ees : une heuristique de construction produisant rapidement une solution initiale, et une m´etaheuristique LNS permettant d’am´eliorer la qualit´e. Les exp´erimentations ont montr´e que l’heuristique est tr`es rapide mais approximative, tandis que la LNS am´eliore significativement la qualit´e (jusqu’`a 40 % sur les petites instances) au prix d’un temps de calcul plus ´elev´e. Ces r´esultats soulignent la compl´ementarit´e des deux m´ethodes et l’int´erˆet des m´etaheuristiques pour optimiser le transport hospitalier.