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

Xin ZHAO

Doctorant
(Statut lors de son départ du LGI2A)
Travaille dans les thèmes :

Revue Internationale avec Comité de Lecture

Xin ZHAO -- Gilles GONCALVES -- Rémy DUPAS
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, 11/2010

Conférence Internationale avec Comité de Lecture

Jie LI -- Xin ZHAO -- Gilles GONCALVES -- Rémy DUPAS
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, 12/2009
Xin ZHAO -- Gilles GONCALVES -- Rémy DUPAS
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, 07/2009
Xin ZHAO -- Gilles GONCALVES -- Rémy DUPAS
Dynamic vehicle routing problem with real-time time-dependent travel times
IEEE Intelligent Vehicles Symposium, IV'09, Xian, Chine, 3-5, 06/2009
Xin ZHAO -- Gilles GONCALVES -- Rémy DUPAS
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, 06/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, 03/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, 09/2007

Conférence Nationale avec Comité de Lecture

Xin ZHAO -- Gilles GONCALVES -- Rémy DUPAS
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, 02/2009
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, 02/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é.