Reduction in greenhouse gas (GHG) emissions from transportation is essential in combating global warming and climate change. For example, the EU has committed to reduce GHG emissions to 20% below 1990 levels by 2020; and in the EU, emissions from transportation account for nearly a quarter of the total GHG emissions. Eco-routing, which enables drivers to use the most eco-friendly routes, is a simple yet effective approach to reducing vehicle emissions.
We study how to enable eco-routing using big transportation data, including GPS (Global Positioning System) data, CAN (Controller Area Network) bus data, and 3D laser scan data. In particular, we achieve eco-routing through the following three major steps: quantifying vehicular environmental impact, assigning eco-weights to a road network, and developing novel eco-routing algorithms.
To recommend the most eco-friendly routes, it is necessary to be able to reliably quantify the emissions of vehicles as they travel in a road network. Actual emissions of vehicles can be obtained from CAN bus data. In addition, vehicular emissions can also be computed based on vehicles' speeds and accelerations and road grades using appropriate vehicular environmental impact models.
EcoMark [1, 2]: To understand the usability of various vehicular environmental impact models in eco-routing, a series of evaluation frameworks, i.e., EcoMark [1] and EcoMark 2.0 [2], are developed based on GPS data (containing vehicles' speeds and accelerations), CAN bus data (containing vehicles' actual emissions), and 3D road networks (containing road grades). In the evaluation frameworks, we identify the conditions under which a model can be used for reliably quantifying vehicular emissions.
Lifting 2D road networks to 3D road networks [3]: Most vehicular environmental impact models require the information of road grades to accurately compute vehicular emissions. However, most existing on-line map service providers (e.g., OpenStreetMap) only provide 2D road networks where the road grades are unavailable. A spatial network lifting framework is developed to lift a 2D road network to a 3D road network using 3D laser scan data, where the 3D road network contains road grades information.
Eco-routing relies on a weighted-graph representation of the underlying road network, where each edge is associated with an eco-weight. The eco-weights should accurately capture the vehicular emissions of traversing the edges. We categorize eco-weights into two groups, simple v.s. advanced weights and static v.s. dynamic weights.
Simple eco-weights are time-dependent and deterministic, while advanced eco-weights are time-dependent and uncertain. In particular, a simple eco-weight employs a single value to capture the emissions of traversing an edge during an interval; while an advanced weight employs a random variable to capture the distribution of the emissions of traversing an edge during an interval.
Static weights capture typically traffic patterns, e.g., peak v.s. off-peark intervals, and remain relatively stable. In contrast, dynamic weights capture dynamic and instant traffic patterns, e.g., accidents, and keep updating as the real-time GPS data stream in. A series of methods are developed to enable various types of eco-weights, as shown in Table 1.
| Static Weights | Dynamic Weights | |
| Simple Weights | Graph Weight Annotation [4] | Spatio-Temporal Hidden Markov Model [7] |
| Advanced Weights | Time-Dependent Uncertain Graph [5, 6] | Spatio-Temporal Hidden Markov Model [7] |
Graph Weight Annotation [4]: This method annotates all edges in a road network with static, simple eco-weights based on a set of historical GPS data that only covers a fraction of the edges in the road network. The whole period of interest is separated into pre-defined intervals, e.g., weekday peek, weekday offpeak, and weekends. The GPS data occurred in an interval are employed for annotating hot edges (i.e., the edges that are covered by the GPS data) with eco-weights in the interval. Next, the eco-weight of a cold edge (i.e., an edge that is not covered by the GPS data) is inferred from the eco-weights of the hot edges that are topologically correlated to the cold edge. The topological relationship between two edges are defined based on their weighted PageRank values and on whether they are adjacent, which can all be derived from the topology of the road network.
Time-Dependent Uncertain Graph [5, 6]: This method assigns static, advanced eco-weights to edges with sufficient amount historical GPS data. The whole period of interest is partitioned into 15-minute intervals. Given an edge, for each interval, a random variable is derived from the GPS data occurred on the edge during the interval. If two random variables in two adjacent intervals are similar with each other, the two intervals are combined into a long interval and a new random variable is derived from the GPS data during the long interval. This process continues iteratively until no adjacent intervals are similar enough to be combined. A random variable is represented by either a histogram [5] or a Gaussian mixture model [6], since both presentations are able to describe an arbitrary distribution. Various histogram compression methods are proposed to ensure histogram based representation compact and accurate.
Spatio-Temporal Hidden Markov Model (STHMM) [7]: This model assigns dynamic, both simple and advanced eco-weights to edges with sufficient amount of historical GPS data and real time GPS data. Specifically, each edge has an associated emissions time series which is derived from GPS data on the edge. The time series may be sparse because GPS data cannot always cover all intervals. Nearby edges' time series may be dependent because the traffic condition (e.g., congestion) on an edge may affect the traffic conditions on nearby edges. Different edges' time series are heterogeneous because the traffic conditions on different edges may have distinct characteristics. An STHMM models the edges' sparse, dependent, and heterogeneous emissions time series in a combined manner and is able to infer the near future emissions (both expected emission and emissions distribution) as GPS data stream in.
Enabling practically useful eco-routing services calls for novel eco-routing algorithms that fully utilize the various eco-weights. To this end, three novel eco-routing algorithms, stochastic skyline routing, context-aware, personalized routing, and continuous routing, are developed.
Stochastic skyline routing [6]: Eco-routing is not about only minimizing emissions when planing routes, but about considering various factors. For example, if the eco-route with the least emissions takes twice travel time of the fastest route, users may not be interested in taking the eco-route. Stochastic skyline routing considers multiple travel costs (specifically, travel distance, travel time, and emissions), time-dependency (i.e., peak vs. off-peak traffic patterns), and uncertainty (e.g., due to differences in driving behavior). Given a source-destination pair and a trip starting time, it is able to return a set of pareto-optimal routes (a.k.a. skyline routes) that consider all travel costs of interest.
Context-aware, personalized routing [8]: This routing strategy takes into account the different driving behaviors of different drivers and the context-varying preferences of individual drivers (e.g., time-efficient driving or fuel-efficient driving). Given a source-destination pair and a trip starting time, a single route that best satisfies the driver’s preferences, which are learned automatically from the driver’s past trajectories, is returned.
Continuous routing [9]: Dynamic eco-weights may change substantially due to instant traffic conditions, e.g., accidents. Continuous routing is able to re-route vehicles according to the latest eco-weights and the current locations of the vehicles.
EcoTour [10]: The EcoTour prototype computes and compares the shortest, the fastest, and the most eco-friendly routes for arbitrary source-destination pairs in Denmark.
EcoSky [11]: The EcoSky prototype consolidates techniques we have developed for eco-weight annotation and eco-routing. The EcoSky system annotates a road network with time-dependent and uncertain eco-weights that are determined primarily based on GPS data and offers different types of eco-routing based on eco-weights, including basic eco-routing, skyline eco-routing, and personalized eco-routing.
iPark [12]: Search for parking by drivers is a significant contributor to congestion in cities and thus also generates considerable amounts of greenhouse gas emissions. However, parking spaces are often missing in full or in part for cities in existing maps (e.g., Google Maps, Bing Maps, and OpenStreetMap). The iPark prototype identifies parking spaces, including parking zones and on-street parking lanes, from trajectories and is able to annotate the parking information to OpenStreetMap.
Finding Shortest Paths on Terrains [13]: Given two locations on a terrain, this method is able to find the shortest path between the locations efficiently. This operation may be useful when building new roads.
| [1] | Chenjuan Guo, Yu Ma, Bin Yang, Christian S. Jensen, Manohar Kaul: EcoMark: evaluating models of vehicular environmental impact. SIGSPATIAL/GIS 2012: 269-278. |
| [2] | Chenjuan Guo, Bin Yang, Ove Andersen, Christian S. Jensen, Kristain Torp: EcoMark 2.0: Empowering Eco-Routing with Vehicular Environmental Models and Actual Vehicle Fuel Consumption Data. GeoInformatica. |
| [3] | Manohar Kaul, Bin Yang, Christian S. Jensen: Building Accurate 3D Spatial Networks to Enable Next Generation Intelligent Transportation Systems. MDM (1) 2013: 137-146. Best Paper Award. |
| [4] | Bin Yang, Manohar Kaul, Christian S. Jensen: Using Incomplete Information for Complete Weight Annotation of Road Networks. IEEE Trans. Knowl. Data Eng. 26(5): 1267-1279 (2014). |
| [5] | Yu Ma, Bin Yang, Christian S. Jensen: Enabling Time-Dependent Uncertain Eco-Weights For Road Networks. GeoRich 2014. |
| [6] | Bin Yang, Chenjuan Guo, Christian S. Jensen, Manohar Kaul, Shuo Shang: Stochastic skyline route planning under time-varying uncertainty. ICDE 2014: 136-147. |
| [7] | Bin Yang, Chenjuan Guo, Christian S. Jensen: Travel Cost Inference from Sparse, Spatio-Temporally Correlated Time Series Using Markov Models. PVLDB 6(9): 769-780 (2013). |
| [8] | Bin Yang, Chenjuan Guo, Yu Ma, Christian S. Jensen: Towards Context Aware, Personlized Routing. The VLDB Journal 24(2): 297-318 (2015). |
| [9] | Manohar Kaul, Raymond Chi-Wing Wong, Christian S. Jensen, Bin Yang, Yu Ma: Scalable Real-time Continuous Fastest Route Planning. In submission. |
| [10] | Ove Andersen, Christian S. Jensen, Kristian Torp, Bin Yang: EcoTour: Reducing the Environmental Footprint of Vehicles Using Eco-routes. MDM (1) 2013: 338-340. Best Demo Award. |
| [11] | Chenjuan Guo, Bin Yang, Ove Andersen, Christian S. Jensen, Kristain Torp: EcoSky: reducing vehicular environmental impact through eco-routing. ICDE 2014. |
| [12] | Bin Yang, Nicolas Fantini, Christian S. Jensen: iPark: identifying parking spaces from trajectories. EDBT 2013: 705-708. |
| [13] | Manohar Kaul, Raymond Chi-Wing Wong, Bin Yang, Christian S. Jensen: Finding Shortest Paths on Terrains by Killing Two Birds with One Stone. PVLDB 7(1): 73-84 (2013). |
This work was partially supported by the REDUCTION project that is funded by the European Commission as an FP7-ICT-2011-7 STREP project, contract number 288254.