Recourse policies in the vehicle routing problem with stochastic demands

Dans le domaine de la logistique, de nombreux problèmes pratiques peuvent être formulés comme le problème de tournées de véhicules (PTV). Dans son image la plus large, le PTV vise à concevoir un ensemble d’itinéraires de collecte ou de livraison des marchandises à travers un ensemble de clients avec des coûts minimaux. Dans le PTV déterministe, tous les paramètres du problème sont supposés connus au préalable. Dans de nombreuses variantes de la vie réelle du PTV, cependant, ils impliquent diverses sources d’aléatoire. Le PTV traite du caractère aléatoire inhérent aux demandes, présence des clients, temps de parcours ou temps de service. Les PTV, dans lesquels un ou plusieurs paramètres sont stochastiques, sont appelés des problèmes stochastiques de tournées de véhicules (PSTV). Dans cette dissertation, nous étudions spécifiquement le problème de tournées de véhicules avec les demandes stochastiques (PTVDS). Dans cette variante de PSTV, les demandes des clients ne sont connues qu’en arrivant à l’emplacement du client et sont définies par des distributions de probabilité. Dans ce contexte, le véhicule qui exécute une route planifiée peut ne pas répondre à un client, lorsque la demande observée dépasse la capacité résiduelle du véhicule. Ces événements sont appelés les échecs de l’itinéraire; dans ce cas, l’itinéraire planifié devient non-réalisable. Il existe deux approches face aux échecs de l’itinéraire. Au client où l’échec s’est produit, on peut récupérer la realisabilite en exécutant un aller-retour vers le dépôt, pour remplir la capacité du véhicule et compléter le service. En prévision des échecs d’itinéraire, on peut exécuter des retours préventifs lorsque la capacité résiduelle est inférieure à une valeur seuil. Toutes les décisions supplémentaires, qui sont sous la forme de retours au dépôt dans le contexte PTVDS, sont appelées des actions de recours. Pour modéliser le PTVDS, une politique de recours, régissant l’exécution des actions de recours, doit être conçue. L’objectif de cette dissertation est d’élaborer des politiques de recours rentables, dans lesquelles les conventions opérationnelles fixes peuvent régir l’exécution des actions de recours. Nous fournissons un cadre général pour classer les conventions opérationnelles fixes pour être utilisées dans le cadre PTVDS. Dans cette classification, les conventions opérationnelles fixes peuvent être regroupées dans (i) les politiques basées sur le volume, (ii) les politiques basées sur le risque et (iii) les politiques basées sur le distance. Les politiques hybrides, dans lesquelles plusieurs règles fixes sont incorporées, peuvent être envisagées. Dans la première partie de cette thèse, nous proposons une politique fixe basée sur les règles, par laquelle l’exécution des retours préventifs est régie par les seuils prédéfinis. Nous proposons notamment trois politiques basées sur le volume qui tiennent compte de la capacité du véhicule, de la demande attendue du prochain client et de la demande attendue des clients non visités. La méthode “Integer L-Shaped" est réaménagée pour résoudre le PTVDS selon la politique basée sur les règles. Dans la deuxième partie, nous proposons une politique de recours hybride, qui combine le risque d’échec et de distance à parcourir en une seule règle de recours, régissant l’exécution des recours. Nous proposons d’abord une mesure de risque pour contrôler le risque d’échec au prochain client. Lorsque le risque d’échec n’est ni trop élevé ni trop bas, nous utilisons une mesure de distance, ce qui compare le coût de retour préventif avec les coûts d’échecs futurs. Dans la dernière partie de cette thèse, nous développons une méthodologie de solution exacte pour résoudre le VRPSD dans le cadre d’une politique de restockage optimale. La politique de restockage optimale résulte d’un ensemble de seuils spécifiques au client, de sorte que le coût de recours prévu soit réduit au minimum.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.