A higher resolution is required to access the IDE
- 21
Learning Opportunities
This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
Statement
Capacitated Vehicle Routing
In the Vehicle Routing Problem, you must serve a
set of customers with a fleet of vehicles.
In the Capacitated variant, vehicles have a limited capacity.
You must find the shortest possible set of tours.
In the Capacitated variant, vehicles have a limited capacity.
You must find the shortest possible set of tours.
Rules
- The vehicles start from the depot (index 0) and must return to it.
- Every customer must be visited exactly once.
-
For each tour, the sum of the demands of the customers visited must not exceed the capacity of the
vehicles.
- The distance between two points is Euclidean, rounded to the nearest integer: dist(a, b) = round(sqrt((xa - xb)2 + (ya - yb)2))
Game Input
The program must first read the given inputs, then output a single line representing the vehicle tours.
Input
Line 1: an integer n, the number of customers (+1 for the depot)
Line 2: an integer c, the capacity of the vehicles
Next n lines: 4 space-separated integers for each customer/depot
- index, the index of the customer (or 0 for the depot)
- x, the first coordinate of the customer or depot
- y, the second coordinate of the customer or depot
- demand, the customer's demand. The depot (index=0) has a demand of 0.
Output
A single line containing the tours separated by a semicolon.
Each tour must be the indices of the customers separated by a space.
The depot (0) should not be included in the output.
Constraints
Response time is limited to
Example
Given the input of the first test case:
5 10 -> n = 5, c = 10
0 0 0 0 -> depot at (0,0) - no demand
1 0 10 3 -> customer 1 at (0,10) demand=3
2 -10 10 3 -> customer 2 at (-10,10) demand=3
3 0 -10 3 -> customer 3 at (0,-10) demand=3
4 10 -10 3 -> customer 4 at (10,-10) demand=3
Some example outputs in the correct format:
5 10 -> n = 5, c = 10
0 0 0 0 -> depot at (0,0) - no demand
1 0 10 3 -> customer 1 at (0,10) demand=3
2 -10 10 3 -> customer 2 at (-10,10) demand=3
3 0 -10 3 -> customer 3 at (0,-10) demand=3
4 10 -10 3 -> customer 4 at (10,-10) demand=3
Some example outputs in the correct format:
-
1 2 3;4
The first vehicle goes 0 -> 1 -> 2 -> 3 -> 0. The second vehicle goes 0 -> 4 -> 0.
The distance is dist(0, 1) + dist(1, 2) + dist(2, 3) + dist(3, 0) + dist(0, 4) + dist(4, 0) = 10 + 10 + sqrt(500) + 10 + sqrt(200) + sqrt(200) ≈ 80.6. -
4 2 1 3
The first vehicle goes 0 -> 4 -> 2 -> 1 -> 3 -> 0.
This solution is invalid: the sum of demands is 3 + 3 + 3 + 3 > c = 10. -
1;2 4;3 2
This solution is invalid: Customer 2 is visited twice. -
1;3 4
This solution is invalid: Customer 2 is not visited. -
1 2;3 4
This solution is valid and optimal.
The distance is dist(0, 1) + dist(1, 2) + dist(2, 0) + dist(0, 3) + dist(3, 4) + dist(4, 0) = 10 + 10 + sqrt(200) + 10 + 10 + sqrt(200) ≈ 68.3.
Some Tips
-
The VRP is a classic NP-Hard problem. Finding an optimal solution is incredibly difficult, so you should use
approximation algorithms - time to bring out your favorite metaheuristics!
- Have you already solved the Travelling Salesman Problem ? If so, maybe you can reuse your code: every vehicle tour is basically a small TSP.
About the Test & Validation Instances
- The 4 benchmark instances are from the CVRPLib, specifically sets A and M. Their known optima is used to give you the optimality gap. Feel free to use other instances from the library to tune your algorithms.
- Validation instances will be similar but different to prevent hard-coded solutions.
A higher resolution is required to access the IDE