Confection de tournées de livraison dans un réseau urbain à l'aide de métaheuristiques et de méthodes de forage de données massives

La confection de tournées de livraison dans un réseau urbain est un problème qui peut faire appel à la recherche opérationnelle, au forage de données, à l'intelligence artificielle et à la géomatique, entre autres disciplines. Il s'agit de trouver une affectation des clients aux véhicules de livraison et un ordre de visite des clients pour chacun des véhicules afin d'optimiser une certaine fonction objectif. La considération d'une version dynamique du problème, où le processus d'optimisation doit aussi tenir compte de nouvelles données qui affluent en temps réel, rend la résolution encore plus complexe. De tels problèmes se retrouvent, par exemple, dans les entreprises qui offrent des services de livraison à domicile. Dans un contexte d'intégration, de globalisation et de compétitivité, ces entreprises se doivent de prendre les décisions menant aux meilleures tournées de livraison possibles. La recherche d'une solution optimale est souvent impossible pour des instances de taille réaliste. Afin d'obtenir de bonnes solutions dans des temps de calcul raisonnables, des approches heuristiques et métaheuristiques ont été proposées dans la littérature. Cependant, la majorité des travaux se basent sur des instances synthétiques qui, entre autres, négligent la topologie des réseaux routiers rencontrés dans la pratique. Cette thèse vise, dans un premier temps, à contribuer à l'intégration des méthodes de forage de données et d'apprentissage automatique dans la prédiction des vitesses de parcours dans un réseau routier réel. Grâce à la collaboration d'un partenaire industriel, nous disposons d'une base de données de points GPS recueillis dans la région métropolitaine de Montréal à partir de dispositifs embarqués dans des véhicules de livraison, couvrant une période de plus de deux ans. Nous proposons une méthode de prédiction des vitesses sur les arcs de ce réseau en faisant appel au forage de données massives et à l'apprentissage automatique : techniques de réduction de dimensionnalité, méthodes d'imputation et d'apprentissages supervisé et non supervisé. L'ensemble de cette méthodologie a fait l'objet d'un article, actuellement en révision, soumis à la revue scientifique EURO Journal on Transportation and Logistics. Cette thèse vise aussi à contribuer à l'avancement des métaheuristiques pour la résolution de problèmes de tournées de livraisons à domicile définies sur un réseau routier, avec des vitesses et temps de parcours qui dépendent du moment de la journée, des fenêtres de temps pour le service aux clients et une capacité maximale pour les véhicules. Plus précisément, nous proposons une recherche tabou qui remet en question l'ordre de visite des clients ainsi que le chemin utilisé dans le réseau routier pour se rendre d'un client à un autre, en fonction du moment de la journée. Un développement majeur de ce travail est la conception de techniques d'évaluation en temps constant de la réalisabilité ainsi que du coût approximatif des solutions dans le voisinage de la solution courante. Ces techniques permettent de réduire l'effort computationnel et de résoudre des instances avec 200 noeuds et 580 arcs dans des temps de calcul très raisonnables. L'approche de résolution incluant la description des techniques d'évaluation en temps constant de la réalisibilité des solutions dans le voisinage et de leurs coûts approximatifs a fait l'objet d'un article soumis à la revue scientifique Transportation Science. Enfin, la thèse s'attaque à une variante dynamique du problème précédent, dans un contexte où les vitesses sur les arcs du réseau routier varient de façon dynamique due à des incidents imprévus. Un simulateur a été développé pour générer les perturbations dynamiques aux vitesses sur les arcs, tout en respectant les relations spatio-temporelles entre ces derniers. Une procédure permet ensuite de réagir aux perturbations en modifiant la solution courante de façon plus ou moins importante selon l'importance des perturbations. La démarche développée pour résoudre ce problème dynamique de confection de tournées qui inclut l'ajustement à des plans de livraison déjà optimisés dans un contexte statique est présentée dans un article ayant été soumis à la revue scientifique European Journal of Operational Research.

Abstract

Fleet management for home deliveries in an urban context is at the crossroads between several disciplines such as operations research, data mining, artificial intelligence, geomatic, etc. The objective is to find 1) assignment of customers to vehicles and 2) sequence of customers visited by each vehicle to optimize a certain objective function. Since accurate travel time predictions are of foremost importance in urban environments, it is important to address dynamic variants of vehicle routing problems, because they better model the problems faced by transportation companies like home delivery services. In an era where companies have to integrate their supply chain, face globalization and competitiveness, it is important for them to make decisions leading to the best possible delivery routes. Therefore, in this thesis, we first consider the prediction of travel speeds using as input GPS traces of commercial vehicles collected over a significant period of time. We propose a forecasting framework based on machine learning and data mining techniques: dimensionality reduction techniques, imputation methods, unsupervised and supervised learning. Secondly, we propose a solution approach to solve a time-dependent vehicle routing problem with time windows in which travel speeds are defined on the road network itself. The solution approach involves a tabu search heuristic that considers different shortest paths between pairs of customers at different times of the day. A major contribution of this work is the development of techniques to evaluate the feasibility as well as the approximate cost of a solution in constant time, thus allowing the overall solution approach to handle instances with up to 200 nodes and 580 arcs in very reasonable computing times. Finally, we consider a dynamic vehicle routing problem motivated from home delivery applications that can adapt to changes in speeds by modifying the paths used in the road network to go from one customer to the next and by modifying the sequences of customers in the planned routes. Here, uncertainty comes from a single source, namely, the occurrence of new traffic information that affects speeds. To mimic real-time perturbations in the road network, we developed a simulator that generates traffic events and updates the speeds accordingly.