Branch-and-cut-and-price algorithms based on set-partitioning formulations are popular methods for optimally solving vehicle routing problems (VRPs). This talk explores vehicle routing heuristics based on the branch-and-cut-and-price approach. The exact method is turned into a heuristic by partially exploring the branch-and-bound tree and only solving the pricing problem heuristically. Results will be presented for the vehicle routing problem with time windows, the pickup and delivery problem with time windows, the dial-a-ride problem, the vehicle routing problem with drones, the electric vehicle routing problem with time windows, and the vehicle routing problem with stochastic demand. The handling of the master problem and the cutting and branching are generic for all considered VRP types, while the pricing sub-problem heuristics are tailored for the problem at hand.

Hexaly Optimizer, formerly known as LocalSolver, is a model-and-run solver that integrates heuristics and exact methods. A set-based modeling formalism was introduced to simplify the modeling of certain combinatorial problems like routing or packing problems. For instance, in a routing problem, list variables can be used to model the sequence of visits made by each truck. These decision variables are well suited for a heuristic search but are much more difficult to integrate in a mathematical programming approach to compute lower bounds. A direct reformulation in a Mixed Integer Linear Programming (MILP) model introduces a quadratic number of binary decisions with several big M constraints leading to poor scalability and bounds. Hexaly 13.0 automatically detects such structures in a user model and reformulates them in an extended MILP model to compute lower bounds. This model is solved efficiently using state of the art branch-cut-and-price technics from the literature. This talk will present the general approach and the algorithms used for the resolution and some benchmarks on the CVRP (capacitated vehicle routing problem) library.

Ridesharing has emerged as a promising solution to tackle urban mobility challenges, offering affordability and convenience while potentially alleviating congestion and environmental impact. This study investigates the use of transportation hubs, equipped with parking facilities, which serve as both the origin and destination of rideshare trips. The proposed system integrates personal vehicles with carpooling options and shuttle services as dynamic transit solutions to serve ride requests. Our study encompasses the needs and goals of users, operators, emissions reduction, and the overarching system efficiency. Employing a multifaceted approach, we solve the system optimization problem using column generation, ensuring that our investigation captures the diverse interests and priorities within the realm of urban mobility. Through this lens, we provide a holistic assessment of the proposed approach under various scenarios, illuminating its efficacy in addressing the complex challenges of large-scale urban mobility.