Task 4 — Capacity-Constrained Route Planning
Objective
Create delivery routes for vehicles with limited capacity.
Each delivery location has:
ID
Demand
Vehicles start and finish at a common depot.
Every delivery location must be visited exactly once.
A vehicle must never carry more demand than its capacity.
The objective is to minimize:
TotalRouteCost
Locations
Use:
DEPOT
L01
L02
L03
L04
L05
L06
Demand
L01 = 4
L02 = 6
L03 = 3
L04 = 7
L05 = 5
L06 = 2
Total demand:
27
Vehicles
Use three identical vehicles:
V01 Capacity=10
V02 Capacity=10
V03 Capacity=10
Total available capacity:
30
Route Cost Matrix
Use the following symmetric costs:
DEPOT L01 L02 L03 L04 L05 L06
DEPOT 0 4 6 3 8 7 5
L01 4 0 5 3 7 6 4
L02 6 5 0 4 3 5 6
L03 3 3 4 0 6 4 2
L04 8 7 3 6 0 4 7
L05 7 6 5 4 4 0 3
L06 5 4 6 2 7 3 0
Models
type DeliveryLocation struct {
ID string
Demand int
}
type Vehicle struct {
ID string
Capacity int
}
A route may be represented as:
type Route struct {
VehicleID string
Locations []string
TotalDemand int
Cost int
}
Overall result:
type RoutePlan struct {
Routes []Route
TotalCost int
Valid bool
}
Route Rules
Every used route must:
start at DEPOT
visit one or more delivery locations
return to DEPOT
For example:
DEPOT -> L01 -> L03 -> L06 -> DEPOT
Capacity
For every vehicle:
sum of demands on route <= vehicle capacity
Example:
L01 = 4
L03 = 3
L06 = 2
Total = 9
which fits capacity 10.
Complete Coverage
Every location:
L01 through L06
must appear exactly once across all routes.
The solution is invalid if a location is:
missing
visited twice
Route Cost
Route cost is the sum of every traversed edge.
Example:
DEPOT -> L03 -> L06 -> DEPOT
Cost:
DEPOT -> L03 = 3
L03 -> L06 = 2
L06 -> DEPOT = 5
Total = 10
Optimization Goal
Find a valid plan with minimum:
TotalCost
Number of Vehicles
The implementation does not need to use every available vehicle.
Example:
three vehicles exist
but if two vehicles can legally serve all locations and produce a lower total cost, using two is allowed.
However, capacity still applies.
In the provided base dataset:
Total Demand = 27
Vehicle Capacity = 10
therefore at least three vehicles are required.
Deterministic Tie-Breaking
If several plans have the same minimum cost:
- prefer fewer used vehicles
- sort routes by VehicleID
- compare route location sequences lexicographically
Validation
Reject invalid input where:
duplicate location ID
duplicate vehicle ID
negative demand
vehicle capacity <= 0
unknown matrix location
negative route cost
non-zero diagonal cost if your representation requires zero
missing cost between required locations
Impossible Case
The plan is impossible if any single location has demand larger than every vehicle capacity.
Example:
L07 Demand=14
maximum vehicle capacity = 10
No route can legally contain L07.
Additional Small Test Case
Locations:
A Demand=4
B Demand=4
C Demand=2
Vehicle capacity:
6
Vehicles:
V1
V2
A valid split is:
V1: A + C = 6
V2: B = 4
while:
A + B = 8
is invalid.
Important Note
This task intentionally uses a small dataset.
Route planning grows combinatorially.
The goal is to implement exact optimization for manageable inputs rather than build a production vehicle-routing engine.
Optional Extension — Vehicle-Specific Cost
Different vehicles may have different travel costs.
For example:
large truck fuel multiplier = 1.25
small van fuel multiplier = 1.00
Route cost then depends on both:
path
vehicle
Optional Extension — Time Windows
Each location may define:
EarliestArrival
LatestArrival
ServiceDuration
A route becomes valid only if every delivery occurs within its allowed time window.
Goal
This task combines:
partitioning
capacity constraints
graph cost
route ordering
global optimization
The implementation must optimize both:
which locations belong together
and:
in which order they are visited