MAS Active Controline — Bus Routing Optimizer

Performance Summary

Baseline Cost (No Optimisation)

—

Direct point-to-point routing

Optimised Cost (OR-Tools CVRP)

—

Buses Deployed

—

CO₂ Emissions Saved

—

kg CO₂ saved this shift @ 0.67 kg/km diesel

Route Visualisation Loading...

Real road-traced routes via OSRM. The depot is shown in orange. Passenger stops are shown in blue. Each coloured line represents a unique bus route.

Depot Stops Optimised Routes

Optimisation Methodology

This system solves a real-world logistics problem using classical Operations Research, powered by Google OR-Tools. Below is a full walkthrough of the model formulation, solver technique, and constraints applied.

Step 1

Problem Formulation — Capacitated Vehicle Routing Problem (CVRP)

The transport scheduling problem is modelled as a Capacitated Vehicle Routing Problem (CVRP) — one of the most well-studied problems in combinatorial optimisation and Operations Research.

▣

Single Depot
All buses originate from and return to the MAS Controline Pallekele factory. This is the depot node in the graph.

●

99 Passenger Stops
Each stop has a fixed passenger demand (workers to collect or drop). The solver must decide which bus visits which stops.

▪

Homogeneous Fleet
All buses are identical — same seat capacity. The solver allocates the minimum number of buses needed to cover all stops.

◎

Objective Function
Minimise the total distance (km) travelled by the entire fleet across all routes combined for a single shift.

Minimise: ∑_k ∑_i ∑_j d_ij · x_ijk where d_ij = real road distance between stop i and j, x_ijk = 1 if bus k travels from i to j

Step 2

Real Road Distance Matrix via OSRM

Straight-line (Haversine) distances are fundamentally inaccurate for Sri Lanka's mountainous terrain. The Kandy district has steep hills and winding roads where a 5 km straight line can be a 15 km road journey.

◈

OSRM Table API
The Open Source Routing Machine (OSRM) is called with all 100 coordinates (1 depot + 99 stops) to produce a 100×100 pairwise road distance matrix in a single API call.

═

OpenStreetMap Data
OSRM uses real OpenStreetMap road network data — actual driving routes, road types, and speeds. All distances are in kilometres.

↻

LRU Caching
The distance matrix is cached in memory. Re-running the optimiser with different fleet/capacity/cost parameters reuses the same matrix — no repeated API calls.

⊘

Pre-filtering
Before solving, any stop whose road distance from the depot exceeds the user-set one-way limit is excluded before entering the solver — reducing problem size.

Step 3

Constraints Applied to the Model

Three hard constraints are enforced. No solution that violates any of these is accepted by the solver.

Seat Capacity Constraint

The total passenger demand assigned to any single bus cannot exceed its seat capacity. Formally: ∑ demand(i) ≤ capacity for all stops i on that bus's route. This is enforced using OR-Tools' AddDimensionWithVehicleCapacity.

Maximum Route Distance Constraint

Each bus route has a total distance cap of 3× the one-way limit. This models a real-world commute time ceiling — workers should not be on a bus for an unreasonable duration. Enforced via OR-Tools' Distance Dimension.

Fleet Size Constraint

The number of active routes cannot exceed the user-specified fleet size. Rather than silently adding more buses, the solver uses AddDisjunction to make stops optional with a high penalty — dropping the least-accessible stops when the fleet is insufficient instead of exceeding the limit.

Step 4

Solver Engine — Google OR-Tools Routing API

The CVRP is NP-Hard — meaning an exact optimal solution for 99 stops is computationally infeasible in real time. OR-Tools uses a two-phase heuristic + metaheuristic strategy to find a near-optimal solution within a fixed time limit.

Phase 1

Constructive Heuristic — Path Cheapest Arc

Builds an initial feasible solution by always extending the current partial route to the nearest unvisited stop. Fast and greedy — guarantees a valid starting point but not optimality. Acts as the seed for Phase 2.

→

Phase 2

Metaheuristic — Guided Local Search (GLS)

Iteratively improves the Phase 1 solution by exploring neighbouring solutions (swap stops between routes, re-order within routes). GLS uses penalty terms to escape local optima — it penalises frequently visited solution features to force exploration of new areas of the search space. Runs for 4 seconds.

Note: Why GLS over simpler local search? Simple hill-climbing gets trapped in local optima (a good solution that cannot be improved by small changes, but is not globally optimal). GLS's penalty mechanism forces the solver to explore beyond local optima, consistently producing better final solutions.

Step 5

Baseline Comparison — Measuring the Saving

To quantify how much the optimiser saves, we compare against a naive baseline: sending one dedicated bus directly from the depot to each stop and back — no shared routes, no grouping. This is the worst-case scenario that represents an unoptimised operation.

┃

Baseline Distance
Sum of all individual round trips: ∑ (depot→stop + stop→depot) for every active stop. Uses real OSRM road distances.

✓

Optimised Distance
Total kilometres driven by the entire fleet under the CVRP solution — buses share routes and collect multiple stops in one trip.

Financial Saving
(Baseline − Optimised) × Operating Cost/km. Reported in LKR per shift. Directly represents daily fuel and operational savings.

↓

CO₂ Saving
Saved km × 0.67 kg CO₂/km (standard diesel bus emission factor). Quantifies the environmental benefit of route consolidation.

How Google OR-Tools Works — Under the Hood

Google OR-Tools is an open-source Operations Research library developed by Google. It provides solvers for optimisation problems including linear programming, constraint programming, vehicle routing, and graph algorithms. Below is a detailed breakdown of exactly how OR-Tools is used in this project — from mathematical formulation to code implementation.

Overview

What is Google OR-Tools?

Google OR-Tools (Operations Research Tools) is a free, open-source software suite developed by Google's Optimization Team. It is written in C++ with bindings for Python, Java, and C#. OR-Tools provides state-of-the-art algorithms for solving combinatorial optimisation problems that are too complex for brute-force approaches.

■

OR-Tools Library

Core C++ engine with Python wrapper (ortools package)

→

⚙

Constraint Solver

pywrapcp — the constraint programming routing solver

→

⟶

Routing API

RoutingModel + RoutingIndexManager

→

✓

Solution

Optimised routes assigned to each vehicle

Reference: Key Modules Used in This Project:
from ortools.constraint_solver import routing_enums_pb2, pywrapcp

• pywrapcp — Python wrapper around OR-Tools' C++ constraint programming solver
• routing_enums_pb2 — Protocol buffer enums for configuring search strategies
• RoutingIndexManager — Maps between solver's internal indices and user-defined node IDs
• RoutingModel — The main model object that holds variables, constraints, and the objective

Part A

Decision Variables — What the Solver Decides

In any optimisation problem, decision variables are the unknowns that the solver must assign values to. In the CVRP solved by OR-Tools, the solver decides which bus visits which stops and in what order.

Variable	Notation	Type	What It Means
Route assignment	x_ijk	Binary (0 or 1)	= 1 if bus k travels directly from stop i to stop j; 0 otherwise
Next variable	NextVar(i)	Integer	OR-Tools' internal representation — for each node i, stores the index of the next node visited by the same bus
Vehicle assignment	VehicleVar(i)	Integer	Which bus (0 to K−1) visits node i

≫ Code ↔ Math Mapping

                        manager = pywrapcp.RoutingIndexManager(n, effective_fleet, 0)
                        Creates the index manager: n nodes, effective_fleet buses, depot at node 0
                    
                        routing = pywrapcp.RoutingModel(manager)
                        Creates the routing model — this object holds all decision variables, constraints, and the objective function internally
                    
                        solution.Value(routing.NextVar(idx))
                        Reads the solver's decision: "after visiting node idx, which node does this bus visit next?"

Part B

Objective Function — What the Solver Minimises

The objective function is the mathematical expression that the solver tries to minimise (or maximise). In our CVRP, the objective is to minimise the total distance travelled by all buses combined across all routes.

OBJECTIVE FUNCTION Minimise

min Z = ∑_k=1^K ∑_i=0ⁿ ∑_j=0ⁿ d_ij · x_ijk

Z Total distance driven by the entire fleet (the value to minimise)

K Number of buses in the fleet

n Number of stops (nodes), including depot at index 0

d_ij Real road distance from stop i to stop j (from OSRM, in metres)

x_ijk Binary variable = 1 if bus k travels from i to j, else 0

≫ How This Is Set in Code

                        def distance_callback(from_index, to_index):
                        This function returns dij — the road distance between any two nodes
                    
                          return dist_int[manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]
                        Looks up the pre-computed OSRM distance matrix (integers, in metres)
                    
                        transit_cb = routing.RegisterTransitCallback(distance_callback)
                        Registers the distance callback with OR-Tools — the solver will call this millions of times during search
                    
                        routing.SetArcCostEvaluatorOfAllVehicles(transit_cb)
                        THIS IS THE OBJECTIVE FUNCTION. It tells OR-Tools: "minimise the sum of all arc (edge) costs across all vehicles." The arc cost is the distance callback.

Note: In plain English: OR-Tools doesn't require you to write min Z = ... explicitly. Instead, you register a cost callback function using SetArcCostEvaluatorOfAllVehicles(), and OR-Tools automatically minimises the total sum of those costs across all routes. This is the implicit objective function.

Part C

Constraints — The Rules the Solver Must Obey

Constraints are hard rules that every valid solution must satisfy. If a solution violates any constraint, OR-Tools rejects it. There are three explicit constraints and several implicit ones built into the Routing API.

C1 Vehicle Capacity Constraint

∑_{i ∈ Route(k)} q_i ≤ Q_k ∀ k ∈ {1, ..., K}

q_i = passenger demand at stop i Q_k = seat capacity of bus k Route(k) = set of stops visited by bus k

In plain English: The total number of passengers picked up by any single bus cannot exceed its seat capacity. If a bus has 50 seats, the sum of passengers across all stops on that bus's route must be ≤ 50.

≫ Implementation in Code

                                def demand_callback(from_index):
                                Returns qi — passengers waiting at each stop
                            
                                  return demands[manager.IndexToNode(from_index)]
                                Looks up the demand array (depot = 0, stops = random 5–25)
                            
                                routing.AddDimensionWithVehicleCapacity(demand_cb, 0, capacities, True, 'Capacity')
                                Enforces C1. Parameters: callback, slack=0, max per vehicle=capacities list, start_cumul_to_zero=True, name='Capacity'

C2 Maximum Route Distance Constraint

∑_{(i,j) ∈ Route(k)} d_ij ≤ D_max ∀ k ∈ {1, ..., K}

d_ij = road distance from stop i to stop j D_max = 3 × (Max One-Way Distance)

In plain English: Each bus's total round-trip distance (depot → stops → depot) cannot exceed 3× the one-way limit. If Max One-Way is 30 km, each route is capped at 90 km total. This prevents workers from spending excessive time commuting.

≫ Implementation in Code

total_budget_km = max_oneway_km * 3 D_max = 3 × user-set one-way limit (e.g. 30 km → 90 km budget)

                                routing.AddDimension(transit_cb, 0, int(total_budget_km * 1000), True, 'Distance')
                                Enforces C2. Creates a "Distance" dimension tracking cumulative distance per route, capping it at Dmax (in metres)
                            

C3 Fleet Size Constraint (Soft, with Penalties)

Number of active routes ≤ K_max (fleet size)

If demand > fleet capacity, OR-Tools drops least-critical stops instead of adding extra buses

In plain English: The solver cannot use more buses than the user specifies. When the fleet is insufficient to serve all stops, OR-Tools uses a disjunction mechanism — it makes each stop "optional" with a high penalty for dropping. The solver will prefer to serve all stops, but mathematically may drop some if constrained.

≫ Implementation in Code

drop_penalty = int(total_budget_km * 1000 * 20) Very high penalty (cost) for dropping a stop — the solver avoids this unless absolutely necessary

                                routing.AddDisjunction([manager.NodeToIndex(node_idx)], drop_penalty)
                                Enforces C3. Makes each stop optional. If the solver drops stop i, it incurs drop_penalty added to the objective — forcing the solver to serve as many stops as possible
                            

Implicit Constraints (Built Into OR-Tools Routing API)

↺

Each stop visited exactly once
The Routing API guarantees that no two buses visit the same stop. Each stop appears on exactly one route (unless dropped via disjunction).

△

All routes start and end at depot
Every bus begins at node 0 (the factory depot) and must return to node 0 after serving all its assigned stops.

⟷

Route continuity
Each route is a connected sequence of nodes — the bus must travel through consecutive arcs (edges) without teleporting.

Non-negative distances
All arc costs (distances) must be ≥ 0. This is satisfied by using real road distances from OSRM.

Part D

The OR-Tools Solver Pipeline — Step by Step

When routing.SolveWithParameters(params) is called, OR-Tools executes a multi-stage pipeline internally. Here is exactly what happens:

Model Construction

OR-Tools builds an internal graph with n nodes and n × n edges. Each edge has a cost (distance). Decision variables (NextVar) are created for each node — one per node per vehicle.

RoutingIndexManager(n, K, 0) — creates the node-to-index mapping

Constraint Propagation

Before searching, OR-Tools performs domain reduction — it eliminates impossible assignments based on the constraints. For example, if a stop's demand exceeds bus capacity, that stop cannot be the only stop on any route (it must be dropped). This dramatically reduces the search space.

Phase 1: Initial Solution — Path Cheapest Arc

A constructive heuristic builds the first feasible solution. Starting from the depot, it greedily extends the current route by always choosing the nearest unvisited stop that doesn't violate any constraint. When a bus is full or its distance budget is exhausted, a new bus starts.

params.first_solution_strategy = FirstSolutionStrategy.PATH_CHEAPEST_ARC

Note: This runs in O(n²) time — very fast, but produces a suboptimal "greedy" solution.

Phase 2: Improvement — Guided Local Search (GLS)

Starting from the Phase 1 solution, OR-Tools applies local search operators — small modifications that try to improve the total distance:

2-opt Reverses a segment within a single route to uncross paths

Or-opt Moves 1–3 consecutive stops from one position to another within the same route

Relocate Moves a stop from one bus's route to another bus's route

Exchange Swaps stops between two different bus routes

Cross Swaps tails of two routes — repartitions stops between buses

Guided Local Search (GLS) adds penalty terms to frequently used edges. When the solver gets stuck in a local optimum (no single move improves the solution), GLS penalises the most-used edges, making the solver temporarily "forget" them and explore different route structures. This escapes local optima and finds better solutions.

params.local_search_metaheuristic = LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH

Time Limit & Solution Extraction

Phase 2 runs iteratively until the 4-second time limit expires. The best solution found is returned. Routes are extracted by following the NextVar chain for each vehicle from routing.Start(vid) to routing.IsEnd(idx).

params.time_limit.FromSeconds(4)

Part E

Complete Data Flow — From Raw Data to Optimised Routes

This diagram shows the complete end-to-end flow of how data moves through the system, from the user interface through the OR-Tools solver and back to the map visualisation.

◧

Input Data

99 stops with coordinates + passenger demands per shift

→

◉

OSRM API

100×100 real road distance matrix (km)

→

⊘

Pre-filtering

Drop stops beyond one-way distance limit

↓

◈

Map Rendering

DeckGL + OSRM route geometry tracing

←

☰

Solution Extraction

Follow NextVar chains → bus routes + KPIs

←

⚙

OR-Tools Solver

CVRP: Cheapest Arc → GLS (4s) → Best routes

Part F

Why Google OR-Tools? — Comparison with Alternatives

Several tools exist for solving vehicle routing problems. Here's why Google OR-Tools was chosen for this project.

Feature	Google OR-Tools	Gurobi / CPLEX	Manual Heuristic
Cost	Free & Open Source	Commercial License	Free
CVRP Support	Built-in Routing API	Manual formulation	Must code from scratch
Solution Quality	Near-optimal (GLS)	Optimal (exact)	Poor (greedy)
Speed (99 stops)	~4 seconds	Minutes to hours	Milliseconds
Python Integration	Native `pip install`	Complex setup	Native Python
Scalability	1000+ nodes	Limited by license	Degrades fast

Conclusion: Google OR-Tools provides the best balance of solution quality, speed, ease of use, and zero licensing cost — making it ideal for this real-world CVRP application in a factory transport context.

Summary

Key OR-Tools API Calls Used in This Project

Below is a complete reference of every OR-Tools API call made in optimizer.py and what each one does mathematically.

RoutingIndexManager(n, K, 0)

Create index manager mapping n nodes to K vehicles with depot at node 0

RoutingModel(manager)

Instantiate the CVRP model (creates all internal decision variables)

RegisterTransitCallback(fn)

SetArcCostEvaluatorOfAllVehicles(cb)

Set the objective function — minimise ∑ d_ij · x_ijk over all arcs and vehicles

RegisterUnaryTransitCallback(fn)

AddDimensionWithVehicleCapacity(cb, 0, caps, True, name)

Add capacity constraint — cumulative demand per route ≤ vehicle capacity

AddDimension(cb, 0, max, True, name)

Add distance constraint — cumulative distance per route ≤ D_max

AddDisjunction([node], penalty)

Make node optional — solver can skip it by paying the penalty cost

SolveWithParameters(params)

Execute the solver pipeline (heuristic → metaheuristic → return best solution)

solution.Value(routing.NextVar(idx))

Read the solution: "which node does bus visit after node idx?"

Synthetic Data Generation Pipeline

MAS Active Controline Pallekele employs approximately 2,500 workers across two shifts (morning and afternoon). Since real employee home-address data is confidential, this system generates a realistic synthetic dataset scaled to match the actual factory headcount of ~2,500 workers. The pipeline has four stages.

Stage 1

Coordinate Generation — Random Sampling Within Radius

Random geographic coordinates are generated uniformly within a user-configurable recruitment radius (default 40 km) around the MAS Controline Pallekele factory (7.2842°N, 80.7061°E). A bounding box is sampled first, then a Haversine distance filter discards points outside the circular radius — ensuring all stops are realistically reachable from the factory.

Note: Why uniform distribution? Workers in a real factory live spread across the surrounding area without a strong geographic bias. A uniform distribution across the radius approximates this spread. A pool of 5× the required stops is generated to ensure enough valid candidates survive the road-snapping step.

Stage 2

Road Snapping — OSRM Nearest API (Parallel)

Raw random coordinates often land in fields, rivers, or buildings — locations that cannot be reached by road. Each coordinate is submitted to the OSRM Nearest API, which snaps it to the closest drivable road point on the OpenStreetMap network.

⇆

40 Parallel Threads
All road-snap requests are fired simultaneously using Python's ThreadPoolExecutor. This reduces dataset generation from ~2 minutes (sequential) to ~8–12 seconds.

▸

100% Routable Stops
Only road-snapped coordinates are accepted. Any snapped point that exceeds the radius limit is discarded. Fallback coordinates near the depot pad the dataset if too few candidates survive.

◈

OpenStreetMap Network
OSRM uses the Sri Lanka road network from OSM — including A-grade, B-grade, and local roads in the Kandy district. All snapped stops are reachable by standard bus.

≡

Area Name Labelling
Each accepted stop is assigned a real Kandy district area name (99 names pre-loaded) for realistic readability, shuffled randomly using the seed.

Stage 3

Demand Generation — Scaled to ~2,500 Total Headcount

For each stop, raw passenger demand is generated independently for two worker groups — morning shift and afternoon shift — using a Discrete Uniform Distribution U[5, 25]. These raw values are then proportionally scaled so that each shift totals ~1,250 workers (morning + afternoon = ~2,500 total headcount, matching the real MAS Controline Pallekele factory workforce). The drop demands are derived (not independently randomised) to enforce real-world logical consistency.

Morning Shift Group (randomly generated)

Demand_10AM_Collect ~ U[5, 25] — buses collect these workers from home at 10 AM.
Demand_2PM_Drop = Demand_10AM_Collect — the same workers are dropped home at 2 PM. No independent value is generated.

Afternoon Shift Group (randomly generated)

Demand_2PM_Collect ~ U[5, 25] — buses collect these workers from home at 2 PM.
Demand_10PM_Drop = Demand_2PM_Collect — the same workers are dropped home at 10 PM. No independent value is generated.

Note: Seed behaviour: The first page load uses seed 42 (reproducible, consistent demo). Each click of "Regenerate Dataset" uses a time-based seed — producing genuinely different passenger distributions to simulate day-to-day variation in attendance.

Stage 4

Shift Structure — Four Optimisable Transport Events per Day

10:00 AM

COLLECT ↑

Morning shift workers picked up from home stops and transported to factory

2:00 PM

DROP ↓

Same morning shift workers dropped back to their home stops from factory

2:00 PM

COLLECT ↑

Afternoon shift workers picked up from home stops and transported to factory

10:00 PM

DROP ↓

Same afternoon shift workers dropped back to their home stops from factory

Note: Each of the four shift events is independently optimisable — select any shift in the sidebar to run the CVRP solver for that specific transport event. Route plans, bus deployments, and cost savings are computed per-shift.

Passenger Dataset ~2,500 employees

All 99 destination stops within the selected radius with simulated daily passenger demand per shift. Demands are scaled to match the real factory headcount of approximately 2,500 workers across two shifts (~1,250 morning shift + ~1,250 afternoon shift).

Loading dataset...