This seminar will take place on May 29 at 15:00, online via Zoom (link below)
https://zoom.us/j/99679130263?pwd=QUwJmjV4K6olZV0xaoYOUMhFk8YUO9.1
Our seminars are free to attend and open to everyone. Please share with whomever may be interested.
Summary
VRPSolver is an advanced branch-and-cut-and-price solver for a generic model that encompasses a wide class of vehicle routing problems as well as several other types of problems. A VRPSolver model is a general MIP with additional constraints that force some variables to be linear combinations of resource-constrained shortest paths in user-defined graphs. The first generation of VRPSolver features the Bucket Graph Solver, a bidirectional dynamic programming labeling algorithm for the Resource-Constrained Shortest Path Problem, in which labels are stored and extended according to the so-called bucket graph. This organization significantly reduces the number of dominance checks and the algorithm's running time. It is used for the crucial pricing step in VRPSolver, a branch-cut-and-price algorithm that achieves the current best exact results for many VRP variants. Bucket Graph Meta-Solver is a code refactoring that separates the intricate, general bucket-graph-based core from the functions that implement resource-specific elements such as label extension, dominance, and concatenation. In this talk, we show how a user can create new resources in Meta-Solver to handle more complex routing variants. Computational experiments on the Cumulative Cost VRP and the Simultaneous Pickup and Delivery VRP illustrate the power of Meta-Solver.
Speaker's bio
Teobaldo Bulhões holds a Bachelor's degree in Computer Science from the Universidade Federal da Paraíba (Brazil), a Master's degree in Informatics from the same institution, and a Ph.D. in Computer Science from the Universidade Federal Fluminense (Brazil). He is currently an Associate Professor in the Department of Scientific Computing at the Universidade Federal da Paraíba. His research interests are mainly focused on the exact and heuristic resolution of combinatorial optimization problems, especially vehicle routing and machine scheduling problems, and he has published several articles in operational research journals and related fields. He is currently an Associate Editor of the journal Omega. He was part of the VRPSolver development team, a generic solver for the exact resolution of combinatorial optimization problems with a focus on vehicle routing. In the past five years, he has been collaborating with companies to develop decision support systems applied to real-world optimization problems.