nVisionX'26 Design Challenge

Team RouteMind

Heterogeneous Fleet
Optimization

A Site-Dependent Capacitated Vehicle Routing Problem (SD-CVRP)
Solver for GHMC's Logistics

3,093 km Total Distance ~35.1 km/active vehicle avg
96 min Avg Turnaround Collection → SCTP → Return
220 Total Trips 100% GVP Coverage
2.5 Trips/Shift Per Active Vehicle Avg
Scope: 1,583 GVPs | Waste: 1,349 T/Day | Fleet: 88 Active Vehicles | CO₂ Intensity: 0.80 kg/T

Abstract

The rapid urbanization of Greater Hyderabad has created critical challenges in Municipal Solid Waste (MSW) logistics. This dissertation presents the development and implementation of a Site-Dependent Capacitated Vehicle Routing Problem (SD-CVRP) solver tailored for the complex road hierarchy of Indian metropolises.

Our approach integrates geospatial road-width constraints with a "Green Cascade" heuristic to optimize collection points, achieves 100% service coverage while reducing carbon intensity to 0.80 kg CO2/Tonne (Global Best-in-Class). The topology-aware routing reduced the 4T fleet dependencies, achieving a sustainable 2.5 trips/day schedule.

This report documents the end-to-end methodology, from raw data audit (correcting ~1,200 coordinate errors) to the final optimization logic.

Geospatial Solution

Optimized Route Network

16T (Arterial) 8T (Feeder) 4T (Last-Mile) | SCTP (Transfer) GVP (Waste)

Map Styling

16T
8T
4T
Routes
GVP
SCTP
Map BG

1. Introduction

1.1 Background

Effective MSW management is a cornerstone of sustainable urban development. For Hyderabad, a city characterized by a mix of historic narrow lanes and modern arterial highways, the logistical challenge is twofold: accessibility and efficiency. Conventional VRP models often fail because they treat the road network as homogenous, leading to infeasible routes where large compactors are sent to narrow "gullies".

1.2 Problem Statement

The objective is to minimize the total operational cost (proxy for CO2 emissions) for collecting 1,349 Tonnes of waste daily from 1,583 Garbage Vulnerable Points (GVPs), subject to:

Core Constraints

  • Heterogeneous Fleet: Limited inventory of 4T (Small), 8T (Medium), and 16T (Large) vehicles. (Click for Specs)
  • Site-Dependency: Large trucks cannot access roads narrower than specific thresholds. (Click to learn why)
  • Capacity Limits: Strict payload enforcement (Qk).
  • Time Windows: Operations limited to 8-hour shifts, enforcing multi-trip logic (Click for Detail).

The Data Challenge

An initial audit revealed critical quality issues in the provided dataset:

1,583 Total Points
1,269 Swapped Coordinates
(Click for Detail)
80% Error Rate

Detected Latitude > 75 (Longitude range). Fixed via `repair_dataset.py`.

1.3 Compliance Matrix

Mapping Design Brief requirements to solution features:

Requirement Solution Outcome
Minimize Travel Green-weighted costs 3,093 km
100% Service Assignment Constraint 1,583 GVPs
Site-Dependency OSM + Road Tier Logic Large trucks blocked
Traffic Congestion 1.4x-1.8x multipliers Peak delays modeled

2. Methodology and Data Strategy

Given the NP-Hardness of the SD-CVRP on a city-scale graph (1,583 nodes), a purely exact formulation was computationally infeasible. We developed a robust 5-Stage Pipeline:

The 5-Stage Data Science Pipeline

Click on each stage to learn more:

1

Data Mapping

Audit & Snap to OSM

2

Road Tagging

3-Tier Classification

3

K-Means

18 SCTP Zones

4

GA-SA Solver

Hybrid Optimization

5

Visualization

QGIS / Web Layers

2.1 Data Acquisition and Audit

The project utilized a raw dataset of 1,583 Garbage Vulnerable Points. An initial spatial audit using `audit_data.py` revealed significant quality issues:

Coordinate Swapping Logic

Anomaly: 1,269 records (80%) had Latitude > 75. Since Hyderabad is at ~17°N/78°E, these were inverted.

Fix: Automated swap applied: if lat > 75: lat, lon = lon, lat.

Outlier Rectification

Manual Review: Three specific points (IDs 4, 939, 1159) were found in Vikarabad and Medchal, >60km from the city center.

Action: These were manually removed to prevent routing skew.

2.2 Road Network Analysis (OSM)

We constructed a custom graph using OSMnx. Roads were categorized into a 3-Tier Hierarchy:

Tier OSM Tags Width Allowed Fleet
🟢 Arterial primary, secondary, tertiary >30 ft 16T, 8T, 4T
🟡 Residential residential, unclassified 15-30 ft 8T (16T if First-Mile*)
🔴 Narrow living_street, service, track <12 ft 4T Only

🎯 Smart Access Rule (100m Proximity)

*If a GVP on a Residential road is within 100 meters of an Arterial spine, it is flagged as "First-Mile Accessible." This allows 16T trucks to perform high-volume pickups at colony entrances without penetrating deep into narrow internal networks.

2.3 Algorithm Design: "Green Cascade"

The "Green Cascade" is a priority-based insertion heuristic designed to maximize the utility of the greenest vehicles first.

01

Priority Assignment (16T)

Solver filters for points accessible by 16T. It routes them first to minimize CO2/Ton.

02

Geometric Feasibility

Routes are overlaid on the OSM Graph. Any edge width violation triggers a rejection.

03

Cascade & Preemption

Rejected demand "cascades" down to the 8T fleet, and finally to the 4T fleet (the "catch-all").

Constraint Logic (Python Snippet)
def get_road_constraints(G, gvps):
    # ROAD CONSTRAINT LOGIC
    if highway in ['living_street']:
        return 4500 # Strict Limit
    elif highway in ['residential']:
        return 16000 # Upgraded (1-hop arterial check)
    else:
        return 16000 # Arterial
    
# Multi-Trip Factor
TRIPS_PER_VEHICLE = 3

2.4 Hybrid GA-SA Metaheuristic

To transcend the limitations of greedy heuristics, we implemented a Hybrid Genetic Algorithm (GA) + Simulated Annealing (SA) engine:

🧬 Genetic Algorithm (Global Search)

  • Chromosome: Permutation of 1,583 GVPs
  • Decoder: Split procedure segments tour into routes
  • Crossover: OX1 (Ordered Crossover)
  • Population: 50 individuals, 20 generations

🔥 Simulated Annealing (Local Refinement)

  • Applied to: Top 10% of offspring
  • Perturbations: Swap, 2-Opt moves
  • Cooling: T = T × 0.95 per iteration
  • Accept: Worse solutions with probability e^(-ΔCost/T)
Fitness Function: Cost = (Distance × Fuel_Factor) + (Uncollected × High_Penalty) + (Fleet_Violation × Penalty)

3. Mathematical Formulation

We formulate the problem as a Site-Dependent CVRP (SD-CVRP) on a complete graph \(G=(V, A)\).

3.1 Sets and Indices

  • \(V = \{0, 1, ..., N\}\): Set of nodes, where 0 is the Transfer Station (SCTP) and \(V' = V \setminus \{0\}\) are GVPs.
  • \(K = \{4T, 8T, 16T\}\): Set of vehicle types.
  • \(R_k\): Set of available vehicles of type \(k\).

3.2 Parameters

  • \(d_{ij}\): Travel distance between node \(i\) and \(j\) (km).
  • \(q_i\): Waste demand at node \(i\) (kg).
  • \(Q_k\): Payload capacity of vehicle type \(k\) (kg).
  • \(W_i\): Road width category of node \(i\).
  • \(A_k\): Set of accessible road categories for vehicle type \(k\).
  • \(E_k\): Emission factor for vehicle type \(k\) (kg CO2/km).

3.3 Decision Variables

  • \(x_{ijk}\): Binary variable, 1 if vehicle \(k\) travels from \(i\) to \(j\), 0 otherwise.
  • \(y_{ik}\): Binary variable, 1 if node \(i\) is serviced by vehicle \(k\).

3.4 Objective Function

Minimize the total Environmental Cost:

$$ \text{Minimize } Z = \sum_{k \in K} \sum_{v \in R_k} \sum_{(i,j) \in A} (d_{ij} \times E_k) \cdot x_{ijv} $$

3.5 Constraints

$$ \sum_{k \in K} y_{ik} = 1, \quad \forall i \in V' $$ (Assignment: Each GVP serviced exactly once)
$$ \sum_{i \in V} q_i y_{ik} \leq Q_k, \quad \forall k $$ (Capacity: Demand cannot exceed vehicle payload)
$$ y_{ik} = 1 \implies W_i \in A_k $$ (Road Accessibility: Vehicle must fit road width)
$$ \sum_{j \in V} x_{0jk} \leq \text{FleetCount}_k \times \text{Trips}_{max} $$ (Inventory & Shift Constraints: Multi-trip logic)

4. Results and Discussion

4.0 AI Optimization — Route Distance Trend

Running best route distance observed across all generated trips. Each point shows the shortest individual trip distance found up to that index — a proxy for solver quality over the optimization run.

4.1 Operational Verification

The topology-aware optimization achieved 100% service coverage with the following fleet breakdown:

Metric 16T 8T 4T Total
Physical Trucks 14 28 66 108
Trips Generated 28 56 136 220
Avg Trips/Truck 2.0 2.0 2.1 2.0
Waste Cleared (T) 426 448 476 1,349
Distance (km) 769 1,166 1,158 3,093
CO2 (kg) 423 408 232 1,063
Key Finding: The 4T fleet requires 2.1 trips/day average due to inventory constraints. The multi-trip scheduling logic (TRIPS_PER_VEHICLE = 3) ensures 100% clearance within 8-hour shifts.

4.2 Turnaround Time Analysis

Average time metrics per trip including loading, travel, and unloading:

Metric 16T 8T 4T
Avg GVPs/Trip 12 8 6
Loading Time (@ 10 min/GVP) 120 min 80 min 60 min
Unloading @ SCTP 20 min 15 min 10 min
Travel Time (@ 25 km/h) 40 min 30 min 20 min
Total Turnaround ~3 hrs ~2 hrs ~1.5 hrs
Assumption: Loading time = 10 min/GVP average. Unloading at SCTP = 10-20 min based on truck size. Travel speed = 25 km/h (urban avg).

Operational Load Distribution

Fleet Mix Analysis

4.2 CO2 Emission Efficiency

Emission Efficiency

The optimization successfully balanced the load. Current CO2 share by fleet is 22% for 4T, 40% for 16T, and 38% for 8T.

4.3 Zonal Excellence Leaderboard

Ranking transfer station efficiency based on finalized AI routes. Top performing zones achieve the highest waste-cleared to distance ratio.

4.4 Comprehensive Master Fleet Schedule

Detailed temporal analysis of all 220 routes across 18 zones, verifying multi-trip feasibility within an 8-hour shift.

Open High-Res PNG
Master Gantt Schedule

Scroll vertically to view all 108 available physical fleet slots. Active in this run: 88 vehicles with assigned trip sequences.

5. Conclusion and Limitations

5.1 Limitations

  • Traffic Data: The current model uses static Time-of-Day factors (1.2x, 1.8x). Real-time API integration would improve ETA accuracy.
  • Turnaround Time: The 2.1 trips/day 4T schedule assumes near-ideal turnaround at SCTPs (20 mins). Any delay at the transfer station will cascade, potentially extending shifts beyond 8 hours.

5.2 Strategic Recommendations

✅

Fleet is Sufficient

With 2.1 trips/day, the current fleet of 66 small trucks is sufficient.

🚧

Formalize Road Upgrades

Conduct a physical survey to validate that 16T trucks can access residential colonies.

5.3 Traffic Consideration (Subjective)

While real-time traffic data was not available, the model incorporates the following subjective traffic adjustments:

  • Peak-Hour Avoidance: Shift start at 6:00 AM ensures trucks operate before major congestion (8-10 AM).
  • Zone-Based Delay Coefficients: High-density zones (Jubilee Hills, Kukatpally) assigned 1.2× travel time multiplier.
  • Urban Speed Assumption: Conservative 25 km/h (vs. 40 km/h highway) to account for signals and traffic.
Future Enhancement: Integration with Google Maps Distance Matrix API for real-time travel times.

5.4 Model Scalability

The routing model is designed to scale efficiently:

Aspect Current Scalable To
GVPs 1,583 10,000+
Zones (SCTPs) 18 Dynamic K-Means
Fleet Types 3 Configurable
Computation Time ~30 sec O(n log n) per zone
Design Principle: K-Means decomposition ensures linear scalability. Adding 2× GVPs doubles zones, not computation complexity per zone.

End of Report Integration

Route Telemetry

Optimization STANDBY
Distance 0 km
Waste 0 T
Trips 0
CO2 0 kg
Telemetry Feed Active ● Routes: 220