Traffic congestion is a real problem

A Continuous Query System for Dynamic Route Planning

Nirmesh Malviya (IIT Kanpur, MIT) Samuel Madden (MIT) Arnab Bhattacharya (IIT Kanpur)

Published in ICDE 2011

Traffic congestion is a real problem

Click to edit Master text styles

Second level

Third level

Fourth level Fifth level

•

$115 billion congestion cost in 2009 (in USA)

•

34 hours of yearly peak delay for

average commuter

COMAD 2011 Arnab Bhattacharya 2

Continuous Routing Queries

Click to edit Master text styles

Second level

Third level

Fourth level Fifth level

A traffic aware dynamic route planning service

User registers pair <source s, destination t>

Continuously monitors s-t routes as traffic delays change

Keeps user updated with a near-optimal s-t route

Scalable

COMAD 2011 Arnab Bhattacharya 3

Doesn’t Google Maps solve this problem already?

Click to edit Master text styles

Second level

Third level

Fourth level Fifth level

•

Routing

based on pre- processed

edge weights

•

Ad-hoc

routing only

•

Real time traffic layer overlay for visualization

COMAD 2011 Arnab Bhattacharya 4

Roadblocks

Can’t do repeated shortest-path recalculation Not scalable

Academic work on incremental SP algorithms High space overhead (memory-resident) High computation overhead

Tries to get optimal (which is not critical here)

COMAD 2011 Arnab Bhattacharya 5

Solution: A Continuous Query System

Click to edit Master text styles

Second level

Third level

Fourth level Fifth level

Click to edit Master text styles

Second level

Third level

Fourth level Fifth level

COMAD 2011 Arnab Bhattacharya 6

Key Ideas

Traffic updates affect only a small part of the road network Mix of pre-computation and on-the-fly route calculation Update only when there are significant delay changes

COMAD 2011 Arnab Bhattacharya 7

Our Algorithms

K-Candidate-Paths

Click to edit Master text styles

Second level

Third level

Fourth level Fifth level

Proximity-based approach

Click to edit Master text styles

Second level

Third level

Fourth level Fifth level

COMAD 2011 Arnab Bhattacharya 8

K candidate paths

Pre-compute K different routes

Dynamically select the best candidate as delays change Re-computation limited to K routes

Want changes in traffic delays to not adversely affect all K routes simultaneously

Different strategies for computing K paths

COMAD 2011 Arnab Bhattacharya 9

Yen’s algorithm

Find the shortest path

Pick a vertex v from the path

Delete edges joining v in the path Find the shortest path again

COMAD 2011 Arnab Bhattacharya 10

K-Variance

Perturb randomly the edge weights

For every perturbation, find the shortest path

Sample the edge cost from a Gaussian distribution Parameters learnt from history

Run the algorithm until K distinct paths are found Lots of overlap in paths

COMAD 2011 Arnab Bhattacharya 11

Partially overlapping paths

Click to edit Master text styles Second level

Third level

Fourth level Fifth level

COMAD 2011 Arnab Bhattacharya 12

System Architecture

Click to edit Master text styles Second level

Third level

Fourth level Fifth level

COMAD 2011 Arnab Bhattacharya 13

K-Statistical

Variant of Yen’s K shortest loopless paths algorithm

Loopy paths, i.e., paths with cycle don’t make sense

Delete each edge of the path found in the previous iterations with some probability

Re-do the shortest path calculation on the modified graph

COMAD 2011 Arnab Bhattacharya 14

Proximity-based

Compute shortest paths in a constrained region Constraint on proximity

Shape of constrained region is ellipse Polygons take more space

Ellipses better represent human behavior than rectangles

COMAD 2011 Arnab Bhattacharya 15

Proximity-based

COMAD 2011 Arnab Bhattacharya 16

Results

7,000 drives chosen from CarTel log containing 150,000 real drives Replayed data from 2 months of our traffic delay database

Crucial parameters:

ϵ: captures number of segments with delay updates ϒ: captures degree of change in segment delay

K: set to 5

COMAD 2011 Arnab Bhattacharya 17

Two orders of magnitude faster

COMAD 2011 Arnab Bhattacharya 18

500 1000 1500 3000 5000

1 10 100 1000 10000

Naïve A*

K-STATISTICAL

Number of continuous routing queries registered in the system

Total processing times (s) - log scale

New routes are near optimal

COMAD 2011 Arnab Bhattacharya 19

0.05 0.1 0.25 0.5 0.75000000000000011 1

-0.01 0.01 0.03 0.05 0.07 0.09 0.11 0.13 0.15

Y-STATISTICAL NAÏVE A*

ϵ : threshold fraction of updated segments on any of the K paths^O

ptimality Ratio = (cost-optimal)/optimal

Previously reported routes are near optimal on no update

COMAD 2011 Arnab Bhattacharya 20

0.1 0.25 0.5 0.75000000000000011 1

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

K-STATISTICAL

Precomputed K-STATISTICAL

ϵ : threshold fraction of updated segments on any of the K pathsOptimality Ratio = (cost-optimal)/optimal

Conclusions

Fast and scalable continuous routing scheme which is accurate Routes delivered by our techniques are within 4-7% of the optimal

average optimality gap for pre-computed routes over 30% in all cases

COMAD 2011 Arnab Bhattacharya 21

Conclusions

Fast and scalable continuous routing scheme which is accurate Routes delivered by our techniques are within 4-7% of the optimal

average optimality gap for pre-computed routes over 30% in all cases

COMAD 2011 Arnab Bhattacharya 22

THANK YOU