A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem

Kevin Dalmeijer and Remy Spliet

No EI2016-39, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: 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 small scale instances previously presented in the literature.

Keywords: Vehicle Routing; Time Window Assignment; Precedence Inequalities; 90B06 (Transportation); 90C11 (Mixed integer programming); 90C57 (Branch-and-cut) (search for similar items in EconPapers)
Pages: 31
Date: 2016-10-19
New Economics Papers: this item is included in nep-cmp, nep-tre and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/97802/EI2016-39.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:97802

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).