Pedestrian-Network Clustering Heuristics for Bus Stop Assignment in the Employee Bus Routing Problem

We propose two road-network clustering heuristics for bus stop assignment in the Employee Bus Routing Problem (EBRP), computing real walking distances on an OpenStreetMap graph via GraphHopper instead of Haversine approximations.

Both variants share a Max-Min initialization with forced seeds for reduced-mobility employees, an opening-cost-guided assignment, median refinement on the pedestrian network, and move-and-swap local search. The first variant selects stop locations freely; the second prioritizes existing stops as anchors through a greedy weighted Set Cover.

Experiments on a real-world instance from the public sector of Ceará (1,267 employees) show feasible solutions under walking, capacity, and accessibility constraints, with the free-stop variant producing more cohesive partitions and lower average walking distances.