findRoute Function

Overview

The findRoute function is the core of the route-finding algorithm. It takes bus stop data and route parameters, then uses a breadth-first search with distance-based heuristics to find an optimal path from a starting location to a destination.

Function Signature

findRoute(busStopsData, routeData)

Parameters

busStopsData

Array<Object>

required

Array of bus branches, where each branch contains an array of stops

[
  {
    branch_id: "route_a",
    stops: [
      { id: "1", branch_id: "route_a", name: "First Stop", latitude: 40.7128, longitude: -74.0060 },
      { id: "2", branch_id: "route_a", name: "Second Stop", latitude: 40.7580, longitude: -73.9855 }
    ]
  }
]

routeData

Object

required

Object containing the start and destination coordinates

Show properties

from

Object

required

Starting location with lat and lng properties (as strings or numbers)

Object

required

Destination location with lat and lng properties (as strings or numbers)

Returns

route

Array<Stop>

An ordered array of Stop instances representing the optimal route from start to destination

Throws

"No existen paradas para empezar" - No bus stops found within walking distance of start or destination
"No hay rutas disponibles" - No valid route found to the destination

Algorithm Configuration

The algorithm uses the following constants to calculate travel times and determine walkability:

const walkKmh = 1       // Walking speed: 1 km/h
const busKmh = 60       // Bus speed: 60 km/h
const busWaitH = 0.5    // Bus wait time: 0.5 hours (30 minutes)
const maxWalkKm = 0.8   // Maximum walking distance: 0.8 km (800 meters)

These configuration values affect how routes are evaluated. The maxWalkKm determines which stops are considered “walkable” from any given point, while the speed and wait time constants are available for future time-based optimizations.

Helper Functions

The algorithm defines several helper functions for route exploration:

getNextStop()

Finds the next stop on the same bus route.

function getNextStop(point){
    if(! point instanceof Stop ){
        return null
    }
    const stopIndx = allStops.findIndex( s => point.id === s.id)
    if( allStops.length -1 === stopIndx ){
        return null
    } else if( allStops[stopIndx + 1].branch_id !== point.branch_id ){
        return null
    } 
    return allStops[stopIndx + 1]
}

Verify Stop Type

Ensure the point is a Stop instance

Find Current Position

Locate the stop in the global stops array

Check Bounds

Return null if this is the last stop in the array

Verify Same Branch

Return null if the next stop belongs to a different branch (end of route)

Return Next Stop

Return the next stop in the sequence

getCloseStops()

Finds all stops within walking distance of a given point.

function getCloseStops(from){
    return allStops
            .filter(stop => from.distance(stop) <= maxWalkKm)
}

This function is used to:

Find starting stops near the origin
Find ending stops near the destination
Find transfer stops the user can walk to

posiblesNextStops()

Combines both strategies to find all possible next stops from a given stop.

function posiblesNextStops(stop){
    const ns = getNextStop(stop)
    const closestStops = getCloseStops(stop)
    return closestStops.concat( ns ? ns : [] )
}

This returns:

All stops within walking distance (potential transfers)
The next stop on the same bus route (if available)

By combining both walking and riding options, the algorithm can explore multi-modal routes that involve both bus rides and walking/transfers.

Algorithm Flow

The route-finding algorithm follows these steps:

Initialize Stop Data

Flatten the bus stops data structure and create Stop instances

const allStops = busStopsData
                .reduce( (stops,branch) => stops.concat(branch.stops) ,[])
                .map(s => new Stop(s))

Parse Start and Destination

Create Point instances for the start and destination locations

const start = new Point(
    parseFloat(routeData.from.lat),
    parseFloat(routeData.from.lng)
)
const destination = new Point(
    parseFloat(routeData.to.lat),
    parseFloat(routeData.to.lng)
)

Validate Starting Points

Find stops within walking distance of the start location

const firstStops = getCloseStops(start) 
if(firstStops.length < 1){
    throw new Error("No existen paradas para empezar")
}

Validate Ending Points

Find stops within walking distance of the destination

const endsStops = getCloseStops(destination)
if(firstStops.length < 1){
    throw new Error("No existen paradas para empezar")
}

Initialize Routes

Create initial single-stop routes from each starting stop

let allRoutes = firstStops.map( s => new Route([s]) )

Breadth-First Search

Iteratively expand routes until a solution is found or limits are reached

let go = true
let maxCount = 50
while (go) {
    // Expand all routes
    const nextRoutes = allRoutes.map( r => r.getNexRoutes() )
                                .filter( r => r.length)
    
    if(nextRoutes.length === 0 || maxCount === 0 ){
        go = false
    } else {
        // Add new routes to the pool
        nextRoutes.forEach((routes)=>{
            routes.forEach( (r )=>allRoutes.push(r))
        })
    }
    
    maxCount --
    
    // Remove duplicates
    allRoutes = allRoutes.filter( (r1,i,self) => 
        self.findIndex( r2 => r2.isEqual(r1)) === i 
    )
    
    // Sort by distance to destination (heuristic)
    allRoutes.sort( (r1,r2) => 
        r1.distance(destination) - r2.distance(destination) 
    )
    
    // Stop if closest route is within walking distance
    if(allRoutes[0].distance(destination) < walkKmh ){
        go = false
    }
    
    // Limit to top 10,000 routes
    allRoutes = allRoutes.slice(0, maxRoutes)
}

Filter Valid Routes

Find routes that end within walking distance of the destination

validRoutes = allRoutes.filter( r => r.distance(destination) < maxWalkKm )

Return Best Route

Return the first valid route (already sorted by distance)

if(validRoutes.length){
    return validRoutes[0].p
}
throw new Error("No hay rutas disponibles")

Search Strategy

The algorithm employs a breadth-first search with distance-based prioritization:

Breadth-First Expansion

Each iteration expands all current routes by one stop:

const nextRoutes = allRoutes.map( r => r.getNexRoutes() )
                            .filter( r => r.length)

This ensures that shorter routes (fewer stops) are explored before longer ones.

Distance Heuristic

Routes are sorted by their distance to the destination:

allRoutes.sort( (r1,r2) => r1.distance(destination) - r2.distance(destination) )

This prioritizes routes that are getting closer to the destination, making the search more efficient.

Deduplication

Duplicate routes are removed after each iteration:

allRoutes = allRoutes.filter( (r1,i,self) => 
    self.findIndex( r2 => r2.isEqual(r1)) === i 
)

This prevents the algorithm from exploring the same path multiple times.

Route Validation

Only routes that don’t visit the same stop twice are kept:

return nextStops.map( s => new Route (this.p.concat(s)) )
                .filter(r => r.isValid() )

This prevents circular routes and backtracking.

Algorithm Limits

Two limits prevent infinite loops and excessive resource usage:

maxRoutes

Maximum number of routes to maintain in memory:

const maxRoutes = 10000
allRoutes = allRoutes.slice(0, maxRoutes)

After sorting by distance, only the top 10,000 most promising routes are kept.

maxCount

Maximum number of iterations:

let maxCount = 50
while (go) {
    // ... search logic
    maxCount --
}

The search stops after 50 iterations, even if no solution is found.

These limits are safeguards against pathological cases where the bus network might cause excessive route exploration. In practice, most routes are found within a few iterations.

Early Termination

The algorithm can stop early under two conditions:

1. No More Routes to Expand

if(nextRoutes.length === 0 || maxCount === 0 ){
    go = false
}

If no routes can be expanded further (dead ends reached), the search terminates.

2. Within Walking Distance

if(allRoutes[0].distance(destination) < walkKmh ){
    go = false
}

If the best route is within walking distance of the destination, the search stops immediately.

The walking distance check uses walkKmh (1 km) rather than maxWalkKm (0.8 km). This appears to be a bug in the original code - it should likely use maxWalkKm for consistency.

Usage Example

const busStopsData = [
    {
        branch_id: "route_1",
        stops: [
            { id: "1", branch_id: "route_1", name: "Stop A", latitude: 40.7128, longitude: -74.0060 },
            { id: "2", branch_id: "route_1", name: "Stop B", latitude: 40.7580, longitude: -73.9855 }
        ]
    },
    {
        branch_id: "route_2",
        stops: [
            { id: "3", branch_id: "route_2", name: "Stop C", latitude: 40.7589, longitude: -73.9851 },
            { id: "4", branch_id: "route_2", name: "Stop D", latitude: 40.7489, longitude: -73.9681 }
        ]
    }
];

const routeData = {
    from: { lat: "40.7128", lng: "-74.0060" },
    to: { lat: "40.7489", lng: "-73.9681" }
};

try {
    const route = findRoute(busStopsData, routeData);
    console.log(`Found route with ${route.length} stops`);
    route.forEach((stop, i) => {
        console.log(`${i + 1}. ${stop.name} (${stop.branch_id})`);
    });
} catch (error) {
    console.error(error.message);
}

Performance Characteristics

Time Complexity

Worst case: O(maxCount × maxRoutes × avgNextStops)
Typical case: Much better due to early termination and distance heuristic

Space Complexity

Maximum: O(maxRoutes) = O(10,000) routes in memory
Each route stores an array of Stop references

Optimizations

Distance-based sorting: Prioritizes promising routes
Deduplication: Avoids redundant exploration
Route pruning: Limits memory usage to top 10,000 routes
Early termination: Stops when destination is reachable
Validation: Prevents circular routes

The algorithm prioritizes finding a solution quickly over finding the optimal solution. The first valid route found (closest to destination) is returned, which may not be the absolute shortest or fastest route.

Point Class - Geographic coordinate representation
Stop Class - Bus stop representation
Route Class - Route representation and expansion

Endpoints

Route Algorithm

Overview

Function Signature

Parameters

Returns

Throws

Algorithm Configuration

Helper Functions

getNextStop()

getCloseStops()

posiblesNextStops()

Algorithm Flow

Search Strategy

Breadth-First Expansion

Distance Heuristic

Deduplication

Route Validation

Algorithm Limits

maxRoutes

maxCount

Early Termination

1. No More Routes to Expand

2. Within Walking Distance

Usage Example

Performance Characteristics

Time Complexity

Space Complexity

Optimizations

Build docs developers (and LLMs) love

Endpoints

Route Algorithm

​Overview

​Function Signature

​Parameters

​Returns

​Throws

​Algorithm Configuration

​Helper Functions

​getNextStop()

​getCloseStops()

​posiblesNextStops()

​Algorithm Flow

​Search Strategy

​Breadth-First Expansion

​Distance Heuristic

​Deduplication

​Route Validation

​Algorithm Limits

​maxRoutes

​maxCount

​Early Termination

​1. No More Routes to Expand

​2. Within Walking Distance

​Usage Example

​Performance Characteristics

​Time Complexity

​Space Complexity

​Optimizations

​Related Classes

Build docs developers (and LLMs) love

Overview

Function Signature

Parameters

Returns

Throws

Algorithm Configuration

Helper Functions

getNextStop()

getCloseStops()

posiblesNextStops()

Algorithm Flow

Search Strategy

Breadth-First Expansion

Distance Heuristic

Deduplication

Route Validation

Algorithm Limits

maxRoutes

maxCount

Early Termination

1. No More Routes to Expand

2. Within Walking Distance

Usage Example

Performance Characteristics

Time Complexity

Space Complexity

Optimizations

Related Classes