An exact solution framework for multitrip vehicle-routing problems with time windows
| Autor: | Roberto Roberti, Demetrio Laganà, Wout Dullaert, Rosario Paradiso |
|---|---|
| Přispěvatelé: | Operations Analytics, Amsterdam Business Research Institute |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Pollution
Computer science media_common.quotation_subject 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Column generation Dynamic programming Exact methods Multitrip vehicle routing Time windows 0502 economics and business Vehicle routing problem media_common 050208 finance 021103 operations research business.industry 05 social sciences Drone SDG 11 - Sustainable Cities and Communities Computer Science Applications business Computer network |
| Zdroj: | Paradiso, R, Roberti, R, Lagana, D & Dullaert, W 2020, ' An exact solution framework for multitrip vehicle-routing problems with time windows ', Operations Research, vol. 68, no. 1, pp. 180-198 . https://doi.org/10.1287/OPRE.2019.1874 Operations Research, 68(1), 180-198. INFORMS Inst.for Operations Res.and the Management Sciences |
| ISSN: | 0030-364X |
| Popis: | Multitrip vehicle-routing problems (MTVRPs) generalize the well-known VRP by allowing vehicles to perform multiple trips per day. MTVRPs have received a lot of attention lately because of their relevance in real-life applications - for example, in city logistics and last-mile delivery. Several variants of the MTVRP have been investigated in the literature, and a number of exact methods have been proposed. Nevertheless, the computational results currently available suggest that MTVRPs with different side constraints require ad hoc formulations and solution methods to be solved. Moreover, solving instances with just 25 customers can be out of reach for such solution methods. In this paper, we proposed an exact solution framework to address four different MTVRPs proposed in the literature. The exact solution framework is based on a novel formulation that has an exponential number of variables and constraints. It relies on column generation, column enumeration, and cutting plane. We show that this solution framework can solve instances with up to 50 customers of four MTVRP variants and outperforms the state-of-the-art methods from the literature. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|