Paula Fermín Cueto, Ivona Gjeroska, Albert Solà Vilalta et Miguel F. Anjos
Article de revue (2021)
|
Libre accès au plein texte de ce document Version officielle de l'éditeur Conditions d'utilisation: Creative Commons: Attribution (CC BY) Télécharger (2MB) |
Résumé
We present a solution approach for a multi-trip vehicle routing problem with time windows in which the locations of a prescribed number of depots and the fleet sizes must also be optimized. Given the complexity of the task, we divide the problem into subproblems that are solved sequentially. First, we address strategic decisions, which are solved once and remain constant thereafter. Depots are allocated by solving a p-median problem and fleet sizes are determined by identifying the vehicle requirements of several worst-case demand instances. Then, we address the operational planning aspect: optimizing the vehicle routes on a daily basis to satisfy the fluctuating customer demand. We assign customers to depots based on distance and “routing effort,” and for the routing problem we combine a tailor-made branch-and-cut algorithm with a heuristic consisting of a route construction phase and packing of routes into vehicle trips. Our strategic decision models are robust in the sense that when applied to unseen data, all customers could be visited with the allocated fleet sizes and depot locations. Our operational routing methods are both time and cost-effective. The exact method yields acceptable optimality gaps in 20 min and the heuristic runs in less than 2min, finding optimal or near-optimal solutions for small instances. Finally, we explore the trade-off between depot and fleet costs, and routing costs to make recommendations on the optimal number of depots. Our solution approach was entered into the 12th AIMMS-MOPTA Optimization Modeling Competition and was awarded the first prize.
Mots clés
branch-and-cut, fleet sizing, heuristics, multiple depots, multiple trips, subtour elimination constraints, time windows, vehicle routing
Sujet(s): | 1600 Génie industriel > 1600 Génie industriel |
---|---|
Département: | Département de mathématiques et de génie industriel |
Organismes subventionnaires: | The Maxwell Institute Graduate School in Analysis and its Applications, Centre for Doctoral Training funded by the UK Engineering and Physical Sciences Research Council, Scottish Funding Council, Heriot-Watt University, University of Edinburgh |
Numéro de subvention: | EP/L016508/01 |
URL de PolyPublie: | https://publications.polymtl.ca/10630/ |
Titre de la revue: | Networks (vol. 78, no 4) |
Maison d'édition: | Wiley |
DOI: | 10.1002/net.22028 |
URL officielle: | https://doi.org/10.1002/net.22028 |
Date du dépôt: | 18 juil. 2023 12:06 |
Dernière modification: | 09 avr. 2024 03:26 |
Citer en APA 7: | Fermín Cueto, P., Gjeroska, I., Solà Vilalta, A., & Anjos, M. F. (2021). A solution approach for multi‐trip vehicle routing problems with time windows, fleet sizing, and depot location. Networks, 78(4), 503-522. https://doi.org/10.1002/net.22028 |
---|---|
Statistiques
Total des téléchargements à partir de PolyPublie
Téléchargements par année
Provenance des téléchargements
Dimensions