Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows
| Autor: | Wout Dullaert, David S.W. Lai, Daniele Vigo, Maaike Hoogeboom |
|---|---|
| Přispěvatelé: | Hoogeboom M., Dullaert W., Lai D., Vigo D., Operations Analytics, Amsterdam Business Research Institute |
| Rok vydání: | 2020 |
| Předmět: |
050210 logistics & transportation
021103 operations research Computer science 05 social sciences Real-time computing Multiple time windows 0211 other engineering and technologies Metaheuristic Transportation Metaheuristics 02 engineering and technology Vehicle routing Time windows 0502 economics and business Vehicle routing problem Multiple time Multiple time window Civil and Structural Engineering |
| Zdroj: | Transportation Science, 54(2), 400-416. INFORMS Inst.for Operations Res.and the Management Sciences Hoogeboom, M, Dullaert, W, Lai, D & Vigoa, D 2020, ' Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows ', Transportation Science, vol. 54, no. 2, pp. 400-416 . https://doi.org/10.1287/trsc.2019.0912 |
| ISSN: | 1526-5447 0041-1655 |
| DOI: | 10.1287/trsc.2019.0912 |
| Popis: | In the vehicle routing problem with multiple time windows (VRPMTW), a single time window must be selected for each customer from the multiple time windows provided. Compared with classical vehicle routing problems with only a single time window per customer, multiple time windows increase the complexity of the routing problem. To minimize the duration of any given route, we present an exact polynomial time algorithm to efficiently determine the optimal start time for servicing each customer. The proposed algorithm has a reduced worst-case and average complexity than existing exact algorithms. Furthermore, the proposed exact algorithm can be used to efficiently evaluate neighborhood operations during a local search resulting in significant acceleration. To examine the benefits of exact neighborhood evaluations and to solve the VRPMTW, the proposed algorithm is embedded in a simple metaheuristic framework generating numerous new best known solutions at competitive computation times. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|