A Method for the Optimization of Daily Activity Chains Including Electric Vehicles

Abstract

The focus of this article is to introduce a method for the optimization of daily activity chains of travelers who use Electric Vehicles (EVs) in an urban environment. An approach has been developed based on activity-based modeling and the Genetic Algorithm (GA) framework to calculate a suitable schedule of activities, taking into account the locations of activities, modes of transport, and the time of attendance to each activity. The priorities of the travelers concerning the spatial and temporal flexibility were considered, as well as the constraints that are related to the limited range of the EVs, the availability of Charging Stations (CS), and the elevation of the road network. In order to model real travel behavior, two charging scenarios were realized. In the first case, the traveler stays in the EV at the CS, and in the second case, the traveler leaves the EV to charge at the CS while conducting another activity at a nearby location. Through a series of tests on synthetic activity chain data, we proved the suitability of the method elaborated for addressing the needs of travelers and being utilized as an optimization method for a modern Intelligent Transportation System (ITS).

1. Introduction

In most urban environments, there is an ever-growing need for navigation through transportation networks. Although more and more mobility services are offered to travelers, the complexity of their use has risen alongisde the offer and demand for such services. Thus, the utilization of Intelligent Transportation Systems (ITS) and the development of travel-related services have become an immense need for the facilitation of the everyday life of citizens.

With the expected rise of the use of Electric Vehicles (EVs) all over the world [1] and the positive impacts that they are expected to bring [2], advanced EV travel planning algorithms are now essential more than ever [3]. Alongside the growth of EVs on global markets and the impact that they will have on power grids, transportation networks, and the environment [4], the study for intelligent driver assistance solutions for EV users is critical. Not only their development and availability are vital, but also the user experience and the satisfaction of specific user preferences are two crucial points when creating such services [5]. Nonetheless, those solutions can help to mitigate the risk of electrification of transportation and deal with one of the enormous obstacles in EV adoption that is called range anxiety, a term used to describe the psychological worry of EV drivers that the remaining electric energy in the vehicle is not enough to attend their destination. While the battery capacity of the EVs is growing at a satisfactory rate and is even expected to double until 2030 [6], it is proven that range anxiety is still one of the most significant concerns of EV drivers and is one of the most critical obstacles towards universal adoption and mainstream use [7]. While it has been shown that EV users that have a charger available at home mainly cover their needs at a satisfactory rate, for users that solely depend on public charging infrastructure, charging can be a more challenging task [8].

Alongside the ability of those methods to address problems of EV drivers on an individual level, they can improve the situation for the system-level [3], too. Mitigation strategies on electrification on a regional level, as their importance as highlighted in recent articles [9], can benefit from driver assistance ITS, since the underlying methods can be independent of the spatial-context and are reproducible over several regions according to needs of travelers of those specific regions.

Apart from the work of Cuchý et al. [3], little research has been conducted to study the flexibility or willingness to use travel planning services for EV drivers. However, the authors believe that based on other previous research on other modes of transport, and mainly conventional automobiles [10], a driver assistance system customized for EV users can be of crucial importance. This observation can be further highlighted by other literature studies that have shown that travel patterns can vary further when influenced by technologic systems [11]. While traveler groups’ flexibility can differ according to age groups [12] and social characteristics [13], if the benefits acquired from the planning process are perceived as worthy [14], benefits emerge for planning trips in pre-trip phase [15] or in real-time [16].

The goal of this research is to provide a realistic approach to the Daily Activity Chain Optimization (DACO-EV) problem by exploiting activity-based modeling and the Genetic Algorithm (GA) framework. While the incorporation of the EV range constraints is a significant part of our work, a particular focus is also given to mechanisms that enable the implementation of such a system in a real-world ITS system that will serve the travelers. Section 2 presents a literature review on related topics. Section 3 provides a detailed description of the DACO-EV method, its parameters, and its attributes. Section 4 discusses the implementation of the method and to provide realistic solutions to travelers. Section 5 presents the results, including use cases. Section 6 serves as a conclusion to the article and its contribution.

2. Literature Review

To the best of our knowledge, an approach to the DACO-EV method, including enough parameters to render its solution useful in realistic settings, does not exist in the scientific literature prior to the publication of this article. However, insights and valuable research directions can be extracted from articles regarding the incorporation of electromobility into transportation problems.

The activity-based analysis of transportation systems stems from the idea that the demand for transportation between locations is interconnected with the demand for participation in some activity. As indicated by a series of works in the literature [17,18,19], it has been extensively studied and used for the analysis of travel behavior and the planning of transportation systems. Our work on the optimization of daily activity chains falls under the umbrella of activity-based research in transportation. Recent notable articles [20,21] show that activity-based modeling has been successfully applied to cases where electromobility is incorporated into transportation systems. In the first paper by Dong et al. [20], the impact of different types of deployment of charging infrastructure is analyzed in regard to the range anxiety of EV users. An activity-based method is used to evaluate the deployments according to travel patterns. In the work by Kontou et al. [21], activity-travel patterns from a National Household Travel Survey data are used, in order to assess two schemes for centralized charging management of EVs, one scheme that regards preferences of individuals and another that considers the government perspective. The results indicate the differing nature of the interests of those two stakeholders, and confirm that the availability of charging stations at the workplace can greatly affect the charging profiles of EV travelers. The latter observation is one of great importance that can be found in other studies [8], too.

In regard to the problem of Daily Activity Chains Optimization (DACO), the basic instance of DACO-EV, it has been previously addressed in the literature, and a GA approach has been introduced [22,23]. Charypar et al. [24] have addressed a similar problem and introduced a similar solution approach. The authors have considered several simplifications, such as the computation of distances according to geometric distance and not based on the real transportation network. Another similar work was conducted by Abbaspour et al. [25], where the authors tackled the same problem but had a specific focus on the touristic aspect of the optimization of activity chains. Although the aforementioned papers regard heuristic optimization methods that have been developed to solve the DACO problem, different modelings could also be considered. A modern approach was presented by Liao et al. [26], who modeled the problem as a graph super-network. They included space-time constraints to enable the valid selection of locations for activities in time, multi-modal transport options and modeled the parking choice. While their activity-travel scheduling algorithm computes the final solutions to the problem in minimal time, in the scheduling problem and the modeling, the priorities and the flexibilities of the travelers are not included, like in the case of DACO.

There is a lack of exact optimization approaches for the DACO or DACO-EV in the literature. Exact optimization methods, where the gap between the solution calculated and the globally optimal solution of the problem is zero, are based on mathematical models of the transportation problem. Although exact approaches tend to provide better solutions in terms of reduction of cost according to criteria, they cannot yield solutions in the amount of time that heuristics can, and usually take much more time to complete the calculations. Works can be found in the literature where routing in multi-modal networks has been addressed with exact approaches [27,28].

One motivation for the extension of our method was to provide an efficient tool dealing with the range anxiety of EV drivers in urban environments. Range anxiety is one of the main bottlenecks of EV adoption and affects both inner-city and inter-city trips. Many studies [29] exist in the literature that addressed this topic and provided useful insights regarding key factors that can evaluate its effect and help deal with it. Although technology, and its advancement, is one of the main ways to deal with range anxiety, other key factors are considered as important for the medium-term horizon, such as battery costs, coverage of the charging stations network and CO₂ vehicle standards [7]. Range anxiety has also been studied in the context of daily schedules by Neubauer et al. [8]. Significant findings in their studies showed that workplace charging could play an essential role in promoting the utility of EVs for high mileage commuters. Additionally, the broadly available charging infrastructure has been shown to be important to both high and low mileage commuters. Range anxiety importance has also been shown in computational studies that discussed its relationship with the CS network. In the work by Guo et al. [30], the battery charging station location problem was addressed where range anxiety and distance convenience were taken into account. While the KSIGALNS algorithm that they developed to solve their bi-level integer programming model was proven to be very effective compared to standard and previous solutions approaches, the analysis of range anxiety as a parameter shows that it is an essential factor to the location strategy of the CS network. Other interesting computational studies exist in the context of range anxiety, such as the one by Esmaili et al. [31], where the authors examine EVs as distributed energy storage units and their potential contribution to microgrids when vehicle-to-grid service is considered. An interesting result that emerges from the solution of their Mixed-Integer Linear Programming (MILP) model is that when range anxiety, as modelled in their mathematical optimization program, is in higher levels, then the average State of Charge of the EV drivers rises and, as a result, the total cost of the microgrid is higher, too.

Range anxiety, however, is a phenomenon that is being progressively dealt with on both a personal and systemic level. It is more evident than ever that not all EVs are the same regarding experiencing range anxiety [32]. There are observations that range anxiety is minimally experienced by users of specific types of EVs in specific regions, such as in the study by Gorenflo et al. [33], in which, their analysis of the e-bike usage and battery charging data supports that range anxiety does not exist among the participants of the survey. Finally, in order to underline the importance of guidance systems, like the one presented in this paper, we further present the study of Cuchý et al. [3]. In their work, they were able to evaluate multi-destination transportation scenarios according to single-user perspective and infrastructure perspective by using AgentPolis simulation framework. Except for the obvious benefits for EV users, they showed that when users plan their mobility up-front, the total utilization of infrastructure can increase by more than 100%.

Particular focus was given to articles dealing with EV routing and the parameters that were considered when it comes to the range that vehicles can cover. Extensive work on the subject has been conducted by the team of Baum. Notably, in work conducted in 2013 [34], they extended their algorithm, named Customizable Route Planning (CRP), to calculate fast queries on graphs that are suited to Electric Vehicles (EV). Their goal was to calculate energy optimal routes, where several parameters can be included, such as the recuperation of the electric vehicle, the battery capacity constraints, and the dynamic behavior in energy consumption of the vehicle. In their next work conducted in 2016 [35], they proposed a framework with a more holistic approach to the problem, where parameters are included, such as the use and location of charging stations, turn costs, and the adjustment of speed in order to save energy. In their work conducted in 2015 [36], they introduced an approach named CHArge, which solves the EV routing problem in realistic settings. They discussed the properties of charging functions, which are used to map an initial State of Charge (SoC) and the duration of charging sessions with a resulting SoC. The works by Baum et al. [34,35,36], are very close to our approach in terms of methods and calculation mechanisms that were used to deal with the incorporation of electromobility. Additionally, useful information about the charging network, charging sessions, plugs, and strategies were also extracted from the work of Moghaddass et al. [37].

There is a series of articles that are connected to our work since they address the optimization of activity chains considering the use of EVs. The work of Liao et al. [38] is very close to our approach, but they do not solve the same problem. The authors provide modeling and solution to the EV shortest travel time path problem and the fixed tour EV touring problem. They consider a battery swap system for the touring problem, where two cases are discussed: the on-site station model, where each city is considered as a swapping station, and the off-site model, where the swapping station is further away from the city. Although their approach addresses a similar problem to ours, the presented work is not directly linked to a real-world application. In the works of Cuchý et al. [39,40], the authors tackled the Whole Day Mobility Planning with Electric Vehicles (WDMEV) problem and modeled it according to graph theory. The definition of the problem is similar to DACO-EV, but the authors included fewer parameters than in our problem definition. They did not include the priorities of the travelers, and they are neglecting the time windows of the desired attendance of the traveler. Furthermore, the authors did not include in the models the consumption according to Worldwide Harmonized Light Vehicle Test Procedure (WLTP), different EV models, and it is not clear if they consider the charging connector types. In the modeling, the overall weight of the vehicle and the option to have a final desired amount of energy in the battery when the tour ends were not included. Finally, the availability of the chargers was not taken into account in the calculation of the routes, but they considered waiting time at Charging Station (CS) according to randomly parameterized models. The aforementioned parameters may lead to very different solutions spaces and computational results, so the two problems and methods cannot be directly compared.

Overall, the main contribution of this article lies in the elaboration of a method that addresses the DACO-EV problem, including all the necessary parameters that allow the solution of the problem to be personalized to the specific needs of travelers, and enabling the use of the method in realistic settings. The method includes:

• Consumption calculation mechanisms of the EV according to the features of the road network and the EV market model (battery capacity, weight, charging rate, charging plug, WLTP ratings).
• The Starting State of Charge (SSoC) and the desired Final Stage of Charge (FSoC) of the EV used by the traveler.
• A real charging stations network and the availability of those charging stations based on past usage data.
• Two charging scenarios in order to further model realistic travel behavior.

3. Method Description

3.1. Parameters of the DACO-EV

The DACO-EV method incorporates the use of an EV; therefore, it requires modeling of the constraints regarding the energy equilibrium that takes place in the energy storage mechanism of the car while visiting several locations. Because EVs are still in an early phase in their adoption by the public, the available charging facilities are not always optimally distributed, and the minimum distance between available charging points can reach up to several kilometers depending on the type of road network [41]; this situation renders a demanding reality for EV drivers that need to utilize the public charging network to cover their charging needs. The extra parameters that affect this energy equilibrium can be grouped into three major categories, such as vehicle design, driver behavior, and the environment [42]. In our attempt to provide a realistic and practical method for the elaboration of meaningful solutions to the EV drivers, we have included several of those parameters, while we ignored others of lesser importance.

The problem and the elaborated method are based on three sets of parameters. The first set is defined by the traveler and refers to his or her schedule and overall preferences concerning the activities. The second group of parameters is about the constraints related to electromobility when the traveler utilizes an EV. The third set consists of the parameters that do not depend on the user and refer to the existing network, the timeframe of operation of facilities and services.

Table 1. The first group of parameters.

Parameter	Description
Starting time of the tour	Earliest time in the day when the first trip to the first activity can begin. Solutions that start earlier than this time are considered infeasible.
Ending time of the tour	Latest time in the day when the traveler can arrive at the ending (final) activity.
The starting position of the traveler	The starting location of the tour. Commonly it is also the ending position of the tour and is associated with the traveler’s home.
The ending position of the traveler	The ending location of the tour.
Activities and their type	This parameter refers to the types of activities that need to be conducted. The type can be chosen from a predefined list (e.g., bank, restaurant, hairdresser, bakery).
Locations of the activities	Defines which are the locations that the traveler would like to conduct each activity.
Processing time at each activity	This parameter is used to specify how much time is needed for the traveler to conduct each activity.
Priorities of the activities	The traveler specifies the level of flexibility for each activity. It can be spatially and temporally fixed, only spatially flexible, only temporally flexible, or flexible.
Desired earliest start time for each activity	The traveler must specify when the preferred time for each activity to start is.
Desired latest end time for each activity	The traveler must specify when the preferred time for each activity to end is.
Used EV model	By having specified the manufacturer and the model of EV that is used by the traveler, we can utilize the information about several aspects of the vehicle. The range and the possible charging locations of the EV are the most important of those aspects (if the mode of transport used is EV).
Starting State of Charge (SSoC)	The energy level of the battery at the start of the tour (if the mode of transport used is EV).
Final State of Charge (FSoC)	The desired energy level of the battery at the end of the tour (if the mode of transport used is EV).

refers to the parameters that are set by the traveler.

Particular emphasis should be put on the second group of parameters about the EV and its use. Since the traveler specifies the used EV model, the parameters of this second group can be considered as sub-parameters of the first group (

Table 2. The second group of parameters concerning the characteristics of the Electric Vehicle (EV).

Parameter	Description
The capacity of the battery of the EV	Also referred to as usable battery capacity, which is the maximum amount of energy that can be stored in the vehicle.
Plug type of the EV	The type of plug that the vehicle uses for charging.
The consumption rate of the EV	The consumption rate of energy is a function of the vehicle speed and the use of auxiliaries. This rate can be extracted from an EV database.
Charging rate of the EV	The time needed to reach the desired energy levels while charging. This rate can also be extracted from an EV database.
Energy recuperation	The EV can recharge its battery while braking, especially when the path to be followed is a downhill road.
Vehicle weight	The weight of the vehicle plays a vital role in how much energy is consumed, especially in cases where the tour includes gains or losses of elevation.

).

Finally, there is the third group of parameters that are needed for the problem to be fully described. Those parameters are not defined for each passenger, but instead, they are specified for the network, the modes of transport, and the types of activities available. They can also be described as the static parameters of the DACO-EV problem (

Table 3. The third group of parameters that are independent of the user’s input.

Parameter	Description
Network topology	The transportation network that is connecting the available locations for each type of activity. The elevation of the road segments is considered part of this parameter.
Alternative locations and Time-windows	Locations of facilities of activities, time-windows of operation of the facilities, and types of activities that can be conducted at each location.
Charging stations network	Locations of charging points and types of chargers available at each point.
Availability of charging points	Availability of charging stations as calculated by past usage data.

).

3.2. Degrees of Freedom of the Problem and Decision Variables of the Solution

At this point, we should make a reference to the decision variables of the DACO-EV that fully define a solution for the travelers. Those decision variables are essential for the modeling as they will form the chromosomes of the solution encoding of the Genetic Algorithm. In

Table 4. Decision variables of DACO-EV.

Decision Variables	Description
Order of the activities in the chain	The order of the activities in the tour in relation to their initial order.
Locations of activities	The traveler can conduct the same activity at multiple locations. This variable refers to one of the available locations that have been chosen for a specific solution.
Time windows of attendance to each activity	This variable is used to specify the arrival and departure of the traveler to the activity.
Charging time, charging station and subtour information	This variable is a set of quantities that contains all the information that regards the subtour for charging if one is included.

, the decision variables and their descriptions are provided.

All of the aforementioned variables (ones included in Table 4) are the independent variables of the problem. By deciding on the order, the locations, the time windows of attendance, the modes of transport, and the charging time, we decide on a specific way that the first tour changes and gets optimized. Of course, that information is not enough in order to fully articulate a meaningful solution for a traveler in a human-readable format. From the independent variables, we can extract a series of information, such as exact paths to be followed in between activities, battery power after the visits at each of the locations, starting and ending time of the whole tour, travel time of the tour, starting and final state of charge of the EV.

3.3. Charging Scenarios

To fully cover the description of the DACO-EV problem, we also need to deal with the possible types of charging. As a first charging scenario, we consider the case where the EV users want to charge their vehicle at a CS, and they want to conduct one of their activities at another location. This is called the en passant charging scenario. Usually, it can occur when a charger and a location for an activity are close to each other, and the user can just walk a few hundred meters to the facility and back to the charging station after completing the activity. As a second charging scenario, the classic scenario of charging is included, where the traveler again deviates from the first tour and embarks on a subtour to a CS, but in this case, he or she just waits in the car until the charging is finished.

First, we provide a graphical example of the classic charging scenario of the DACO-EV (Figure 1). Given a set of five initial activities, the activity chain is optimized. For simplicity reasons, we only provide an optimized tour where nothing changes in the spatial context except for the inclusion of a charging session. The charging station is indicated by the blue circle, which is a new activity in the chain.

In Figure 2, present the en passant charging scenario of the DACO-EV. The charging detour happens between Activities 4 and 5, and the transfers from the CS to the location of Activity 5 are represented by the dotted lines. In this case, the EV remains at the CS, while the user processes Activity 5 using another mode of transportation (e.g., walking).

3.4. Optimization Method

The method is based on a Genetic Algorithm (GA) that iteratively solves the Travelling Salesman Problem with Time-Windows (TSP-TW) for different combinations of the characteristics of the possible solutions and evaluates each of them according to several criteria. The efficiency of the proposed method has been previously tested and proved for the primary instance of the problem in the articles by Esztergár-Kiss et al. [22,23]. After running the algorithm for several iterations, a more optimal solution for the initial schedule and the preferences of the traveler is derived. In the algorithm, we make sure that after the traveler executes the tour suggested, and given the EV usage constraints, the EV has the desired FSoC when it reaches home.

By defining the properties (i.e., decision variables) of an individual (i.e., candidate solution) of the problem, we can form the populations of solutions in the solution space. Then the genetic operators of selection, mutation, and crossover are utilized to search the available space of solutions and derive the ones that are more suitable for each case of traveler. Except for the genetic operators that have been used, and according to GA literature [43], the method is characterized by a set of parameters, such as:

• Population size—Number of solutions initially created at the solution space initialization phase and kept by the selection operator at the end of each iteration of the algorithm. The population size that was selected for the solution of the DACO-EV is 30 individuals.
• Base mutation probability—Defines how much we want to search for solutions with totally new attributes compared to an initial population of solutions. The mutation probability that was selected is 20%.
• Crossover probability—Defines how many new solutions (i.e., individuals) are produced at each iteration of the algorithm based on previous populations. The crossover probability that was selected for the efficient solution of the problem is 10%.
• Generations—Defines the iterations of the GA algorithm that run until we get a final solution. No other termination criterion is used for the algorithm, which means the number of generations, will define the final optimality gap of the solution calculated by the run of the algorithm. The number of generations until a more optimal solution is calculated for the traveler is 30. The number of generations for this algorithm can vary according to if pre-optimization techniques are applied to the solution approach or not.

3.4.1. The Genetic Algorithm

Although the GA framework contains more or less standard data structures, functions, and operations utilized for each application, it was considered appropriate that a more formal specification of the algorithm is presented. This algorithm describes how temporal and spatial flexibility were handled and includes several technical details in order to enable its reproduction.

Algorithm 1	A genetic algorithm for addressing the DACO-EV problem
Input:	Parameters for the execution of the GA, Parameters of the problem
Output:	The solution of the problem: an optimal schedule for the traveler
Steps:
1:	Read the data and the parameters, create appropriate data structures;
2:	Initialize a population of feasible solutions (i.e., individuals) for the DACO-EV problem;
3:	For generation i in the range [0, generations):
3.1:		Apply the crossover operator between the individuals of generation i;
3.2:		Apply the mutation operator to the individuals of generation i;
3.2.1:			Stochastically swap the order of two activities in any individual;
3.2.2:			If there is a spatially flexible activity, then stochastically change its location to a new suitable location;
3.2.3:			If an EV is used and if the SoC at the final location is not at the desired level, or a negative number at any point in the tour, add a detour at a random CS. If the detour exists, stochastically change the location of the CS in the tour;
3.3:		Calculate the distances matrix (and the kilometric distances, elevation gained, and elevation lost matrices if needed) for the locations involved in the individuals of generation i; Normalize the attributes (calculate time-windows, battery power at each activity/location) of the individuals according to the order of the activities and the detour;
3.4:		Evaluate all individuals according to the fitness function;
3.4.1:			Label as infeasible all individuals who do not satisfy the temporal constraints;
3.4.2:			Label as infeasible all individuals who do not satisfy the priorities’ constraints;
3.4.3:			Label as infeasible all individuals who do not satisfy the energy equilibrium. Apply Scaled Ranking of infeasible solutions;
3.4.4:			If an EV is used, label infeasible all individuals who include CS which are unlikely to be available (As described in Section 4.3. Availability of Charging Stations) ;
3.5:		Select the individuals with the best fitness to form a population and reproduce in the next generation;
4:	Select the individual with the best fitness from the population of the final generation;
5:	End of the algorithm.

3.4.2. Fitness Function and Optimization Criteria

For the efficient solution of the DACO-EV, several criteria have been considered. While most of them regard travel time, whose reduction has been our primary aim, a few more criteria were considered as important to include. The method is capable of handling five criteria. They were weighted by the corresponding parameters a, b, c, d, e to create an efficient multi-criteria fitness function for the problem.

$$U\left(X\right)=\left(a\ast TT\right)+\left(b\ast TTST\right)+\left(c\ast AT\right)+\left(d\ast WT\right)+\left(e\ast CT\right)$$

(1)

Fitness function U has been applied to every candidate solution X that has been calculated by the genetic algorithm. This evaluation, as indicated in the algorithm at Step 3.4, was applied to each potential solution, when not infeasible, and has been utilized to label and prioritize according to the potential needs of travelers. For the first criterion, TT, its actual value is given in regard to the time that the user has spent traveling within his or her tour. The second criterion, the Travel Time in the Subtour (TTST), regards travel time only in the charging subtour. This specific type of travel time has been calculated as an extra variable, in order to be able to be separately included in cases, where the effect of the subtour needs to be minimized in the overall solutions. Arrival Time (AT) at the final destination is also another criterion considered that can be essential for some users, as well as, the Walking Time(WT), when it occurs in the sub-tour for charging, and the en-passant scenario. Finally, Charging Time (CT) has been additionally considered as an extra criterion, and has been added to the function as a possibility for optimization. The reason for including all five criteria was to provide a robust optimization approach that is applicable to a wide set of real-world applications. While usage of the method is independent of spatial context, the potential needs of travelers vary across different cities, countries, and the available charging stations network.

For the values of the parameters a, b, c, d, e, different solutions are derived. The proper choice of the values is of great importance to the type of solutions that will be calculated. A sensitivity analysis of the effect of the parameters on the solutions produced is one of the future steps to take in order to assure suitable performance for each real-world case (i.e., region of application) and understand the effect of each criterion on the activity chain.

4. Implementation of the Method

For the efficient functioning of a modern application that will support the travelers in their daily commutes, the implementation of the method has been realized. Because of the complexity of the problem addressed and the vast amount of calculations needed, a series of heuristic rules were applied to the method in order to direct the search of the solution space and yield meaningful results within realistic computation times. This addition to the method is called the pre-optimization phase, which creates a smaller solution space for the algorithm to search. However, in this paper, we focus on the charging related functions of the method.

For the implementation of the method, Python programming language was utilized. Data from OpenStreetMap and Geofabrik [44] was used for establishing the road network, OpenTripPlanner (OTP) engine [45], was the primary tool for the calculation of road distances and routes, and calculations for the availability of CS were conducted based on data from e-MOBI [46] about the charger network. The chargers based on which the availability was calculated were 89. Elevation data are taken from NASA’s Shuttle Radar Topography Mission (SRTM). Regarding the EV model used, the traveler is allowed to enter the vehicle that he or she is going to use, and we were able to extract the properties (battery capacity, available plug types, consumption according to WLTP, vehicle weight) of each vehicle from an electric vehicle database [47]. A simplification was made regarding the charging rate, which was considered according to the available plug types at both the charging station and the EV. A matchmaking mechanism was developed to match EVs with fast charging plugs if they are likely to be available, or with standard charging plugs, otherwise. Regarding the priorities of the travelers, we included them in four levels which are described in

Table 5. Priorities of the travelers considered.

Priority Label	Priority Label Description	Spatial Flexibility	Temporal Flexibility
1	Totally fixed	×	×
2	Spatially flexible	√	×
3	Temporally flexible	×	√
4	Totally flexible	√	√

:

When an activity is assigned with Priority Label 1, it means that the traveler considers this activity as both spatially and temporally fixed. Priority Label 2 is assigned by the travelers to activities that are spatially flexible, which means they can be conducted at several locations, but temporally not, meaning that the algorithm is bound to calculate the visit within the desired time windows. With Priority Label 3, the traveler indicates that the activity must be conducted at the provided location, but it can happen in any time-window within the day. Oppositely to Priority Label 1, Priority Label 4, is the case where the traveler indicates that the activity is totally flexible, which means that it can be both conducted in another location (providing the same type of service) and at any time (within the overall timeframe of the user and the operating hours of venues and shops).

Before actually providing information about the implementation of the GA and its mechanisms that allow the effective solution of the DACO-EV, an overview of the work is presented in Figure 3 that depicts the method, its parameters, external tools, and data used. On the one hand, the traveler provides an initial activity chain and information about his or her preferences by setting the first, and thus the second, group of parameters. On the other hand, the third group of parameters provide external information, such as the network topology (road network and elevation), the electric vehicle database for consumption calculations, and the alternative activities’ location database for calculating the optimized activity chain by examining the full spectrum of the spatial possibilities for the activity chain. Finally, based on the charging station usage data and other related information to the CS (i.e., charging stations database), the availability of charging stations was calculated using data mining techniques. Before using the heuristic optimization model, a pre-optimization is performed, and the routing engine is used to calculate optimal routes between activity locations. As a result, the genetic algorithm calculates optimized activity chains for users.

4.1. Explanation of the Pre-Optimization Phase

The pre-optimization of each solution is a useful tool that can help make the GA approach more efficient. In the context of this work, several techniques were implemented in order to make the GA compute better results faster. The pre-optimization phase aims at reducing the initial solution space of the algorithm, which is created every time that an instance of the problem is created according to the static and dynamic parameters of the problem, from a generalized vast solution space to, what one can call, a personalized solution space.

The personalized network is achieved by deciding on some aspects of the solution before triggering the actual search for the optimal solution, thus creating a smaller solution space. It considers the activities with spatially fixed priorities to serve as gravity points for the optimization procedure. More specifically, after the traveler provides the input of the preferences, we have an initial set of choices that the traveler initially intends to follow. This cutting of the solution space happens around the locations of activities that the travelers consider as totally or spatially fixed. This creates a subset of alternative locations of activities and charging stations. Then this subset of the initial space is searched with the GA in the main optimization phase.

For example, if an activity is fixed (Priority Label 1) in the search for an optimal solution, all other temporal and spatial choices concerning this activity can be ignored. In the same way, if the activity is temporally fixed, we include all alternative facilities (locations), but we do not permit the algorithm to search outside the time windows specified by the traveler. If the activity is spatially fixed, then we cut out the parts of the solution space that has to do with other location of facilities for the activity, and we only allow the algorithm to search for different time windows. If we have the fourth case of total flexibility, then we have to search both for alternative facilities and time windows of attendance, and we cannot pre-optimize.

4.2. Calculation of the Charging Time and Deciding the Charging Scenario

Charging time is a deterministic variable and a function of the rest of the attributes. The amount of time spent at the CS is calculated with a forward lookup of the energy requirements of the EV to cover the full tour. This calculation occurs by comparing the SSoC, the FSoC, and the remaining energy in the battery of the vehicle at every location. The candidate solutions (i.e., individuals) to the problem fully describe the locations to visit and the order of attendance to the activities. From those two attributes, we can extract the exact routes between locations of activities, as well as the kilometric distance, elevation gained and lost, and charging time at the CS.

Several aspects of the detour are modeled as independent variables and can stochastically change. Thus, we included a heuristic rule in the solution process that further directs our search. This rule defines that if the CS is within a direct distance K from the location of the activity after the trip to the CS, then the charging scenario is set to en passant charging scenario. When the CS is at a direct distance greater than K, then the charging scenario is set to a classic charging scenario. By setting K to the appropriate value, the algorithm can lead to better solutions by avoiding assigning the en passant scenario to cases where the location of the CS is too far away from the next location of the activity. The values of K can vary according to what modes are included and are available in the detour when the EV is left for charging. In our implementation, we only added walking mode for the en passant scenario, and we have noticed that the implementation yields satisfying results for the values of 800 to 1000 m for urban environments.

In the cases where the solution gets mutated to include the detour right at the end of the tour before the traveler goes to the desired final destination, the charging scenario is always set to the classic charging scenario. In Figure 4, a combination is given, where the heuristic rule is applied, and charging station A is utilized with the en passant scenario, while charging station B is utilized with the classic charging scenario. For the optimization of this initial activity chain (i.e., green markers), charging stations that fall within a distance K from the location of Activity 5, can be utilized under the en passant scenario (dotted lines) since the walking distance is considered walkable. Otherwise, the algorithm sets the charging method to the classic charging scenario.

4.3. Availability of Charging Stations

Regarding the availability of charging stations, a method has been elaborated in order to incorporate this parameter of the problem. We used the data provided by e-Mobi [46], which is the organization responsible for e-mobility investments (especially for deploying charging stations) in Hungary, to derive a suitable metrics that could be included in the optimization of the DACO-EV problem for travelers in Budapest. The dataset provided information about the names, locations, and plug types of chargers in Budapest. Furthermore, we had a list of charging sessions for those chargers that happened between the 23rd of February 2018 and the 12th of February 2019. For this period, we applied data mining techniques to derive average statistical properties that lead to a percentage of the occupation, in similar terms, probability for the charger to be occupied for each hour of a day. If the charger was occupied for 20 min on average in a specific hour in the examined period, then it was assumed that this charger was occupied for 33.33% on average.

These statistics were included in the method for the optimization of the DACO-EV. The main component of the method that was utilized for including the availability of CS was the evaluation operator of the GA. Every time we needed to evaluate a solution that emerged from the mutation and crossover operators of the GA, we applied the evaluation operator and checked whether the CS included in the solution is likely to be occupied. We aimed to prioritize solutions in the population that include chargers that are less likely to be occupied. The prioritization occurs only by labeling the solutions, and the corresponding charger as feasible or infeasible. Other than that, the percentage to be occupied did not have any impact on the fitness function and did not change its value. In order to avoid empirical bias in how the solutions get labeled, we implemented a labeling mechanism based on stochasticity. The method produced a random percentage in the positive continuous set of [0,100], and if that random percentage was lower than the calculated percentage of the occupation, then the solution was marked infeasible. In that regard, CS, whose rate of occupation was high were more likely to be labeled as infeasible and were not included in the population of solutions.

In Figure 5, we provide example graphs for the availability of Charging Stations (CS) as calculated by the method. The percentage of occupation for four random CS in Budapest can be seen for 24 h. The percentage of hourly occupation can significantly vary between the chargers. In the case of CS 1 and CS 3, nearly 0% occupancy rate can be derived, while in the case of CS 2 and CS 4, the occupancy rate reaches almost 50% in the morning hours.

As a future step of the data mining method for the calculation of the availability of charging stations, we would include a calculation of the rate of occupation also according to the day of the week. A more enormous dataset than the one available would be more suitable for this kind of extension. For example, this extension would help the method performing better on special days like weekends, where the availability may be different from weekdays.

4.4. Energy Consumption Model and the Incorporation of Elevation

The incorporation of elevation of the road segments was a significant part of our work, and it was based on several articles [48,49,50,51], with the work of Fišer [52] being a vital starting point to our work. In his thesis, he proposed an Approximated Consumption Function:

$$g\left(e,m\right)=\{\begin{array}{l}\kappa ·\delta \left(e\right)+\lambda ·\Delta ele{v}_e,\hspace{1em}if \Delta ele{v}_e\ge 0\\ \kappa ·\delta \left(e\right)+a·\Delta ele{v}_e,\hspace{1em}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}$$

(2)

where g is the consumption function, δ is a function that assigns a distance to an edge, e and m are the edge traversed and the EV model correspondingly, Δelev_e is the difference in elevation from the start of the edge u to end of it, v. Furthermore, κ, λ, and a are tuning constraints through which we can control the values of function g in order to yield realistic results. However, to cover the needs of our more practical approach, we moved on to introduce the Practical Consumption Function, which can be described by the following equation:

$$g\left(e,m\right)=\{\begin{array}{l}ConsWLT{P}_{e,m}+coef{f}_{uphill}\ast \left(m\ast g\ast \Delta ele{v}_e\right),\hspace{1em}if \Delta ele{v}_e\ge 0\\ ConsWLT{P}_{e,m}-coef{f}_{downhill}\ast \left(m\ast g\ast \Delta ele{v}_e\right),\hspace{1em}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}$$

(3)

where ConsWLTP is the consumption according to EV model and the WLTP standard, and the Electric Vehicle database [47]. The reason for using coeff_uphill and coeff_downhill is to emulate the performance of the motor of the vehicle when going uphill and the performance of the recuperation system going downwards. The energy recuperated while braking on a flat road is ignored. In comparison to other approximation functions used for considering the consumption for EV routing, our Practical Consumption Function avoids using further tuning parameters and includes the actual interchange between the potential and kinetic energy of the vehicle. Nonetheless, the results derived from our Practical Consumption Function are realistic and very close to findings reported in the literature of EV routing. The incorporation of more advanced formulas like ones presented in [53,54] our method can be considered as the next step in our research.

In order to provide the necessary background for the use of the Practical Consumption Function, the data for the distance and elevation are derived from the OpenTripPlanner API, which bases its calculations on OpenStreetMap data for the road network and SRTM data for the elevation. The aim of this model is not to introduce an EV consumption calculation model as compared to recent approaches [53,54], but to provide a mechanism for our method calculating meaningful results considering limited computation times. The model itself is based on WLTP standard for the consumption of EV models that already includes several parameters and laboratory tests and is only extended to include the effect of elevation, for the road segments traversed in the tour of the traveler. The consideration of more complex approaches are not necessary and not within the scope of this research.

5. Results

5.1. Use Cases

The experiments were run on ten instances of problems, where the solution space can significantly differ according to different preferences of the user. While one traveler may need to attend a set of fixed activities, another may be flexible concerning the locations of the activities or the temporal schedule of the activities. This means that the first traveler’s initial schedule and preferences would not allow the method to search for alternatives since there is no flexibility concerning the schedule, while the second traveler’s preferences would enable the method to search through a vast solution space for other options.

For all of the cases used for our tests, the activity chains contained at minimum one out-of-the-house activity and at maximum four out-of-the-house activities. For the first six instances of problems, cases 1 to 6, we considered synthetic cases of the problem, where the locations, types of activities, and flexibility were based on real activity chains of travelers, but also randomized in some of their attributes to a certain degree. For the rest of the examined cases, cases 7 to 10, we kept the set of locations and types of activities the same as in case 6, and then we included potential combinations of flexibility flags. We consider cases 1 to 6 the balanced cases, which could be input from real-world travelers, and cases 7 to 10, the extreme cases where the computational limits of the algorithm are tested.

In our use cases for the DACO-EV, the same vehicle was considered, and the SSoC was set to a medium-range percentage while the FSoC was required to be at a higher percentage than the SSoC, which means that a detour for charging is needed in all cases of problems displayed. For the results presented, and regarding case-specific characteristics, and the results presented below, for the provided instance of tests, for cases 1, 2, and 5 to 10 we have four out-of-the-house activities, whereas for cases 3 and 4, three out-of-the-house activities were conducted. Finally, let us state that the results provided here are calculated based on one of the criteria that are available in the method described and in Section 3.4.2, that of travel time. Thus, the parameters in the fitness function are all set to 0 except for parameter a that is set equal to 1.

5.2. DACO-EV Results

The results for the evaluation of the performance of the method in addressing the DACO-EV problems are presented. The performance of the algorithm is compared in regard to the travel time in the initial activity chain of the travelers and the resulting activity chain in both cases when precomputation is applied and when not, are given. The columns of the tables are the following:

• Initial time: Average travel time of the initial tour of the traveler (min)
• Opt. time (no pre): Average travel time for an optimized tour (without precomputation applied to the solution process) (min)
• Subtour (no pre): Average travel time in the subtour for a DACO-EV tour (without precomputation applied to the solution process) (min)
• Comp. time (no pre): Average computation time for the optimization of a tour (without precomputation applied to the solution process) (s)
• Opt. time (pre): Average travel time for an optimized tour (with precomputation applied to the solution process) (min)
• Subtour (pre): Average travel time in the subtour for a DACO-EV tour (with precomputation applied to the solution process) (min)
• Comp. time (pre): Average computation time for the optimization of a tour (with precomputation applied to the solution process) (min)

In

Table 6. Comparisons for the runs addressing the DACO-EV—effect of precomputation on solutions and computation time.

	Initial Time (Min)	Opt. Time (No Pre) (Min)	Subtour (No Pre) (Min)	Comp. Time (No Pre) (s)	Opt. Time (Pre) (Min)	Subtour (Pre) (Min)	Comp. Time (Pre) (s)
Case 1	32.61	57.79	30.19	59.25	38.11	23.57	14.28
Case 2	79.60	85.62	33.5	72.56	75.79	21.37	24.41
Case 3	70.75	66.73	27.23	85.53	55.37	13.83	17.59
Case 4	67.28	65.73	28.81	25.49	59.27	22.94	13.94
Case 5	81.28	85.33	39.82	110.43	75.64	33.95	19.89
Case 6	79.98	74.82	28.71	105.05	62.35	10.36	26.95
Case 7	79.98	81.15	26.38	35.48	80.72	24.34	20.50
Case 8	79.98	87.32	35.04	67.42	31.57	15.6	41.85
Case 9	79.98	81.67	30.86	37.65	76.03	25.19	18.81
Case 10	79.98	77.77	31.52	303.78	28.43	9.74	51.68

, the results addressing the several cases of experiments are presented.

It can be stated that the developed approach provides appropriate results that can serve EV drivers in their daily commutes. On the one hand, the overall travel time gets optimized(travel time for attending activities plus travel time in the introduced subtour), while the computation times remain at acceptable levels for a driver assistance system, that can be run by the driver for a few seconds in his or her pre-trip planning phase.

The optimized overall travel time is not reduced in all cases. This is because for the tests that we have run, in which charging is required because of the SSoC and FSoC levels, an extra charging activity or charging session was added. Although activity chains are optimized to reduce travel time, in some cases (e.g., cases 1 and 2), the travel time is raised. When precomputation is applied, the algorithm still finds only a solution with more travel time than the initial one (e.g., case 1), but it can calculate solutions that have less travel time than the initial one (e.g., case 2). It can be noticed that the travel time for the subtour, which, in most cases, is a big part of the overall travel time. A positive observation is that the computation time in balanced cases was 19.51 seconds(s) on average, which is a reasonable solution time if the method can be possibly reproduced to serve real travelers in their daily lives.

In Figure 6 and Figure 7, and

Table 7. Part of the input of the traveler regarding the spatial and temporal aspect of activities.

Activity Order	Type of Activity	Processing Time	Priority Label	Demand Time Start	Demand Time Close
Start	Home	0	1	480	480
1	University	480	1	540	1020
2	Burger Place	30	4	1060	1090
3	Coffee Shop	20	2	1170	1190
End	Home	0	3	1440	1440

and

Table 8. Attributes of the solution regarding the visits to the activities.

Activity Order	Type of Activity	Processing Time	Priority Label	Time of Attendance Start	Time of Attendance Close
Start	Home	0	1	480	480
1	University	480	1	540	1020
2	Burger Place	30	4	1024.37	1054.37
CS	Charging Station	97.2	−	1064.57	1161.77
3	Coffee Shop	20	2	1170	1190
End	Home	0	1	1201.3	1201.3

, we present an instance of case 3 in more detail to show how an activity chain of the traveler is initially set and how it can change after applying our algorithm. In Figure 6, we can see the initial activity chain, and in Figure 7, we can see how the algorithm produces an optimal activity chain. The travel time of the tour depicted in Figure 6 is 70.75 minutes (min), while the tour depicted in Figure 7 takes 55.37 min. The figures present the spatial aspects of the initial and optimized activity chain, and the tables present the temporal attributes of the two activity chains.

Regarding the initial activity chain of the traveler, it can be noticed that it includes three out-of-the-house activities, each with different levels of flexibility. Except for the first visit, that is conducted at the university, the other two activities are spatially flexible. This fact, in combination with the significant difference between the SSoC and the FSoC that forces the algorithm to add a visit to a CS, changes the spatial attributes of the initial activity chain to a great extent. In other words, the method proposes different locations to be visited by the traveler. In this specific example, the order of the visits to the activities does not change, but a charging session is added between the visits to the locations for the second and the third activities. Finally, we can notice that while the optimized activity chain includes an extra activity that corresponds to the detour for charging, the selection of alternative locations and suitable CS enables the reduction of the overall travel time.

5.3. Research Implications for EV Usage and Energy Systems

Apart from the obvious benefits that the method presents on an individual level for travelers, such as decreasing the travel time in their daily activity chains and dealing with range anxiety, there are two main takeaways regarding the use of EVs. Firstly, on an individual level, the method can be an effective supporting tool that helps minimize consumption, distributing drivers to the suitable CS according to availability and allowing them to find possible charging opportunities according to two realistic charging scenarios. The travelers that do not own chargers at their homes can greatly benefit from this method since it allows the calculation of tours and routes, that guarantee a FSoC for the drivers when reaching their home. On a system-level, the use of such a method, although it is aimed for personal usage, can provide benefits for cities. The better distribution of drivers to charging stations is a major possible benefit, as well as, the more efficient tours that are to be followed will minimize the consumed energy and the load on the charging stations network as a whole. As shown in work by Cuchý et al. [3], and their simulation efforts based on multi-destination planning tools like the one provided in this article, those methods can allow the better alignment of supply and demand and can help to make the overall transition to electromobility smoother.

6. Conclusions

A method has been elaborated for the solution DACO-EV problem, which many EV drivers face in their daily lives. Given the initial schedule of activities of the traveler, their locations, and priorities concerning each activity, our method calculates an optimal tour that guides the travelers in a better way. At the same time, travelers do not need to face range anxiety since the solution guarantees that the EV battery level remains above the desired energy level. In the modeling, two charging scenarios were included, where the traveler can charge the EV either while staying in the EV at the CS or leaving it for charging at a CS while conducting another activity. This article describes the following contributions of the method:

• Consumption calculation mechanisms based on previous literature and real-world EV usage attributes.
• Calculation of an optimal tour based on the Starting State of Charge (SSoC) and the desired Final Stage of Charge (FSoC) of the EV used.
• A real charging stations network for Budapest, Hungary, and the availability of those charging stations based on past usage data.
• Two real-world charging scenarios for the detour of travelers, when they need to charge their vehicles.

Our research efforts aimed to develop an optimization model that is capable of modeling the real-world problem of optimization of daily activity chains for EV users and can serve as a driver assistance solution that reduces the range anxiety of EV users. The model itself can be used for studying the utilization of CS networks in urban environments and the study of the expected behavior of EV drivers. As discussed earlier in this article, although those methods address the problem on an individual level, they can be beneficial for the system-level, the CS network infrastructure, and the road network.

As a few next steps in this research, we propose further investigation of the incorporation of the availability of charging stations. It should be studied how solution times and the quality of solutions delivered by the algorithm change when the availability is considered according to different data mining methods. A worth mentioning research direction is the inclusion of the effect of traffic on the tours that happen on rush-hours and may get delayed travel times in regard to traffic. The utilization of this algorithm as part of a simulation framework based on activity-based modeling is a long-term research goal.