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.