{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:48Z","timestamp":1750220628228,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T00:00:00Z","timestamp":1598832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NIH","award":["UL1 TR002494, KL2 TR002492, TL1 TR002493"],"award-info":[{"award-number":["UL1 TR002494, KL2 TR002492, TL1 TR002493"]}]},{"DOI":"10.13039\/100000199","name":"USDA","doi-asserted-by":"crossref","award":["2017-51181-27222"],"award-info":[{"award-number":["2017-51181-27222"]}],"id":[{"id":"10.13039\/100000199","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000005","name":"USDOD","doi-asserted-by":"crossref","award":["HM1582-08-1-0017, HM0210-13-1-0005"],"award-info":[{"award-number":["HM1582-08-1-0017, HM0210-13-1-0005"]}],"id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["1541876, 1029711, IIS-1320580, IIS-0940818, IIS-1218168"],"award-info":[{"award-number":["1541876, 1029711, IIS-1320580, IIS-0940818, IIS-1218168"]}]},{"DOI":"10.13039\/100006133","name":"Advanced Research Projects Agency-Energy","doi-asserted-by":"crossref","award":["DE-AR0000795"],"award-info":[{"award-number":["DE-AR0000795"]}],"id":[{"id":"10.13039\/100006133","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM\/IMS Trans. Data Sci."],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>Given a spatial graph, an origin and a destination, and on-board diagnostics (OBD) data, the energy-efficient path selection problem aims to find the path with the least expected energy consumption (EEC). Two main objectives of smart cities are sustainability and prosperity, both of which benefit from reducing the energy consumption of transportation. The challenges of the problem include the dependence of EEC on the physical parameters of vehicles, the autocorrelation of the EEC on segments of paths, the high computational cost of EEC estimation, and potential negative EEC. However, the current cost estimation models for the path selection problem do not consider vehicles\u2019 physical parameters. Moreover, the current path selection algorithms follow the \u201cpath + edge\u201d pattern when exploring candidate paths, resulting in redundant computation. Our preliminary work introduced a physics-guided energy consumption model and proposed a maximal-frequented-path-graph shortest-path algorithm using the model. In this work, we propose an informed algorithm using an admissible heuristic and propose an algorithm to handle negative EEC. We analyze the proposed algorithms theoretically and evaluate the proposed algorithms via experiments with real-world and synthetic data. We also conduct two case studies using real-world data and a road test to validate the proposed method.<\/jats:p>","DOI":"10.1145\/3406596","type":"journal-article","created":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T10:52:46Z","timestamp":1600080766000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Physics-guided Energy-efficient Path Selection Using On-board Diagnostics Data"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9683-9908","authenticated-orcid":false,"given":"Yan","family":"Li","sequence":"first","affiliation":[{"name":"University of Minnesota - Twin Cities, Union Street SE, Minneapolis, MN"}]},{"given":"Pratik","family":"Kotwal","sequence":"additional","affiliation":[{"name":"University of Minnesota - Twin Cities, Union Street SE, Minneapolis, MN"}]},{"given":"Pengyue","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Minnesota - Twin Cities, Church St SE, Minneapolis, Minnesota"}]},{"given":"Yiqun","family":"Xie","sequence":"additional","affiliation":[{"name":"University of Minnesota - Twin Cities, Union Street SE, Minneapolis, MN"}]},{"given":"Shashi","family":"Shekhar","sequence":"additional","affiliation":[{"name":"University of Minnesota - Twin Cities, Union Street SE, Minneapolis, MN"}]},{"given":"William","family":"Northrop","sequence":"additional","affiliation":[{"name":"University of Minnesota - Twin Cities, Church St SE, Minneapolis, Minnesota"}]}],"member":"320","published-online":{"date-parts":[[2020,9,14]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"0","article-title":"Network-wide impacts of eco-routing strategies: A large-scale case study","volume":"25","author":"Ahn Kyoungho","year":"2013","unstructured":"Kyoungho Ahn and Hesham A. Rakha . 2013 . Network-wide impacts of eco-routing strategies: A large-scale case study . Transport. Res. Part D: Transport Environ. 25 , 0 (Dec. 2013). Retrieved from https:\/\/trid.trb.org\/view\/1284524. Kyoungho Ahn and Hesham A. Rakha. 2013. Network-wide impacts of eco-routing strategies: A large-scale case study. Transport. Res. Part D: Transport Environ. 25, 0 (Dec. 2013). Retrieved from https:\/\/trid.trb.org\/view\/1284524.","journal-title":"Transport. Res. Part D: Transport Environ."},{"key":"e_1_2_1_2_1","volume-title":"A MapReduce-based approach for shortest path problem in large-scale networks. Eng. Applic. Artif. Intell. 41 (May","author":"Aridhi Sabeur","year":"2015","unstructured":"Sabeur Aridhi , Philippe Lacomme , Libo Ren , and Benjamin Vincent . 2015. A MapReduce-based approach for shortest path problem in large-scale networks. Eng. Applic. Artif. Intell. 41 (May 2015 ), 151--165. Sabeur Aridhi, Philippe Lacomme, Libo Ren, and Benjamin Vincent. 2015. A MapReduce-based approach for shortest path problem in large-scale networks. Eng. Applic. Artif. Intell. 41 (May 2015), 151--165."},{"volume-title":"KI 2010: Advances in Artificial Intelligence (Lecture Notes in Computer Science)","author":"Artmeier Andreas","key":"e_1_2_1_3_1","unstructured":"Andreas Artmeier , Julian Haselmayr , Martin Leucker , and Martin Sachenbacher . 2010. The shortest path problem revisited: Optimal routing for electric vehicles . In KI 2010: Advances in Artificial Intelligence (Lecture Notes in Computer Science) . Springer , Berlin , 309--316. Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. 2010. The shortest path problem revisited: Optimal routing for electric vehicles. In KI 2010: Advances in Artificial Intelligence (Lecture Notes in Computer Science). Springer, Berlin, 309--316."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Annual Conference on Artificial Intelligence. Springer, 309--316","author":"Artmeier Andreas","year":"2010","unstructured":"Andreas Artmeier , Julian Haselmayr , Martin Leucker , and Martin Sachenbacher . 2010 . The shortest path problem revisited: Optimal routing for electric vehicles . In Proceedings of the Annual Conference on Artificial Intelligence. Springer, 309--316 . Andreas Artmeier, Julian Haselmayr, Martin Leucker, and Martin Sachenbacher. 2010. The shortest path problem revisited: Optimal routing for electric vehicles. In Proceedings of the Annual Conference on Artificial Intelligence. Springer, 309--316."},{"key":"e_1_2_1_5_1","volume-title":"Gutin","author":"Bang-Jensen J\u00fcrgen","year":"2008","unstructured":"J\u00fcrgen Bang-Jensen and Gregory Z . Gutin . 2008 . Digraphs : Theory, Algorithms and Applications. Springer . J\u00fcrgen Bang-Jensen and Gregory Z. Gutin. 2008. Digraphs: Theory, Algorithms and Applications. Springer."},{"volume-title":"FASTSim: A Model to Estimate Vehicle Efficiency, Cost and Performance. SAE Technical Paper 2015-01-0973. SAE International","author":"Brooker Aaron","key":"e_1_2_1_6_1","unstructured":"Aaron Brooker , Jeffrey Gonder , Lijuan Wang , Eric Wood , Sean Lopp , and Laurie Ramroth . 2015. FASTSim: A Model to Estimate Vehicle Efficiency, Cost and Performance. SAE Technical Paper 2015-01-0973. SAE International , Warrendale, PA . Aaron Brooker, Jeffrey Gonder, Lijuan Wang, Eric Wood, Sean Lopp, and Laurie Ramroth. 2015. FASTSim: A Model to Estimate Vehicle Efficiency, Cost and Performance. SAE Technical Paper 2015-01-0973. SAE International, Warrendale, PA."},{"volume-title":"Proceedings of the IEEE 5th International Conference on Intelligent Transportation Systems. 801--809","author":"Cappiello A.","key":"e_1_2_1_7_1","unstructured":"A. Cappiello , I. Chabini , E. K. Nam , A. Lue , and M. Abou Zeid . 2002. A statistical model of vehicle emissions and fuel consumption . In Proceedings of the IEEE 5th International Conference on Intelligent Transportation Systems. 801--809 . A. Cappiello, I. Chabini, E. K. Nam, A. Lue, and M. Abou Zeid. 2002. A statistical model of vehicle emissions and fuel consumption. In Proceedings of the IEEE 5th International Conference on Intelligent Transportation Systems. 801--809."},{"key":"e_1_2_1_8_1","first-page":"4","article-title":"Shortest path finding problem in stochastic time-dependent road networks with stochastic first-in-first-out property","volume":"14","author":"Chen B. Y.","year":"2013","unstructured":"B. Y. Chen , W. H. K. Lam , Q. Li , A. Sumalee , and K. Yan . 2013 . Shortest path finding problem in stochastic time-dependent road networks with stochastic first-in-first-out property . IEEE Trans. Intell. Transport. Syst. 14 , 4 (Dec. 2013), 1907--1917. B. Y. Chen, W. H. K. Lam, Q. Li, A. Sumalee, and K. Yan. 2013. Shortest path finding problem in stochastic time-dependent road networks with stochastic first-in-first-out property. IEEE Trans. Intell. Transport. Syst. 14, 4 (Dec. 2013), 1907--1917.","journal-title":"IEEE Trans. Intell. Transport. Syst."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.02.007"},{"key":"e_1_2_1_10_1","first-page":"3","article-title":"Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment","volume":"12","author":"Deng Yong","year":"2012","unstructured":"Yong Deng , Yuxin Chen , Yajuan Zhang , and Sankaran Mahadevan . 2012 . Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment . Appl. Soft Comput. 12 , 3 (Mar. 2012), 1231--1237. Yong Deng, Yuxin Chen, Yajuan Zhang, and Sankaran Mahadevan. 2012. Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Appl. Soft Comput. 12, 3 (Mar. 2012), 1231--1237.","journal-title":"Appl. Soft Comput."},{"key":"e_1_2_1_11_1","unstructured":"Department of Energy. 2016. Energy Department Announces $58 Million to Advance Fuel-Efficient Vehicle Technologies. Retrieved from https:\/\/www.energy.gov\/articles\/energy-department-announces-58-million-advance-fuel-efficient-vehicle-technologies.  Department of Energy. 2016. Energy Department Announces $58 Million to Advance Fuel-Efficient Vehicle Technologies. Retrieved from https:\/\/www.energy.gov\/articles\/energy-department-announces-58-million-advance-fuel-efficient-vehicle-technologies."},{"key":"e_1_2_1_12_1","unstructured":"Diane Cook and Len Jenshel. 2017. Buying Guide\u2014Cars and Their Environmental Impact. Retrieved from https:\/\/www.nationalgeographic.com\/environment\/green-guide\/buying-guides\/car\/environmental-impact\/.  Diane Cook and Len Jenshel. 2017. Buying Guide\u2014Cars and Their Environmental Impact. Retrieved from https:\/\/www.nationalgeographic.com\/environment\/green-guide\/buying-guides\/car\/environmental-impact\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.11.003"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI\u201911)","author":"Eisner Jochen","year":"2011","unstructured":"Jochen Eisner , Stefan Funke , and Sabine Storandt . 2011 . Optimal route planning for electric vehicles in large networks . In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI\u201911) . AAAI Press, 1108--1113. Jochen Eisner, Stefan Funke, and Sabine Storandt. 2011. Optimal route planning for electric vehicles in large networks. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI\u201911). AAAI Press, 1108--1113."},{"key":"e_1_2_1_16_1","unstructured":"EU Horizon 2020 Research and Innovation Programme. 2020. optiTruck. Retrieved from https:\/\/optitruck.eu\/.  EU Horizon 2020 Research and Innovation Programme. 2020. optiTruck. Retrieved from https:\/\/optitruck.eu\/."},{"key":"e_1_2_1_17_1","first-page":"6","article-title":"Shortest path problem with uncertain arc lengths","volume":"62","author":"Gao Yuan","year":"2011","unstructured":"Yuan Gao . 2011 . Shortest path problem with uncertain arc lengths . Comput. Math. Applic. 62 , 6 (Sept. 2011), 2591--2600. Yuan Gao. 2011. Shortest path problem with uncertain arc lengths. Comput. Math. Applic. 62, 6 (Sept. 2011), 2591--2600.","journal-title":"Comput. Math. Applic."},{"key":"e_1_2_1_18_1","first-page":"10","article-title":"A critical-time-point approach to all-departure-time Lagrangian shortest paths","volume":"27","author":"Gunturi V. M. V.","year":"2015","unstructured":"V. M. V. Gunturi , S. Shekhar , and K. Yang . 2015 . A critical-time-point approach to all-departure-time Lagrangian shortest paths . IEEE Trans. Knowl. Data Eng. 27 , 10 (Oct. 2015), 2591--2603. V. M. V. Gunturi, S. Shekhar, and K. Yang. 2015. A critical-time-point approach to all-departure-time Lagrangian shortest paths. IEEE Trans. Knowl. Data Eng. 27, 10 (Oct. 2015), 2591--2603.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"volume-title":"Advanced Vehicle Technology","author":"Heisler Heinz","key":"e_1_2_1_20_1","unstructured":"Heinz Heisler . 2002. 14 - Vehicle body aerodynamics . In Advanced Vehicle Technology ( Second Edition), Heinz Heisler (Ed.). Butterworth-Heinemann, Oxford , 584--634. DOI:https:\/\/doi.org\/10.1016\/B978-075065131-8\/50015-4 Heinz Heisler. 2002. 14 - Vehicle body aerodynamics. In Advanced Vehicle Technology (Second Edition), Heinz Heisler (Ed.). Butterworth-Heinemann, Oxford, 584--634. DOI:https:\/\/doi.org\/10.1016\/B978-075065131-8\/50015-4"},{"key":"e_1_2_1_21_1","volume-title":"Eco-routing based on a data driven fuel consumption model. arXiv:1801.08602 [stat] (Jan","author":"Huang Xianan","year":"2018","unstructured":"Xianan Huang and Huei Peng . 2018. Eco-routing based on a data driven fuel consumption model. arXiv:1801.08602 [stat] (Jan . 2018 ). Xianan Huang and Huei Peng. 2018. Eco-routing based on a data driven fuel consumption model. arXiv:1801.08602 [stat] (Jan. 2018)."},{"key":"e_1_2_1_22_1","unstructured":"James Manyika Michael Chui Brad Brown Jacques Bughin Richard Dobbs Charles Roxburgh and Angela Hung Byers. 2011. Big data: The next frontier for innovation competition and productivity. Retrieved from https:\/\/www.mckinsey.com\/business-functions\/digital-mckinsey\/our-insights\/big-data-the-next-frontier-for-innovation.  James Manyika Michael Chui Brad Brown Jacques Bughin Richard Dobbs Charles Roxburgh and Angela Hung Byers. 2011. Big data: The next frontier for innovation competition and productivity. Retrieved from https:\/\/www.mckinsey.com\/business-functions\/digital-mckinsey\/our-insights\/big-data-the-next-frontier-for-innovation."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"J. Kwon A. Rousseau and P. Sharer. 2007. Analyzing the Uncertainty in the Fuel Economy Prediction for the EPA MOVES Binning Methodology. SAE Technical Paper 2007-01-0280. SAE International Warrendale PA.  J. Kwon A. Rousseau and P. Sharer. 2007. Analyzing the Uncertainty in the Fuel Economy Prediction for the EPA MOVES Binning Methodology. SAE Technical Paper 2007-01-0280. SAE International Warrendale PA.","DOI":"10.4271\/2007-01-0280"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340964.3340971"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274895.3274933"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653818"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2631775.2631799"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_2_1_29_1","volume-title":"International Energy Outlook","author":"U.S. Energy Information Administration","year":"2017","unstructured":"U.S. Energy Information Administration . 2017. International Energy Outlook 2017 . Technical Report DOE\/EIA-0484(2017). Washington, DC. U.S. Energy Information Administration. 2017. International Energy Outlook 2017. Technical Report DOE\/EIA-0484(2017). Washington, DC."},{"key":"e_1_2_1_30_1","unstructured":"U.S. Energy Information Administration. 2017. Total U.S. energy expenditures in 2015 were the lowest in more than a decade. Retrieved from https:\/\/www.eia.gov\/todayinenergy\/detail.php?id&equals;32432.  U.S. Energy Information Administration. 2017. Total U.S. energy expenditures in 2015 were the lowest in more than a decade. Retrieved from https:\/\/www.eia.gov\/todayinenergy\/detail.php?id&equals;32432."},{"key":"e_1_2_1_31_1","unstructured":"USDOE. 2016. ARPA-E | NEXTCAR. Retrieved from https:\/\/arpa-e.energy.gov\/?q&equals;arpa-e-programs\/nextcar.  USDOE. 2016. ARPA-E | NEXTCAR. Retrieved from https:\/\/arpa-e.energy.gov\/?q&equals;arpa-e-programs\/nextcar."},{"volume-title":"Automated Model Based Design Process to Evaluate Advanced Component Technologies. SAE Technical Paper 2010-01-0936. SAE International","author":"Vijayagopal Ram","key":"e_1_2_1_32_1","unstructured":"Ram Vijayagopal , Larry Michaels , Aymeric P. Rousseau , Shane Halbach , and Neeraj Shidore . 2010. Automated Model Based Design Process to Evaluate Advanced Component Technologies. SAE Technical Paper 2010-01-0936. SAE International , Warrendale, PA . Ram Vijayagopal, Larry Michaels, Aymeric P. Rousseau, Shane Halbach, and Neeraj Shidore. 2010. Automated Model Based Design Process to Evaluate Advanced Component Technologies. SAE Technical Paper 2010-01-0936. SAE International, Warrendale, PA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0491-4"},{"volume-title":"Proceedings of the IEEE Intelligent Vehicles Symposium. 1242--1248","author":"Zhu L.","key":"e_1_2_1_34_1","unstructured":"L. Zhu , J. Holden , E. Wood , and J. Gonder . 2017. Green routing fuel saving opportunity assessment: A case study using large-scale real-world travel data . In Proceedings of the IEEE Intelligent Vehicles Symposium. 1242--1248 . L. Zhu, J. Holden, E. Wood, and J. Gonder. 2017. Green routing fuel saving opportunity assessment: A case study using large-scale real-world travel data. In Proceedings of the IEEE Intelligent Vehicles Symposium. 1242--1248."}],"container-title":["ACM\/IMS Transactions on Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406596","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406596","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:35Z","timestamp":1750197695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,31]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3406596"],"URL":"https:\/\/doi.org\/10.1145\/3406596","relation":{},"ISSN":["2691-1922"],"issn-type":[{"type":"print","value":"2691-1922"}],"subject":[],"published":{"date-parts":[[2020,8,31]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}