Workshop Details

The last decade has witnessed the impressive development of machine learning (ML) techniques. These techniques have been successfully applied to traditional statistical learning tasks as image recognition and led to breakthroughs like the famous AlphaGo system. Motivated by those successes, many scientific disciplines have started to investigate the potential of the use of large amount of data crunched by ML techniques in their context. Combinatorial optimization (CO) has been no exception to this trend and the ML use in CO has been analyzed from many different angles with various levels of success. In this talk, we will review the state of the art of such scientific path, interpreting the level of maturity reached by the integration of ML techniques in CO and discussing the challenges. We will finish by presenting one particular area in which we consider this integration having a remarkable potential, i.e., repeatedly solving CO problems with little data variations with special attention to Capacitated Vehicle Routing problems.

[Video]

Join me on a tour! Our first stop is 'learning to solve routing problems', where I'll give a sneak peak into my PhD research on solving vehicle routing problems using deep (reinforcement) learning. I'll then take you along our path to winning the DIMACS challenge VRPTW track. Next, we'll continue our journey towards organizing the EURO Meets NeurIPS vehicle routing competition (challenge): we'll discuss the lessons learned along the way, and the many interesting findings at our destination (all credits to the participants!). I'll show how, along the way, the Hybrid Genetic Search (HGS) algorithm by Thibaut gradually evolved into PyVRP, a high-performance, yet flexible VRP solver using Python with C++ components. Finally, I'll discuss some of the challenges of solving vehicle routing problems in practice.

[Video]

Recent contributions have shown that embedding a combinatorial optimization layer in machine learning pipeline could provide state-of-the-art algorithms for static and dynamic vehicle routing problems. In this talk, we draw lessons from several static and dynamic application to identify classes of vehicle routing problems that can benefit from such approaches. We also detail several pipeline architectures that lead to efficient algorithms. Several approaches to learn these pipelines will also be detailed. We finally illustrate how our recent open source library InferOpt.jl simplifies the implementation and training of such pipelines.

[Video]

With the rise of e-commerce and increasing customer requirements, logistics service providers face a new complexity in their daily planning, mainly due to efficiently handling same day deliveries. Existing multi-stage stochastic optimization approaches that allow to solve the underlying dynamic vehicle routing problem are either computationally too expensive for an application in online settings, or -- in the case of reinforcement learning -- struggle to perform well on high-dimensional combinatorial problems. To mitigate these drawbacks, we propose a novel machine learning pipeline that incorporates a combinatorial optimization layer. We apply this general pipeline to a dynamic vehicle routing problem with time windows, which was recently promoted in the EURO Meets NeurIPS Vehicle Routing Competition at NeurIPS 2022. Our methodology ranked first in this competition, outperforming all other approaches in solving the proposed dynamic vehicle routing problem. This presentation details our approach and provides a comprehensive numerical study that further highlights the efficacy and benefits of the proposed pipeline beyond the results achieved in the competition, e.g., by showcasing the robustness of the encoded policy against unseen instances and scenarios.

[Video]

Nowadays, practical vehicle routing problems (VRPs) are almost exclusively solved by heuristic algorithms and solvers. However, there has been a notable increase in the development of exact mathematical optimization approaches for VRPs, which are becoming increasingly relevant for practical applications. In this talk, we will provide an overview of the latest progress in this area, highlighting the potential for generic exact VRP solvers to become practical tools for solving these problems. We will also introduce VRPSolverEasy, a new Python package with a simple interface that can solve a range of popular VRP variants to optimality. With this tool, practitioners can easily apply complex exact optimization methods to their VRP instances.

[Video]

Despite the extensive research efforts and the promising results obtained by the ML community on Vehicle Routing Problems, most of the proposed techniques are still seldom employed by the OR community. With the current work, we highlight a number of challenges arising during the computational evaluation of heuristics for VRPs. The resulting guidelines aim at defining a common testing setup for the approaches designed by the two communities, thus promoting and strengthening the collaboration between them.

[Video]

This talk has two parts. In the first part I will discuss PyVRP, a high-performance Python vehicle routing solver package that Wouter Kool, Leon Lan and I spun off from our DIMACS and Euro/NeurIPS solver submissions. The second part presents some recent work solving a large, practical case of urban waste collection in the municipality of Groningen (NL). We model this problem as a prize-collecting VRP that we implement using PyVRP. We show several ways to develop granular neighbourhood structures taking prizes into account, and discuss some acceleration techniques to efficiently solve the large-scale problem.

[Video]

In this talk, we present Adaptive Iterated Local Search (AILS), which considers diversity control mechanisms, to solve vehicle routing problems (VRPs). This metaheuristic outperformed state-of-the-art algorithms for the Capacitated VRP (CVRP) and Heterogeneous VRP (HVRP). More recently, a version of this framework for large-scale CVRP instances achieved outstanding results.

[Video]

Vehicle Routing Problems (VRPs) are a class of combinatorial optimization problems with a wide range of applications. In the past decades, numerous heuristic and exact approaches have been proposed to solve various VRP variants. However, developing a unifying framework for VRP heuristics is complex due to the balance required between the generality of the approach and the specificity in exploiting problem characteristics. A successful framework proposed by Vidal et al. [1] separated generic and variant-specific components of the algorithm. This separation helped to achieve a good compromise between efficiency and generality. However, the wide adoption of such a framework has been limited, possibly due to the absence of a public library to aid researchers with new heuristics ideas and techniques. In this ongoing work, we aim to extend the Resource Extension Function framework to generalize it to other classes of constraints and objective functions. Additionally, we plan to study and develop a taxonomy of VRP constraints and introduce reflection capabilities to the framework to enable specialized handling of the most costly operations, while still maintaining the generality of the unifying approach. Furthermore, we will apply the same rationale to the algorithmic counterpart and present a framework that can assist in the development of meta-heuristics by decomposing them into basic algorithmic components and providing ways to compose them together.

[Video]

Hybrid genetic algorithms have proven successful in solving various routing problems, with the design of highly effective crossover operators being a crucial factor. In this talk, we will present recent advances of the edge assembly crossover operator (EAX) to solve several routing problems, including the split-delivery vehicle routing problem (SDVRP), the orienteering problem (OP), the prize-collecting traveling salesman problem (PCTSP), the minmax multiple traveling salesman problem (minmax mTSP), and the Hamiltonian-P median problem (HpMP). We show that by leveraging the strengths of the EAX operator, we can achieve remarkable improvements in the quality of solutions and computational efficiency in these areas. We will also show how the EAX operator can be extended to handle rich (multi-attribute) routing problems. By adapting the EAX operator to these rich routing problems, we hope to enable researchers and practitioners to tackle a broader range of real-world routing problems.

[Video]

Deep reinforcement learning (DRL) offers a way to automatically learn heuristics to solve routing problems. Over the past years, these techniques have rapidly improved in terms of the quality of solutions they find, although they have not yet overtaken state-of-the-art "traditional" OR heuristics. I provide an overview of how to solve routing problems using DRL, starting from constructing solutions, and continuing on to advanced search techniques. This talk discusses both the limitations and opportunities of DRL to try to determine whether learning to optimize is just the latest trend or a future technology.

[Video]

Over the past few years, I have had the chance to apply reinforcement learning techniques using deep neural networks on vehicle routing problems. Building a practical RL-based algorithm is not an easy task, and I would like to share my experience on many failed attempts.

[Video]

The Amazon fulfillment network consists of Amazon buildings and transportation lanes among them. In this talk, I will focus on the network with nodes representing Amazon Fulfillment Centers, Sortation Centers, and the Delivery Stations, where the links are the truck and air lanes among them. The lanes of this network are highly dynamic: their capacity can be changed a few days in advance, and they can also be deprecated or launched with short notice. On the other hand, large buildings are planned years ahead. Designing and expanding this network, as well as adjusting the nodes and links capacities for everyday operation demands an orchestration of complex OR systems. In this talk, I will describe this process.

[Video]

Experienced drivers in last-mile delivery may follow stop sequences that are more efficient than the theoretically shortest-distance routing under real-life operational conditions, due to their knowledge on factors unique to the service area. Thus, predicting the actual stop sequence that a human driver would take can enhance route planning in last-mile delivery.

In this presentation, we propose two methods for predicting drivers' route trajectories in last-mile delivery. The first approach is an optimization-based method using a hierarchical Traveling Salesman Problem (TSP) optimization with a customized cost matrix that accounts for routing patterns beyond the shortest travel time. This approach won second place in the 2021 Amazon Last-Mile Routing Challenge.

The second approach is a deep learning-based method that uses a pair-wise attention-based pointer neural network. In addition to the common encoder-decoder architecture for sequence-to-sequence prediction, we introduce a novel attention mechanism to capture the local pair-wise information for each pair of stops. To further improve the global efficiency of the route, we iterative over multiple possible sequences to select the one with the lowest operational cost. Our extensive case study on real operational data from Amazon's last-mile delivery operations in the US demonstrates that our proposed method outperforms traditional optimization-based approaches and other deep learning methods, such as the Long Short-Term Memory encoder-decoder and the pointer network, in finding stop sequences that closely resemble high-quality routes executed by experienced drivers in the field.

Based on our analysis, optimization-based techniques produce reliable and predictable sequences while reducing overall operational costs, without the need for training. Nevertheless, they have limited adaptability in incorporating soft constraints and heavily rely on pre-existing knowledge embedded in the cost matrix. Conversely, deep learning models can capture complex patterns with automatic feature learning. However, they demand a significant amount of training data, and the quality of their outputs is strongly impacted by the quality of input data.

[Video]

Last-mile routing refers to the final step in a supply chain, delivering packages from a depot station to the homes of customers. At the level of a single van driver, the task is a traveling salesman problem. But the choice of route may be constrained by warehouse sorting operations, van-loading processes, driver preferences, and other considerations, rather than a straightforward minimization of tour length.

We propose a simple and efficient penalty-based local search algorithm for route optimization in the presence of such constraints, adopting a technique developed by Helsgaun to extend the Lin-Kernighan-Helsgaun algorithm for the traveling salesman problem to general vehicle routing problems. We apply his technique to handle combinations of constraints obtained from an analysis of historical routing data, enforcing properties that are desired in high-quality solutions. Our code is available under the open-source MIT license.

An earlier version of the code received the $100,000 top prize in the Amazon Last Mile Routing Research Challenge organized in 2021.

[Video]

[Video]

[Video]

[Video]

Together with David Applegate and Keld Helsgaun, we have found a tour through the 3D positions of 265,637,087 stars. We discuss how linear programming allows us to prove the tour is at most a factor of 1.00025 longer than an optimal tour. Like most computational studies, our work has been influenced by ideas of David Johnson. We discuss his great TSP research, focusing on an experimental estimate of the BHH constant.

[Video]

David Johnson made many fundamental contributions to computer science, including in the theory of NP-completeness, approximation algorithms, and the analysis of heuristics for hard optimization problems. In this talk I will discuss some of his pioneering work and its impact on our field, and reflect on our friendship through many years together at Bell Labs and afterwards.

[Video]

Pattern mining techniques have been applied to find components that frequently appear together in high-quality solutions to a combinatorial optimization problem, which can support metaheuristics in several ways.

This talk will discuss two approaches that mine frequent paths from high-quality solutions found by vehicle routing metaheuristics and use them to improve the methods' performance.

The first uses the mined patterns to initialize new solutions by inserting their frequent paths in the routes. The other, named MineReduce, uses them to decompose the solving process in two stages: (i) solving a subproblem obtained by contracting their frequent paths and (ii) searching the original solution space using the subproblem solution as starting point. These approaches have recently been applied to the capacitated VRP and the heterogeneous fleet VRP, improving the underlying metaheuristics' solution quality and convergence speed.

[Video]

In the context of the Amazon Last-Mile Routing Research Challenge, in this talk we present a machine-learning framework for optimizing last-mile delivery routes. Contrary to most routing problems where an objective function is clearly defined, in the real-world setting considered in the challenge, an objective is not explicitly specified and must be inferred from data. Leveraging techniques from machine learning and classical traveling salesman problem heuristics, we propose a \`\`pool and select’’ algorithm to prescribe high-quality last-mile delivery sequences. In the pooling phase, we exploit structural knowledge acquired from data, such as common entry and exit regions observed in training routes. In the selection phase, we predict the scores of candidate sequences with a high-dimensional, pre-trained, and regularized regression model. The score prediction model, which includes a large number of predictor variables such as sequence duration, compliance with time windows, earliness, lateness, and structural similarity to training data, displays good prediction accuracy and guides the selection of efficient delivery sequences. Overall, the framework is able to prescribe competitive delivery routes, as measured on out-of-sample routes across several datasets. Given that desired characteristics of high-quality sequences are learned and not assumed, the proposed framework is expected to generalize well to last-mile applications beyond those immediately foreseen in the challenge.

[Video]

Same-day delivery has become common in many cities. These services can involve the delivery of goods ordered online such as services offered by Amazon PrimeNow or InstaCart or the delivery meals such those offered by GrubHub. In this talk, we focus on the former and particularly on the case where customers order good online and these orders are fulfilled from a central depot. In this case, a customer seeks to place an order for online. The company must determine if the service can be provided same-day, and then if the customer chooses that service what vehicle and on what route the goods should be delivered. Decision making is complicated by the fact that orders arrive sequentially and randomly over time. This talk will discuss the use of reinforcement learning for decision making and will particularly look at issues of fairness and the impact of decision on the evolution of demand over time.

[Video]

The talk will present an improved version of the solution method that won the inventory routing problem track of the 12th DIMACS Implementation Challenge. The solution method is a branch-and-cut embedded matheuristic where a matheuristic is called every time a new primal solution is found in a branch-and-cut method. The matheuristic consists of a construction heuristic and an improvement heuristic. The construction heuristic uses a giant tour method and a shifting assignments method to generate a set of promising routes which, in turn, are combined into a feasible solution to the problem by solving a route-based mathematical program. The improvement heuristic then solves a series of extended route-based mathematical programs where clusters of customers may be inserted and/or removed from the routes of the initial feasible solution. Compared with published state-of-the-art methods, the proposed method found the best-known solution for 741 out of 878 multi-vehicle inventory routing instances, where 247 of them are strictly better than the previously best-known solutions. Furthermore, we prove optimality for 458 of these solutions. The proposed method is also able to find the best-known solution for 116 out of 226 benchmark instances for the split delivery vehicle routing problem.

[Video]

The improvement MIPs used in the MrOptimal solver for the IRP has proven to be efficient when solving the inventory routing problem (IRP), production routing problem, and the VRP with split deliveries. However, are they efficient when used on other routing problems with a higher degree of intra-route constraints? This talk will discuss this question and look at the CVRP, multi-trip VRP, VRPTW, and the pickup and delivery problem with time windows.

[Video]

Contextual stochastic optimization combines auxiliary information and machine learning to solve problems subject to uncertainty. While this integrated approach can improve performance, it leads to complex decision pipelines that lack transparency. Yet, practitioners need to understand and trust new solutions in order to replace an existing policy. To explain the solutions of contextual stochastic problems, we revisit the concept of counterfactual explanations introduced in the classification setting. We identify minimum changes in the features of the context that lead to a change in the optimal decisions. We formalize the explanation problem and develop mixed-integer linear models to find optimal explanations of decisions obtained through random forests and nearest-neighbor predictors. We apply our approach to selected operations research problems, such as inventory management and routing, and show the value of the explanations obtained.