-
Notifications
You must be signed in to change notification settings - Fork 0
Routing Traffic Engine Research
This section presents the research conducted on routing and traffic simulation, the challenges identified, and the architectural decisions made to address them.
VeloSim requires a routing sub-system capable of:
- Route Generation: Calculate routes between arbitrary positions using real-world map data
- Traffic Simulation: Model dynamic traffic conditions that affect travel speeds
- Multi-Simulation Support: Run multiple simulations concurrently, potentially with different traffic states
- Real-Time Updates: Handle traffic changes during simulation and propagate them appropriately
The core challenge is balancing performance (fast route queries) with flexibility (dynamic traffic states per simulation).
| Question | Related Issue |
|---|---|
| How do different routing engines handle traffic data? | #643, #644, #645, #646 |
| Can multiple traffic states coexist without resource duplication? | #501 |
| How should traffic propagate between simulation and routing layers? | #506, #503 |
| What is the tradeoff between pre-computed vs dynamic routing? | #512 |
Four open-source routing engines were evaluated for their traffic handling capabilities:
| Engine | Traffic Model | Multi-State Support | Rebuild Required | Issue |
|---|---|---|---|---|
| OSRM | Pre-computed speeds | No (single state per instance) | Yes (osrm-customize) |
#643 |
| GraphHopper | Custom Models per-request | Yes (different model per request) | No | #646 |
| Valhalla | Memory-mapped live + historical | Partial (live has priority) | No | #644 |
| pgRouting | Dynamic SQL-based costs | Yes (different query per request) | No | #645 |
Architecture: OSRM pre-computes a contraction hierarchy (CH) or multi-level Dijkstra (MLD) graph for fast query times.
Traffic Handling:
- Traffic is applied via CSV file with speed updates
- Requires
osrm-customizecommand (~2 seconds) to rebuild - Only one traffic state can exist per instance
Key Limitation (from GitHub Issue #5099):
"OSRM cannot currently do this - there is only 1 optimized routing graph, and the structure of the graph cannot be changed at runtime. What you suggest (default speed or traffic speed) would require two optimized routing graphs, which is basically what running two instances of OSRM does." — @danpat (OSRM maintainer)
Implication: Multiple simulations with different traffic states would require either:
- Multiple OSRM containers (memory overhead)
- State multiplexing with ~2s swap latency
Architecture: Supports "Custom Models" - a JSON DSL for per-request routing modifications.
Traffic Handling:
{
"speed": [
{"if": "in_congested_area", "multiply_by": "0.5"},
{"if": "road_class == MOTORWAY", "limit_to": "80"}
],
"areas": { "type": "FeatureCollection", "features": [...] }
}Advantage: Per-request traffic customization without rebuild.
Tradeoff: Slower than pre-computed routing; requires mapping traffic data to rules.
Architecture: Tiled graph with memory-mapped traffic files.
Traffic Handling:
- Historical: DCT-II encoded weekly patterns (2016 intervals)
-
Live: Memory-mapped
.tarfile, updatable at runtime
Advantage: Native time-dependent routing; live updates without restart.
Limitation: Live traffic has priority over historical - cannot easily compare states.
Architecture: Extends PostgreSQL/PostGIS with graph algorithms.
Traffic Handling:
SELECT * FROM pgr_dijkstra(
'SELECT e.id, e.source, e.target,
e.base_cost * COALESCE(t.multiplier, 1.0) AS cost
FROM edges e LEFT JOIN traffic t ON e.id = t.edge_id',
start_vertex, end_vertex
);Advantage: Maximum flexibility - different queries = different traffic states instantly.
Tradeoff: Slower than pre-computed engines for large networks.
| Criterion | OSRM | GraphHopper | Valhalla | pgRouting |
|---|---|---|---|---|
| Query Speed | Excellent | Moderate | Good | Low |
| Traffic Flexibility | Poor | Good | Moderate | Excellent |
| Setup Complexity | Moderate | Low | High | High |
| Multi-State Support | None | Excellent | Partial | Excellent |
Related: #501
Context: The application can run multiple parallel simulations, each potentially with different traffic states.
Challenge: Routing engines (especially OSRM) maintain a single traffic state. Multiple simulations expecting different states creates a reader-writer conflict.
┌─────────────────────────────────────────────────────────────────────────┐
│ THE PROBLEM │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Simulation A (Traffic State X) ───┐ │
│ ├──▶ OSRM Container ◀── ??? │
│ Simulation B (Traffic State Y) ───┘ (Single State) │
│ │
│ Which traffic state should OSRM have loaded? │
│ Both simulations expect different routing responses! │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Context: In the real world, GPS systems don't have instant traffic information. There's a delay between an incident occurring and routes being updated.
Challenge: The simulation should model this delay - traffic events affect vehicles immediately (slower speeds), but the routing engine learns about it later (future routes avoid the area).
┌─────────────────────────────────────────────────────────────────────────┐
│ REAL-WORLD TRAFFIC PROPAGATION │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ [Traffic Event Occurs] │
│ │ │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ Simulation Layer │ ◄── Immediate: Roads get traffic state │
│ │ (TrafficController)│ │
│ └──────────┬──────────┘ │
│ │ │
│ │ Propagation Delay (simulates real-world GPS lag) │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ Routing Provider │ ◄── Delayed: Future routes consider traffic │
│ │ (OSRM/Valhalla) │ │
│ └─────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Context: When traffic conditions change, existing routes may become suboptimal. GPS systems typically offer rerouting.
Challenge: Efficiently identify which active routes are affected by a traffic change and offer recalculation.
Context: Multiple routes may share the same physical road segments. If traffic is applied to a segment, all routes using it should be affected.
Challenge: Avoid polynomial search complexity when updating traffic on shared segments.
Solution: The Flyweight pattern - keep a single road instance in memory, shared across all routes that use it.
Based on the research findings, the following architectural decisions were made:
Related: #501
Decision: Separate traffic into two independent layers.
Rationale: This solves the multi-simulation problem without requiring multiple routing engine instances.
| Layer | Purpose | Scope |
|---|---|---|
| Simulation Layer | Speed multipliers for route traversal | Per-simulation |
| Routing Layer | Traffic that affects route calculation | Shared/Global |
Consequence: A route can be calculated once, then traffic applied independently per simulation.
Decision: Identify road segments by coordinate endpoints (SegmentKey), not provider-specific IDs.
SegmentKey = ((start_lon, start_lat), (end_lon, end_lat))Rationale: Provider-neutral identification enables:
- Switching routing engines without refactoring traffic logic
- Road reuse across routes
- Traffic application by geometry
Related: #506
Decision: Maintain a HashMap mapping roads to routes and vice versa.
Rationale: Solves the route starvation problem with O(1) lookup:
roads_to_routes: Dict[Road, Set[Route]]
# When traffic applied to road → instantly find all affected routesDecision: Store traffic state independently of road existence. Apply when roads are allocated.
Rationale: Traffic events may arrive before routes are created. The system should "remember" traffic and apply it when relevant roads come into existence.
Decision: Traffic modifies behavior (speed, duration) without altering base road data.
Rationale: Enables:
- Easy traffic clearing (revert to base state)
- Comparison of with/without traffic scenarios
- Multiple traffic states on same road data
Decision: Start with OSRM for fast queries, but abstract behind a RoutingProvider interface.
Rationale: OSRM provides the best query performance. The abstraction allows future migration to GraphHopper or pgRouting if multi-state routing becomes critical.
┌─────────────────────────────────────────────────────────────────────────┐
│ SIMULATION LAYER │
│ ┌──────────────┐ ┌────────────────────┐ │
│ │ Simulator │────▶│ SimulatorController│ │
│ └──────────────┘ └─────────┬──────────┘ │
│ │ owns │
├─────────────────────────────────────────────────────────────────────────┤
│ MAP LAYER │
│ ┌──────────────────────────────────────────────────────────────────┐ │
│ │ MapController (Facade) │ │
│ └───────┬─────────────────────┬─────────────────────┬──────────────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌───────────────┐ ┌────────────────┐ ┌──────────────────┐ │
│ │RouteController│ │TrafficController│ │ RoutingProvider │ │
│ └───────────────┘ └────────────────┘ └─────────┬────────┘ │
├─────────────────────────────────────────────────────────────────────────┤
│ ENTITY LAYER │
│ ┌─────────┐ ┌─────────┐ ┌────────────────────┐ │
│ │ Route │─────▶│ Road │◀────▶│ RoadTrafficState │ │
│ └─────────┘ └─────────┘ └────────────────────┘ │
├─────────────────────────────────────────────────────────────────────────┤
│ ROUTING PROVIDER LAYER │
│ ┌──────────────────────────────────────────────────────────────────┐ │
│ │ OSRMAdapter (implements RoutingProvider) │ │
│ └──────────────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────────────┘
| Component | Responsibility |
|---|---|
| MapController | Facade for routing subsystem |
| RouteController | Road/route lifecycle, deduplication, mapping |
| TrafficController | Traffic state management, persistence |
| RoutingProvider | Abstract routing interface |
| OSRMAdapter | OSRM-specific implementation |
| Pattern | Implementation | Purpose |
|---|---|---|
| Facade | MapController, TrafficController | Unified interface, low cognitive load |
| Flyweight | RouteController | Single road instance shared across routes |
| Adapter | RoutingProvider interface | Decouple domain from external routing APIs |
| State | TrafficController | Manage multiple traffic layers over roads |
| Factory | TrafficStateFactory | Handle many combinations of traffic states |
| Callbacks | RouteController | TrafficController subscribes to road lifecycle events |
The MapController strictly follows the Facade pattern. All routing and traffic is abstracted behind a single method (get_route), keeping cognitive complexity low. Callers don't need to understand RouteController, TrafficController, or RoutingProvider internals.
Similarly, TrafficController acts as a facade for all traffic state management, abstracting the complexity of persistent storage, lazy application, and point regeneration.
The RouteController implements the Flyweight pattern for road reuse. When a road appears in multiple routes, a single instance is kept in memory rather than duplicating the object. This is achieved through the segment_key_to_road dictionary:
# RouteController maintains a single instance per road geometry
segment_key_to_road: Dict[SegmentKey, Road]
# When creating roads for a route:
if segment_key in segment_key_to_road:
road = segment_key_to_road[segment_key] # Reuse existing instance
else:
road = Road(...) # Create new only if doesn't existThis reduces memory usage and enables efficient traffic updates (change one road instance, all routes using it are affected).
The system was becoming tightly coupled to OSRM. To resolve this, a RoutingProvider interface was introduced as an adapter, allowing routing engines to be swapped via dependency injection. This:
- Improves maintainability
- Removes single point of failure
- Creates clear separation between domain objects and API objects
class RoutingProvider(ABC):
@abstractmethod
def get_route(self, start: Position, end: Position) -> RouteResult: ...
class OSRMAdapter(RoutingProvider):
# Adapts OSRM-specific API to our domain interfaceThe TrafficController follows the State behavioral pattern to manage multiple speed modulation layers over existing roads in memory. Traffic state can change dynamically during simulation, and the controller handles transitions between states (FREE_FLOW, MODERATE, SEVERE).
The TrafficStateFactory creates traffic state objects. A factory was needed because there are many possible combinations of traffic states (different multipliers, sources, congestion levels, point collections). The factory encapsulates this complexity:
class TrafficStateFactory:
@staticmethod
def create(multiplier: float, points: List[Position], source: str) -> RoadTrafficState:
congestion = multiplier_to_congestion_level(multiplier)
return RoadTrafficState(multiplier, congestion, points, source)Related: #541
| Term | Definition |
|---|---|
| SegmentKey | Ordered coordinate tuple ((lon₁, lat₁), (lon₂, lat₂)) identifying a road segment. Provider-neutral. |
| Position | Value object with longitude and latitude. |
| Term | Definition |
|---|---|
| Route | Ordered collection of Roads. Manages traversal state (current road/point indices). |
| Road | Segment with geometry, length, maxspeed, optional traffic state. Identified by SegmentKey. |
| RouteResult | Provider-neutral response with coordinates, distance, duration, steps, segments. |
| Term | Definition |
|---|---|
| RoadTrafficState | Traffic applied to a road: multiplier (0.1-1.0), congestion level, pre-computed points. |
| TrafficEvent | CSV-loadable specification: coordinates, multiplier, event_id, source. |
| CongestionLevel | Enum: FREE_FLOW (≥0.825), MODERATE (0.40-0.825), SEVERE (<0.40). |
| Multiplier | Meaning |
|---|---|
| 1.0 | Free flow (maximum speed) |
| 0.65 | Moderate traffic |
| 0.1 | Severe congestion (minimum) |
| 0.0 | Standstill (out of scope) |
Roads are deduplicated using geometry-based identification:
def create_roads_from_steps(route_result):
for segment in route_result.segments:
segment_key = segment.segment_key
if segment_key in segment_key_to_road:
road = segment_key_to_road[segment_key] # Reuse existing
else:
road = Road(segment)
segment_key_to_road[segment_key] = road
notify_road_allocated(segment_key) # Trigger traffic check┌────────────────────────────────────────────────────────────────────┐
│ TrafficController │
│ │
│ _active_traffic (Persistent) │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ SegmentKey → (multiplier, source) │ │
│ │ Survives road deallocation │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │ │
│ │ applied when road allocated │
│ ▼ │
│ _segment_key_to_traffic (Applied) │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ SegmentKey → RoadTrafficState │ │
│ │ Only exists when road is active │ │
│ └─────────────────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────────┘
When traffic is applied, affected routes are identified in O(1):
# Traffic applied to a segment
affected_road = route_controller.get_road_by_segment_key(segment_key)
affected_routes = route_controller.roads_to_routes[affected_road] # O(1)
for route in affected_routes:
route.check_for_better_path() # Notify for potential rerouteRelated: #541
Routes are traversed at ~1 position per second of travel:
def generate_point_collection(geometry, length, maxspeed, is_final):
line = LineString(geometry)
duration_seconds = length / (maxspeed * 1000 / 3600)
num_points = max(1, int(duration_seconds))
points = []
for i in range(num_points):
fraction = i / num_points
point = line.interpolate(fraction, normalized=True)
points.append(Position(point.x, point.y))
if is_final:
points.append(Position(*line.coords[-1])) # Include endpoint
return pointsWhen traffic is applied, new points are generated at the effective speed:
effective_speed = road.maxspeed * multiplier
traffic_points = generate_point_collection(..., maxspeed=effective_speed)Related: #541
Problem: When traffic is applied mid-traversal, the point distribution changes. There is no 1:1 correspondence between indices in the old and new distributions.
Consider a driver at index 6 in a 10-point road. Traffic reduces it to 5 points:
- Keep index 6? Out of bounds (only indices 0-4 exist)
- Clamp to max (index 4)? Driver teleports to the end
- Points increase instead? Keeping same index means less progress (driver moves backward)
Requirement: The driver must NEVER move backward, only forward or stay in place.
Solution: The TAMM algorithm maps indices by preserving progress ratio:
def map_index_forward(current_idx: int, old_count: int, new_count: int) -> int:
"""Map index from old collection to new, ensuring forward-only progress."""
if old_count <= 1 or new_count <= 1:
return min(current_idx, new_count - 1)
progress = current_idx / (old_count - 1) # 0.0 to 1.0
return min(math.ceil(progress * (new_count - 1)), new_count - 1)Key insight: Since we know the percent complete of the current distribution, we can map this ratio to the new distribution.
Properties:
- O(1) time complexity
-
ceil()guarantees forward-only mapping (progress >= current progress) - Handles both point increases and decreases
- Found in
map_index_forward()in route.py
Example:
Before traffic: [P0, P1, P2, P3, P4, P5, P6, P7, P8, P9] (10 points)
Driver at index 7 (70% through)
Traffic applied: [P0, P1, P2, P3] (4 points)
progress = 7 / 9 = 0.78
new_index = ceil(0.78 * 3) = ceil(2.33) = 3
Driver mapped to index 3 (75% through) - moved slightly forward, never backward
Future Enhancement: TAMM can be extended to support non-uniform motion (acceleration/deceleration at intersections) via local linear approximations.
Driver.travel_to(destination)
│
▼
MapController.get_route(start, end)
│
▼
RouteController.get_route_from_positions()
├──▶ RoutingProvider.get_route() → RouteResult
│
└──▶ create_roads_from_steps()
├── Check segment_key_to_road (reuse or create)
├── Notify road_allocated (traffic callback)
└── Return List[Road]
│
▼
Route(roads) ← ready for traversal
TrafficController.set_traffic(segment_key, multiplier)
│
├──▶ Store in _active_traffic (persistent)
│
└──▶ If road exists:
├── Generate traffic points at effective speed
├── Create RoadTrafficState
└── Road.set_traffic_state()
[Each tick]
│
▼
Route.next()
├── Get road.active_pointcollection
│ └── Returns traffic points if available, else base points
├── Return points[current_index]
├── Advance index
└── Handle road transitions
sim/
├── map/
│ ├── MapController.py # Facade (entry point)
│ ├── route_controller.py # Road/route management
│ └── routing_provider.py # Abstract interface + data classes
│
├── osm/
│ ├── OSRMConnection.py # HTTP client
│ ├── osrm_adapter.py # RoutingProvider implementation
│ └── osrm_result.py # OSRM-specific types
│
├── traffic/
│ ├── traffic_controller.py # Traffic state management
│ ├── traffic_event.py # TrafficEvent model
│ ├── traffic_event_loader.py # CSV loading
│ ├── csv_traffic_parser.py # Parsing + validation
│ └── traffic_state_factory.py
│
└── entities/
├── driver.py # Driver entity
├── route.py # Route with traversal
├── road.py # Road with traffic support
├── position.py # Position value object
└── traffic_data.py # RoadTrafficState, CongestionLevel
If per-simulation routing-level traffic becomes critical, consider:
- GraphHopper: Custom Models enable per-request traffic without rebuild
- pgRouting: SQL-based costs provide maximum flexibility
The RoutingProvider abstraction enables this migration without refactoring the simulation layer.
For OSRM with multiple traffic states:
- Batch requests per simulation
- Swap states between batches (~2s overhead)
- Cache routes to minimize swap frequency
Future enhancement: Valhalla's historical traffic (DCT-II encoded) could enable time-dependent routing predictions.
Traffic simulation is ongoing R&D. An experimental branch was created to validate feasibility before merging: #474. For upcoming traffic features, see user story #457.
Simulation Meeting Minutes
Frontend Meeting Minutes
Backend Meeting Minutes
Risks
User Consent and End-User License Agreement
Legal and Ethical Issues
Economic
Budget
Personas
Diversity Statement
Overall Architecture and Class Diagrams
Infrastructure and Tools
Name Conventions
Testing Plan and Continuous Integration
Security
Performance
Deployment Plan and Infrastructure
Missing Knowledge and Independent Learning
Glossary
Mockups
UI Evolution
Logging
Metrics
VeloSim Observability & Performance Insights
User Manual
Usability Tests