Conception de Tournées de Véhicules Régulières

L'optimisation de problèmes de tournées de véhicules se concentre généralement sur la minimisation de la distance parcourue ou du temps de parcours. Optimiser la qualité de service est un critère au moins aussi important dans de nombreux contextes (Paquette et al. [1]). En particulier, dans le cas de clients servis de manière répétitive au cours du temps, maintenir une certaine régularité dans le service peut être grandement apprécié. Un cas très représentatif est celui des grandes sociétés de messagerie (type UPS, DHL...) pour la livraison de colis auprès de grands comptes industriels (Groër et al [2]). Du fait de l'importance de l'activité des entreprises clientes, les réceptions de colis se répètent sur une base presque quotidienne. Être capable de proposer à la fois un horaire de livraison et un chauffeur réguliers à chaque livraison procure un vrai confort pour le client, facilite la réception des livraisons et affermit la confiance entre transporteur et client (Day et al. [3], Haughton [4]). Un autre cas emblématique est celui du transport de personnes handicapées vers et à partir d'établissements médico-sociaux (CAT, IME). Du fait de leur manque d'autonomie, la plupart des personnes qui se rendent dans ces établissements ne peuvent le faire par leurs propres moyens. Les établissements ont donc recours à des sociétés de transport pour organiser ces trajets quotidiens. Dans de nombreux cas, la demande des clients est connue, mais présente de légères variations au niveau des conditions de prise en charge (par exemple une personne qui n'émet pas de demande de transport pour le mercredi après-midi, ou une personne souhaitant être déposée à une autre adresse le vendredi). De plus, ce type de passagers est particulièrement sensible aux changements de planning. Il est alors primordial d'essayer de maintenir un horaire de service aussi régulier que possible malgré les variations de la demande (Lehuédé et al. [5]). Dans cette présentation, nous nous intéressons à la planification de tournées en prenant compte la régularité des horaires. Le projet se décline en plusieurs sous-objectifs : - Nous cherchons à donner une ou plusieurs définitions de la notion de la régularité et discuter des liens de cette notion avec d'autres concepts proches (robustesse, distance entre solutions, analyse de sensibilité...). Pour chaque client, on définit une classe horaire comme un ensemble de dates de service considérées comme identiques. Par exemple, un client livré à 10h20 le lundi et 10h23 le mardi ne percevra aucune différence entre ces horaires, qui peuvent donc être considérés comme appartenant à la même classe. La notion de régularité est étroitement liée au nombre de classes horaires pour chaque client. - Nous examinons plusieurs manières d'inclure la régularité dans les modèles d'optimisation de tournées. Une première approche consiste à minimiser uniquement le nombre de classes sans se préoccuper du coût des tournées). La solution optimale peut aboutir à des tournées aberrantes du point de vue logistique. Cette approche peut présenter un intérêt lorsque la régularité du service prime sur la performance logistique, ce qui est parfois le cas dans les activités de service à la personne. En pratique, on cherchera à minimiser le nombre de classes en s'assurant que les tournées soient simplement acceptables d'un point de vue logistique. Une autre approche consiste à fixer a priori un nombre de classes acceptable pour chaque client. Le modèle recherche les tournéees de longueur minimale, en limitant le nombre de classes à cette valeur maximale pour tout client. Ce modèle est voisin de celui présenté dans [2], la principale différence réside dans la définition de la régularité. Une optimisation bi-objectif peut être réalisée assez facilement faisant varier le nombre de classes acceptables entre 1 et le nombre de périodes de l'horizon de planification. - Nous évaluons quantitativement l'impact de la régularité sur la résolution des problèmes ainsi définis. La résolution des modèles évoqués précédemment par le solveur Xpress-MP nécessite des heures de calcul pour des problèmes de taille très réduite (de l'ordre de 10 clients pour 3 véhicules sur un horizon de 5 jours). Nous proposons donc l'heuristique suivante. Considérons une journée particulière j et l'ensemble des tournées de cette journée. Les clients de cette journée ont déjà un certain nombre de classes sur les autres journées. Leur attribuer un nouvel horaire de passage au jour j permet soit de conserver le nombre de classes, soit de l'augmenter de 1 unité en cas d'incompatibilité. Pour chaque client, on peut facilement déterminer la ou les fenêtres horaires permettant de ne pas augmenter le nombre de classes. Trouver les meilleures tournées de la journée j consiste donc à résoudre un VRP en respectant des fenêtres horaires multiples et sans temps d'attente entre clients. Partant d'une solution donnée, une solution voisine peut être construite en effaçant une journée et en résolvant le VRP à fenêtres multiples associé