Vehicle Routing
Overview
The Vehicle Routing Problem (VRP) is a classic logistics optimization problem combining aspects of the Traveling Salesman Problem, time window scheduling, and knapsack constraints. It has direct applications in delivery services, supply chain management, and transportation planning.
Problem Description
Given:
- A fleet of $k$ vehicles, each with capacity $X$
- A central depot
- A set of customers $C = \{1,\ldots,n\}$ with demands $d_i$ for $i \in C$
- Time windows for each customer
- Distance/cost matrix between all locations
Objective: Determine routes for all vehicles to serve all customers while:
- Respecting vehicle capacity constraints
- Satisfying time window requirements
- Minimizing total distance or cost
Instance Parameters:
- $k = 4$ vehicles
- $n = 20$ customers
Performance
Runtime to reach best-known objective
Sorted instances vs total runtime. A point (x, y) means x instances were solved within y seconds. Solid line + filled circle = proven exact; dashed line + open diamond = heuristic. Lower-right is better.
Time-to-solution (TTS) to reach best-known objective
Same as the runtime cactus but uses the reported Time-to-Solution rather than total runtime. Solid = exact, dashed = heuristic.
Solution quality (performance profile)
Share of instances each group brings within a given optimality gap of the best-known objective. Higher is better; the value at “best” is the share solved exactly.
Runtime scaling with instance size
Fastest feasible runtime (log scale) per instance versus Customers — shows how each group scales.
Submissions
(1)
| Method | Submitter | Type | Date | Instances |
|---|---|---|---|---|
| MemeticGA_LoopUntilFeasible | Othmane El Yaakoubi | Classical | 2026-07-21 | 110 |