Using Machine Learning in BPC for Vehicle Routing Problems

The planning and execution of deliveries represents a significant share of the costs in the area of distribution logistics and there is a great interest in exploiting the optimization potential in this area as best as possible. Therefore, route planning problems are also one of the central issues of Operations Research (OR). The use of optimization methods for route planning promises great potential for cost savings through the higher quality of the planning results as well as through the automation and acceleration of the planning process. There are numerous variants of route planning problems based on the different real-world requirements that transport service providers face. In most route planning problems, the task is finding the cheapest set of routes for a given fleet of vehicles such that a given set of orders is fulfilled while taking various side-constraints into account. The most powerful exact route planning algorithms are based on branch-cut-and-price (BCP), which in turn is based on column generation techniques. Here, a master problem is responsible for the best selection of the available routes, while one or more so-called pricing problems successively generate new routes. The planned project is intended to generate new insights into the use of machine learning (ML) in BCP to solve route planning problems. The key question is how ML can be used in OR algorithms, because optimization problems are very different from most problems successfully solved by ML.

The project provided new insights into the integration of supervised learning into operations research optimization algorithms for solving vehicle routing problems. In particular, it was demonstrated that supervised learning can also be applied in exact optimization algorithms. In this context, careful selection of learning objectives was crucial. Often, it was not clear from the outset what could be learned and how the learned knowledge would affect the overall algorithm. It proved useful to first test the algorithm with perfectly learned knowledge to determine the potential for improvement. If only marginal improvements can be achieved even with perfect learning, a real-world learning method will certainly not yield any significant improvement. Regarding learning methods, it has been shown that traditional approaches, such as random forests, can achieve results just as good as those of neural networks-and with significantly less effort. Some of the components of Branch-Cut-and-Price that were examined could not be significantly improved through the integration of machine learning. For example, a master's thesis on the selection of cutting planes did not yield any significant improvement in runtime. Successes were achieved, however, i) in learning complex parameterizations, such as configuring an elementary neighborhood, and ii) in solving the subproblem, for example, when creating reduced networks or when deciding on good and bad labels in dynamic programming.