Overview
The Route class represents a potential path through the bus network. It contains a sequence of points (stops) and provides methods for validation, comparison, distance calculation, and route expansion during the breadth-first search algorithm.
Constructor
Parameters
points
Array<Point | Stop>
required
An ordered array of Point or Stop instances representing the path. The sequence matters as it represents the order in which points are visited.
Implementation
class Route{
constructor(points){
this.p = points
}
// ... methods
}
Example
const stop1 = new Stop({ id: "1", branch_id: "A", name: "First Stop", latitude: 40.7128, longitude: -74.0060 });
const stop2 = new Stop({ id: "2", branch_id: "A", name: "Second Stop", latitude: 40.7580, longitude: -73.9855 });
const route = new Route([stop1, stop2]);
Properties
Array of points representing the route sequence
Methods
isValid()
Validates that a route does not contain duplicate stops. A route is invalid if it visits the same stop twice.
Returns
true if the route contains no duplicate stops, false otherwise
Implementation
isValid(){
for( let i = 0 ; i < this.p.length - 1 ; i ++ ){
for( let j = i +1 ; j < this.p.length ; j ++) {
if(this.p[i].id != null && this.p[j].id !=null && this.p[i].id == this.p[j].id )
return false
}
}
return true
}
The validation checks all pairs of stops in the route. If any two stops share the same id, the route is considered invalid. This prevents circular routes and unnecessary backtracking.
Example
const stop1 = new Stop({ id: "1", branch_id: "A", name: "Stop 1", latitude: 40.71, longitude: -74.00 });
const stop2 = new Stop({ id: "2", branch_id: "A", name: "Stop 2", latitude: 40.75, longitude: -73.98 });
const stop3 = new Stop({ id: "1", branch_id: "B", name: "Stop 1", latitude: 40.71, longitude: -74.00 });
const validRoute = new Route([stop1, stop2]);
console.log(validRoute.isValid()); // true
const invalidRoute = new Route([stop1, stop2, stop3]);
console.log(invalidRoute.isValid()); // false (stop1 and stop3 have same id)
isEqual()
Compares two routes to determine if they are equivalent based on their stop sequences.
route.isEqual(otherRoute)
Parameters
Another Route instance to compare with
Returns
true if routes have the same length and same stop IDs in the same order, false otherwise
Implementation
isEqual(otherRoute){
if(this.p.length !== otherRoute.p.length)
return false
for( let i = 0 ; i < otherRoute.p.length ; i ++ ){
if(otherRoute.p[i].id != null && this.p[i].id !=null && otherRoute.p[i].id != this.p[i].id )
return false
}
return true
}
This method is used to remove duplicate routes during the search process. By filtering out equivalent routes, the algorithm avoids exploring the same path multiple times.
distance()
Calculates the distance from the route’s last point to a destination point.
route.distance(destination)
Parameters
The destination point to calculate distance to
Returns
Distance in kilometers from the route’s last point to the destination
Implementation
distance(destination){
const lastPoint = this.p[this.p.length - 1]
return lastPoint.distance(destination)
}
Usage in Algorithm
The distance() method is crucial for the algorithm’s heuristic. Routes are sorted by their distance to the destination, prioritizing routes that are closer to the goal.
allRoutes.sort( (r1,r2) => r1.distance(destination) - r2.distance(destination) )
getNexRoutes()
Generates all possible next routes by expanding from the current route’s last point. This is the core method for route exploration during the breadth-first search.
Returns
Array of new Route instances, each representing a possible continuation of the current route
Implementation
getNexRoutes(){
const lastPoint = this.p[this.p.length - 1]
const nextStops = posiblesNextStops(lastPoint)
return nextStops.map( s => new Route (this.p.concat(s)) )
.filter(r => r.isValid() )
}
Get Last Point
Extract the last point in the current route
Find Possible Next Stops
Call posiblesNextStops() to get all stops reachable from the last point (either the next stop on the same bus route or nearby stops within walking distance)
Create New Routes
For each possible next stop, create a new Route by appending it to the current route’s points
Filter Invalid Routes
Remove any routes that would visit the same stop twice
Example
// Assume we have a route ending at stop1
const currentRoute = new Route([stop1]);
// Generate all possible continuations
const nextRoutes = currentRoute.getNexRoutes();
// Returns: [Route([stop1, stop2]), Route([stop1, stop3]), ...]
// where stop2 is the next stop on the bus, and stop3 is a nearby stop
This method automatically filters out invalid routes, so the returned array only contains routes where no stop is visited twice.
Route Expansion Strategy
Routes are expanded using a breadth-first search with distance-based prioritization:
let allRoutes = firstStops.map( s => new Route([s]) )
let go = true
let maxCount = 50
while (go) {
// Expand all current routes
const nextRoutes = allRoutes.map( r => r.getNexRoutes() )
.filter( r => r.length)
if(nextRoutes.length === 0 || maxCount === 0 ){
go = false
} else {
// Add all new routes
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
allRoutes.sort( (r1,r2) =>
r1.distance(destination) - r2.distance(destination)
)
// Stop if we're close enough
if(allRoutes[0].distance(destination) < walkKmh ){
go = false
}
// Limit total routes to prevent memory issues
allRoutes = allRoutes.slice(0, maxRoutes)
}
The algorithm maintains a maximum of 10,000 routes and performs up to 50 iterations. These limits prevent infinite loops and excessive memory usage while still allowing thorough exploration of the route network.
Route Deduplication
After each iteration, duplicate routes are removed using isEqual():
allRoutes = allRoutes.filter( (r1,i,self) =>
self.findIndex( r2 => r2.isEqual(r1)) === i
)
Route Pruning
Routes are sorted by distance and limited to the top 10,000:
allRoutes.sort( (r1,r2) => r1.distance(destination) - r2.distance(destination) )
allRoutes = allRoutes.slice(0, maxRoutes)