Ing. Marek Cuchý

Electric vehicle (EV) travel planning is a complex task that involves planning the routes and the charging sessions for EVs while optimizing travel duration and cost. We show the applicability of the multi-objective EV travel planning algo- 5 rithm with practically usable solution times on country-sized road graphs with a large number of charging stations and a realistic EV model. The approach is based on multi-objective A* search enhanced by Contraction hierarchies, optimal dimensionality reduction, and sub-optimal ϵ-relaxation tech10 niques. We performed an extensive empirical evaluation on 182 000 problem instances showing the impact of various algorithm settings on real-world map of Bavaria and Germany with more than 12 000 charging stations. The results show the proposed approach is the first one capable of performing 15 such a genuine multi-objective optimization on realistically large country-scale problem instances that can achieve practically usable planning times in order of seconds with only a minor loss of solution quality. The achieved speed-up varies from ∼ 11× for optimal solution to more than 250× for sub20 optimal solution compared to vanilla multi-objective A*.

Being an NP-hard problem, multicriteria shortest path search is difficult to solve with speed satisfactory for real-world use. Therefore, this article examines the combination of t-discarding kPC-MLS [1] and multiple pruning heuristics. Apart from comparing the efficiency of the individual techniques, the research also evaluates the ability of t-discarding kPC-MLS to employ such heuristics. Since the experiments were conducted on country-size roadmaps, the results are expected to be relevant to real-world applications. According to the measurements, t-discarding kPC-MLS gains a higher speedup than standard MLS [2], operating on comparable roadmaps in a matter of seconds.

The charging infrastructure for electric vehicles faces the challenges of insufficient capacity and long charging duration. These challenges decrease the electric vehicle users’ satisfaction and lower the profits of infrastructure providers. Reservation systems can mitigate these issues. We introduce a reference architecture for interoperable reservation systems. The advantages of the proposed architecture are: it (1) considers the needs of the most relevant electric mobility stakeholders, (2) satisfies the interoperability requirements of existing technological heterogeneity, and (3) provides a classification of reservation types based on a morphological methodology. We instantiate the reference architecture and verify its interoperability and fulfillment of stakeholder requirements. Further, we demonstrate a proof-of-concept by instantiating and implementing an ad-hoc reservation approach. Our validation was based on simulations of real-world case studies for various reservation deployments in the Netherlands. We conclude that, in certain high demand situations, reservations can save significant time for electric vehicle trips. The findings indicate that a reservation system does not directly increase the utilization of the charging infrastructure.

As the number of electric vehicles on the roads increases, new technologies and concepts such as fast/super-fast charging and dynamic pricing are developed and implemented respectively. With those innovations on the rise, reservation of charging stations for electric vehicles will play a pivotal role in seamlessly integrating them into the transportation and mobility system. In this paper we derive basic requirements for building interoperable reservation systems and identify four generic approaches to reservation. For designing the system model and engineering the charging station reservation system, we utilize the E-Mobility Systems Architecture framework. For one of the reservation types, we implement a proof-of-concept and demonstrate its usefulness by conducting a showcase in Bavaria, Germany. Further, we set up and conduct a simulation-based evaluation to compare the four different reservation types regarding their benefit to users and providers as well as overall system efficiency. To the best of our knowledge, this is the first contribution proposing an interoperable reservation system for electric vehicle charging. The results presented in this paper provide insights regarding the feasibility of the different reservation types under varying conditions.

The basic premise of existing route planning algorithms is that complete information required for computing optimum routes is available at the time of the search. With the increasing complexity of transport systems, such an assumption is no longer valid as transport service providers are not willing to disclose full information about certain aspects of their services for business sensitivity reasons. Therefore, new approaches capable of computing optimal routes while minimizing the required amount of information about the services are required. In this paper, we investigate the incomplete information route planning problem in the context of planning routes with charging for electric vehicles. We have formalized the problem as a resource-constrained shortest path problem with time-dependent edge costs; the costs are only partially known and their values can be obtained by querying external data sources. We propose an optimum algorithm solving this problem utilizing two interchanging phases built on a multi-objective A* algorithm. We evaluate the properties of the algorithm on a comprehensive suite of test scenarios based on real-world data and derive insights into the properties of this emerging route planning problem.

Over the last two decades, route planning algorithms have revolutionized the way we organize car travel. The advent of electric vehicles (EVs), however, bring new challenges for travel planning. Because of electric vehicle limited range and long charging times, it is beneficial to plan routes, charging, and activities jointly and in the context of the whole day—rather than for single, isolate journeys as done by standard route planning approaches. In this work, we therefore present a novel approach to solving such a whole day mobility problem. Our method works by first preprocessing an energy-constrained route planning problem and subsequently planning the temporally and spatially constrained activities. We propose both an optimal algorithm for the day mobility planning problem and a set of sub-optimal speedup heuristics. We evaluate the proposed algorithm on a set of benchmarks based on real-world data and show that it is significantly faster than the previous state-of-the-art approach. Moreover, the speedups provide dramatic memory and time improvements with a negligible loss in solution quality.

A major challenge for large-scale deployment of electrical vehicles (EVs) is charging. In general, the number of EVs that can be charged can be increased either by physically expanding charging capacity or by better exploiting existing charging capacity. In this paper, we focus on the latter, exploring how advanced EV travel planning systems can be used to better align where and when EV charging happens with where and when charging capacity is available. Our novel travel planner enables EV users to plan their trips and EV charging in a way that meets their needs yet reflects charging availability. The core innovation of our approach is that we take a broader, multidestination perspective to EV travel planning - this gives our planning system more flexibility and scope for deciding when and where charging should happen and, consequently, enables a better alignment between the need for charging implied by the EV travel and the availability of charging. We evaluate our approach on an agent-based simulation of several medium-scale scenarios based on real-world data. The results confirm the benefits of our multi-destination approach, especially in scenarios in which charging service providers support upfront booking of charging slots.

We propose a novel and challenging variant of trip planning problems – Whole Day Mobility Planning with Electric Vehicles (WDMEV). WDMEV combines several concerns, which has been so far only considered separately, in order to realistically model the problem of planning mobility with electric vehicles (EVs). A key difference between trip planning for combustion engine cars and trip planning for EVs is the comparatively lower battery capacity and comparatively long charging times of EVs – which makes it important to carefully consider charging when planning travel. The key idea behind WDMEV is that the user can better optimize his/her mobility with EVs, if it considers the activities he/she needs to perform and the travel required to get to the locations of these activities for the whole day - rather than planning for single trips only. In this paper, we formalize the WDMEV problem and propose a solution based on a label-setting heuristic search algorithm, including several speed-ups. We evaluate the proposed algorithm on a realistic set of benchmark problems, confirming that the whole day approach reduces the time required to complete one’s day travel with EVs and that it also makes it cheaper, compared to the traditional single-trip approach.

Even though the agent-based simulation modelling has become a standard tool in transport research, current imple- mentations still treat travellers as passive data structures, updated synchronously at infrequent, predefined points in time, thus failing to cover within-the-day decision making and negotiation necessary for cooperative behaviour in a dynamic transport system. Leveraging the fully agent-based modelling approach, we have built large-scale activity-based models of multimodal mobility covering areas up to thousands of square kilometres and simulating populations of up to millions of inhabitants of several European cities. Citizens are represented by autonomous, self-interested agents which schedule and execute their activities (work, shopping, leisure, etc.) and trips in time and space. Indi- vidual decisions are influenced by agent’s demographic attributes and modelled using the data from mobility surveys. The model is statistically validated against origin-destination matrices and travel diary data sets.