Transportation Optimization

Learn more »

linklab
logo3

Dmodel:

A Demand Forecasting Model for Taxicab Passengers from a Roving Sensor Network


Dmodel

Investigating passenger demand is essential for the taxicab business. Existing solutions are typically based on dated and inaccurate offline data collected by manual investigations. To address this issue, we propose Dmodel, using roving taxicabs as real-time mobile sensors to (i) infer passenger arriving moments by interactions of vacant taxicabs, and (ii) infer passenger demand by a customized online training with both historical and real-time data. Such huge taxicab data (almost 1TB per year) pose a big data challenge. To address this challenge, Dmodel employs a novel parameter called pickup pattern (accounts for various real-world logical information, e.g., bad weather) to increase the inference accuracy. We evaluate Dmodel with a real-world 450 GB dataset of 14, 000 taxicabs, and results show that compared to the ground truth, Dmodel achieves a 76% accuracy on the demand inference and outperforms a statistical model by 39%.

View details »





pCruise:

Online Cruising Mile Reduction in Large-Scale Taxicab Networks


pCruise

In the taxicab industry, a long-standing challenge is how to reduce taxicabs’ miles spent without fares, i.e., cruising miles. The current solutions for this challenge usually depend on passengers to actively provide their locations in advance for pickups. To address this challenge without the burden on passengers, in this paper, we propose a cruising system, pCruise, for taxicab drivers to find efficient routes to pick up passengers to reduce cruising miles. According to the real-time pick-up events from nearby taxicabs, pCruise characterizes a cruising process with a cruising graph, and assigns weights on edges of the cruising graph to indicate the utility of cruising corresponding road segments. Our weighting process considers the number of nearby passengers and taxicabs together in real-time, aiming at two scenarios where taxicabs are explicitly or implicitly coordinated with each other. Based on a weighted cruising graph, when a taxicab becomes vacant, pCruise provides a distributed online scheduling strategy to obtain and update an efficient cruising route with the minimum length and at least one arriving passenger. We evaluate pCruise based on a real-world GPS dataset from a Chinese city Shenzhen with 14;000 taxicabs. The evaluation results show that pCruise assists taxicab drivers to reduce cruising miles by 42 percent on average.

View details »





Online Cruising Mile Reduction in Large-Scale Taxicab Networks


RHC

Traditional taxi systems in metropolitan areas often suffer from inefficiencies due to uncoordinated actions as system capacity and customer demand change. With the pervasive deployment of networked sensors in modern vehicles, large amounts of information regarding customer demand and system status can be collected in real time. This information provides opportunities to perform various types of control and coordination for large-scale intelligent transportation systems. In this paper, we present a receding horizon control (RHC) framework to dispatch taxis, which incorporates highly spatiotemporally correlated demand/supply models and real-time Global Positioning System (GPS) location and occupancy information. The objectives include matching spatiotemporal ratio between demand and supply for service quality with minimum current and anticipated future taxi idle driving distance. Extensive trace-driven analysis with a data set containing taxi operational records in San Francisco, CA, USA, shows that our solution reduces the average total idle distance by 52%, and reduces the supply demand ratio error across the city during one experimental time slot by 45%. Moreover, our RHC framework is compatible with a wide variety of predictive models and optimization problem formulations. This compatibility property allows us to solve robust optimization problems with corresponding demand uncertainty models that provide disruptive event information.

View details »





Data-Driven Distributionally Robust Vehicle Balancing Using Dynamic Region Partitioning


Partitioning

With the transformation to smarter cities and the development of technologies, a large amount of data is collected from sensors in real-time. This paradigm provides opportunities for improving transportation systems' performance by allocating vehicles towards mobility predicted demand proactively. However, how to deal with uncertainties in demand probability distribution for improving the average system performance is still a challenging and unsolved task. Considering this problem, in this work, we develop a data-driven distributionally robust vehicle balancing method to minimize the worst-case expected cost. We design an efficient algorithm for constructing uncertainty sets of random demand probability distributions, and leverage a quad-tree dynamic region partition method for better capturing the dynamic spatial-temporal properties of the uncertain demand. We then prove equivalent computationally tractable form for numerically solving the distributionally robust problem. We evaluate the performance of the data-driven vehicle balancing framework based on four years of taxi trip data for New York City. We show that the average total idle driving distance is reduced by 30% with the distributionally robust vehicle balancing method using quad-tree dynamic region partition method, compared with vehicle balancing solutions based on static region partitions without considering demand uncertainties. This is about 60 million miles or 8 million dollars cost reduction annually in NYC.

View details »





PreGo:

Smart Personalized Routing for Smart Cities


PreGo

In smart cities, commuters have the opportunities for smart routing that may enable selecting a route with less car accidents, or one that is more scenic, or perhaps a straight and flat route. Such smart personalization requires a data management framework that goes beyond a static road network graph. This paper introduces PreGo, a novel system developed to provide real time personalized routing. The recommended routes by PreGo are smart and personalized in the sense of being (1) adjustable to individual users preferences, (2) subjective to the trip start time, and (3) sensitive to changes of the road conditions. Extensive experimental evaluation using real and synthetic data demonstrates the efficiency of the PreGo system.

View details »





eRoute:

Dynamic Integration of Heterogeneous Transportation Modes under Disruptive Events


eRoute

An integrated urban transportation system usually consists of multiple transport modes that have complementary characteristics of capacities, speeds, and costs, facilitating smooth passenger transfers according to planned schedules. However, such an integration is not designed to operate under disruptive events, e.g., a signal failure at a subway station or a breakdown of a bus, which have rippling effects on passenger demand and significantly increase delays. To address these disruptive events, current solutions mainly rely on a substitute service to transport passengers from and to affected areas using ad-hoc schedules and static routes, e.g., sending shuttles to closed subway stations. These solutions are highly inefficient and do not utilize real-time data to estimate dynamic passenger demand. To fully utilize heterogeneous transportation systems under disruptive events, we design a service called eRoute based on a hierarchical receding horizon control framework to automatically reroute, reschedule, and reallocate multi-mode transportation systems based on real-time and predicted demand and supply. Focusing on an integration of subway and bus, we implement and evaluate eRoute with large datasets including (i) a bus system with 13,000 buses, (ii) a subway system with 127 subway stations, (iii) an automatic fare collection system with a total of 16,840 readers and 8 million card users from a metropolitan city. The data-driven evaluation results show that our solution improves the ratio of served passengers (RSP) by up to 11.5 times and reduces the average traveling time by up to 82.1% compared with existing solutions

View details »





Planning Electric Vehicle Charging Stations Based on User Charging Behavior


evs

Electric vehicles (EVs) as a green alternative of fossil-fuel vehicles (FFVs) have been promoted by many governments all over the world. As a result, constructing an efficient charging pile network has become a crucial task for governments and manufacturers to increase EV adoption, as well-planned charging sites can serve more EV users at a lower cost and improve user satisfaction. Unfortunately, most of existing planning approaches for EV charging stations estimate charging demand and optimize locations based on traffic patterns of FFVs, e.g., traffic flow and parking locations, and the patterns of charging behavior are overlooked causing an inefficient network layout for existing EV users. In this paper, we propose and implement a novel algorithm to estimate charging demand and to plan new charging stations. The observations and analysis of the usage data of the charging mobile app developed by the official EV public service platform of Beijing and pile usage data of the charging pile network (CPN) of Beijing are presented. Users’ charging-related search behavior and navigation behavior and the pile usage pattern are analyzed and modeled. A Bayesian-inference-based algorithm is proposed to fuse the three models to estimate charging demand. A flexible objective function is introduced to tune the benefit between serving the existing EV users well and attracting more FFV drivers. Finally, a reference system is developed using Beijing as a target city, and providing extensive experiments to demonstrate the performance of our system.

View details »





Employing Opportunistic Charging for Electric Taxicabs to Reduce Idle Time


pickachu

For electric taxicabs, the idle time spent on cruising for passengers, seeking chargers, and charging is wasteful. Previous works can only save cruising time through better routing, or charger seeking and charging time through proper charger deployment, but not for both. With the advancement of wireless charging techniques, efficient opportunistic charging of electric vehicles at their parked positions becomes possible. This enables a taxicab to get charged while waiting for the next passenger. In this paper, we present an opportunistic wireless charger deployment scheme in a city, which both maximizes the taxicabs’ opportunity of picking up passengers at the chargers and supports the taxicabs’ continuous operability on roads, while minimizing the total deployment cost. We studied a metropolitan-scale taxicab dataset on several factors important for deploying wireless chargers and determining the numbers of the chargers in the regions: the number of passengers, the functionalities of buildings, and the frequency of passenger appearance in a region, and taxicab traffic flows in a city. Then, we formulate a multi-objective optimization problem and find the solution. Our trace-driven experiments demonstrate the superior performance of our scheme over other representative methods in terms of reducing idle time and supporting the operability of the taxicabs.

View details »






Publications

  • D. Zhang, T. He, S. Munir, J. Stankovic, and S. Lin, Dmodel: A Demand Forecasting Model for Taxicab Passengers from a Roving Sensor Network, IEEE 3rd Int. Conf. on BigData, acceptance rate 19%, June 2014. [pdf] [slides]

  • D. Zhang, T. He, S. Lin, S. Munir, and J. Stankovic, Online Cruising Mile Reduction for Large-Scale Taxicab Networks, IEEE TPDS, Vol. 26, Issue 11, 2015, pp. 3122-3135. [link]

  • F. Miao, S. Han, S. Lin, J. Stankovic, D. Zheng, S. Munir, H. Huang, T. He, and G. Pappas, Taxi Dispatch with Real-Time Sensing Data in Metropolitan Areas - a Receding Horizon Control Approach, IEEE Trans. on Automation Science and Engineering, (invited as one of best papers in ICCPS), Vol. 13, No. 2, April 2016, pp. 463-478. [link]

  • F. Miao, S. Han, A. Hendawi, J. Stankovic, and G. Pappas, Data-Driven Distributionally Robust Vehicle Balancing Using Dynamic Region Partitioning, ICCPS, April 2017. [link]

  • A. Hendawi, D. Hazel, A. Rustum, A. Teredesai, D. Oliver, M. Ali, A. Ahmadain, and J. Stankovic, Smart Personalized Routing for Smart Cities, ICDE, March 2017.[link]

  • Y. Yuan, D. Zhang, F. Miao, J. Stankovic, T. He, G. Pappas, and S, Lin, Dynamic Integration of Heterogeneous Transportation Modes Under Disruptive Events, ICCPS, 2018. [pdf] [link]

  • J. Li, X. Sun, Q. Liu, W. Zhang, H. Liu, and J. Stankovic, Planning Electric Vehicle Charging Stations Based on User Charging Behavior, IOTDI 2018 , April 2018. [pdf]

  • L. Yan, H. Shen, Z. Li, A. Sarkar, J. Stankoivc, J. Zhao, C. Xu and C. Qui, Employing Opportunistic Charging for Electric Taxicabs to Reduce Idle Time, ACM Interactive, Mobile, Wearable, and Ubiquitous Technologies , to appear. [link]



People

John A. Stankovic (PI)

BP America Professor, Director, Link Lab

Department of Computer Science

University of Virginia


Haiying (Helen) Shen

Associate Professor

Department of Computer Science, the Department of Systems \& Information Engineering and the Department of Electrical \& Computer Engineering Department

University of Virginia


Abdeltawab Hendawi

Research Associate

Department of Computer Science

University of Virginia