Efficient approaches for large-scale time-dependent route planning problems with traveler's preference
Approches efficaces pour la résolution de problèmes de planification d'itinéraires à grande échelle dépendant du temps incluant les préférences des voyageurs
Abstract
Time-dependent route planning in real-world networks is still a big challenge today. In addition, travelers may have multi-preferences such as travel time, beautiful scenery, safety, and low carbon, simultaneously. With the development of infrastructures and the advancement of information technology, various spatio-temporal data that record the interactions between humans and the cyber-physical world can be collected and used to design traveler's preference-driven route planning. However, most of research focuses on finding the shortest path in a time-dependent network. In particular, 1) some works focus on optimizing the total traveler's preference score, but only propose a non-linear model that cannot be efficiently addressed; 2) few works investigate multi-objective time-dependent route planning problems, in which traveler preference score is assumed to be unvarying. However, traveler preference can vary with time; 3) recent works study group-oriented route planning problems, but consider the travel time and traveler preference to be time-unvarying. To reduce theory and practice gaps, three new time-dependent route planning problems with traveler's preference (TRPPs-TP) are investigated in this thesis.Firstly, a single-objective TRPP-TP is investigated in that the preference score on road segments is assumed to be time-dependent. The objective is to maximize the total preference score. For the problem, an integer linear programming model is proposed, and the NP-hard complexity of the problem is analyzed. To address the problem efficiently, a novel two-phase method is developed. Numerical experiments on randomly generated road networks and real-world road networks demonstrate the superiority of the developed method.Secondly, a bi-objective TRPP-TP with the time-dependent preference score is studied. The first objective is to maximize the total preference score, and the second one is to minimize the total travel time. For the problem, an integer linear programming model is formulated. For the problem, an exact epsilon-constraint method is applied to find the Pareto front on small-sized instances. To handle large-sized instances, an efficient problem-specific non-dominated sorting genetic algorithm-II (NSGA-II) is developed. Especially, a new region-based coding is designed and a feasible route condition is provided to find near-optimal solutions in a reasonable computation time. Experiments on randomly generated road networks and real-world road networks demonstrate the performance of the proposed NSGA-II.Finally, a bi-objective eco-friendly group-oriented TRPP-TP is addressed. The first objective is to maximize the total traveler preference score and the second one is to minimize the total CO2 emissions. For this problem, a new integer linear programming model is proposed, and an epsilon-constraint method is used. Numerical experiments on randomly generated road networks are conducted to find the best balancing solutions.
La planification d'itinéraires en fonction du temps dans les réseaux du monde réel reste aujourd'hui un défi majeur. De plus, les voyageurs peuvent avoir simultanément de multiples préférences telles que le temps de trajet, la beauté des paysages, la sécurité et les faibles émissions de carbone. Avec le développement des infrastructures et les progrès des technologies de l'information, diverses données spatio-temporelles qui enregistrent les interactions entre les humains et le monde cyber-physique peuvent être collectées et utilisées pour concevoir la planification d'itinéraires en fonction des préférences des voyageurs. Cependant, la plupart des recherches se concentrent sur la recherche du chemin le plus court dans un réseau dépendant du temps. En particulier, 1) certains travaux se concentrent sur l'optimisation du score de préférence total du voyageur, mais proposent uniquement un modèle non linéaire qui ne peut être abordé efficacement ; 2) peu de travaux étudient les problèmes de planification d'itinéraires multi-objectifs dépendant du temps, dans lesquels le score de préférence du voyageur est supposé in- changé. Cependant, les préférences du voyageur peuvent varier avec le temps ; 3) des travaux récents étudient les problèmes de planification d'itinéraires axés sur les groupes, mais considèrent que le temps de trajet et les préférences des voyageurs ne varient pas dans le temps. Afin de réduire les écarts entre la théorie et la pratique, trois nouveaux problèmes de planification d'itinéraires dépendant du temps en prenant compte des préférences du voyageur (TRPPs-TP) sont étudiés dans cette thèse.Premièrement, un TRPP-TP à objectif unique est étudié dans la mesure où le score de préférence sur les segments routiers est supposé dépendre du temps. L'objectif est de maximiser le score de préférence total. Pour le problème, un modèle de programmation linéaire en nombres entiers est proposé et la complexité NP-difficile du problème est analysée. Pour résoudre le problème efficacement, une nouvelle méthode en deux phases est développée. Des expériences numériques sur des réseaux routiers générés aléatoirement et sur des réseaux routiers réels démontrent la supériorité de la méthode développée.Deuxièmement, un TRPP-TP bi-objectif avec un score de préférence dépendant du temps est étudié. Le premier objectif est de maximiser le score de préférence total, et le second est de minimiser le temps de trajet total. Pour résoudre ce problème, un modèle de programmation linéaire en nombres entiers est formulé. Pour résoudre le problème, une méthode de epsilon-contrainte exacte est appliquée pour trouver le front de Pareto sur des instances de petite taille. Pour gérer des instances de grande taille, un algorithme génétique de tri non dominé spécifique à un problème-II (NSGA-II) est développé. En particulier, un nouveau codage basé sur la région est conçu et une condition d'itinéraire réalisable est fournie pour trouver des solutions quasi optimales dans un temps de calcul raisonnable. Des expériences sur des réseaux routiers générés aléatoirement et sur des réseaux routiers réels démontrent les performances du NSGA-II proposé.Enfin, un TRPP-TP bi-objectif éco-responsable et orienté groupe est abordé. Le premier objec- tif est de maximiser le score total de préférence des voyageurs et le second est de minimiser les émissions totales de CO2. Pour ce problème, un nouveau modèle de programmation linéaire en nombres entiers est proposé, et une méthode de epsilon-contrainte est utilisée. Des expérimentations numériques sur des réseaux routiers générés aléatoirement sont menées afin de trouver les meilleures solutions d'équilibrage.