Laboratoire de Génie Informatique et d’Automatique de l’Artois

Xin ZHAO

Doctorant
(Statut lors de son départ du LGI2A)
Membre des axes :
A dynamic vehicle routing problem based on real-time traffic information
International Journal of Innovative Computing and Applications, IJICA, pp 215 - 225, Vol. 2, No. 4, Inderscience Publishers, novembre 2010
A real-time intelligent routing planning solved by genetic algorithm
International Conference on Computational Intelligence and Software Engineering, CiSE 2009, Wuhan, Chine, 11-13 Dec. 2009, décembre 2009
On-line genetic algorithm for the dynamic vehicle routing problem with real-time time-dependent travel times
39th International Conference on Computers & Industrial Engineering, CIE 2009, Troyes, France, 6-9, juillet 2009
Dynamic vehicle routing problem with real-time time-dependent travel times
IEEE Intelligent Vehicles Symposium, IV'09, Xian, Chine, 3-5, juin 2009
Un problème de tournées de véhicules temps réel avec temps de parcours variables
10 ème conférence de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, ROADEF 2009, Nancy, France, 10-12, février 2009
A Genetic Approach to Solving the Vehicle Routing Problem with Time-Dependent Travel Times
16th IEEE Mediterranean Conference on Control and Automation, MED'08, pp 413 - 418, Ajaccio , FRANCE, juin 2008
Un problème de tournées de véhicules avec temps de trajet dépendant du temps
7ème Conférence Internationale de Modélisation et Simulation, MOSIM'08, Paris, France, mars 2008
2007
Conférence Internationale avec Comité de Lecture
Repairman routing problem with time-dependent travel times
International Conference on Artificial Intelligence and Systems, AIS'07/CAD07, Divnomorskoe, 2-10 September, Russie, septembre 2007
Tournées du réparateur avec temps de trajet dépendant du temps
Conférence conjointe FRANCORO V /ROADEF 2007, ROADEF 2007, Grenoble, France, 20 au 23 février 2007, février 2007

Auteur de la thèse intitulée "Une méthode génétique pour la résolution du problème dynamique de routage de véhicules avec temps de parcours variables"

2004 - 2008

Le problème de tournées de véhicules (PTV ou VRP pour Vehicle Routing Problem) est un problème rencontré en logistique qui se situe à un niveau important : la planification opérationnelle qui concerne l’optimisation d’une flotte de véhicules. C’est un nom générique pour désigner une classe de problèmes dans laquelle un certain nombre de clients doit être visité par un certain nombre de véhicules. Les tournées de véhicules doivent être organisées de façon à équilibrer ou à optimiser un certain nombre de critères tels que la distance totale parcourue, le nombre de véhicules utilisés et les temps d’attente des clients.

Le PTV est l’un des problèmes les plus populaires et donc les plus étudiés de la communauté Recherche Opérationnelle. Il y a de nombreuses variantes de ce problème intégrant une ou plusieurs des contraintes suivantes : capacité des véhicules, fenêtres de temps pour visiter les clients, etc. Le VRP permet de modéliser de nombreux types d’applications. Les exemples peuvent concerner la conception, la reconfiguration d’un réseau de transport, ainsi que la gestion quotidienne de la collecte et de la livraison de marchandises, organisation des services de messageries ou de soins à domicile.

La majorité des études effectuées sur le VRP suppose que les données sont parfaitement connues et disponibles au moment où l’on effectue la planification des tournées. Dans la réalité, nous avons beaucoup de causes externes qui peuvent remettre en question cette hypothèse : congestions du réseau routier, pannes de véhicule, arrivées de nouveaux clients, etc.

Dans nos travaux, nous nous sommes placés dans un cadre dit dynamique c’est-à-dire que nous considérons que des informations nouvelles vont apparaître au cours du temps et influer sur la planification en cours. Les problèmes de décision en temps réel jouent un rôle de plus en plus important car les technologies de communication et d’information permettent aujourd’hui d’obtenir et de traiter rapidement l’information en temps réel. Par conséquent, nous traitons plus précisément le problème de l’élaboration dynamique de tournées de véhicules avec fenêtres de temps (DVRPTW) et le problème de la tournée du réparateur partiellement dynamique (PDTRP) où la prise en compte de nouveaux clients en cours de l’exécution des tournées est possible. De plus, dans une résolution classique de ce problème, les valeurs moyennes issues d’historiques sont généralement considérées pour déterminer le temps de trajet entre deux clients. On suppose généralement qu’elles ne sont pas sujettes à des variations stochastiques, la vitesse est considérée constante pour toute la journée.

Dans une première approche, nous considérons des profils de vitesse basés sur des temps de trajet moyens qui varient selon la période de temps (matin, midi, après midi) pour tenir compte de l’évolution du trafic routier. En fonction du type de connexion entre les deux clients, plusieurs profils peuvent être considérés. Dans une seconde approche, nous intégrons des informations trafic obtenues en temps réel pour modifier le profil de vitesse par rapport aux aléas du réseau routier (congestions, etc.). Nous adoptons un lissage exponentiel amélioré pour prévoir le temps de trajet en fonction des vitesses mesurées sur le parcours considéré.