Variant: VRP with Time Windows and Capacity Constraints (TSP + Time Window + Knapsack)
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.
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
- instances/ - VRP problem instances
- models/ - Mathematical model formulations
- solutions/ - Optimal or best-known solutions
- misc/ - Utility scripts and visualization tools
-
Sun, B., et al. (2021). Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst. 4.
-
Sun, B., et al. (2022). The online knapsack problem with departures. Proc. ACM Meas. Anal. Comput. Syst. 6.
-
Federer, M., et al. (2022). Application benchmark for quantum optimization on electro-mobility use case. In 2022 IEEE Vehicle Power and Propulsion Conference (VPPC), pp. 1–6.