prise de décision dynamique en cas d'incertitude dans l'acheminement des véhicules et la logistique
2020
Cette these presente trois etudes menees sur des problemes de tournees dynamiques. En particuliere, elle se concentre sur les challenges resultants de l'utilisation de vehicules electriques dans les systemes logistiques et de transports. Dans la premiere etude, nous introduisons le probleme de tournees de vehicules electriques avec des bornes de recharge publiques et privees. Dans ce contexte, les vehicules peuvent recharger leurs batteries en route, dans des bornes publiques, ainsi qu'au depot (bornes privees). Pour se proteger contre l'incertitude de la disponibilite des bornes publiques, nous presentons des politiques de routage qui anticipent la dynamique des files d'attente des bornes. Nos politiques se basent sur une decomposition du probleme en deux phases : routage et planification des operations de recharge. Grâce a cette decomposition, nous obtenons la politique statique optimale, ainsi qu'un certain nombre de politiques dites « anticipatoires » et une borne inferieure. Des tests numeriques effectues sur des instances reelles fournies par une entreprise, monter que nos politiques sont capables de livrer des solutions avec un gap d'optimalite de moins de 5%. Nos tests montrent aussi que permettre aux vehicules de charger en dehors du depot (meme en presence d'incertitude sur la disponibilite des bornes) se traduit par des economies considerables dans la duree des routes. Dans la deuxieme etude, nous considerons le probleme d'un operateur controlant une flotte de vehicules de tourisme avec chauffeur (VTCs) electriques. L'operateur, qui cherche a maximiser ses revenus, doit affecter les vehicules aux demandes au fur et a mesure de leur apparition ainsi que charger et repositionner les vehicules en prevision des demandes futures. Pour attaquer ce probleme, nous utilisons des approches basees sur l'apprentissage par renforcement profond. Pour mesurer la qualite de nos approches, nous avons developpe aussi une heuristique proche de celle typiquement utilisee dans l'affectation de taxis, ainsi que des bornes superieures. Nous testons nos approches dans des instances construites a partir de donnees reelles de l'ile de Manhattan. Nos tests montrent que notre meilleure politique basee sur l'apprentissage profond livre des resultats superieurs a ceux livres par l'heuristique. Les tests montrent aussi que cette strategie passe facilement a l'echelle et peut etre deployee sur de plus grandes instances sans entrainement supplementaire. La derniere etude introduit une nouvelle approche generique pour modeliser des problemes d'optimisation dynamique sous la forme de jeux video de type Atari. L'objectif est de les rendre abordables a travers de methodes de solution issus de communaute d'apprentissage par renforcement profond. L'approche est flexible et applicable a un large eventail de problemes. Pour illustrer son application, nous nous attaquons a un probleme bien etablie dans la litterature : le probleme de tournees de vehicules avec des requetes de service stochastiques. Nos resultats preliminaires sur ce probleme sont tres encourageants et montrent que « l'Atari-fication » peut etre la voie pour resoudre des problemes d'optimisation dynamique qui s'averent difficiles pour les approches basees sur les outils classiques de la recherche operationnelle. Le dernier chapitre presente deux logiciels developpees pour supporter nos recherches. Le premier, VRP-REP Mapper, est un outil web pour visualiser et analyser des solutions pour les problemes de tournees de vehicules. Cette outil a ete integre a www.vrp-rep.org, la plateforme de reference pour le partage de donnees scientifiques dans le domaine. Le deuxieme outil, nomme frvcpy, permet de determiner l'insertion optimal des operations de recharge dans une tournee predeterminee. Ce logiciel et son code source, presente comme une bibliotheque Python, a ete mis a disposition de la communaute scientifique.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI