Abstract
The Wireless Power Transfer (WPT) system that enables in-motion charging (or wireless charging) for Electric Vehicles (EVs) has been introduced to resolve battery-related issues (such as long charging time, high cost, and short driving range) and increase the wide-acceptance of EVs. In this paper, we study the WPT system with the objectives of minimizing energy consumption, travel time, charging monetary cost on the way, and range anxiety for online EVs. Specifically, we propose the Multi-Objective Route Planner system (MORP) to guide EVs for the multi-objective routing. MORP incorporates two components: traffic state prediction and optimal route determination. For the traffic state prediction, we conducted analysis on a traffic dataset and observed spatial-temporal features of traffic patterns. Accordingly, we introduce the horizontal space-time Autoregressive Integrated Moving Average (ARIMA) model to predict vehicle counts (i.e., traffic volume) for locations with available historical traffic data. And, we use the spatial-temporal ordinary kriging method to predict vehicle counts for locations without historical traffic data. Based on vehicle counts, we use the non-parametric kernel regression method to predict velocity of road sections, which is used to predict travel time and then, energy consumption of a route of an EV with the help of the proposed energy consumption model. We also estimate charging monetary cost and EV related range anxiety based on unit energy cost, predicted travel time and energy consumption, and current onboard energy. We design four different cost functions (travel time, energy consumption, charging monetary cost, and range anxiety) of routing and formulate a multi-objective routing optimization problem. We use the predicted parameters as inputs of the optimization problem and find the optimal route using the adaptive epsilon constraint method. We evaluate our proposed MORP system in four different aspects (including traffic prediction, velocity prediction, energy consumption prediction, and EV routing). From the experimental studies, we find the effectiveness of the proposed MORP system in different aspects of the online EV routing system.
- 2017. Hourly Traffic Data. (2017). http://www.dot.state.sc.us/ Accessed: May, 2017.Google Scholar
- 2017. INRIX Traffic Scorecard. (2017). http://inrix.com/scorecard/ Accessed: May, 2017.Google Scholar
- 2017. NetworkX Graph. (2017). http://networkx.readthedocs.io/en/networkx-1.10 Accessed: May, 2017.Google Scholar
- 2017. Pricing Data. (2017). http://www.nyiso.com/public/markets_operations/market_data/pricing_data/index.jsp Accessed: May, 2017.Google Scholar
- 2017. Spark Electriv Vehicle. (2017). http://www.chevrolet.com/spark-fuel-efficient-car Accessed: May, 2017.Google Scholar
- Afshin Abadi, Tooraj Rajabioun, and Petros A Ioannou. 2015. Traffic flow prediction for road transportation networks with limited traffic data. IEEE Trans. on ITS 16, 2 (2015).Google Scholar
- Javed Aslam, Sejoon Lim, Xinghao Pan, and Daniela Rus. 2012. City-scale traffic estimation from a roving sensor network. In Proc. of ENSS. Google ScholarDigital Library
- Mordecai Avriel. 2003. Nonlinear programming: analysis and methods.Google Scholar
- RaúL BañOs, Julio Ortega, ConsolacióN Gil, Antonio L MáRquez, and Francisco De Toro. 2013. A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows. Computers 8 Industrial Engineering 65, 2 (2013).Google Scholar
- Chenyi Chen, Yin Wang, Li Li, Jianming Hu, and Zuo Zhang. 2012. The retrieval of intra-day trend and its influence on traffic prediction. Transportation research part C: Emerging Technologies 22 (2012). Google ScholarCross Ref
- Tao Cheng, Jiaqiu Wang, James Haworth, Benjamin Heydecker, and Andy Chow. 2014. A dynamic spatial weight matrix and localized space--time autoregressive integrated moving average for network modeling. Geographical Analysis 46, 1 (2014). Google ScholarCross Ref
- Pierre A Cholette. 1982. Prior information and ARIMA forecasting. Journal of Forecasting 1, 4 (1982).Google ScholarCross Ref
- Noel Cressie. 1988. Spatial prediction and ordinary kriging. Mathematical geology 20, 4 (1988). Google ScholarCross Ref
- Mathijs M de Weerdt, Sebastian Stein, Enrico H Gerding, Valentin Robu, and Nicholas R Jennings. 2016. Intention-aware routing of electric vehicles. IEEE Trans. on ITS 17, 5 (2016).Google Scholar
- Kalyanmoy Deb, Karthik Sindhya, and Jussi Hakanen. 2016. Multi-objective optimization. In Decision Sciences: Theory and Practice. Google ScholarCross Ref
- Yan Ding, Chao Chen, Shu Zhang, Bin Guo, Zhiwen Yu, and Yasha Wang. 2017. GreenPlanner: Planning personalized fuel-efficient driving routes using multi-sourced urban data. In Proc. of PERCOM.Google Scholar
- Matthias Ehrgott, Jonas Ide, and Anita Schöbel. 2014. Minmax robustness for multi-objective optimization problems. European Journal of Operational Research 239, 1 (2014). Google ScholarCross Ref
- Gerhard H Fischer and Ivo W Molenaar. 2012. Rasch models: Foundations, recent developments, and applications. Springer Science 8 Business Media.Google Scholar
- Keivan Ghoseiri and Seyed Farid Ghannadpour. 2010. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing 10, 4 (2010). Google ScholarDigital Library
- Jeffrey D Hart and Thomas E Wehrly. 1986. Kernel regression estimation using repeated measurements data. JASA 81, 396 (1986).Google Scholar
- Eric Horvitz and John Krumm. 2012. Some help on the way: Opportunistic routing under uncertainty. In Proc. of UBICOMP. Google ScholarDigital Library
- Shenggong Ji, Yu Zheng, and Tianrui Li. 2016. Urban sensing based on human mobility. In Proc. of UBICOMP. Google ScholarDigital Library
- Malte F Jung, David Sirkin, Turgut M Gür, and Martin Steinert. 2015. Displayed uncertainty improves driving experience and behavior: The case of range anxiety in an electric car. In Proc. of CHI.Google ScholarDigital Library
- Lei Kang, Bozhao Qi, Dan Janecek, and Suman Banerjee. 2015. EcoDrive: A Mobile Sensing and Control System for Fuel Efficient Driving. In Proc. of Mobicom. Google ScholarDigital Library
- Daniel Krajzewicz, Jakob Erdmann, Michael Behrisch, and Laura Bieker. 2012. Recent Development and Applications of SUMO - Simulation of Urban MObility. International Journal On ASM (2012).Google Scholar
- John Krumm and Eric Horvitz. 2006. Predestination: Inferring destinations from partial trajectories. In Proc. of UBICOMP. Google ScholarDigital Library
- Marco Laumanns, Lothar Thiele, Kalyanmoy Deb, and Eckart Zitzler. 2002. Combining convergence and diversity in evolutionary multiobjective optimization. Evolutionary computation 10, 3 (2002). Google ScholarDigital Library
- Marco Laumanns, Lothar Thiele, and Eckart Zitzler. 2006. An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 3 (2006). Google ScholarCross Ref
- I Lawrence and Kuei Lin. 1989. A concordance correlation coefficient to evaluate reproducibility. Biometrics (1989).Google Scholar
- Arthur Lewbel and Oliver Linton. 2002. Nonparametric censored and truncated regression. Econometrica 70, 2 (2002). Google ScholarCross Ref
- Ruimin Li, Geoffrey Rose, and Majid Sarvi. 2006. Using automatic vehicle identification data to gain insight into travel time variability and its causes. JTRB 1945 (2006).Google ScholarCross Ref
- Jie Lin, Wei Yu, Xinyu Yang, Qingyu Yang, Xinwen Fu, and Wei Zhao. 2015. A novel dynamic En-route decision real-time route guidance scheme in intelligent transportation systems. In Proc. of ICDCS. Google ScholarCross Ref
- Jeremy Neubauer and Eric Wood. 2014. The impact of range anxiety and home, workplace, and public charging infrastructure on simulated battery electric vehicle lifetime utility. Journal of Power Sources 257 (2014). Google ScholarCross Ref
- Chenxi Qiu, Ankur Sarker, and Haiying Shen. 2017. Power distribution scheduling for electric vehicles in wireless power transfer systems. In Proc. of SECON. Google ScholarCross Ref
- Chenxi Qiu, Haiying Shen, Ankur Sarker, Vivekgautham Soundararaj, Mac Devine, and Egan Ford. 2016. Towards Green Transportation: Fast Vehicle Velocity Optimization for Fuel Efficiency. In Proc. of IEEE CloudCom.Google ScholarCross Ref
- Nadine Rauh, Thomas Franke, and Josef F Krems. 2015. Understanding the impact of electric vehicle driving experience on range anxiety. Human factors 57, 1 (2015). Google ScholarCross Ref
- Jackeline Rios, Pablo Sauras-Perez, Andrea Gil, Andre Lorico, Joachim Taiber, and Pierluigi Pisu. 2014. Battery electric bus simulator-a tool for energy consumption analysis. Technical Report. SAE Technical Paper.Google Scholar
- Ankur Sarker, Zhuozhao Li, William Kolodzey, and H. Shen. 2017. Opportunistic energy sharing between power grid And electric vehicles: A game theory-based nonlinear pricing policy. In Proc. of ICDCS. Google ScholarCross Ref
- Ankur Sarker, Chenxi Qiu, Haiying Shen, Andrea Gil, Joachim Taiber, Mashrur Chowdhury, Jim Martin, Mac Devine, and AJ Rindos. 2016. An efficient wireless power transfer system to balance the state of charge of electric vehicles. In Proc. of ICPP.Google ScholarCross Ref
- Michael Schneider, Andreas Stenger, and Dominik Goeke. 2014. The electric vehicle-routing problem with time windows and recharging stations. Transportation Science 48, 4 (2014). Google ScholarDigital Library
- Liuwang Kang Haiying Shen and Ankur Sarker. 2017. Velocity optimization of pure electric vehicles with traffic dynamics and driving safety considerations. In Proc. of ICDCS.Google Scholar
- V Srinivasan and Gerald Luther Thompson. 1976. Algorithms for minimizing total cost, bottleneck time and bottleneck shipment in transportation problems. Naval Research Logistics 23, 4 (1976).Google Scholar
- Chao Sun, Scott Jason Moura, Xiaosong Hu, J Karl Hedrick, and Fengchun Sun. 2015. Dynamic traffic feedback data enabled energy management in plug-in hybrid electric vehicles. IEEE Trans. on CST 23, 3 (2015).Google Scholar
- Nick T Thomopoulos. 2015. Demand forecasting for inventory control. In Demand Forecasting for Inventory Control.Google Scholar
- Matt P Wand and M Chris Jones. 1994. Kernel smoothing. Crc Press.Google Scholar
- H. Wang, J. Gong, Y. Zhuang, H. Shen, and J. Lach. 2017. Healthedge: Task scheduling for edge computing with health emergency and human behavior consideration in smart homes. In Proc. of Big Data.Google Scholar
- Xiaokun Wang and Kara Kockelman. 2009. Forecasting network data: Spatial interpolation of traffic counts from texas data. JTRB 2105 (2009).Google Scholar
- Daniel B Work, Sébastien Blandin, Olli-Pekka Tossavainen, Benedetto Piccoli, and Alexandre M Bayen. 2010. A traffic model for velocity data assimilation. Applied Mathematics Research eXpress 2010, 1 (2010).Google Scholar
- Jie Xu, Dingxiong Deng, Ugur Demiryurek, Cyrus Shahabi, and Mihaela van der Schaar. 2015. Mining the situation: Spatiotemporal traffic prediction with big data. IEEE Journal of STSP 9, 4 (2015). Google ScholarCross Ref
- Mengwen Xu, Dong Wang, and Jian Li. 2016. DESTPRE: a data-driven approach to destination prediction for taxi rides. In Proc. of UBICOMP. Google ScholarDigital Library
- Li Yan and Haiying Shen. 2016. TOP: Vehicle trajectory based driving speed optimization strategy for travel time minimization and road congestion avoidance. In Proc. of MASS. Google ScholarCross Ref
- Li Yan, Haiying Shen, Juanjuan Zhao, Chengzhong Xu, Feng Luo, and Chenxi Qiu. 2017. CatCharger: Deploying Wireless Charging Lanes in a Metropolitan Road Network through Categorization and Clustering of Vehicle Traffic. In Proc. of INFOCOM. Google ScholarCross Ref
- Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. 2011. Driving with knowledge from the physical world. In Proc. of KDD. Google ScholarDigital Library
- Desheng Zhang, Juanjuan Zhao, Fan Zhang, Ruobing Jiang, and Tian He. 2015. Feeder: supporting last-mile transit with extreme-scale urban infrastructure data. In Proc. of IPSN. Google ScholarDigital Library
- Fuzheng Zhang, David Wilkie, Yu Zheng, and Xing Xie. 2013. Sensing the pulse of urban refueling behavior. In Proc. of UBICOMP. Google ScholarDigital Library
- Rick Zhang, Federico Rossi, and Marco Pavone. 2016. Routing autonomous vehicles in congested transportation networks: Structural properties and coordination algorithms. arXiv preprint arXiv:1603.00939 (2016).Google Scholar
- Yu Zheng, Tong Liu, Yilun Wang, Yanmin Zhu, Yanchi Liu, and Eric Chang. 2014. Diagnosing New York city's noises with ubiquitous data. In Proc. of UBICOMP. Google ScholarDigital Library
- Yu Zheng, Yanchi Liu, Jing Yuan, and Xing Xie. 2011. Urban computing with taxicabs. In Proc. of UBICOMP. Google ScholarDigital Library
- Brian D Ziebart, Andrew L Maas, Anind K Dey, and J Andrew Bagnell. 2008. Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior. In Proc. of UBICOMP.Google ScholarDigital Library
Index Terms
- MORP: Data-Driven Multi-Objective Route Planning and Optimization for Electric Vehicles
Recommendations
Joint electric vehicle routing and battery health management integrating an explicit state of charge model
AbstractAlthough fleet management has been extensively explored in transportation science, the rise of electromobility imposes several scientific challenges and opportunities. So far, few attempts were made to include battery degradation in the Electric ...
Highlights- A new EVRP formulation that includes battery degradation and speed limitations.
- Realistic SoH and SoC models that can be included in optimization problems.
- A method to estimate the battery degradation after performing missions.
Estimating energy consumption and charging duration of electric vehicle in multigraph
AbstractThe two main features of electric vehicles are their ability to recuperate energy and their spent time in charging stations, including the waiting time in the queue and the battery charge duration. In this paper, we focus on estimating ...
Highlights- This article focuses on Electric vehicles and energy issues.
- Energy consumption ...
The Electric Vehicle Routing Problem with Capacitated Charging Stations
Electric vehicle routing problems (E-VRPs) deal with routing a fleet of electric vehicles (EVs) to serve a set of customers while minimizing an operational criterion, for example, cost or time. The feasibility of the routes is constrained by the autonomy ...
Comments