Workload Equity in Vehicle Routing Problems Over Multiple Periods

Dans les problèmes de tournées de véhicules, la minimisation des coûts est rarement le seul objectif à considérer. D'autres objectifs doivent également être pris en compte dans la pratique, tel le partage équitable de la charge de travail entre les chauffeurs (équité, balancement des routes). On sait que la minimisation des coûts est susceptible de mener à des solutions où la charge de travail n'est pas distribuée équitablement. Autrement dit, des coûts additionnels doivent être encourus pour obtenir des solutions équitables. Il arrive souvent en pratique que l'équité doive être atteinte sur un certain nombre de périodes (e.g., journées) et non à chaque période. Dans ce mémoire, un problème de tournées de véhicules multi-périodes avec un objectif visant l'équité sur l'ensemble des périodes est résolu à l'aide d'une méthode en deux phases. Dans la première phase, une solution de distance minimale est produite pour le problème de tournées de véhicules associé à chaque période. Les routes ainsi obtenues sont ensuite distribuées entre les chauffeurs dans la seconde phase afin d'atteindre l'équité au niveau de la distance totale parcourue par chacun des chauffeurs sur l'ensemble des périodes. Une étude expérimentale démontre les bénéfices de cette approche sur des instances tests dérivées d'instances classiques pour le problème de tournées de véhicules avec contraintes de capacité. Les résultats démontrent en particulier que l'équité entre les chauffeurs peut être atteinte sans coût additionnel si le nombre de périodes est suffisamment grand.

Abstract

In vehicle routing problems, cost minimization is rarely the only concern. There are other objectives that must be taken into account. One of these objectives is a fair distribution of the workload among drivers (equity, balance). It is known that minimizing operations costs is prone to lead to poorly balanced solutions, which means that better-balanced solutions lead to additional operations costs. In many real life problems, equity must be achieved over a certain number of periods (e.g., days), not within each period. In this thesis, a multi-period vehicle routing problem with an equity objective is addressed with a two-phase problem-solving methodology. In the first phase, a minimum-distance solution is produced for each period. The routes obtained are then combined in a second phase to achieve equity among drivers with regard to their total distance traveled over all periods. A computational study shows the benefits of this two-phase algorithm, based on instances derived from standard benchmark instances for the capacitated vehicle routing problem. The results show in particular that workload equity can be attained at no additional operations cost when the number of periods is sufficiently large.