A solution approach for multi‐trip vehicle routing problems with time windows, fleet sizing, and depot location
| Autor: | Ivona Gjeroska, Miguel F. Anjos, Paula Fermín Cueto, Albert Solà Vilalta |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
time windows
Computer Networks and Communications Depot Computer science fleet sizing Real-time computing heuristics multiple trips Sizing branch-and-cut Hardware and Architecture Time windows multiple depots Vehicle routing problem subtour elimination constraints Heuristics vehicle routing Branch and cut Software Information Systems |
| Zdroj: | 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 . https://doi.org/10.1002/net.22028 |
| ISSN: | 1097-0037 0028-3045 |
| DOI: | 10.1002/net.22028 |
| Popis: | 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 2 min, 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text