A machine learning-based branch and price algorithm for a sampled vehicle routing problem

• Published in: OR Spectrum 2021-09, Vol.43 (3), p.693-732
• Main Authors: Furian, Nikolaus, O’Sullivan, Michael, Walker, Cameron, Çela, Eranda
• Format: Article
• Language: English
• Subjects: Algorithms; Business and Management; Calculus of Variations and Optimal Control; Optimization; Feature selection; Human performance; Machine learning; Operations Research/Decision Theory; Optimization; Pattern recognition; Quality assessment; Regular Article; Reliability analysis; Robustness (mathematics); Route planning; Variables; Vehicle routing; Windows (intervals)
• ISSN: 0171-6468; 1436-6304
• DOI: 10.1007/s00291-020-00615-8

Planning of operations, such as routing of vehicles, is often performed repetitively in rea-world settings, either by humans or algorithms solving mathematical problems. While humans build experience over multiple executions of such planning tasks and are able to recognize common patterns in different problem instances, classical optimization algorithms solve every instance independently. Machine learning (ML) can be seen as a computational counterpart to the human ability to recognize patterns based on experience. We consider variants of the classical Vehicle Routing Problem with Time Windows and Capacitated Vehicle Routing Problem, which are based on the assumption that problem instances follow specific common patterns. For this problem, we propose a ML-based branch and price framework which explicitly utilizes those patterns. In this context, the ML models are used in two ways: (a) to predict the value of binary decision variables in the optimal solution and (b) to predict branching scores for fractional variables based on full strong branching. The prediction of decision variables is then integrated in a node selection policy, while a predicted branching score is used within a variable selection policy. These ML-based approaches for node and variable selection are integrated in a reliability-based branching algorithm that assesses their quality and allows for replacing ML approaches by other (classical) better performing approaches at the level of specific variables in each specific instance. Computational results show that our algorithms outperform benchmark branching strategies. Further, we demonstrate that our approach is robust with respect to small changes in instance sizes.