1629. Resolution of Vehicle Routing Problems with optional visits using Hexaly
Invited abstract in session WC-58: Team Orienteering Problems, stream Vehicle Routing and Logistics.
Wednesday, 12:30-14:00Room: Liberty 1.13
Authors (first author is the speaker)
| 1. | Maxime Rougier
|
| Hexaly |
Abstract
Vehicle routing problems aim to determine efficient routes for one or more vehicles to visit a set of locations. In classic cases, every point must be visited exactly once. However, in practice, several industrial applications require models where some locations are optional. The choice of points to visit adds a new layer of combinatorial decisions.
This presentation focuses on two such problems: the Team Orienteering Problem (TOP) and the Prize-Collecting VRP (PCVRP). In the TOP, the goal is to maximize collected benefits while respecting distance constraints, whereas PCVRP seeks a balance between minimizing travel distance and uncollected benefits. We explore how to model and solve these problems using Hexaly, an optimization solver combining exact and heuristic methods.
Hexaly adopts a compact set-oriented modeling formalism. For routing problems the decision variables manipulated by the solver are lists, they are handled as permutations on dynamic subsets of the points. Each vehicle’s route is represented as a list. The solver provides built-in set-based operators to manage constraints and objectives. This approach allows for concise and scalable formulations, making it easy to incorporate additional constraints and objectives as needed.
Hexaly's solutions, after 60 seconds of computation, are within 1\% of the best known solutions on academic instances for those two problems. We will also show that the solver scales to industrial cases with more than 10,000 points.
Keywords
- Vehicle Routing
- Software
- Combinatorial Optimization
Status: accepted
Back to the list of papers