On December 2, 2010, Qatar was announced to host 2022 FIFA World Cup. That was time for celebrating the first-ever Middle Eastern country to organize the tournament. The 1.8M population of Qatar then (2.8M today) never imagined the journey their country was about to embarked. Indeed, in less than 10 years, the population grew by more than a half, pushing the available urban resources and services to their limit. At the same time, the country undertook an ambitious investment plan of $200B on various infra-structural projects including a brand new three-line metro network, six new stadiums, several new satellite cities, and an astonishing 4,300km of new roads, which tripled the size of the road network in only five years.3
While this enterprise boosted the socio-economical life of people in Qatar, it did disrupt the way they navigate the urban space and their mobility patterns in general. Simple commutes to work, drops and pickups of kids to and from schools, became challenging and impossible to plan with daily changes in the road layout, including temporary and permanent closures, deviations, new connections, conversions of roundabouts into signaled intersections, turn restrictions, to name but a few. A commute to school that lasted 10 minutes yesterday, could last 25 minutes today. Cab drivers in the city of Doha (Qatar's capital), who are mostly foreigners, also wish they could rely on popular navigation services such as Google Maps, Here, or Tomtom.
Yet, all such systems fall short in coping up with the rapid urbanization and the ever-changing roads in Doha. This was actually depicted in a very popular caricature in one of the most widely distributed daily local newspapers showing Google maps as a limping turtle that is helplessly trying to catch a bunny representing the road changes in the city of Doha.4
Besides the general public who is not happy with the routes offered by navigation systems, other stakeholders from public and private sectors were struggling with the poor quality of existing digital maps. For example, the Ministry of Transport and Communication was facing issues getting access to the most accurate map of the road network, needed for their traffic modeling. Also, transportation, delivery, and logistics companies that heavily rely on accurate maps, routes, and travel time estimates were tired of the many lost drivers and missed rendezvous.
Early work: Silent maps are not enough. The issue of inaccurate local maps has triggered an early work at Qatar Computing Research Institute (QCRI) in collaboration with Qatar Mobility Innovation Center (QMIC) to come up with an accurate map for the city of Doha, Qatar.7 The idea was to use data collected from a fleet of vehicles that are continuously tracked, for accurate and timely detection of road changes, such as new roads, road closures, and detours. Though that early work was successful in coming up with a more accurate map than what navigation systems have, it was not enough to address the main problem of routing. Accurate topological maps do not say much about the time needed to go through each road segment—a main functionality needed for any routing application.
Data access and collaboration. To address the routing problem in the ever-changing roads of Doha, we partnered with the national taxi company Karwa. The collaboration gives us access to all taxi data (both historic and live) that took place in the country, including pick-up and drop-off locations, time, duration, speed, fare, route, as well as sampled GPS points for each trip—a gold mine for our research agenda. But most importantly, we also learned from our partners about the real challenges they face, which helped us prioritize our projects.
Map enrichments for traffic-aware routing. Our first project with Karwa was to enrich the topological maps with traffic information, that is, accurate edge weights for each road segment for each hour of the day. Inferring traffic information from a large number of vehicles can be relatively straightforward. However, the problem is much more challenging when the data is sparse and does not cover many roads with large frequency. We tackle these problems in Stanojevic et al.5,6 and derive a traffic layer with an accuracy comparable to the commercial maps using only sparse data available to us either from Karwa Taxi data as in Stanojevic et al.5 or from using commercial map APIs as in Stanojevic et al.6 In particular, we devise a supervised learning approach for inferring the travel times on the individual road segments using a cohort of trajectories with known travel times. To tackle the issue of data sparsity, we group road segments that are likely to have similar road speeds at a given time. In order to ensure our inferred traffic model accurately models the actual road conditions, we explicitly constrain the solution to the problem using the available metadata and Ridge regularization. For example, a road segment cannot have an average speed that is negative or larger than its speed limit. The resulting machine learning framework allows us to accurately detect the traffic model on every road segment in the city (including many that have little or no data). We validate our model using not only out-of-sample testing, but also by continuously evaluating the accuracy of the model in the deployed system over hundreds of thousands of trajectories every week.
Our research led to the deployment of a system in production for two large companies making over six million routing and travel time requests per month.
Indeed, our proposal led to the creation of a new traffic-aware routing system, named QARTA. To evaluate the quality of our system, we designed a comparison of QARTA API vs. Google Maps API, in which we requested travel-time predictions from both systems for ~ 200K real taxi trips before they took place. By using an up-to-date map of the city and accurate traffic models, our system achieved a 20% reduction in median absolute errors compared to Google Maps API. This gain is quite substantial at scale. Indeed, for a taxi or delivery company that makes 1M trips/month with an average trip duration of 15 minutes, saving one minute on each trip can lead to virtually 6.66% operational efficiency improvement either by increasing the number of trips or by reducing the waiting time.
Travel time estimation. Another interesting line of work is concerned with accurate travel-time predictions which is at the core of the taxi and delivery industry. There are several instances where companies need travel time without routes. For example, the case of driver dispatching where a driver is selected among others based on proximity to the target. Thus, we came up with STAD, which stands for Spatio-Temporal ADjustment of travel time.1 The idea behind STAD is as follow: Let say Layla wants to go from the Pearl neighborhood to Lusail stadium for a soccer game on Thursday night. A free-flow routing engine can spit a route and a travel time of 16 minutes, based on roads free-flow speed. However, if we have access to historical trips in the city, with their origin and destination locations, departure time, and duration, then it should be possible for us to learn an adjustment factor of the free-flow travel time, by taking into account the spatial localization of the origin and destination points, as well as the departure time and day, leading to a more accurate travel time estimation of 23 minutes. In our implementation, we partition the city into small area zones (that is, block polygons) and map each location (origin or destination) to its corresponding block that we use as spatial features. We also partition the time into hours of the day and days of the week and we use as temporal features. Finally, we devise a supervised regression model based on gradient boosting machines to learn the adjustment factor for different spatio-temporal combinations of trips. Our experiments on 750K trips in Doha show that STAD API achieves a median absolute error of 126 seconds against 146 seconds for Google Maps, yielding an error reduction of 14%.
From research to practice. While tackling the research questions discussed here was academically exciting, making true impact required deploying our solution and putting it in the end-user's hands. To that end, we built QARTA, a traffic-aware digital map engine, supporting enterprise customers, for example, transportation and logistics companies, via routing APIs. Currently, we have two major customers of QARTA API that use our technology in production. The first is Karwa taxi company for which we resolve around 1M routing and travel time requests per week; the second is Rafeeq delivery company which makes over 750,000 requests per week to our system, yielding improved QoS and significant financial savings compared to the commercial solution they previously used. We are currently actively exploring partnerships with the adjacent logistics sector (food and last-mile delivery) where accurate route and travel-time predictions are of paramount value for efficient operation.
Next steps. Qatar is not the only fast-growing country, as many countries and cities in the Middle East, Africa, and Southern Asia are also significantly expanding their infrastructure,2 creating a real opportunity for more functional and fast-updating digital maps. We plan to take our system QARTA beyond local impact in Qatar to other international markets.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment