As reported by MIT Technology Review: Here’s an interesting question: how do you identify the most
important junctions in a city? One way it is to measure the origin,
route, and destination of each road trip through a city and then work
out where they cross.
That’s never been possible in the past because this kind of data has
always been hard to collect. But in recent years, the growing use of GPS
navigating devices has changed all that.
Today, Ming Xu at Tsinghau University in Beijing and a few pals have
collected the GPS data from hundreds of thousands of taxi journeys in
Beijing and use it to do exactly this calculation. The result is a
comprehensive map of the most important crossroads in Beijing,
information that traffic planners could make good use of to keep the
traffic flowing during roadworks, building projects, and so on.
Beijing has a population of more than 21 million people and its road
traffic network is correspondingly huge. It contains 13,722 crossroads
connected by over 25,000 roads. The network of roads in Beijing is
dominated by four more or less concentric ring roads along with a number
of arterial routes that head into the city center. To discover the most
important of these crossroads, Ming and co used the routes taken by
10,000 taxicabs in Beijing during the month of October 2012.
This dataset consisted of each taxi’s GPS location sampled around
once a minute. The team was particularly interested in the peak traffic
conditions and so used only the data taken between 7:30 a.m. and 10 a.m.
and between 5 p.m. and 7:30 p.m. This consisted of more than 500,000
fare-paying taxi trips between one location and another.
First, they mapped each of these trips onto a map of Beijing to
determine the origin, route and destination of each. They also counted
the number of crossroads traversed on each trip, a number that varied
mainly between 7 and 18. That allowed the team to calculate things like
the amount of traffic that passes through any given crossroads during
the peak commuter period.
But then notion of an “important crossroad” is more subtle in Ming
and co’s model of a city and they use a Pagerank-style algorithm to
calculate this.
The Pagerank algorithm is Google’s famous method for ranking
important webpages. It judges a webpage to be important if it is linked
to by other important webpages. It works by a process of iteration, in
which the importance of each webpage is calculated at every step and
this is then used to update the calculation in the next step.
Ming and co use the same approach to rank the importance of
crossroads. In their algorithm, called CRRANK, a crossroad is important
if it is linked to by important roads. And roads are important if they
link important crossroads. By iterating this algorithm, a ranking of
important crossroads emerges.
 |
| Deshengmen City Gate Tower |
The results clearly show which crossroads in Beijing are the most
significant. The most important is called Deshengmen Bridge. It is the
junction of the second ring road with the Badaling Expressway, near the
Deshengmen city gate in the northern part of the city wall. It is well
known as a major transportation mode.
The second is Xuanwumen Bridge in the southern part of the city and
the former location of another gate in the city wall. It is also known
as a major transportation hub.
The ranking lists over 100 important, with the most important being
on the second ring road. It picks out important junctions on the third
and fourth ring roads as well, which are further out. But the trend is
that more important junctions tend to be nearer the center. “This is
consistent with our daily experience,” say Ming and co.
Incidentally, the most important route is between Jinrong Street in the center of town and Beijing airport.
That’s an interesting way of ranking the importance of crossroads.
Other groups have studied the network of roads within cities by creating
a model of road traffic, and then removing nodes to see how the network
performs without them. This simulates the crossroads becoming blocked
by an accident, for example. That also reveals crucial junctions, some
of which are so important that entire cities can come to a standstill
when they become blocked.
The trouble with these earlier studies is that they have to be done
with traffic flow simulations. But the availability of large amounts of
high quality traffic data from real vehicles makes this kind of work
much more valuable. There’s no reason now why these different approaches
can’t be combined in future.
That should help when planning traffic flow during building works.
Nevertheless, the traffic in big cities has always been bad.
Victorian commentators describe people running over the roofs of
horse-drawn cabs in the traffic-jammed streets of 19th-century London.
Any Londoners reading this will know that things haven’t improved much
since then.
But with data like this and the ability to number crunch it
effectively, perhaps it is reasonable hold out a small candle of hope
that traffic jams will become a thing of the past. Then again, possibly
not.
Ref: arxiv.org/abs/1407.2506 : Discovery of Important Crossroads in Road Network using Massive Taxi Trajectories
No comments:
Post a Comment