Optimization Algorithm

Overview

The core optimization runs inside ClusterModel (src/optimizationModels/clusterModel/clusterModel.py). It takes a set of delivery orders, clusters them across time slots and geography, balances load across vans, attaches bike deliveries to van stops, and sequences routes via Route4me — retrying until an SLA target is met.

Top-Level Flow

flowchart TD
    Input([Input: orders, vans, shift]) --> S1["1. Preparation\nClassify orders & size fleet"]
    S1 --> S2["2. Van Route Planning\nCluster, sequence & verify SLA"]
    S2 --> S3["3. Bike Route Planning\nSequence bike pickup/delivery routes"]
    S3 --> S4Check{Box pickups\nneeded?}
    S4Check -->|Yes| S4["4. Box Pickup Routes\nRoute composed box pickups"]
    S4Check -->|No| S5
    S4 --> S5["5. Final Output\nAssemble response & calculate SLA"]
    S5 --> Response([Response])

Step Summary

Step	Title	Description
1	Preparation	Set up the optimization by classifying deliveries and determining fleet size
1.1	Order Classification & Fleet Sizing	Sort each delivery into van, bike, or bag type based on package count, then calculate the minimum number of vans needed
1.2	Bag Grouping	Group bag deliveries into physical boxes and assign a pickup point for each (only runs when bag orders are present)
2	Van Route Planning	Build and optimize van routes through geographic clustering, sequencing, and on-time delivery checks
2.1	Minimum Stop Enforcement	Ensure each van has enough stops per time slot; promote small bike deliveries to van deliveries if needed
2.2	Geographic Grouping	Cluster nearby deliveries within each time slot so each van covers a compact area
2.3	Van Assignment	Assign delivery clusters to specific vans across all time slots, minimizing total travel distance
2.4	Stop Redistribution	Move stops between vans so no van has too few deliveries in any time slot
2.5	Bike Attachment	Link each bike delivery to the nearest van stop, which serves as its pickup point
2.6	Capacity Balancing	Redistribute deliveries from overloaded vans until all are within capacity limits
2.7	Van Route Sequencing	Send each van's stops to Route4me to determine the optimal driving order
2.8	Delivery Target Check	Evaluate if routes meet the on-time delivery target (SLA); if not, split problem stops or add a van and retry from Step 2.1
3	Bike Route Planning	Build pickup-and-delivery routes for bike couriers
3.1	Bike Route Sequencing	Send each bike's pickup and dropoff pair to Route4me for optimal ordering
3.2	Bike Reassignment	If a bike route cannot be completed, reassign it to an earlier van stop and retry
4	Box Pickup Routes	Build routes for composed box pickups when bag orders are present
5	Final Output	Assemble all routes into the response and calculate the overall on-time delivery rate (SLA)

Step 1.1 — Order Classification & Fleet Sizing

At initialisation, each address (excluding depot) is classified:

Condition	Type
`pieces <= BIKE_BOXES_NUMBER`	bike candidate
`pieces > BIKE_BOXES_NUMBER`	normal (van)
`is_bag: true`	composed (handled by bag grouping in Step 1.2 before ClusterModel runs)

The minimum number of vans (min_car) is computed as:

min_car = ceil(total_pieces / (vehicle_capacity x PERCENTAGE_VEHICLE_CAPACITY))

Step 1.2 — Bag Grouping

When any address has is_bag: true, the bags module groups them into physical boxes before the main optimization begins.

flowchart LR
    BagOrders["Bag orders\n(fractional pieces)"] --> CalcBoxes["Calculate boxes needed\nceil(sum of pieces)"]
    CalcBoxes --> KMeans["Constrained K-Means\ngroup bags, sum <= 1.0 per cluster"]
    KMeans --> SelectParent["For each cluster:\nselect bag closest to centroid\nas parent (pickup stop)"]
    SelectParent --> BuildStructure["Build composed_boxes:\n{parent_id, children[]}"]
    BuildStructure --> ClusterModel["Feed into ClusterModel\nas normal orders"]

Each physical box becomes one stop on a van route. The box's children are delivered by a dedicated bike route from the parent stop.

Step 2 — Van Route Planning

Van route planning combines geographic clustering (Steps 2.1–2.6) with route sequencing and an SLA retry loop (Steps 2.7–2.8). The clustering pipeline runs once per attempt, and the retry loop repeats until the on-time delivery target is met.

Steps 2.1–2.6 — Clustering Pipeline

flowchart TD
    S2_1["2.1 Minimum Stop Enforcement\nPromote bike to van if\ntoo few van stops per slot"]
    S2_1 --> S2_2["2.2 Geographic Grouping\nK-Means per time slot"]
    S2_2 --> S2_3["2.3 Van Assignment\nPuLP linear programming:\nassign clusters to vans\nacross time slots"]
    S2_3 --> S2_4["2.4 Stop Redistribution\nMove stops to vans\nbelow MIN_NUMBER_STOPS"]
    S2_4 --> S2_5["2.5 Bike Attachment\nLink each bike order\nto nearest van stop"]
    S2_5 --> S2_6["2.6 Capacity Balancing\nRedistribute stops until\nall vans within capacity"]

Key clustering concepts

Geographic Grouping (Step 2.2): Orders are grouped by time_window_start. Within each slot, K-Means clusters them spatially so nearby deliveries share a van.

Van Assignment (Step 2.3): A linear program minimises the total distance vans travel between slots. It assigns the spatial clusters from each time slot to specific van IDs consistently across the whole shift.

Load balancing: After clustering, Step 2.4 ensures no van is below MIN_NUMBER_STOPS (prevents routes with too few stops) and Step 2.6 ensures no van exceeds vehicle_capacity pieces.

Steps 2.7–2.8 — Sequencing & SLA Retry Loop

flowchart TD
    Start(["Start Van Route Planning"]) --> WhileLoop{"SLA < target\nAND vans available?"}
    WhileLoop -->|No — done| End(["Return van routes"])
    WhileLoop -->|Yes — try| ForLoop{"Attempt 1, 2, or 3\n(max 3 per van count)"}
    ForLoop --> Cluster["Steps 2.1–2.6\nRun clustering pipeline"]
    Cluster --> S2_7["2.7 Van Route Sequencing\nCall Route4me"]
    S2_7 --> UnroutedCheck{Any vans\nunrouted?}
    UnroutedCheck -->|Yes| Retry["Retry Route4me\nwithout speed buffer"]
    UnroutedCheck -->|No| SlaCheck
    Retry --> SlaCheck{"2.8 Delivery Target Check\nSLA >= target?"}
    SlaCheck -->|Yes| End
    SlaCheck -->|No, attempts left| Split["Split furthest stop\ninto bike deliveries"]
    Split --> ForLoop
    SlaCheck -->|No, all attempts used| AddVan["Add one more van"]
    AddVan --> WhileLoop

The retry loop has two levels: - Outer loop: increments van count after exhausting split attempts, continues until the SLA goal is reached or available vans are exhausted. - Inner loop (up to 3 attempts): tries up to 2 satellite splits per van count. On each split, the stop furthest from its cluster centroid is converted into individual bike deliveries and the algorithm reruns from Step 2.1.

Intermediate routes created during failed attempts are deleted via Route4me.deleteRoute() before the loop exits.

Step 3 — Bike Route Planning

flowchart TD
    Start(["Start Bike Route Planning"]) --> S3_1["3.1 Bike Route Sequencing\nSend pickup/dropoff pairs\nto Route4me"]
    S3_1 --> UnroutedCheck{Any bikes\nunrouted?}
    UnroutedCheck -->|No| End(["Return bike routes"])
    UnroutedCheck -->|Yes| Retry["Retry Route4me\nwithout speed buffer"]
    Retry --> StillUnrouted{Still\nunrouted?}
    StillUnrouted -->|No| End
    StillUnrouted -->|Yes| S3_2["3.2 Bike Reassignment\nReassign to earlier van stop"]
    S3_2 --> S3_1

Bike route structure

Each bike order becomes two addresses in Route4me:

Pickup stop (at parent satellite location):
  - time_window: parent's projected_departure_time +/- 5 min - bike_service_overhead
  - service_time: BIKE_SERVICE_TIME

Dropoff stop (at the delivery address):
  - time_window: original order time window
  - service_time: original order time_service

Parent validation (`bike.check_sla()`)

Before building the route, each bike's parent is validated: 1. If the parent is unrouted by Route4me, the bike is reassigned to the closest stop in a valid time slot. 2. If no valid time slot exists, the parent is set to -1 (warehouse) and the bike is picked up from the depot. 3. If the parent's SLA is failing (arrived too late), the bike is reassigned to the nearest earlier stop on the route.

Step 4 — Box Pickup Routes

When bag orders are present (Step 1.2 produced composed boxes), dedicated routes are built for the box pickups. Each composed box group gets a route linking the parent pickup stop to its child delivery addresses.

Step 5 — Final Output & SLA Calculation

SLA is computed in finalJson.createOutput() after all routing is complete.

estimated_sla = len(fulfilled) / (len(fulfilled) + len(delayed))

A stop is fulfilled when:

projected_arrival_time < time_window_end + SLA_THRESHOLD_FINAL

A stop is delayed if it exceeds that threshold, and unrouted if Route4me returned is_unrouted: true for it.

Time window fallback

Route4me occasionally returns null for time_window_start or time_window_end. The system infers them from the projected arrival time:

Condition	Inferred window
`projected_arrival <= 46800s` (13:00)	09:00–13:00
`projected_arrival > 46800s`	15:00–18:00
Warehouse stop (`order_id = 1`)	Adds 900 s (15 min) buffer to end

Key Configuration Parameters

Parameter	Effect
`SLA_VANS_GOAL`	Target SLA ratio; loop exits when this is met
`SLA_THRESHOLD_VANS`	Seconds of slack applied during van routing SLA checks
`SLA_THRESHOLD_FINAL`	Seconds of slack for the final output SLA calculation
`MIN_NUMBER_STOPS`	Minimum stops per van per time slot; bike-to-normal promotions enforce this
`PERCENTAGE_VEHICLE_CAPACITY`	Fraction of `vehicle_capacity` actually used (e.g. `0.9` = 90%)
`PERCENTAGE_VAN_SLOWDOWN`	Travel time buffer for vans (Route4me `slowdowns.travel_time`)
`PERCENTAGE_BIKE_SLOWDOWN`	Travel time buffer for bikes
`CONVEX_OPTIMIZATION_TIME_LIMIT`	Max seconds the PuLP LP solver may run
`BIKE_BOXES_NUMBER`	Max pieces for a stop to be eligible for bike delivery
`BIKE_SERVICE_TIME`	Total seconds at the parent stop for bike pickup
`SERVICE_TIME_OVERLAP`	Seconds of overlap between van service and bike pickup at the same stop