Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles

References

• Abraham I, Delling D, Fiat A, Goldberg AV, Werneck RF (2012) HLDB: Location-based services in databases. Proc. 20th ACM SIGSPATIAL Internat. Sympos. Adv. Geographic Inform. Systems (GIS’12) (ACM, New York), 339–348.Crossref, Google Scholar
• Bast H, Delling D, Goldberg AV, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck RF (2016) Route planning in transportation networks. Kliemann L, Sanders P, eds. Algorithm Engineering, Lecture Notes in Computer Science, vol. 9220 (Springer, Cham, Switzerland), 19–80.Crossref, Google Scholar
• Batz GV, Geisberger R, Sanders P, Vetter C (2013) Minimum time-dependent travel times with contraction hierarchies. ACM J. Experiment. Algorithmics 18:1.4:1–1.4:43.Google Scholar
• Bauer R, Delling D, Sanders P, Schieferdecker D, Schultes D, Wagner D (2010) Combining hierarchical and goal-directed speed-up techniques for Dijkstra’s algorithm. ACM J. Experiment. Algorithmics 15:2.3:1–2.3:31.Google Scholar
• Baum M, Dibbelt J, Pajor T, Wagner D (2013) Energy-optimal routes for electric vehicles. Proc. 21st ACM SIGSPATIAL Internat. Conf. Adv. Geographic Inform. Systems (GIS’13) (ACM, New York), 54–63.Crossref, Google Scholar
• Baum M, Dibbelt J, Pajor T, Wagner D (2016) Dynamic time-dependent route planning in road networks with user preferences. Goldberg A, Kulikov A, eds. Experimental Algorithms (SEA 2016), Lecture Notes in Computer Science, vol. 9685 (Springer, Cham, Switzerland), 33–49.Crossref, Google Scholar
• Baum M, Dibbelt J, Wagner D, Zündorf T (2017a) Modeling and engineering constrained shortest path algorithms for battery electric vehicles. Proc. 25th Annual Eur. Sympos. Algorithms (ESA’17), Leibniz International Proceedings in Informatics (LIPIcs), vol. 87 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 11:1–11:16.Google Scholar
• Baum M, Sauer J, Wagner D, Zündorf T (2017b) Consumption profiles in route planning for electric vehicles: Theory and applications. Proc. 16th Internat. Sympos. Experiment. Algorithms (SEA’17), Leibniz International Proceedings in Informatics (LIPIcs), vol. 75 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 19:1–19:18.Google Scholar
• Baum M, Dibbelt J, Gemsa A, Wagner D, Zündorf T, 2015 Shortest feasible paths with charging stops for battery electric vehicles. Proc. 23rd ACM SIGSPATIAL Internat. Conf. Adv. Geographic Inform. Systems (GIS’15) (ACM, New York), 44:1–44:10.Crossref, Google Scholar
• Delling D, Wagner D (2009) Time-dependent route planning. Robust and Online Large-Scale Optimization, Lecture Notes in Computer Science, vol. 5868 (Springer, Berlin, Heidelberg), 207–230.Crossref, Google Scholar
• Delling D, Werneck RF (2015) Customizable point-of-interest queries in road networks. IEEE Trans. Knowledge Data Engrg. 27(3):686–698.Crossref, Google Scholar
• Delling D, Goldberg AV, Werneck RF (2011) Faster batched shortest paths in road networks. Proc. 11th Workshop Algorithmic Approaches Transportation Model. Optim. Systems (ATMOS’11), OpenAccess Series in Informatics (OASIcs), vol. 20 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 52–63.Google Scholar
• Delling D, Goldberg AV, Pajor T, Werneck RF (2017) Customizable route planning in road networks. Transportation Sci. 51(2):566–591.Link, Google Scholar
• Desaulniers G, Errico F, Irnich S, Schneider M (2016) Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res. 64(6):1388–1405.Link, Google Scholar
• Dibbelt J, Pajor T, Wagner D (2015) User-constrained multi-modal route planning. ACM J. Experiment. Algorithmics 19:3.2:1–3.2:19.Google Scholar
• Dibbelt J, Strasser B, Wagner D (2016) Customizable contraction hierarchies. ACM J. Experiment. Algorithmics 21:1.5:1–1.5:49.Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269–271.Crossref, Google Scholar
• Efentakis A, Pfoser D (2013) Optimizing landmark-based routing and preprocessing. Proc. 6th ACM SIGSPATIAL Internat. Workshop Comput. Transportation Sci. (IWCTS’13) (ACM, New York), 25–30.Crossref, Google Scholar
• Eisner J, Funke S, Storandt S (2011) Optimal route planning for electric vehicles in large networks. Proc. 25th AAAI Conf. Artificial Intelligence (AAAI’11) (AAAI Press, Palo Alto, CA), 1108–1113.Google Scholar
• Funke S, Storandt S (2013) Polynomial-time construction of contraction hierarchies for multi-criteria objectives. Proc. 15th Meeting Algorithm Engrg. Experiments (ALENEX’13) (SIAM, Philadelphia), 31–54.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Geisberger R, Vetter C (2011) Efficient routing in road networks with turn costs. Pardalos PM, Rebennack S, eds. Experimental Algorithms (SEA 2011), Lecture Notes in Computer Science, vol. 6630 (Springer, Berlin, Heidelberg), 100–111.Crossref, Google Scholar
• Geisberger R, Kobitzsch M, Sanders P (2010) Route planning with flexible objective functions. Proc. 12th Workshop Algorithm Engrg. Experiments (ALENEX’10) (SIAM, Philadelphia), 124–137.Crossref, Google Scholar
• Geisberger R, Sanders P, Schultes D, Vetter C (2012) Exact routing in large road networks using contraction hierarchies. Transportation Sci. 46(3):388–404.Link, Google Scholar
• Goeke D, Schneider M (2015) Routing a mixed fleet of electric and conventional vehicle. Eur. J. Oper. Res. 245(1):81–99.Crossref, Google Scholar
• Goldberg AV, Harrelson C (2005) Computing the shortest path: A* search meets graph theory. Proc. 16th Annual ACM–SIAM Sympos. Discrete Algorithms (SODA’05) (SIAM, Philadelphia), 156–165.Google Scholar
• Goodrich MT, Pszona P (2014) Two-phase bicriterion search for finding fast and efficient electric vehicle routes. Proc. 22nd ACM SIGSPATIAL Internat. Conf. Adv. Geographic Inform. Systems (GIS’14) (ACM, New York), 193–202.Crossref, Google Scholar
• Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inform. Processing Lett. 1(4):132–133.Crossref, Google Scholar
• Handler GY, Zang I (1980) A dual algorithm for the constrained shortest path problem. Networks 10(4):293–309.Crossref, Google Scholar
• Hansen P (1980) Bicriterion path Pproblems. Fandel G, Gal T, eds. Multiple Criteria Decision Making Theory and Application, Lecture Notes in Economics and Mathematical Systems, vol. 177 (Springer, Berlin, Heidelberg), 109–127.Google Scholar
• Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Crossref, Google Scholar
• Hartmann F, Funke S (2014) Energy-efficient routing: Taking speed into account. Lutz C, Thielscher M, eds. KI 2014: Advances in Artificial Intelligence (KI 2014), Lecture Notes in Computer Science, vol. 8736 (Springer, Cham, Switzerland), 86–97.Google Scholar
• Hausberger S, Rexeis M, Zallinger M, Luz R (2009) Emission factors from the model PHEM for the HBEFA version 3. Technical Report I-20/2009, University of Technology, Graz, Austria.Google Scholar
• Huber G, Bogenberger K (2015) Long-trip optimization of charging strategies for battery electric vehicles. Transportation Res. Record J. Transportation Res. Board 2497(1):45–53.Crossref, Google Scholar
• Johnson DB (1977) Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1):1–13.Crossref, Google Scholar
• Khuller S, Malekian A, Mestre J (2011) To fill or not to fill: The gas station problem. ACM Trans. Algorithms 7(3):36:1–36:16.Crossref, Google Scholar
• Kobayashi Y, Kiyama N, Aoshima H, Kashiyama M (2011) A route search method for electric vehicles in consideration of range and locations of charging stations. Proc. 7th IEEE Intelligent Vehicles Sympos. (IV’11) (IEEE, Piscataway, NJ), 920–925.Crossref, Google Scholar
• Liao CS, Lu SH, Shen ZJM (2016) The electric vehicle touring problem. Transportation Res. Part B: Methodological 86:163–180.Crossref, Google Scholar
• Lin SH, Gertsch N, Russell JR (2007) A linear-time algorithm for finding optimal vehicle refueling policies. Oper. Res. Lett. 35(3):290–296.Crossref, Google Scholar
• Liu C, Wu J, Long C (2014) Joint charging and routing optimization for electric vehicle navigation systems. IFAC Proc. Volumes 47(3):2106–2111.Crossref, Google Scholar
• Mandow L, Pérez-de-la-Cruz JL (2010) Multiobjective A* search with consistent heuristics. J. ACM 57(5):27:1–27:24.Crossref, Google Scholar
• Martins EQV (1984) On a multicriteria shortest path problem. Eur. J. Oper. Res. 16(2):236–245.Crossref, Google Scholar
• Montoya A, Guéret C, Mendoza JE, Villegas JG (2017) The electric vehicle routing problem with nonlinear charging function. Transportation Res. Part B: Methodological 103:87–110.Crossref, Google Scholar
• Murakami K (2018) Formulation and algorithms for route planning problem of plug-in hybrid electric vehicles. Oper. Res. 18(2):497–519.Crossref, Google Scholar
• Pelletier S, Jabali O, Laporte G, Veneroni M (2017) Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models. Transportation Res. Part B: Methodological 103:158–187.Crossref, Google Scholar
• Pourazarm S, Cassandras CG, Wang T (2016) Optimal routing and charging of energy-limited vehicles in traffic networks. Internat. J. Robust Nonlinear Control 26(6):1325–1350.Crossref, Google Scholar
• Qin H, Zhang W (2011) Charging scheduling with minimal waiting in a network of electric vehicles and charging stations. Proc. 8th ACM Internat. Workshop Vehicular Inter-Networking (VANET ’11) (ACM, New York), 51–60.Crossref, Google Scholar
• Sachenbacher M, Leucker M, Artmeier A, Haselmayr J (2011) Efficient energy-optimal routing for electric vehicles. Proc. 25th AAAI Conf. Artificial Intelligence (AAAI’11) (AAAI Press, Palo Alto, CA), 1402–1407.Google Scholar
• Sanders P, Schultes D (2005) Highway hierarchies hasten exact shortest path queries. Brodal GS, Leonardi S, eds. Algorithms (ESA 2005), Lecture Notes in Computer Science, vol. 3669 (Springer, Berlin, Heidelberg), 568–579.Crossref, Google Scholar
• Schiffer M, Walther G (2018) An adaptive large neighborhood search for the location-routing problem with intra-route facilities. Transportation Sci. 52(2):331–352.Link, Google Scholar
• Schneider M, Stenger A, Goeke D (2014) The electric vehicle-routing problem with time windows and recharging stations. Transportation Sci. 48(4):500–520.Link, Google Scholar
• Schönfelder R, Leucker M (2015) Abstract routing models and abstractions in the context of vehicle routing. Proc. 24th Internat. Joint Conf. Artificial Intelligence (IJCAI’15) (AAAI Press, Palo Alto, CA), 2639–2645.Google Scholar
• Schönfelder R, Leucker M, Walther S (2014) Efficient profile routing for electric vehicles. Hsu RCH, Wang S, eds. Internet of Vehicles—Technologies and Services (IOV 2014), Lecture Notes in Computer Science, vol. 8662 (Springer, Cham, Switzerland), 21–30.Crossref, Google Scholar
• Storandt S (2012a) Quick and energy-efficient routes: Computing constrained shortest paths for electric vehicles. Proc. 5th ACM SIGSPATIAL Internat. Workshop Computational Transportation Sci. (IWCTS’12) (ACM, New York), 20–25.Crossref, Google Scholar
• Storandt S (2012b) Route planning for bicycles—Exact constrained shortest paths made practical via contraction hierarchy. Proc. 22nd Internat. Conf. Automated Planning Scheduling (ICAPS’12) (AAAI Press, Palo Alto, CA), 234–242.Google Scholar
• Storandt S, Funke S (2012) Cruising with a battery-powered vehicle and not getting stranded. Proc. 26th AAAI Conf. Artificial Intelligence (AAAI’12) (AAAI Press, Palo Alto, CA), 1628–1634.Google Scholar
• Strehler M, Merting S, Schwan C (2017) Energy-efficient shortest routes for electric and hybrid vehicles. Transportation Res. Part B: Methodological 103:111–135.Crossref, Google Scholar
• Sweda TM, Klabjan D (2012) Finding minimum-cost paths for electric vehicles. Proc. 1st Internat. Electric Vehicle Conf. (IEVC’12) (IEEE, Piscataway, NJ).Crossref, Google Scholar
• Sweda TM, Dolinskaya IS, Klabjan D (2017) Adaptive routing and recharging policies for electric vehicles. Transportation Sci. 51(4):1326–1348.Link, Google Scholar
• Tung CT, Chew KL (1992) A multicriteria Pareto-optimal path algorithm. Eur. J. Oper. Res. 62(2):203–209.Crossref, Google Scholar
• Uhrig M, Weiß L, Suriyah M, Leibfried T (2015) E-mobility in car parks—Guidelines for charging infrastructure expansion planning and operation based on stochastic simulations. Proc. 8th Internat. Electric Vehicle Sympos. Exhibition (Korean Society of Automotive Engineers, Seoul), 1715–1726.Google Scholar
• Wang Y, Jiang J, Mu T (2013) Context-aware and energy-driven route optimization for fully electric vehicles via crowdsourcing. IEEE Trans. Intelligent Transportation Systems 14(3):1331–1345.Crossref, Google Scholar
• Yang H, Yang S, Xu Y, Cao E, Lai M, Dong Z (2015) Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-genetic algorithm. IEEE Trans. Smart Grid 6(2):657–666.Crossref, Google Scholar
• Zündorf T (2014) Electric vehicle routing with realistic recharging models. Unpublished MS thesis, Karlsruhe Institute of Technology, Karlsruhe, Germany.Google Scholar