Faculté des sciences de base SB, Section de mathématiques, Institut de mathématiques IMA (Chaire de recherche opérationnelle SO ROSO)

Sur la planification de tournées de véhicules scolaires

Spada, Michela ; Liebling, Thomas M. (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2004 ; no 3085.

Ajouter à la liste personnelle
    Summary
    The purpose of school bus services is to carry children from their homes to school and back. Scheduling and routing such services manually can be a long and tedious task, as it gives rise to complex combinatorial problems. To tackle those, we propose various heuristics in order to build good quality schedules of school bus routes for small and large size problems. The school bus routing and scheduling problem is modeled by introducing a performance measure corresponding to the service level provided to the children. This quality measure focusing on the children differs from previous approaches to the subject, in which the solution evaluation generally depends on the number of buses used or the lengths of the routes of the vehicles. In addition, our schedules allow the vehicles simultaneously to carry children going to different schools, which to our knowledge has only been treated once in the literature. Two problems are considered: one consisting in maximizing the average quality of children service level and another to maximize the quality of the worst service level provided to a child. These problems can be formulated as binary integer programs, but their size is too large to consider an exact resolution with current software and computers. A constructive method is proposed to obtain a feasible schedule which is optimized thereafter with various heuristics: simulated annealing, tabu search and variable neighborhood search. Let us note that, during optimization, the use of schedules violating the vehicle capacity is authorized. The heuristics employed, in their variant exploring infeasible solution set, are more effective than those that are confined to the feasible solution set. These methods also yield much higher quality schedules for real data sets than those actually used by the schools in question. An ideal schedule should allow to simultaneously optimize both objective functions mentioned above. In order to approach such a solution, a two phase method is proposed. The first phase consists in maximizing the minimum service level and the second in maximizing the average service level without reducing the minimum obtained during the first phase. We also developed an extension of our methods based on decomposition adapted to large scale problems. The proposed decomposition approach allows to considerably reduce computing time without giving up quality and is essential in order to solve problems with a large number of children. Let us finally note that a graphical user interface was developed, allowing to visualize, analyze and modify schedules generated by the heuristics. It is thus possible to integrate additional constraints that have not been modeled, or to adapt a solution in case of a small modification to the problem data.
    Résumé
    Un service de bus scolaires a pour objectif d'emmener des enfants de la maison à l'école et vice versa. L'organisation et la planification d'un tel service s'avèrent longues et fastidieuses si elles sont effectuées manuellement. Afin d'apporter une solution à ce problème combinatoire complexe, diverses heuristiques permettant de construire des planifications de tournées de véhicules scolaires de bonne qualité pour des problèmes de petite et de grande taille sont proposées dans ce travail. Nous avons modélisé le problème de la planification de tournées de véhicules scolaires en introduisant une mesure de performance correspondant au niveau de service fourni aux enfants. Cette mesure de qualité centrée sur les enfants se démarque des précédents travaux sur le sujet, dans lesquels l'évaluation d'une solution dépend généralement du nombre de bus utilisés ou des longueurs des trajets effectués par les véhicules. Par ailleurs, nos planifications permettent à un véhicule de transporter simultanément des enfants devant se rendre en des écoles différentes, ce qui à notre connaissance n'a été envisagé qu'une seule fois dans la littérature. Deux problèmes ont été considérés dans ce travail, l'un consistant à maximiser la qualité de service moyenne des enfants et l'autre à maximiser la qualité du plus mauvais niveau de service fourni. Ces problèmes se laissent exprimer sous la forme de programmes linéaires à variables binaires, mais leur taille est bien trop importante pour envisager une résolution exacte à l'aide des logiciels et machines actuels. Une méthode constructive est proposée pour l'obtention d'une planification admissible qui, par la suite, est optimisée à l'aide de diverses heuristiques : le recuit simulé, la recherche tabou et la recherche à voisinage variable. Notons qu'au cours de l'optimisation, la visite de planifications violant la capacité des véhicules est autorisée. Nos heuristiques, dans leur variante explorant le domaine des solutions non admissibles, s'avèrent plus efficaces que celles se limitant au domaine admissible. Ces méthodes nous ont également permis de produire, pour des instances réelles, des planifications de bien meilleure qualité que celles effectivement utilisées par les écoles en question. Une planification idéale devrait permettre d'optimiser les deux fonctions objectif mentionnées ci-dessus. Afin de s'approcher d'une telle solution, une méthode à deux phases est proposée, la première consistant à maximiser le minimum des niveaux de service et la seconde à maximiser le niveau de service moyen sans réduire le minimum obtenu durant la première phase. Par ailleurs, une extension de nos méthodes adaptée à la gestion des problèmes de grande taille a également été développée. L'approche par décomposition proposée permet de réduire considérablement les temps de calcul sans détériorer la qualité des planifications et se révèle indispensable pour la résolution de problèmes où le nombre d'enfants à transporter est important. Notons finalement qu'une interface utilisateur a été développée. Elle permet de visualiser, d'analyser et de modifier les planifications générées par nos heuristiques. Il est ainsi possible d'intégrer des contraintes supplémentaires non modélisées ou d'adapter une solution en cas de modification légère des données du problème.