Skip to main content


Eco-Routing with Spatial Big Data


Spatial computing, e.g., routing and navigation, are a set of ideas and technologies that facilitate understanding the geo-physical world, knowing and communicating relations to places in that world, and navigating through those places. The transformational potential of mobility services is already evident. From Google Maps to consumer Global Positioning System (GPS) devices, society has benefited immensely from mobility services and technology. Scientists use GPS to track endangered species to better understand behavior, and farmers use GPS for precision agriculture to increase crop yields while reducing costs. We’ve reached the point where a hiker in Yellowstone, a biker in Minneapolis, and a taxi driver in Manhattan know precisely where they are, their nearby points of interest, and how to reach their destinations. Increasingly, however, the size, variety, and update rate of mobility datasets exceed the capacity of commonly used spatial computing and spatial database technologies to learn, manage, and process the data with reasonable effort. Such data is known as Spatial Big Data (SBD). We believe that harnessing SBD represents the next generation of mobility services.

Examples of emerging SBD datasets include temporally detailed (TD) roadmaps that provide speeds every minute for every road-segment, GPS trace data from cell-phones, and engine measurements of fuel consumption, greenhouse gas (GHG) emissions, etc. SBD has transformative potential. For example, a 2011 McKinsey Global Institute report estimates savings of “about $600 billion annually by 2020” in terms of fuel and time saved by helping vehicles avoid congestion and reduce idling at red lights or left turns. Preliminary evidence for the transformative potential includes the experience of UPS, which saves millions of gallons of fuel by simply avoiding left turns (Figure 1(a)) and associated engine idling when selecting routes 26. Immense savings in fuel-cost and GHG emission are possible if other fleet owners and consumers avoided left-turns and other hot spots of idling, low fuel-efficiency, and congestion.

Ideas advanced in this paper may facilitate ‘eco-routing’ to help identify routes that reduce fuel consumption and GHG emissions, as compared to traditional route services reducing distance travelled or travel-time. It has the potential to significantly reduce US consumption of petroleum, the dominant source of energy for transportation (Figure 1(b)). It may even reduce the gap between domestic petroleum consumption and production (Figure 1©), helping bring the nation closer to the goal of energy independence. However, SBD raises new challenges for the state of the art in spatial computing for mobility services such as routing. First, it requires a change in frame of reference, moving from a global snapshot perspective to the perspective of the individual object traveling through a road network. Second, SBD increases the impact of the partial nature of traditional route query specification. It significantly increases computation cost due to the tremendous growth in the set of preference functions beyond travel-distance and travel-time to include fuel consumption, GHG emissions, travel-times for thousands of possible start-times, etc. Third, the growing diversity of SBD sources makes it less likely that single algorithms, working on specific spatial datasets, will be sufficient to discover answers appropriate for all situations. Other challenges include geo-sensing, privacy, prediction, etc.

Address Goals

Discovery: Further research into the Spatial Big Data will lead to reductions in overall greenhouse emissions and related pollutants by increasing the availability of eco-routing to industry, government and the general public. Transportation sources are one of the primary contributors to greenhouse gas emissions. A recent study by the U.S. Environmental Protection Agency reported that in 2008, transportation sources contributed to approximately 27% of total U.S. greenhouse gas emissions. Additionally, transportation was reported to be the fastest-growing source of U.S. greenhouse gas emissions, accounting for 47% of the net increase in total U.S. emissions since 1990. Also, it was found to be largest end-use source of CO2 (most prevalent greenhouse gas). This creates urgent need for research and development of new technologies (e.g., eco-routing), which can mitigate the problem. This problem could be addressed by developing novel technologies that would assist fuel efficient route planning.

Learning: The current computer science curriculum ignores the topics of spatial big data (SBD) and next generation routing services (e.g., eco-routing). Given the growing enthusiasm of industry and government for such services, we believe that a broad range of undergraduate and graduate students should be exposed to these topics. Thus, we propose to leverage the research activities described in previous sections to develop a new curriculum on spatial big data and next generation routing services for graduate and undergraduate courses.