Routing Algorithm

How MND finds optimal routes using 4 intelligent strategies

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

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

Algorithm

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

Example

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

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

Algorithm

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.

Example

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

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

Algorithm

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

Example

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

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

Algorithm

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).

Example

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

1. Deduplication

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

2. Find Fastest

   Route with minimum totalTimeMin (including wait time)

3. Find Least Local

   Route with minimum localTimeMin (paid transport time)

4. 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

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

Scenario:

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

Strategy Results

Strategy 1: Direct Bus

❌ No direct bus serves both TILAGOR and LAKKATURA

Strategy 2: Bus + Local

✅ Option A:

• Bus 1: TILAGOR → AMBARKHANA (30 min)
• CNG: AMBARKHANA → LAKKATURA (10 min, 30 BDT)
• Total: 45 min, 30 BDT

✅ Option B:

• Bus 2: TILAGOR → SUBIDBAZAR (35 min)
• CNG: SUBIDBAZAR → LAKKATURA (8 min, 25 BDT)
• Total: 48 min, 25 BDT

Strategy 3: Transfer

✅ Option C:

• Bus 1: TILAGOR → AMBARKHANA (30 min)
• Wait 10 min
• Bus 5: AMBARKHANA → LAKKATURA (15 min)
• Total: 55 min, 0 BDT

Strategy 4: Local Only

✅ Option D:

• CNG direct: TILAGOR → LAKKATURA (25 min, 70 BDT)
• Total: 25 min, 70 BDT

Final Response

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