Страница публикации

Lifted and Local Reachability Cuts for the Vehicle Routing Problem with Time Windows

Авторы: Avella P., Boccia M., Vasilyev I.L.

Журнал: Computers & Operations Research

Том: 40

Номер: 8

Год: 2013

Отчётный год: 2013

Издательство:

Местоположение издательства:

URL:

Проекты:

DOI: 10.1016/j.cor.2013.03.008

Аннотация: The Vehicle Routing Problem with Time Windows (VRPTW) requires to design minimum cost routes for a fleet of vehicles with identical capacities to serve a set of customers within given time windows. Each customer must be visited exactly once and the load of a vehicle must not exceed its capacity. In this paper we introduce two new basic families of valid inequalities, called Lifted and Local Reachability Cuts, respectively, which extend the Reachability Cuts introduced by J. Lysgaard. Separation procedures for Lifted and Local Reachability Cuts have been implemented and embedded into a Branch-and-Cut framework to validate their computational effectiveness. They were tested on the Solomon and on the Gehring-Homberger benchmark instances (also known as the "Extended Solomon" instances) with 200 customers. Computational experiments show that the new cutting plane families can substantially improve the lower bounds returned by Lysgaard's Reachability Cuts. The Branch-and-Cut algorithm could also provide the optimal solution of three previously unsolved instances - C222, 025 and 026 - with large capacities and wide time windows and therefore difficult for exact algorithms. (C) 2013 Elsevier Ltd. All rights reserved.

Индексируется WOS: Q2

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0