Optimisation de tournées de service en temps réel

Je tiens tout d'abord à remercier Frédéric Semet, mon co-directeur de thèse, pour la confiance qu'il m'a accordée en me proposant cette thèse il y a trois ans, pour le soutien qu'il a su me fournir, pour tous ses conseils qui m'ont beaucoup aidé et appris, d'un point de vue scientifique comme d'un point de vue méthodologie de travail et autonomie.Merci pour toutes les discussions très intéressantes que nous avons eu et pour son soutien financier en fin de thèse.Enfin, je le remercie vivement pour les repas partagés à chacun de mes retours de Montréal, pour sa sympathie et son aptitude à ménager mes humeurs.Je tiens également à remercier Michel Gendreau, mon directeur de thèse, pour sa confiance et pour tout ce qu'il m'a apporté, à savoir son expertise dans le domaine du stochastique, sa connaissance étendue de la littérature, et ses conseils avisés.Il m'a également beaucoup apporté d'un point de vue culturel, en m'accueillant bras ouverts à Montréal, et en me donnant de bonnes adresses et de bons conseils sur place.Un grand merci de m'avoir donné la possibilité de participer à des conférences, même si, pour certaines, je n'y ai participé que par procuration, à mon grand regret.Enfin, merci de m'avoir offert l'opportunité d'encadrer des travaux dirigés à l'Ecole Polytechnique de Montréal.J'ai ainsi pu me rendre compte que la sévérité dans la notation française n'avait pas lieu d'être au Canada.Je tiens aussi à remercier Nicolaï Christov, mon directeur de thèse, qui m'a permis d'effectuer cette thèse et m'a offert son soutien dès le début, alors même qu'il ne me connaissait pas.Il m'a, entre autres, beaucoup assisté dans de nombreuses démarches administratives rendues compliquées par ma cotutelle de thèse.Il a toujours répondu présent et je l'en remercie.Je tiens également à remercier Pierre Dejax, mon deuxième co-directeur de thèse, mais qui pour des raisons administratives, n'a pu apparaître qu'en tant que membre invité dans ce manuscrit alors qu'il mérite largement sa place de co-directeur.En effet, ce projet provient de lui et je n'aurais donc pas pu travailler sur ce sujet sans lui.De plus, il m'a apporté un oeil industriel sur la problématique, m'a fourni de précieux conseils et a toujours répondu à mes demandes de correction/relecture dans les temps impartis, même quand les délais impartis étaient serrés.Un grand merci à Daniele Vigo et François Louveaux, mes rapporteurs, pour leur relecture consciencieuse de mon manuscrit et leur rapports constructifs.Un grand merci également à Louis-Martin Rousseau, examinateur, d'avoir accepté de juger mon travail et de suivre ma soutenance de thèse par visioconférence (ce qui ne fut pas sans quelques difficultés).Merci aussi à Dominique Feillet, examinateur et directeur du jury, d'avoir accepté de juger mon travail et de présider mon jury de soutenance.Merci à tous ces membres de mon jury vi pour leurs questions après ma soutenance, qui m'ont permis d'entrevoir d'autres perspectives futures sur mon travail.Je remercie également les équipes des deux laboratoires (LAGIS et CIRRELT) au sein desquels j'ai pu séjourner durant ma thèse.Je tiens à remercier tout particulièrement Serge Bisaillon du CIRRELT pour son aide et son soutien face aux multiples problèmes informatiques auxquels j'ai été confrontée.Il a toujours répondu présent et m'a permis de résoudre un nombre de problèmes incalculable.Merci à lui pour tout le temps qu'il a su me consacrer et pour ses précieux conseils.Je tiens également à remercier Daniel Charbonneau du CIRRELT, pour son aide dans mon apprentissage de Linux.Je suis arrivée au CIRRELT, n'ayant jamais travaillé sous linux et j'utilise à présent beaucoup plus la console de commandes grâce à tout ce qu'il m'a appris et à tous ses conseils.Un grand merci à Lucie-Nathalie Cournoyer pour sa sympathie et son accueil, ainsi qu'à toute l'équipe du CIRRELT.Je voudrais également remercier tout particulièrement Patrick Gallais du LAGIS pour son aide lors des problèmes d'ordinateur ou de disque dur rencontrés vers la fin de ma thèse.Il a su se montrer d'une grande aide, disponible et efficace et je l'en remercie.Un grand merci à Christine Yvoz et Brigitte Foncez du LAGIS pour leur aide dans de nombreuses démarches administratives et pour leur sympathie.Je tiens également à adresser un remerciement spécial à Bernard Szukala pour ses blagues, son humour, sa bonne humeur et nos nombreuses discussions fort sympathiques au laboratoire.Un grand merci à Mireille pour sa sympathie, ses gâteaux, ses dessins, son sourire et son soutien sans faille.Un grand merci enfin à toutes les personnes du troisième étage du bâtiment C pour leur sympathie et leur sourire.Enfin, j'adresse un remerciement spécial à Thomas Bourdeaud'huy pour m'avoir supportée comme co-bureau durant la deuxième partie de ma thèse.Mes remerciements vont aussi à ma famille et mes amis.Un grand merci à mes parents et mes grand-parents, sans qui je n'en serai pas là aujourd'hui, qui m'ont soutenu avec affection durant ma thèse et qui se sont déplacés pour assister à ma soutenance de thèse.Un grand merci à mes soeurs pour leur soutien sans faille (en particulier lors du problème avec mon disque dur) et pour les super moments de bonheur qu'elles ont su m'offrir durant ma thèse.Merci beaucoup à la famille Thirion, qui a toujours répondu présente et qui m'a soutenue en m'offrant toute son affection ainsi que des moments de pur bonheur durant ces trois années de thèse.Ils sont également venus assister à ma soutenance de thèse (de Nancy et même de Mulhouse), pour mon plus grand bonheur.Un merci tout particulier à Solange Henry pour sa patience d'ange à relire mon manuscrit minutieusement et pour toute son affection et pour son soutien durant ma thèse.Enfin, je remercie également mes amis pour leur compréhension face à ma faible disponibilité durant ma thèse et pour les bons moments passés en leur compagnie.Je remercie également celles et ceux qui ont pu se libérer et venir assister à ma vii soutenance de thèse.Enfin, je tiens à adresser un remerciement tout particulier à mon fiancé, Vincent Thirion, pour le soutien indéfectible qu'il m'a apporté tout au long de ma thèse.A chacun de mes moments de doute (et ils ont été nombreux), il a répondu présent et a su trouver les mots justes pour me redonner la motivation nécessaire.Vincent m'a également donné de précieux conseils tout au long de cette thèse et a supporté toutes mes présentations blanches et relu tous mes documents.Il a su également me supporter durant ces trois années difficiles et a su faire des sacrifices sur certains week-ends, vacances et autres (en se montrant très compréhensif).Plus que tout, il m'a fait passer avant sa vie professionnelle, en quittant un CDD qui le passionnait pour m'accompagner au Canada, en acceptant de rester au Canada avec moi alors qu'il n'avait pas de travail là-bas (pour cause de visa) et en acceptant de prendre un poste à son retour en France dans un tout autre domaine que celui qu'il souhaitait, en attendant la fin de ma thèse.Autant dire que Vincent a fait preuve d'une grande patience et d'un amour sans faille.C'est pour toutes ces raisons que je lui dédie ce manuscrit de thèse et le travail de ces trois dernières années.viii R ÉSUM ÉLes tournées de service concernent l'organisation de déplacement de personnels vers des clients afin d'effectuer différentes activités techniques ou commerciales.Ces tournées peuvent devoir répondre à des objectifs et faire face à des contraintes nombreuses et complexes.Lors de la planification et de l'exécution de tournées de service mono-période, les entreprises sont confrontées aux aléas des temps de service et de parcours.C'est pourquoi, dans cette thèse, nous nous intéressons à une variante du problème de tournées de service, dans laquelle les temps de parcours et de service sont stochastiques.Il s'agit du problème de tournées de service multi-dépôt, incluant fenêtres de temps, temps de service et de parcours stochastiques avec priorité entre les clients (distinction clients obligatoires / clients optionnels).Afin de résoudre cette problématique, nous proposons trois méthodes différentes.Dans la première méthode, nous construisons d'abord des routes contenant uniquement des clients obligatoires puis nous procédons à l'insertion des clients optionnels.La deuxième méthode est une méthode approchée basée sur la génération de colonnes consistant à générer un ensemble de routes de bonne qualité pour chaque véhicule puis à en sélectionner une par véhicule.La dernière méthode est un algorithme de branch and price basé sur la deuxième méthode.Le sous-problème consiste à générer des routes réalisables pour un véhicule donné, tandis que le problème maître permet de sélectionner des routes en s'assurant que la priorité des clients est respectée.Après chacune de ces méthodes, afin d'évaluer la qualité de ces solutions face aux aléas, nous utilisons un algorithme de programmation dynamique et procédons à un ensemble de simulations du déroulement des tournées en temps réel.Nous avons testé ces méthodes sur des problèmes dont les données sont issues du milieu industriel.Mots-clés : Tournées de véhicules, multi-dépôt, fenêtres de temps, temps de service stochastiques, temps de parcours stochastiques, priorité entre les clients ix

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.