Journées de l'optimisation 2022

HEC Montréal, Québec, Canada, 16 — 18 mai 2022

Horaire Auteurs Mon horaire

WC11 - Vehicle routing and scheduling VII

18 mai 2022 15h30 – 17h10

Salle: EY (bleu)

Présidée par François Sarrazin

4 présentations

  • 15h30 - 15h55

    Dynamic Programming for the Fixed Route Electric Vehicle Charging Problem with Nonlinear Energy Management

    • Anthony Deschênes, prés., Université Laval
    • Jonathan Gaudreault, Université Laval
    • Claude-Guy Quimper, Université Laval

    The Fixed Route electric Vehicle Charging Problem with NonLinear Energy Management (FRVCP-NLEM) consists of finding the optimal charging and vehicle speed decisions given a fixed route for an electric vehicle. The objective is to minimize the total route duration including charging duration. The problem takes into consideration the non-linearity of the charging and energy consumption functions. We propose a new dynamic programming model to solve this problem that uses Akima interpolation to take into consideration the continuous state space over the state of charge. Experiment results show that the proposed model solves optimally all instances in less than 0.2 seconds, outperforming the current state of the art model. The complexity of the proposed model has a linear increase as the number of charging stations on the fixed route increases, meaning that it is easily scalable.

  • 15h55 - 16h20

    A dynamic discretization discovery algorithm for the transportation of biomedical samples

    • Daniel Ocampo-Giraldo, prés., ESG-UQÀM
    • Ana María Anaya Arenas, ESG - UQAM
    • Claudio Contardo, ESG UQÀM / GERAD

    We propose a two-step solution algorithm to solve a vehicle routing problem for the distribution of multiple highly perishable commodities. Inspired by an application in healthcare services, the biomedical sample transportation problem, numerous commodities with short lifespan presume multiple transportation requests at the same facility in a day and restrict the maximum time to reach the destination. These two characteristics create an interdependency between the routing and the pickup decisions in time that is highly complex. Our solution method aggregates the network at two levels. First, the commodities are aggregated and artificially consolidated, reducing the symmetry arising when multiple transportation requests are solicited within a short period of time. Second, the space-time nodes in the network are constructed dynamically, thus reducing the size of the mathematical model to be solved at each iteration. Our algorithm proves to be efficient to solve a set of real-life instances from the Quebec laboratory network under the management of the Ministère de la Santé et des Services sociaux (Ministry of Health and Social Services).

  • 16h20 - 16h45

    Optimisation de la collecte des déchets métalliques pour le recyclage

    • Valentin Cherbonnier, prés., Etudiant, ETS
    • Amin Chaabane, École de technologie supérieure
    • Marc Paquet, École de technologie supérieure

    Le but de l’étude présentée dans ce travail est de proposer une méthode d’optimisation pour le problème de tournée de véhicule dans le contexte de la logistique inverse pour une grande entreprise opérant dans le secteur de recyclage des métaux. Le modèle proposé contient différents aspects : logistique inverse, flotte hétérogène, multi-produits, multi-routes, multi-dépôts, fenêtres de temps et multi-demandes (ramassage et livraison). D’autres aspects, moins ordinaires, mais présents dans le modèle, font la spécificité de celui-ci. On relève l’aspect client-dépôt, qui permet l’échange entre différentes entités d’un même niveau, l’aspect priorisation des clients, générant la prise en compte des demandes sur deux jours, l’aspect d’échange direct entre fournisseur et client final de l’entreprise, élevant alors le modèle à une variante multi-échelons et enfin l’aspect sous-traitant dont les tournées sont générées par le modèle. La résolution et validation de celui-ci est faite dans un premier temps avec des méthodes exactes sur des instances de tailles réduites ayant été générées à partir des données de l’entreprise. Sa complexité étant importante, nous proposons une méthode heuristique afin de pouvoir l’appliquer sur des instances de tailles réelles. Enfin, une analyse des résultats est proposée afin de mieux comprendre comment se comporte l’heuristique et pouvoir proposer des pistes d’améliorations.

  • 16h45 - 17h10

    Potential of warehouse sharing and electric bicycle deliveries in the Montreal region

    • François Sarrazin, prés., Université de Montréal
    • Bernard Gendron, Université de Montréal, CIRRELT
    • Martin Trépanier, Polytechnique Montréal, CIRRELT

    More and more, the idea of collaborating between companies to reduce certain costs is gaining ground. Also, cargo bikes, which are easier to use in dense urban areas than conventional trucks, are increasingly used for “last-mile” deliveries. However, these vehicles have a limited autonomy of around 25 km before they have to be recharged.
    As part of our project, we have developed a courier transport optimization model. Using this model and data about courier distribution in the Montreal region, we tested scenarios of warehouse sharing and increased use of cargo bikes. Warehouse sharing would save more than 30% of costs and reduce GHG emissions by more than 40%. An increased use of cargo bikes would also lead to both cost and GHG emissions reductions (between 1% and 2%). These gains increase when the autonomy of cargo bikes increases. A series of sites that could accommodate new warehouses in the Montreal area have also been identified.
    The model has two phases. The first phase simplifies cost measurement and selects through which warehouse each shipment must transit. A second phase of the model allowing for delivery routes has also been developed and is in the process of being implemented.

Retour