Routing Algorithm

Overview

MND’s routing algorithm combines 4 distinct strategies to find the best path from origin to destination. The system balances three key factors:

Total Time

Minimize journey duration including wait time

Cost

Prefer free bus routes over paid local transport

Convenience

Reduce transfers and walking distance

The 4 Routing Strategies

The algorithm runs all 4 strategies in parallel, then selects the top 2-3 options to present to the user.

Strategy 1: Direct Bus Route

Overview
Algorithm
Example

Find a single bus that serves both origin and destination stops, with no transfers required.

Advantages

✅ Zero cost (free university buses)
✅ No transfers (simplest route)
✅ Predictable schedule

Example

TILAGOR → [Bus 1 @ 08:25] → CAMPUS
Time: 45 minutes | Cost: 0 BDT | Transfers: 0

Implementation

private async directBusRoute(
    route: Route,
    from: string,
    to: string,
    requestTime: string
): Promise<RouteOption | null> {
    // Iterate through all trips on this route
    for (const trip of route.trips) {
        const fromIndex = trip.stops.indexOf(from);
        const toIndex = trip.stops.indexOf(to);
        
        // Check if both stops are on this trip in correct order
        if (fromIndex === -1 || toIndex === -1 || fromIndex >= toIndex) {
            continue;
        }
        
        // Calculate departure time from origin
        const hopsBefore = fromIndex;
        const tripStart = parseTime(trip.departure_time);
        const tripStartMin = timeToMinutes(tripStart);
        
        // Estimate time to reach 'from' stop (5 min per hop)
        const timeToFrom = hopsBefore * 5;
        const departureMin = tripStartMin + timeToFrom;
        
        // Check if this departure is after requested time
        const requestMin = timeToMinutes(parseTime(requestTime));
        if (departureMin < requestMin) {
            continue; // Bus already departed
        }
        
        // Calculate travel time
        const hops = toIndex - fromIndex;
        const travelTime = hops * 5; // 5 min average per hop
        const arrivalTime = addMinutes(trip.departure_time, timeToFrom + travelTime);
        const departureTime = addMinutes(trip.departure_time, timeToFrom);
        
        // Create route option
        return {
            label: `${route.name} Direct`,
            category: 'fastest',
            type: 'direct',
            transfers: 0,
            totalTimeMin: travelTime + (departureMin - requestMin),
            totalCost: 0,
            legs: [{
                mode: 'bus',
                route_id: route.route_id,
                trip_id: trip.trip_id,
                from, to,
                departure: departureTime,
                arrival: arrivalTime,
                durationMin: travelTime,
                cost: 0
            }]
        };
    }
    return null;
}

Source: MND-backend/src/core/planner.ts:76-142

Real Route Example

Request:

GET /api/routes?from=TILAGOR&to=CAMPUS&time=08:20

Response:

{
  "from": "TILAGOR",
  "to": "CAMPUS",
  "requestTime": "08:20",
  "options": [
    {
      "label": "Bus 1 Direct",
      "category": "fastest",
      "type": "direct",
      "transfers": 0,
      "totalTimeMin": 50,
      "totalCost": 0,
      "legs": [
        {
          "mode": "bus",
          "route_id": "bus1",
          "trip_id": "bus1_0825",
          "from": "TILAGOR",
          "to": "CAMPUS",
          "departure": "08:25",
          "arrival": "09:10",
          "durationMin": 45,
          "cost": 0
        }
      ]
    }
  ]
}

Route Visualization:

08:20 ⏰ Request time
08:25 🚌 Bus 1 departs TILAGOR (5 min wait)
  ↓   🛣️ Travel through: SHIBGONJ, NAIORPUL, KUMARPARA...
09:10 🏫 Arrive at CAMPUS

Total: 50 minutes (5 min wait + 45 min travel)
Cost: FREE

Strategy 2: Bus + Local Hybrid

Overview
Algorithm
Example

Take a bus as far as possible, then use local transport (CNG/rickshaw) for the final segment.

When to Use

✅ Destination not directly served by bus
✅ Reduces wait time (get off earlier, take local)
✅ Balances cost and speed

Example

NAIORPUL → [Bus 3 @ 08:30] → SUBIDBAZAR → [CNG] → HOSPITAL
Time: 35 minutes | Cost: 40 BDT | Transfers: 1

Implementation

private async busToLocalRoute(
    route: Route,
    from: string,
    to: string,
    requestTime: string
): Promise<RouteOption | null> {
    let bestOption: RouteOption | null = null;
    let minScore = Infinity;
    
    for (const trip of route.trips) {
        const fromIndex = trip.stops.indexOf(from);
        if (fromIndex === -1) continue;
        
        // Try each possible drop-off stop after 'from'
        for (let i = fromIndex + 1; i < trip.stops.length; i++) {
            const dropOffStop = trip.stops[i];
            if (dropOffStop === to) continue; // Use direct route instead
            
            // Calculate local segment from drop-off to destination
            const localPath = graph.localShortestPath(dropOffStop, to);
            
            let localTime = localPath.totalTime;
            let localCost = localPath.totalCost;
            let localDistance = 0;
            let usedDM = false;
            
            // If no local path in graph, try Distance Matrix
            if (!localPath.found) {
                const dmResult = await distanceMatrixClient.getLocalSegment(
                    dropOffStop, to, 'driving'
                );
                if (dmResult.ok) {
                    localTime = Math.round((dmResult.durationSeconds || 0) / 60);
                    localDistance = dmResult.distanceMeters || 0;
                    localCost = Math.round(localDistance / 100) * 2; // 2 BDT per 100m
                    usedDM = true;
                } else {
                    continue; // Skip this drop-off point
                }
            }
            
            // Calculate total time and weighted score
            const busTravelTime = (i - fromIndex) * 5;
            const waitTime = /* ... calculate wait ... */;
            const totalTime = waitTime + busTravelTime + localTime;
            
            // Penalize local transport time (prefer bus travel)
            const LOCAL_PENALTY = 1.5;
            const score = waitTime + busTravelTime + (localTime * LOCAL_PENALTY);
            
            if (score < minScore) {
                minScore = score;
                bestOption = {
                    label: `${route.name} + Local`,
                    category: 'fastest',
                    type: 'direct',
                    transfers: 0,
                    totalTimeMin: totalTime,
                    totalCost: localCost,
                    legs: [busLeg, localLeg]
                };
            }
        }
    }
    return bestOption;
}

Source: MND-backend/src/core/planner.ts:147-251

The algorithm applies a 1.5x penalty to local transport time, favoring bus travel even if slightly slower.

Hybrid Route Example

Scenario: Student at NAIORPUL needs to reach local HOSPITAL (not a bus stop)

{
  "label": "Bus 3 + Local",
  "category": "fastest",
  "type": "direct",
  "transfers": 0,
  "totalTimeMin": 35,
  "totalCost": 40,
  "legs": [
    {
      "mode": "bus",
      "route_id": "bus3",
      "from": "NAIORPUL",
      "to": "SUBIDBAZAR",
      "departure": "08:30",
      "arrival": "08:55",
      "durationMin": 25,
      "cost": 0
    },
    {
      "mode": "local",
      "submode": "driving",
      "from": "SUBIDBAZAR",
      "to": "HOSPITAL",
      "durationMin": 10,
      "distanceMeters": 2000,
      "cost": 40,
      "source": "distance_matrix"
    }
  ]
}

Route Visualization:

08:30 🚌 Bus 3 departs NAIORPUL
  ↓   🛣️ Free bus travel (25 min)
08:55 🚏 Drop off at SUBIDBAZAR
  ↓   🚕 CNG/rickshaw (2 km, 10 min, 40 BDT)
09:05 🏥 Arrive at HOSPITAL

Total: 35 minutes | Cost: 40 BDT

Strategy 3: Bus Transfers

Overview
Algorithm
Example

Connect multiple bus routes by transferring at common stops.

Transfer Points

Key hubs where multiple routes intersect:

AMBARKHANA - 5 routes converge
SUBIDBAZAR - 6 routes pass through
CHOWHATTA - 4 routes intersect

Constraints

⏱️ Wait time ≤ 15 minutes at transfer point
🚶 No walking between stops (same location)
📅 Next bus must arrive after previous bus

Finding Transfer Routes

private async findTransferRoutes(
    from: string,
    to: string,
    requestTime: string
): Promise<RouteOption[]> {
    const options: RouteOption[] = [];
    const allRoutes = graph.getAllRoutes();
    
    // Try all route pairs
    for (const route1 of allRoutes) {
        for (const route2 of allRoutes) {
            if (route1.route_id === route2.route_id) continue;
            
            // Find common transfer points
            const transferPoints = this.findTransferPoints(route1, route2);
            
            for (const transferNode of transferPoints) {
                const option = await this.createTransferRoute(
                    route1, route2, from, to, transferNode, requestTime
                );
                if (option) {
                    options.push(option);
                }
            }
        }
    }
    return options;
}

private async createTransferRoute(
    route1: Route,
    route2: Route,
    from: string,
    to: string,
    transferNode: string,
    requestTime: string
): Promise<RouteOption | null> {
    // Find trip on route1 from 'from' to 'transferNode'
    const leg1 = await this.directBusRoute(route1, from, transferNode, requestTime);
    if (!leg1) return null;
    
    // Calculate arrival time at transfer point
    const arrivalAtTransfer = leg1.legs[0].arrival!;
    
    // Find trip on route2 from 'transferNode' to 'to'
    const leg2 = await this.directBusRoute(route2, transferNode, to, arrivalAtTransfer);
    if (!leg2) return null;
    
    // Check wait time at transfer stop
    const waitTime = /* calculate wait between buses */;
    
    // Only suggest if wait time is reasonable (≤ 15 min)
    if (waitTime < 0 || waitTime > 15) {
        return null;
    }
    
    return {
        label: `Transfer at ${graph.getNode(transferNode)?.name}`,
        category: 'fastest',
        type: 'transfer',
        transfers: 1,
        totalTimeMin: leg1.totalTimeMin + waitTime + leg2.legs[0].durationMin!,
        totalCost: 0,
        legs: [...leg1.legs, ...leg2.legs]
    };
}

Source: MND-backend/src/core/planner.ts:256-345

Transfer Route Example

Scenario: LAKKATURA → CAMPUS, but no direct bus serves both

{
  "label": "Transfer at Subidbazar",
  "category": "least_local",
  "type": "transfer",
  "transfers": 1,
  "totalTimeMin": 55,
  "totalCost": 0,
  "legs": [
    {
      "mode": "bus",
      "route_id": "bus5",
      "from": "LAKKATURA",
      "to": "SUBIDBAZAR",
      "departure": "08:30",
      "arrival": "08:45",
      "durationMin": 15
    },
    {
      "mode": "bus",
      "route_id": "bus1",
      "from": "SUBIDBAZAR",
      "to": "CAMPUS",
      "departure": "08:55",
      "arrival": "09:25",
      "durationMin": 30
    }
  ]
}

Route Visualization:

08:30 🚌 Bus 5 departs LAKKATURA
  ↓   🛣️ 15 min
08:45 🚏 Arrive at SUBIDBAZAR
  ⏰   Wait 10 minutes
08:55 🚌 Bus 1 departs SUBIDBAZAR
  ↓   🛣️ 30 min
09:25 🏫 Arrive at CAMPUS

Total: 55 minutes (45 min travel + 10 min wait)
Cost: FREE (both buses)

Strategy 4: Local Transport Only

Overview
Algorithm
Example

Fallback option when buses are unavailable or inconvenient.

Use Cases

🕐 Late night (no buses running)
🚫 No bus route serves the origin/destination
⚡ Urgent trip (can’t wait for next bus)

Transport Options

CNG (auto-rickshaw): 20-50 BDT, moderate speed
Rickshaw: 10-30 BDT, slower
Walking: Free, very slow

Dijkstra’s Shortest Path

public localShortestPath(
    from: string,
    to: string,
    allowedModes: ('walk' | 'local')[] = ['walk', 'local']
): PathResult {
    if (!this.nodes.has(from) || !this.nodes.has(to)) {
        return { found: false, path: [], totalTime: Infinity, totalCost: 0, edges: [] };
    }
    
    // Initialize Dijkstra's algorithm
    const distances: Map<string, number> = new Map();
    const costs: Map<string, number> = new Map();
    const previous: Map<string, string | null> = new Map();
    const unvisited: Set<string> = new Set();
    
    this.nodes.forEach((_, nodeId) => {
        distances.set(nodeId, Infinity);
        costs.set(nodeId, 0);
        previous.set(nodeId, null);
        unvisited.add(nodeId);
    });
    
    distances.set(from, 0);
    
    while (unvisited.size > 0) {
        // Find node with minimum distance
        let current: string | null = null;
        let minDist = Infinity;
        unvisited.forEach(nodeId => {
            const dist = distances.get(nodeId)!;
            if (dist < minDist) {
                minDist = dist;
                current = nodeId;
            }
        });
        
        if (current === null || minDist === Infinity) break;
        if (current === to) break; // Found destination
        
        unvisited.delete(current);
        
        // Check neighbors
        const neighbors = this.getNeighbors(current);
        neighbors.forEach(edge => {
            if (!allowedModes.includes(edge.mode as any)) return;
            if (!unvisited.has(edge.to)) return;
            
            const newDist = distances.get(current!)! + edge.time_min;
            if (newDist < distances.get(edge.to)!) {
                distances.set(edge.to, newDist);
                costs.set(edge.to, costs.get(current!)! + edge.cost);
                previous.set(edge.to, current);
            }
        });
    }
    
    // Reconstruct path
    const finalDist = distances.get(to)!;
    if (finalDist === Infinity) {
        return { found: false, path: [], totalTime: Infinity, totalCost: 0, edges: [] };
    }
    
    const path: string[] = [];
    let current: string | null = to;
    while (current !== null) {
        path.unshift(current);
        current = previous.get(current) || null;
    }
    
    return {
        found: true,
        path,
        totalTime: finalDist,
        totalCost: costs.get(to)!,
        edges: [/* edge details */]
    };
}

Source: MND-backend/src/core/graph.ts:124-220

This is a classic Dijkstra’s algorithm implementation, optimizing for time (not distance).

Local-Only Route

Scenario: SHEIKHGHAT → LAKKATURA at 11:00 PM (no buses running)

{
  "label": "Local Transport Only",
  "category": "least_local",
  "type": "local_only",
  "transfers": 0,
  "totalTimeMin": 25,
  "totalCost": 60,
  "legs": [
    {
      "mode": "local",
      "submode": "driving",
      "from": "SHEIKHGHAT",
      "to": "LAKKATURA",
      "durationMin": 25,
      "distanceMeters": 3000,
      "cost": 60,
      "source": "distance_matrix"
    }
  ]
}

Cost Calculation:

// Distance Matrix API returns: 3000 meters
const costPerHundredMeters = 2; // BDT
const totalCost = Math.round(3000 / 100) * 2;
// = 30 * 2 = 60 BDT

Route Comparison & Ranking

After running all 4 strategies, the system compares routes and selects the best options:

Ranking Criteria

Deduplication

Remove duplicate routes (same stops, mode, and timing)

Find Fastest

Route with minimum totalTimeMin (including wait time)

Find Least Local

Route with minimum localTimeMin (paid transport time)

Add Alternatives

Include 1-2 additional routes if available (max 3 total)

Comparison Function

private compareRoutes(options: RouteOption[]): RouteOption[] {
    if (options.length === 0) return [];
    
    // Remove duplicates
    const unique = this.deduplicateOptions(options);
    
    // Find fastest
    let fastest = unique[0];
    for (const option of unique) {
        if (option.totalTimeMin < fastest.totalTimeMin) {
            fastest = option;
        }
    }
    
    // Find least local
    let leastLocal = unique[0];
    for (const option of unique) {
        if (option.localTimeMin < leastLocal.localTimeMin) {
            leastLocal = option;
        }
    }
    
    // Mark categories
    fastest.category = 'fastest';
    fastest.label = 'Fastest Route';
    
    leastLocal.category = 'least_local';
    leastLocal.label = 'Least Local Transport';
    
    // Return top options (avoid duplicates)
    const result: RouteOption[] = [fastest];
    if (this.getOptionId(leastLocal) !== this.getOptionId(fastest)) {
        result.push(leastLocal);
    }
    
    return result;
}

Source: MND-backend/src/core/planner.ts:412-462

Performance Optimizations

Distance Matrix Caching

Google Maps API calls are expensive (₹0.50 per request). MND caches results:

// Cache entry structure
interface CacheEntry {
    distanceMeters: number;
    durationSeconds: number;
    timestamp: number; // Unix timestamp
}

// Cache lookup
const cacheKey = `${from}-${to}-${mode}`;
const cached = this.cache.get(cacheKey);

if (cached && (Date.now() - cached.timestamp) < 7 * 24 * 60 * 60 * 1000) {
    return { ok: true, ...cached, fromCache: true };
}

Cache Duration: 7 days

Parallel Strategy Execution

All 4 strategies run concurrently using async/await:

const options: RouteOption[] = [];

// Execute strategies in parallel
for (const route of allRoutes) {
    const [directOption, hybridOption] = await Promise.all([
        this.directBusRoute(route, from, to, requestTime),
        this.busToLocalRoute(route, from, to, requestTime)
    ]);
    
    if (directOption) options.push(directOption);
    if (hybridOption) options.push(hybridOption);
}

Performance: Reduces response time by ~40%

Early Termination

Stop searching once optimal routes are found:

If direct bus exists, skip expensive transfer searches
Limit transfer wait time to ≤ 15 minutes
Reject routes with totalTimeMin > 2 hours

Adjacency List Pre-computation

Graph edges are pre-computed into an adjacency list on server startup:

// Before: O(E) lookup for each neighbor query
edges.filter(edge => edge.from === nodeId)

// After: O(1) lookup
adjacencyList[nodeId] // → [edge1, edge2, ...]

Speedup: 10x faster for Dijkstra’s algorithm

Real-World Example

Let’s trace a complete route planning request:

Request
Strategy Results
Final Response

GET /api/routes?from=TILAGOR&to=LAKKATURA&time=08:20

Scenario:

📍 Origin: TILAGOR (residential area)
📍 Destination: LAKKATURA (residential area)
⏰ Time: 08:20 (morning commute)

After comparison, the system returns the top 2 options:

{
  "from": "TILAGOR",
  "to": "LAKKATURA",
  "requestTime": "08:20",
  "options": [
    {
      "label": "Fastest Route",
      "category": "fastest",
      "type": "direct",
      "transfers": 0,
      "totalTimeMin": 45,
      "totalCost": 30,
      "localTimeMin": 10,
      "legs": [
        {
          "mode": "bus",
          "route_id": "bus1",
          "from": "TILAGOR",
          "to": "AMBARKHANA",
          "departure": "08:25",
          "arrival": "08:55",
          "durationMin": 30,
          "cost": 0
        },
        {
          "mode": "local",
          "submode": "driving",
          "from": "AMBARKHANA",
          "to": "LAKKATURA",
          "durationMin": 10,
          "distanceMeters": 1500,
          "cost": 30
        }
      ]
    },
    {
      "label": "Least Local Transport",
      "category": "least_local",
      "type": "transfer",
      "transfers": 1,
      "totalTimeMin": 55,
      "totalCost": 0,
      "localTimeMin": 0,
      "legs": [
        {
          "mode": "bus",
          "route_id": "bus1",
          "from": "TILAGOR",
          "to": "AMBARKHANA",
          "departure": "08:25",
          "arrival": "08:55",
          "durationMin": 30,
          "cost": 0
        },
        {
          "mode": "bus",
          "route_id": "bus5",
          "from": "AMBARKHANA",
          "to": "LAKKATURA",
          "departure": "09:05",
          "arrival": "09:20",
          "durationMin": 15,
          "cost": 0
        }
      ]
    }
  ]
}

Next Steps

Graph Model

Explore the 19 nodes and 289 edges

Transport Modes

Learn about buses, CNGs, and walking

API Reference

Try the routing API yourself

Architecture

Understand the full system design

Get Started

Core Concepts

User Guides

Documentation Index

​Overview

Total Time

Cost

Convenience

​The 4 Routing Strategies

​Strategy 1: Direct Bus Route

​Advantages

​Example

​Implementation

​Real Route Example

​Strategy 2: Bus + Local Hybrid

​When to Use

​Example

​Implementation

​Hybrid Route Example

​Strategy 3: Bus Transfers

​Transfer Points

​Constraints

​Finding Transfer Routes

​Transfer Route Example

​Strategy 4: Local Transport Only

​Use Cases

​Transport Options

​Dijkstra’s Shortest Path

​Local-Only Route

​Route Comparison & Ranking

​Ranking Criteria

​Comparison Function

​Performance Optimizations

​Real-World Example

​Strategy 1: Direct Bus

​Strategy 2: Bus + Local

​Strategy 3: Transfer

​Strategy 4: Local Only

​Next Steps

Graph Model

Transport Modes

API Reference

Architecture

Build docs developers (and LLMs) love

Overview

The 4 Routing Strategies

Strategy 1: Direct Bus Route

Advantages

Example

Implementation

Real Route Example

Strategy 2: Bus + Local Hybrid

When to Use

Example

Implementation

Hybrid Route Example

Strategy 3: Bus Transfers

Transfer Points

Constraints

Finding Transfer Routes

Transfer Route Example

Strategy 4: Local Transport Only

Use Cases

Transport Options

Dijkstra’s Shortest Path

Local-Only Route

Route Comparison & Ranking

Ranking Criteria

Comparison Function

Performance Optimizations

Real-World Example

Strategy 1: Direct Bus

Strategy 2: Bus + Local

Strategy 3: Transfer

Strategy 4: Local Only

Next Steps