TY - JOUR
T1 - A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem
AU - Dalmeijer, Kevin
AU - Spliet, Remy
PY - 2018
Y1 - 2018
N2 - This paper presents a branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem (TWAVRP), the problem of assigning time windows for delivery before demand volume becomes known. A novel set of valid inequalities, the precedence inequalities, is introduced and multiple separation heuristics are presented. In our numerical experiments the branch-and-cut algorithm is 3.8 times faster when separating precedence inequalities. Furthermore, in our experiments, the branch-and-cut algorithm is 193.9 times faster than the best known algorithm in the literature. Finally, using our algorithm, instances of the TWAVRP are solved which are larger than the instances previously presented in the literature.
AB - This paper presents a branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem (TWAVRP), the problem of assigning time windows for delivery before demand volume becomes known. A novel set of valid inequalities, the precedence inequalities, is introduced and multiple separation heuristics are presented. In our numerical experiments the branch-and-cut algorithm is 3.8 times faster when separating precedence inequalities. Furthermore, in our experiments, the branch-and-cut algorithm is 193.9 times faster than the best known algorithm in the literature. Finally, using our algorithm, instances of the TWAVRP are solved which are larger than the instances previously presented in the literature.
U2 - 10.1016/j.cor.2017.08.015
DO - 10.1016/j.cor.2017.08.015
M3 - Article
SN - 0305-0548
VL - 89
SP - 140
EP - 152
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -