New compact integer programming formulations for the multi-trip vehicle routing problem with time windows
| Autor: | Maichel M. Aguayo, Mathias A. Klapp, Daniel A. Neira, Rodrigo De la Fuente |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
021103 operations research General Computer Science Computer science Node (networking) 0211 other engineering and technologies General Engineering 02 engineering and technology Set (abstract data type) Vehicle routing problem 0202 electrical engineering electronic engineering information engineering Benchmark (computing) Graph (abstract data type) 020201 artificial intelligence & image processing Relaxation (approximation) Limit (mathematics) Integer programming |
| Zdroj: | Computers & Industrial Engineering. 144:106399 |
| ISSN: | 0360-8352 |
| DOI: | 10.1016/j.cie.2020.106399 |
| Popis: | We study two integer programming (IP) models for the multi-trip vehicle routing problem with time windows, service-dependent loading times, and limited trip duration (MTVRPTW-SDLT). Our first two-index formulation model represents vehicle returns to the depot in a graph with multiple copies of the depot node. The second two-index formulation model has just one depot node per vehicle, but includes a parallel arc for each pair of customer nodes representing an intermediate vehicle return to the depot. We compare these formulations against three-index formulations available in the literature over a set of benchmark instances. Results show that our models outperform existing formulations. We also adapt the proposed formulations for a relaxation of the MTVRPTW-SDLT without trip duration limit (LT). Our computational results also suggest that our models also improve their performance on MTVRPTW-SD instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect