Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la for��t vers les usines, de nombreux ��v��nements impr��vus peuvent se produire, ��v��nements qui perturbent les trajets pr��vus (par exemple, en raison des conditions m��t��o, des feux de for��t, de la pr��sence de nouveaux chargements, etc.). Lorsque de tels ��v��nements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit ��tre d��tourn�� vers un chemin alternatif. En l���absence d���informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-m��me "ferm��" suite �� un ��v��nement impr��vu. Il est donc essentiel de fournir aux chauffeurs des informations en temps r��el, en particulier des suggestions de chemins alternatifs lorsqu���une route pr��vue s���av��re impraticable. Les possibilit��s de recours en cas d���impr��vus d��pendent des caract��ristiques de la cha��ne logistique ��tudi��e comme la pr��sence de camions auto-chargeurs et la politique de gestion du transport. Nous pr��sentons trois articles traitant de contextes d���application diff��rents ainsi que des mod��les et des m��thodes de r��solution adapt��s �� chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l���ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent ��tre faits pour minimiser les changements apport��s au plan initial. Bien que la flotte de camions soit homog��ne, il y a un ordre de priorit�� des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est ��galement une priorit��. ��tant donn�� que les cons��quences des ��v��nements impr��vus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l���approche propos��e traite d���abord l���annulation et le retard d���un seul voyage, puis elle est g��n��ralis��e pour traiter des ��v��nements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impact��s durant la m��me semaine de telle sorte qu���une chargeuse soit libre au moment de l���arriv��e du camion �� la fois au site forestier et �� l���usine. De cette fa��on, les voyages des autres camions ne seront pas mo- difi��s. Cette approche fournit aux r��partiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient ��tre obtenues si le r��partiteur ��tait autoris�� �� apporter plus de modifications au plan initial. Dans le second article, nous consid��rons un contexte o�� un seul voyage �� la fois est communiqu�� aux chauffeurs. Le r��partiteur attend jusqu����� ce que le chauffeur termine son voyage avant de lui r��v��ler le prochain voyage. Ce contexte est plus souple et offre plus de possibilit��s de recours en cas d���impr��vus. En plus, le probl��me hebdomadaire peut ��tre divis�� en des probl��mes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des p��riodes limit��es durant la journ��e. Nous utilisons un mod��le de programmation math��matique bas�� sur un r��seau espace-temps pour r��agir aux perturbations. Bien que ces derni��res puissent avoir des effets diff��rents sur le plan de transport initial, une caract��ristique cl�� du mod��le propos�� est qu���il reste valable pour traiter tous les impr��vus, quelle que soit leur nature. En effet, l���impact de ces ��v��nements est captur�� dans le r��seau espace-temps et dans les param��tres d���entr��e plut��t que dans le mod��le lui-m��me. Le mod��le est r��solu pour la journ��e en cours chaque fois qu���un ��v��nement impr��vu est r��v��l��. Dans le dernier article, la flotte de camions est h��t��rog��ne, comprenant des camions avec des chargeuses �� bord. La configuration des routes de ces camions est diff��rente de celle des camions r��guliers, car ils ne doivent pas ��tre synchronis��s avec les chargeuses. Nous utilisons un mod��le math��matique o�� les colonnes peuvent ��tre facilement et naturellement interpr��t��es comme des itin��raires de camions. Nous r��solvons ce mod��le en utilisant la g��n��ration de colonnes. Dans un premier temps, nous relaxons l���int��gralit�� des variables de d��cision et nous consid��rons seulement un sous-ensemble des itin��raires r��alisables. Les itin��raires avec un potentiel d���am��lioration de la solution courante sont ajout��s au mod��le de mani��re it��rative. Un r��seau espace-temps est utilis�� �� la fois pour repr��senter les impacts des ��v��nements impr��vus et pour g��n��rer ces itin��raires. La solution obtenue est g��n��ralement fractionnaire et un algorithme de branch-and-price est utilis�� pour trouver des solutions enti��res. Plusieurs sc��narios de perturbation ont ��t�� d��velopp��s pour tester l���approche propos��e sur des ��tudes de cas provenant de l���industrie foresti��re canadienne et les r��sultats num��riques sont pr��sent��s pour les trois contextes.