A New Approach to the Bus Driver Scheduling Problem Using Multiobjective Genetic Algorithms

Abstract

Nesta tese é apresentada uma abordagem multiobjectivo baseada em algoritmos genéticos para o problema de geração de serviços de motoristas em empresas de transporte colectivo de passageiros. A elaboração dos serviços dos motoristas é uma etapa de extrema importância no planeamento operacional de transportes colectivos, que consiste na definição dos serviços diários dos motoristas por forma a garantir a realização das viagens planeadas para um conjunto de viaturas. Este é um processo complexo, que envolve diversos objectivos, frequentemente conflituosos, tais como custos, qualidade do serviço prestado e satisfação das expectativas dos motoristas. Efectuou-se uma análise detalhada do processo de decisão dos planeadores para a avaliação da qualidade de um horário de serviços. Como resultado desta análise, os principais objectivos e restrições envolvidos neste processo foram identificados.

Por forma a considerar este objectivos simultâneos e conflituosos, propõe-se uma abordagem multiobjectivo baseada em algoritmos genéticos. Dois algoritmos genéticos são considerados, baseados em dois modelos multiobjectivo: o modelo Agregado e o modelo Não Dominado. No modelo Agregado, os objectivos são agrupados numa única função objectivo de acordo com uma função de ponderação apropriada. O modelo Não Dominado utiliza o conceito de solução de Pareto para a ordenação das soluções, tendo sido desenvolvido um novo procedimento de atribuição de fitness. Ambos os algoritmos utilizam o mesmo conjunto de operadores especializados de cruzamento e mutação.

Os algoritmos genéticos encontram-se integrados numa aplicação, GenT, na qual foi dada particular atenção à interacção com o planeador. Esta aplicação, amigável e flexível, permite a um utilizador com experiência e conhecimento do problema produzir e analisar as soluções mais adequadas ao seu problem. A aplicação GenT é inteiramente compatível com o sistema GIST, um sistema de apoio à decisão actualmente em operação em várias empresa de transporte colectivo.

A nova abordagem foi testada num conjunto de problemas reais de três empresas portuguesas e as soluções obtidas foram comparadas com as soluções actualmente implementadas nessas empresas. Os dois algoritmos genéticos produziram várias soluções alternativas competitivas num período de tempo consideravement curto.

A abordagem multiobjectivo proposta nesta tese mostrou-se extremamente útil no apoio à decisão simulação de cenários alternativos em operações quotidianas de planeamento de serviços, assim como na a em horizontes de médio prazo.

Alternate abstract:

This thesis proposes a new approach for the bus driver scheduling problem (BDSP) using multiobjective genetic algorithms (GAS). Bus driver scheduling is a critical stage of the operational planning process in mass transit companies. It consists in constructing a set of legal duties that together cover all the trips planned for a group of vehicles. This is a complex process guided by several, often conflicting objectives, involving costs, quality of service and the satisfaction of the drivers' expectations.

A comprehensive analysis of the decision process and of the drivers' schedule evaluation process was performed. As a result of this analysis, the main objectives and constraints involved in this process have been identified.

In order to tackle those conflicting objectives, a multiobjective approach based on GAS is provided. Two new GAs are proposed, based on two different multiobjective models: the Aggregate (Agg) model and the Non-Dominated (ND) model. In the Agg model all the objectives are merged into a single obj ctive function according to an appropriate weighting function. The ND model uses the concept of Pareto dominance to rank the solutions and a new fitness assignment procedure has been designed. Both models use the same set of knowledge based crossover and mutation operators.

The GAS are integrated in a new software application, GenT, in which particular attention has been given to the interaction with the planner. GenT is a friendly, interactive and flexible software tool that enables planners with knowledge and experience to produce and select the most appropriate solution to their problems. GenT is fully compatible with GIST, a decision support system for the operational planning process currently in use by several companies.

The approach has been tested on a collection of real problem instances from three Portuguese companies and the solutions obtained have been compared with the solutions currently implemented in those companies. Both GAs have been able to consistently provide a set of competitive alternative solutions in a rather short period of time.

The new multiobjective approach proposed in this thesis has proved to be valuable and powerful in supporting decision making for short-term (daily) operations, as well as in the simulation of alternative operating scenarios in a medium-term horizon.

Alternate abstract:

Cette thèse propose une nouvelle approche pour le problème de la génération d'horaires des chaffeurs d'autobus, en employant des algorithmes génétiques multiobjective. La génération des horaires des chauffeurs est une étape critique du processus de planification des opérations aux compagnies de transport en commun. Elle consiste à la construction des services quotidiens des chauffeurs couvrant les voyages faits par un certain ensemble de véhicules.

Établir un horaire de chauffeurs est un processus complexe guidé par plusieurs objectifs, souvent conflitueux, qui comprennent les coûts d'opération, la qualité des services et la satisfaction des expectatives des chauffeurs.

Une analyse exhaustive du processus décisionnel et de l'évaluation des horaires de chauffeurs a été effectuée. De cette analyse, on a pu identifier les principaux objectifs et contraints.

Ave le bût de considérer ces objectifs contradictoires, une approche multiobjective basée sur des algorithmes génétiques a été développée. On propose deux nouveaux algorithmes génétiques, basés sur deux modèles multiobjective différents: le modèle Agrégée (Agg) et le modèle Non-Dominé (ND). Dans le modèle Agg tous les objectifs sont groupés dans une seule fonction objectif selon une fonction de pondération appropriée. Le modèle ND emploie le concept de la dominance de Pareto pour ranger les solutions et un nouveau procédé de "fitness assignment" a été conçu. Les deux algorithmes emploient le même ensemble d'opérateurs de croisement et de mutation.

Les algorithmes génétiques sont intégrés dans une nouvelle application de logiciel, GenT, dans laquelle une attention particulière a été donnée à l'interaction avec le planificateur. GenT est un outil amical, interactif et flexible qui permet à des planificateurs expérimentés produire et choisir la solution la plus appropriée à leurs problèmes. GenT est entièrement compatible avec GIST, un système d'aide à la décision pour le processus de planification opérationnel actuellement en service par plusieurs compagnies.

L'approche a été examinée sur un ensemble d'exemples réels de problèmes de trois compagnies portugaises et les solutions obtenues ont été comparées aux solutions actuellement mises en application à ces compagnies. Les deux algorithmes génétiques ont pu fournir un ensemble de solutions concurrentielles dans une période assez courte.

La nouvelle approche multiobjective proposée dans cette thèse s'est avérée très utile, dans l'aide à la décision pour des opérations (quotidiennes) à court terme aussi bien que dans la simulation des scénarios alternatifs de changes de fonctionnement dans l'horizon à moyen terme.