Ridesharing in Rural Areas with Autonomous Electric Vehicles and Interrelated Trips

Abstract

Passenger cars are responsible for 44% of the greenhouse gas emissions within Europe’s transportation sector. Especially rural areas are still fundamentally dependent on private motor vehicles, which is why in particular the younger and older population in such regions is limited in their mobility. The purpose of this paper is to determine the potential of shared, electric, autonomous vehicles to close the aforementioned mobility gap in an eco-friendly manner. It provides recommendations for the implementation of the associated transport services in terms of vehicle battery size and charging station infrastructure. For this purpose, we present a model for the electric autonomous dial-a-ride problem with interrelated trips (e-ADARP-IT), which is solved by a commercial solver and through a Variable Neighborhood Search heuristic. Computational experiments reveal the superior performance of the heuristic. It is shown that large shares of requested trips can be served efficiently at low operational cost. Results further indicate that expanding vehicle battery capacity seems more relevant than expanding the number of charging stations, even though both developments clearly have to go hand in hand.

1 Introduction

The transport sector is responsible for more than a quarter of the EU’s greenhouse gas emissions. 44% of its share is generated by passenger vehicles and, consequently, has a crucial impact on achieving the 1.5$^{\circ }$ C target of the Paris Climate Agreement [13]. The combination of the three innovations of electrification, autonomous driving, and shared mobility has the disruptive potential to significantly change the personal mobility sector [44]. Together they form the potential for shared autonomous electric vehicles (SAEVs). With the help of SAEVs, greenhouse gas emissions per kilometer can be reduced by over 90% and mobility cost reach 0.16–0.26 €/km, where both these performance measures lie significantly below those of private vehicles with combustion engines [4].

The route planning problem associated with SAEV services is the dial-a-ride problem (DARP), a combinatorial optimization problem. The DARP consists of customer requests for transportation from given origin locations to given destination locations, which have to be scheduled on a finite number of vehicles. The objective could be to maximize a service quality measure or to minimize transportation costs [5]. SAEV services as considered in this paper combine multiple DARP-variants within one problem: The dial-a-ride problem with interrelated trips (DARP-IT), which synchronizes customer requests that are related to each other by means of a common arrival time of multiple customers or a round trip with a desired stay time at a location [27], and the electric autonomous dial-a-ride problem (e-ADARP) that deals with electric and autonomous vehicles including battery management and recharging [5]. This article combines these two variants, resulting in the electric autonomous dial-a-ride problem with interrelated trips (e-ADARP-IT).

Most studies on DARPs for autonomous and electric vehicles focused on urban areas [4, 5, 30]. In contrast to this, [27] considered the DARP-IT for rural areas, where interrelated trips are of particular importance as customers also demand guaranteed return trips, synchronized arrivals for joint meetings, or other complex service patterns. The paper at hand also focuses on rural areas and interrelated trips. Mobility in such areas is characterized by relatively long transport distances and a very limited availability of public transport options. This effects that the population so far relies on privately owned vehicles, which heavily restricts those people that do not own or cannot operate a car on their own, such as young or elderly people, see [27]. We, therefore, explore the potential of SAEV in rural areas by combining the approaches of [27] for the ADARP-IT and of [5] for the e-ADARP within a holistic model and solution approach. The advances over [27] lie in the integration of battery management into the dial-a-ride problem with interrelated trips (ADARP-IT) and thus bridges the gap between these two research directions in the domain of dial-a-ride problems. A heuristic solution is adopted from [27] and compared to the solutions derived from solving the optimization model directly. In our experiments, we then focus on a rural area in the federal state of Schleswig-Holstein, Germany. The associated test instances vary in terms of the number of customer requests, the vehicles being available and their battery capacity, as well as the number of charging stations. The influence of the number of charging stations and the size of the battery capacity is then analyzed w.r.t. the service quality for the interrelated trips in this rural area setting.

Therefore, the implementation of an autonomous ridesharing system in rural areas can provide several advantages, for instance by offering mobility services to people that cannot operate a vehicle themselves, by avoiding operational limitations such as personnel costs and service time constraints of conventional mobility services, and by allowing for more efficient vehicle sharing as well as a provision of services during off-peak hours. As rural areas generally lack an offer of public transport options, such a system can close the gap between the demand for mobility and the supply of mobility services.

The remainder of this paper is organized as follows. Section 2 gives an overview of relevant SAEV literature. Section 3 formalizes the e-ADARP-IT planning problem and presents the corresponding optimization model. Computational experiments in Sect. 4 contrast the optimization model-based results with a heuristic solution approach, focusing on the effects of battery capacity and the number of available charging stations. Section 5 concludes the paper.

2 Literature Review

SAEV services combine features of electrification, autonomous driving, and shared mobility, where autonomous vehicles offer economic and service time advantages due to not having a driver [20]. This typically allows for uninterrupted service provision and greater flexibility in the deployment [5]. Thereby ’shared mobility’ refers to the on-demand use of vehicles by multiple customers in contrast to privately owned vehicles that are exclusively used by their owners. Shared mobility can take various forms such as ridesharing, carsharing, or bike-sharing, and allows for cost savings, reduced greenhouse gas emissions, and less reliance on vehicle ownership [43].

The route planning problem of shared autonomous vehicles (SAVs) is treated within the DARP. The combinatorial optimization problem minimizes the transportation cost and/or maximizes the service quality [5].

[36] classify the literature on SAV research based on booking type and sharing system. The booking type divides into reservation-based and on-demand-based services. In the latter, the customer can book his/her trip in real-time, and those requests have to be integrated into the ongoing vehicle service process, see e.g. [25]. The use of priority rules has been established for this purpose by [15]. In contrast, in reservation-based services, customer requests are known before the vehicle routes are to be determined. This means that the DARP is solved using the data is available up to that time, which typically leads to a static perspective on this optimization problem, see [24] and [5]. Due to the longer distances and longer relocation times of vehicles in rural areas, reservation-based services appear suitable for mobility systems in such regions [27].

The mobility systems for SAVs can be divided into ridesharing, carsharing, and mixed systems based on the way vehicles are shared in the operations [36]. In carsharing, customers typically use a car one after the other, such that requests are serviced in a sequential manner. In ridesharing, several customers that demand transportation from/to similar locations might jointly use the same vehicle. In this context, [9] investigate how to identify suitable meeting points to which customers can walk over short distance from their actual origin location or desired destination location. They incorporate this feature into a DARP in order to reduce detouring of vehicles while offering attractive service routes to customers. In [29], the authors focus on the dial-a-ride problem in an urban road network with ride-sharing by autonomous taxis under consideration of traffic congestion. They propose a non-linear integer programming model embedded within a rolling horizon framework to optimize the routing of the taxis while maximizing the profit of the system. A mixed system is characterized by customers deciding whether to share the vehicle with other customers or use it on their own. The subdivision of SAVs described above also applies to SAEVs. Electric vehicles are more energy efficient and reduce CO$_2$ emissions compared to vehicles with internal combustion engines [14]. In the context of integrating electric vehicles into public transport, finding routes of minimal energy consumption, scheduling vehicle charging processes, and optimizing battery life have been identified as novel challenges [3]. Related issues for SAEVs are battery management and the provision of charging station infrastructure [30]. Aspects of electric vehicle battery management have been investigated in many studies on different vehicle routing problems. Examples include the electric and green vehicle routing problem, e.g. [11, 19, 41], the hybrid electric traveling salesman problem [1, 12], and the vehicle routing problem with time windows and charging stations [2, 22].

Also charging policies and charging functions have been investigated in detail for various routing problems. The charging policy determines the amount of battery capacity that can or must be restored at a charging station [35]. Established policies for the charging process include full charging [41], battery swapping [33], or partial charging [11, 16]. Next to these charging policies, the assumption can be made that a charging process can be terminated prematurely when a new customer request arrives [4, 30]. To deal with the large number of factors affecting the charging process, linear approximations of the charging function are often adopted in research [16, 28, 35]. Furthermore, the majority of approaches assume that the discharge of the battery occurs constantly over the travel time and that the corresponding discharge rate can be derived from an energy consumption model [17, 19, 39]. This assumption is typically valid if the vehicle load is negligible in comparison to the weight of the empty vehicle and if vehicles go at a quite constant speed [5, 11, 40]. Regarding the deployment of charging station infrastructure, different strategies exist, too. For example, [26] place charging stations at cab stands or other points of interest whereas [4] use an elimination strategy: charging stations are initially placed at all permissible locations and, then, those stations with the least impact on the system are eliminated in an iterative process. [31] proposes a two-stage solution approach, addressing the dynamic vehicle charging scheduling problem with the objective of minimizing the costs associated with daily charging operations for the fleet. The approach consists of two components: the scheduling of daily vehicle charging and the online assignment of vehicles to chargers. The above-mentioned elements of battery management are focused in [5] among others. The authors investigate the use of SAEVs in urban environments by modelling an e-ADARP and solving it through a branch-and-cut algorithm.

In our paper, we combine existing approaches from the literature. We investigate the e-ADARP-IT from the perspective of a mobility service provider, who uses autonomous e-vehicles for offering reservation-based ridesharing services in rural areas. We take up the modeling of battery management decisions of [5] and include it into the ADARP-IT of [27]. The ADARP-IT has been established to investigate SAV-services with interrelated trips in rural areas. Through the inclusion of aspects of electric vehicles management, we derive the e-ADARP-IT that closes the gap between these two directions of DARP-research.

In addition, the research conducted opens a potential link to existing publications in the area of demand-responsive transportation. While [10] investigate the benefits of meeting point usage for customer pick-up and drop-off, [23] evaluate the performance of a dial-a-ride service using simulation. With this, operators of transport systems can be provided with guidelines for designing their dial-a-ride services by identifying the parameters that significantly influence the evaluation criteria.

3 Modelling the E-ADARP-IT

In this section, we present the mathematical formulation for the e-ADARP-IT. Subsection 3.1 introduces the different types of customer requests that are to be considered. This is followed by introducing the used notation in Subsect. 3.2 and the presentation of the mixed-integer linear optimization model for the e-ADARP-IT in Subsect. 3.3.

3.1 Classification of Customer Requests

In DARPs, customers place requests for being transported from a specified starting point (pick-up location) to a specified destination point (drop-off location) [8]. In classical variants of the DARP, each customer is assumed to place one such request, without and interrelations among these requests existing, see [7]. We call such requests, conventional requests.

In our work, we also consider more complex trip request types, where two or more trips are interrelated with each other. Such complex customer requests were introduced by [27] and are distinguished into requests with serial relations and requests with parallel relations. Serial relations are characterized by an outbound and a return trip, combined with a stay time at the destination of the outbound trip. The drop-off location of the first trip and the pick-up location of the second trip are, thus, identical. Such trips play a role if a customer demands a guaranteed return trip, which is particularly relevant in urban area settings. The challenge in route planning is to schedule the drop-off of the first trip and the pick-up of the second trip such that the desired stay time is guaranteed. The second type of complex requests are those with parallel relations, which can be further subdivided into parallel drop relations and parallel pick relations. In this paper, only parallel drop relations are considered for reasons of brevity. A characteristic of such a parallel request is that two or more trips share the same drop-off location, for example as the involved customers want to meet there. The complexity of parallel drop requests results from the need to have customers arrive at the common drop-off location at approximately or exactly the same time. As is described by [27], these mentioned customer request types can be flexibly combined in a modular way, resulting in even more complex mobility request types.

Table 1. Notation

3.2 Notation

We use the following notation for modelling the e-ADARP-IT (see also summary in Table 1): The mobility service provider has a fleet of vehicles $K = \{1,...,m\}$, where vehicle $k \in K$ has a passenger capacity $PC^k$, a battery capacity $b_k$, and starts its operations from the origin location $o_k$. These locations form set $O = \{o_1, \ldots o_m\}$. Following the concept of a reservation-based service system, the relevant information about customer requests is known to the service provider at the time of the planning. More precisely, we denote by $R = \{1,...,n\}$ a set of trip requests with corresponding pick-up location $p_i$ and drop-off location $d_i$ of trip $i \in R$. The pick-up and drop-off locations of all trips form sets $P = \{p_1,..., p_n\}$ and $D = \{d_1,...,d_n\}$, respectively. The set of available charging stations for the electric vehicles is denoted $CS = \{cs_1,...,cs_l\}$. The set of all locations in a problem is denoted $V = O \cup P \cup D \cup CS$. Due to the ridesharing concept, a vehicle can serve different requests from multiple customers simultaneously. Each location $i \in V$ is thus characterized by a change in the number of customers $q_i$ that occurs at this location. For pick-up locations $p_i$, $q_{p_i}$ takes a positive value because customers are boarding. At drop-off locations $d_i$, customers leave the car which is reflected by a corresponding negative value $q_{d_i} = - q_{p_i}$. For all locations $i \in O \cup CS$, we set $q_i = 0$. In addition, service times $s_i$ are incurred for customers boarding at pick-up location $p_i$ and being dropped off at destination location $d_i$. Furthermore, we denote by $e_i$ and $s_i$ the earliest and latest time for starting service at a location i. Also, the overall travel time for a trip $i \in R$ is bounded to $\bar{u}_i$ time units in order to restrict the prolonged travel time that the customer might experience due to the detouring in the ridesharing system. For a serial-related outbound trip i, we state by $S_i \subset R$ the set of those trip(s) that have to follow on trip i subsequently. Furthermore, we denote by $\delta _{i}^{min}$ and $\delta _{i}^{max}$ the least and the maximum stay time of the customer at the drop-off location of trip i, respectively, before the subsequent trip(s) can be started. Finally, we denote by $G_{i} \subset R$ the set of those trips that have a parallel drop-off relation with trip i, i.e., that should arrive at the destination at similar time. For this, we denote by $\omega _i^{max}$ the maximum waiting time for the arrival of the customer(s) belonging to trip i and accordingly for the trips in $G_i$.

Each charging station $cs \in CS$ has a charging rate $\alpha _{cs}$. This rate defines the electricity amount (in kWh per minute) that is taken up by a vehicle charging at cs. The charging time $C_{cs}^k$ of vehicle k at station cs is a decision variable and determines the charged electricity quantity as $\alpha _{cs} \cdot C_{cs}^k$. Furthermore, we prescribe a target charging level $\gamma$ that is not to be exceeded when charging a vehicle to proactively restrict long charging times if desired. Finally, $c_{i,j}, t_{i,j}$, and $\beta _{i,j}$ represent the travel cost, travel time, and battery consumption of a vehicle that goes directly from location i to location j. We assume that battery consumption $\beta _{i,j}$ depends linearly on the travel time $t_{i,j}$ and is not influenced by any further factors.

The decisions to be made are modeled through the following decision variables. The binary variable $y_i$ equals 1 if request $i \in R$ is serviced, 0 otherwise. Variable $x_{ij}^k$ equals 1 if vehicle $k \in K$ travels directly from location $i \in V$ to location $j \in V$, 0 otherwise. Variable $z^k_i$ equals 1 if vehicle k ends its trip at location i, 0 otherwise. The continuous variable $T^k_i$ expresses the arrival time of vehicle k at location i. The number of customers in vehicle k after leaving location i is expressed by variable $L^k_i$. While continuous variable $B^k_i$ denotes the charge level of vehicle k’s battery when arriving at location i, variable $C^k_{cs}$ denotes the charging time of vehicle k at charging station $cs \in CS$.

3.3 Optimization Model for the E-ADARP-IT

The e-ADARP-IT is modeled through formulas (1) to (33). The objective function (1) primarily seeks to maximize the number of serviced requests, followed by the secondary objective of minimizing the operational service cost. Coefficient r serves as a weight in this combined objective function and ensures a hierarchy of the two goals if set to a sufficiently large value [27].

$$\begin{aligned} max~Z = r\sum _{i\in R} y_{i} - \sum _{k\in K}\sum _{i\in V}\sum _{j\in V}x_{i,j}^k \cdot c_{i,j} \end{aligned}$$

(1)

$$\begin{aligned} \sum _{j\in V}x_{o_k,j}^k=1&\quad k \in K \end{aligned}$$

(2)

$$\begin{aligned} \sum _{j\in V}\sum _{u\in K\atop {u\ne k}}x_{o_k,j}^u =0&\quad k \in K \end{aligned}$$

(3)

$$\begin{aligned} \sum _{j\in V\atop {j\ne i}}x_{j,i}^k-\sum _{j\in V\atop {j\ne i}}x_{i,j}^k=0&\quad k \in K, i \in P \end{aligned}$$

(4)

$$\begin{aligned} \sum _{j\in V\atop {j\ne i}}x_{j,i}^k-\sum _{j\in V\atop {j\ne i}}x_{i,j}^k-z_{i}^k=0&\quad k \in K, i \in D \cup CS \end{aligned}$$

(5)

$$\begin{aligned} \sum _{i\in D\cup \{o_k\}}z_{i}^k=1&\quad k \in K \end{aligned}$$

(6)

$$\begin{aligned} \sum _{j\in V\atop {j\ne p_{i}}}x_{p_{i},j}^k-\sum _{j\in V\atop {j\ne d_{i}}}x_{j,d_{i}}^k=0&\quad k \in K, i \in R \end{aligned}$$

(7)

$$\begin{aligned} \sum _{j\in V}\sum _{k\in K}x_{p_{i},j}^k \ge y_{i}&\quad i \in R \end{aligned}$$

(8)

$$\begin{aligned} x_{i,i}^k=0&\quad k \in K, i\!\in \!P\!\cup \!D\!\cup \!CS \end{aligned}$$

(9)

$$\begin{aligned} T_{j}^k \ge T_{i}^k+s_{i}+t_{i,j}-M_{i,j}(1-x_{i,j}^k)&\quad k \in K, i,j \in V,i\!\ne \!j \end{aligned}$$

(10)

$$\begin{aligned} T_{d_{i}}^k \ge T_{p_{i}}^k+s_{p_{i}}+t_{p_{i},d_{i}}&\quad k \in K, i \in R \end{aligned}$$

(11)

$$\begin{aligned} e_{i}\le T_{i}^k \le l_{i}&\quad k \in K, i \in V \end{aligned}$$

(12)

$$\begin{aligned} \overline{u}_i \ge T_{d_{i}}^k-T_{p_{i}}^k-s_{p_{i}}&\quad k \in K, i \in R \end{aligned}$$

(13)

$$\begin{aligned} L_{j}^k \ge L_{i}^k+q_j-PC^k(1-x_{i,j}^k)&\quad k \in K, i,j \in V,i\!\ne \!j \end{aligned}$$

(14)

$$\begin{aligned} L_{j}^k \le L_{i}^k+q_j+PC^k(1-x_{i,j}^k)&\quad k \in K, i,j \in V,i\!\ne \!j \end{aligned}$$

(15)

$$\begin{aligned} 0\le L_{i}^k \le PC^k&\quad k \in K, i\in P\cup D \end{aligned}$$

(16)

$$\begin{aligned} L_{i}^k =0&\quad k \in K, i\in O\cup CS \end{aligned}$$

(17)

$$\begin{aligned} y_{i} =y_{j}&\quad i \in R, j\in S_{i}\cup G_{i} \end{aligned}$$

(18)

$$\begin{aligned} T_{p_{j}}^u \ge T_{d_{i}}^k+ \delta _{i}^{min}\!-\!M'_{d_{i,p_{j}}}(2-\!\!\sum _{l\in V}x_{l,d_{i}}^k-\!\!\sum _{l\in V}x_{p_{j},l}^u)&\quad k,u \in K, i\in R,j\in S_{i} \end{aligned}$$

(19)

$$\begin{aligned} T_{p_{j}}^u \le T_{d_{i}}^k+ \delta _{i}^{max}\!-\!M'_{d_{i},p_{j}}(2-\!\!\sum _{l\in V}x_{l,d_{i}}^k-\!\!\sum _{l\in V}x_{p_{j},l}^u)&\quad k,u \in K, i\in R, j\in S_{i} \end{aligned}$$

(20)

$$\begin{aligned} T_{d_{j}}^u \le T_{d_{i}}^k+ \omega _{i}^{max}\!-\!M'_{d_{i},d_{j}}(2-\!\!\sum _{l\in V}x_{l,d_{i}}^k-\!\!\sum _{l\in V}x_{l,d_{j}}^u)&\quad k,u \in K, i\in R, j\in \! G_{i} \end{aligned}$$

(21)

$$\begin{aligned} 0 \le B_{i}^k\le b_{k}&\quad k\in K, i\in V \end{aligned}$$

(22)

$$\begin{aligned} B_{o_{k}}^k = b_{k}&\quad k\in K \end{aligned}$$

(23)

$$\begin{aligned} B_{j}^k \le B_{i}^k -\beta _{i,j}+b_k(1-x_{i,j}^k)&\quad \begin{array}{l} k\in K, i\in V \backslash CS, \\ j \in V \backslash \{o_k\},i \ne j \end{array} \end{aligned}$$

(24)

$$\begin{aligned} B_{j}^k \ge B_{i}^k -\beta _{i,j}-b_k(1-x_{i,j}^k)&\quad \begin{array}{l} k\in K, i\in V \backslash CS, \\ j \in V \backslash \{o_k\},i \ne j \end{array} \end{aligned}$$

(25)

$$\begin{aligned} B_{j}^{k} \le B_{cs}^{k}+ \alpha _{cs} \cdot C_{cs}^{k} -\beta _{cs,j}+b_{k}(1-x_{cs,j}^{k})&\quad \begin{array}{l} k\in K, j\in V, \\ cs \in CS,j \ne cs \end{array} \end{aligned}$$

(26)

$$\begin{aligned} B_{j}^k \ge B_{cs}^k+ \alpha _{cs} \cdot C_{cs}^k -\beta _{cs,j}-b_{k}(1-x_{cs,j}^k)&\quad \begin{array}{l} k\in K, j\in V, \\ cs \in CS,j \ne cs \end{array} \end{aligned}$$

(27)

$$\begin{aligned} C_{cs}^k \ge 0&\quad k\in K, cs\in CS \end{aligned}$$

(28)

$$\begin{aligned} b_{k} \cdot \gamma \ge B_{cs}^k+\alpha _{cs} \cdot C_{cs}^k&\quad k\in K, cs\in CS \end{aligned}$$

(29)

$$\begin{aligned} T_{i}^k \le T_{cs}^k+t_{cs,i}+C_{cs}^k+M_{cs,i}^k(1-x_{cs,i}^k)&\quad \begin{array}{l} k\in K, cs\in CS, \\ i\in \!D\!\cup \!P\!\cup \!CS\!\cup \!\lbrace o_{k}\rbrace , \\ i\ne cs \end{array} \end{aligned}$$

(30)

$$\begin{aligned} T_{i}^k \ge T_{cs}^k+t_{cs,i}+C_{cs}^k-M_{cs,i}^k(1-x_{cs,i}^k)&\quad \begin{array}{l} k\in K, cs \in CS, \\ i\in \!D\!\cup \!P\!\cup \!CS\!\cup \!\lbrace o_{k}\rbrace , \\ i\ne cs \end{array} \end{aligned}$$

(31)

$$\begin{aligned} x_{i,j}^k, z_{i}^k \in \lbrace 0,1\rbrace&\quad k\in K, i,j\in V \end{aligned}$$

(32)

$$\begin{aligned} y_{i} \in \lbrace 0,1\rbrace&\quad i\in R \end{aligned}$$

(33)

According to Constraints (2) and (3), each vehicle starts its tour at its own origin location $o_k$. Constraints (4) ensure the vehicle flow at pick-up locations. Constraints (5) define this for drop-off locations and charging stations. This constraint provides flexibility for the continuation of a route, as a vehicle k may continue its tour to some other location j ($x^k_{ij} = 1$) or end its tour at the current location i ($z^k_i = 1$). Constraints (6) then state that each vehicle route has a defined end location. This location can also be the origin location $o_k$ if the vehicle did not move at all ($z^k_{o_k} = 1$). Constraints (7) ensure that both the pickup and the drop-off of a request are performed by one and the same vehicle. Constraints (8) ensure that a request is considered served, only if the pickup location has actually been visited by a vehicle. Constraints (9) avoid that this requirement is fulfilled via trivial sub-cycles.

Constraints (10) to (13) address the time components of the solution. Constraints (10) propagate the vehicle arrival time from one visited location to the next, where the value $M_{i,j}$ is set to $max(0,l_i+s_i+t_{ij}-e_i)$ as in [5]. Constraints (11) denote that a drop-off location $d_i$ must be visited after the associated pick-up location $p_i$. Constraints (12) ensure the preset time windows for visiting the locations. With $i=o_k$ and a corresponding value for $e_{o_k}$, the time at which vehicle k becomes available for the service system can be considered in this constraint, too. The maximum travel duration of a trip is bounded by Constraints (13).

Capacity restrictions (14) and (15) derive the number of customers $L^k_j$ onboard vehicle k after leaving a visited location j. Constraints (16) respect the vehicle capacity and Constraints (17) ensure that all vehicles are empty at their origin locations and while charging.

From Constraints (18), complex requests are always served completely or not at all, but never partially. More precisely, all interrelated trips $j \in S_i \cup G_i$ are served if trip i is served. Constraints (19) and (20) focus on serially related trips. They ensure the minimum and maximum customer stay times between drop-off and subsequent pick-up, where $M'_{d_i,p_j} = max(l_{d_i} + \delta ^{min}_i - e_{p_j}, l_{p_j} - e_{d_i} - \delta ^{max}_i, 0)$, see [27]. Note that the trips in a serial request can be served by different vehicles k and u ($k\ne u$). For example, vehicle k can drop off the customer at drop-off location $d_i$ and another vehicle u can later collect the customer at pick-up location $p_j$ for the subsequent trip. Constraints (21) focus on the second type of complex requests, the parallel related trips. The restriction synchronizes the arrival times of parallel related trips i and j at the drop-off locations, where $M'_{d_i,d_j} = max(l_{d_j} - e_{d_i} - w^{max}_i, 0)$. For this, trip $j \in G_i$ at the drop-off location $d_j = d_i$ must not occur later than $w^{max}_i$ time units after trip i. By setting $w^{max}_i$ and $w^{max}_j$, flexibility or strictness can be reflected for these trips. For example, if $w^{max}_i = w^{max}_j = 0$, the customers must arrive at the drop-off location at exactly the same time.

Constraints (22) to (31) are for battery management. According to Constraints (22), the battery level of a vehicle k must not be negative nor greater than the battery capacity $b_k$ at any location i. Constraints (23) define that the battery of vehicle k is fully charged at the origin location $o_k$. The depletion of the battery level when going from some location i (which is not a charging station) to a subsequent location j is computed by Constraints (24) and (25). Constraints (26) and (27) calculate the battery status of a vehicle that just visited a charging station cs before going to a subsequent location j. These constraints take care of the charged quantity $\alpha _{cs} \cdot C^k_{cs}$. Charging times $C^k_{cs}$ are non-negative according to Constraints (28). Additionally, through Constraint (29), charging of a vehicle can be restricted to not exceed a target level $\gamma$. This helps, for example, to proactively avoid increasing charging times when approaching the maximum battery level. Furthermore, the charging times of a vehicle at a station cs are included in the propagation of the arrival time at the subsequently visited location i through Constraints (30) and (31), where $M^k_{i,s} = max(0, l_i+s_i+t_{i,s} - e_s)$. Eventually, Constraints (32) and (33) assure the binary character of variables $x_{i,j}^k$, $z_{i}^k$, and $y_{i}$.

The e-ADARP-IT model may be solved by any MIP-solver, provided that the instances are not too large. As an alternative solution approach, we have adopted the ADARP-IT VNS-heuristic of [27]. In general, VNS is a metaheuristic originally proposed by [21] that applies a systematic change of neighborhood structures within a local search scheme. In this paper, we take up the VNS of [27] and apply it to the e-ADARP-IT, by integrating battery management with the concept of a battery matrix derived from the matrix scheme proposed by [32]. This monitors chronologically the battery status of the vehicles and allows to include visits at charging stations suitably into the vehicle routes. The algorithm terminates after a predefined number of iterations without improvement of the current solution or after a prescribed number of fixed runs, whichever occurs first.

4 Computational Experiments

Section 4.1 describes the used test instances. Section 4.2 emphasizes a comparison of the solution approaches being available as well as the effects of battery capacity and charging station infrastructure on the solution quality.

4.1 Description of Test Instances

We use test instances from [27] for our computational experiments. These instances have been generated for the ADARP-IT and are supplemented here by data for an electric mobility system to use them for the e-ADARP-IT. The instances cover a rural area in the federal state of Schleswig-Holstein, Germany. In more detail, this rural area is located near the cities of Husum, Rendsburg, and Heide with the characteristic river Eider. This area is of a size of 45 $\times$ 25 km (approximately 1,125 km$^2$) and has an average population of 85 inhabitants per km$^2$ [37]. The map material of the test instances has been created with the help of OpenStreetMap [18]. Figure 1 presents a map of the studied region, where the areas in light gray indicate the low population density and its spread over the whole region.

Fig. 1.

Area under study.

The pick-up and drop-off locations of the test instances are derived from the distribution of households. Customer requests are, thus, based on population density. Travel times $t_{i,j}$ are calculated by the Open Source Routing Machine [38] for the fastest route between the involved locations. The test instances contain conventional and complex customer requests. For each conventional customer request, a conventional trip with a randomly selected drop-off time within the planning period is created. The associated time window $[e_{d_i}, l_{d_i}]$ is 15 min. For trips with parallel relations, it is assumed that each customer request consists of two trips from two customers. The customers will be picked up at their individual residences and dropped off at the same drop-off location. The customers’ maximum waiting time $w_i^{max}$ for each other is randomly selected from the time interval U [1, 10] minutes. For trips with serial relations, it is assumed that each customer request consists of two trips, one outbound and one return trip, where the drop-off location of the outbound trip is identical to the pick-up location of the return trip. The trips are associated with a stay time at the destination. The least stay time $\delta ^{min}_i$ is drawn from the distribution U [20, 60]. The maximum stay time $\delta ^{max}_i$ is by 10 min greater than $\delta ^{min}_i$. The maximum travel time $\overline{u}_i$ for each trip i is 150% of the direct travel time. The examined planning period of each test instance comprises 12 h. It is assumed that customer requests are evenly distributed over the planning horizon.

We assume a homogeneous vehicle fleet. Each vehicle has a capacity of PC$^k$ = 6 passengers, which is in line with ridesharing provider MOIA [42]. The vehicles’ origin locations are randomly selected from the set of relevant locations within the considered area. The number of customers boarding or alighting at a location is $q_i$ = 1/-1 for all requests. Customers can be picked up and dropped off within negligible time ($s_i$ = 0). Each vehicle has a battery capacity of $b_k$ = 40 kWh and is fully charged at the beginning of the planning horizon. The vehicles constantly consume 0.206 kWh per kilometer driven. All vehicles generate a travel cost of 0.1 monetary units per kilometer. The objective function primarily maximizes the number of served trips and secondarily minimizes the total cost. To ensure this, we set an objective weight of $r = 50$. Note that complex requests are only accepted if all involved trips can be served.

All charging stations support fast charging, meaning that a vehicle can be charged up to 80% within 40 min. This percentage value is also used for the target charge level $\gamma$ in Constraint (29). During the charging process, the vehicles are supplied with a charging quantity of $\alpha _{cs}$ = 0.8 kWh per minute at all stations.

Fig. 2.

Distribution of charging stations in the studied area.

The locations of the charging stations are determined using a grid heuristic [34]. Figure 2 illustrates the distribution of charging stations in the studied area for a total of 8 stations.

Table 2. Composition of the test instances.

Using the above configurations, we employ eight sets of test instances for our experiment, each involving four individual instances. Table 2 provides an overview of these instance sets, illustrating that the number of trips per instance ranges from 10 to 50, with 2 to 5 vehicles, and 4 to 16 charging stations. The requests are a mix of conventional and complex requests. The abbreviations ’CLE’ and ’MOI’ that are added to the name of the last four instance sets refer to two mobility service providers operating in Germany, from which particular battery capacity values of vehicles have been taken as is described in the next subsection.

The VNS heuristic has been implemented in Python 3.7 and all computational experiments were performed on a computer with a 3.2 GHz CPU and 32 GB memory. For the exact solution of the optimization model, the MIP solver CPLEX 12.9 was applied with a maximum runtime per test instance of ten hours (36,000 s).

4.2 Influence of Battery Capacity and Charging Infrastructure on Solution Quality

The experiments first contrast the performance of VNS and CPLEX and afterwards address the impact of the number of charging stations as well as the capacity of vehicle batteries. We first evaluate the performance of VNS and CPLEX for the first four instance sets with 10 to 50 trips, see Table 3. The results reported in a row are the averages over the four instances belonging to each set. The first column of the table identifies the instance set. Columns 2 to 6 report the results of the CPLEX solver and columns 7 to 11 the results of the VNS heuristic. Here, the abbreviation Acc denotes the percentage of accepted trips, i.e., those trips that are actually served in a solution, which refers to the primary goal of the objective function. The secondary objective, total transportation cost, is shown in column Co. UB represents the theoretic upper bound of the overall objective function value as determined by CPLEX. Performance measure $GAP = (obj - UB)/obj$ is the relative deviation of the actual objective function value obj of a solution to the upper bound. Value obj is not shown explicitly in the table but can be computed from the number of accepted requests and the objective weight r = 50 minus the operational cost. The calculation time is shown in column CPU in units of thousand seconds (k sec.). Columns 7, 8, and 11 (Acc, Co, CPU) of the VNS are analogous in meaning to the CPLEX columns. Furthermore, $\varDelta Acc$ maps the difference in accepted trips Acc between the VNS solution and the CPLEX solution. In order to take into account the different acceptance rates $\varDelta \overline{Co}$ represents the relative change in cost per served trip between CPLEX and VNS. Note that the CPU time of the VNS heuristic is composed of the total time of three runs with different initial solutions, which is why it may exceed the computation time limit set for CPLEX in rare cases.

Table 3. Results of the computational experiments for varied instance size.

The GAPs in Table 3 show that the CPLEX solver is hardly able to find optimal solutions. Actually, it only solves two out of the instances with 10 requests and one with 25 requests to optimality. Furthermore, even for the integer feasible solutions obtained for the other instances, the acceptance rate drops significantly the larger these instances are. The VNS algorithm produces comparable results for the very small instances but within negligible computation time. For the instances with 25 and more requests, it clearly outperforms CPLEX with much larger acceptance rates that increase by up to 47% points. At the same time, the operational costs per served trip are much lower (see column $\varDelta \overline{Co}$), indicating that VNS not just manages to serve many more requests than CPLEX but also in a way more efficient fashion and within lower CPU times. Based on the VNS results, SAEVs can serve a large portion of the diverse mobility demands in rural areas, with an average acceptance rate of 86% over all considered test instances.

We next address the question of whether SAEV providers should prioritize a high-density charging infrastructure or vehicles with large battery capacities. Two strategies are developed for investigating this. The first strategy uses vehicles with a battery capacity of 40 kWh and a larger number of charging stations (12 and 16). The battery capacity is derived from the vehicles used by the ride-pooling provider CleverShuttle, which is why the test instances are marked with the abbreviation ‘CLE’ (MIX50V5CS12CLE and MIX50V5CS16CLE) [6]. For the setting with 12 charging stations, these instances are identical to the ones reported in the last row of Table 3. In contrast, the second strategy uses vehicles with a larger battery capacity of 86 kWh and fewer charging stations (4 and 8). The battery capacity is similar to those of vehicles used by ridesharing provider MOIA [42]. The corresponding test instances are, thus, identified by abbreviation ‘MOI’ (MIX50V5CS4MOI and MIX50V5CS8MOI).

Table 4. Results of the computational experiments for varied charging infrastructure and battery capacities.

Table 4 reveals the effects of battery capacity and charging infrastructure on solution quality. The CPLEX solver cannot reach optimality within the given runtime for any solution of these test instances. Its results all have low to moderate acceptance rates and very high GAPs. Best results with an acceptance rate of 59.0% and the only GAP below 100% are obtained for test instances MIX50V5CS4MOI, clearly indicating that the larger the number of charging stations gets, the more CPLEX struggles. If we consider the test instances in ascending order of the number of charging stations, the negative impact of this number on the performance of CPLEX becomes very clear. The average acceptance rate of 59.0% for MIX50V5CS4MOI strictly decreases to 47.5% (MIX50V5CS8MOI) to 37.0% (MIX50V5CS12CLE) and to 20.5% (MIX50V5CS16CLE). At the same time, the GAPs increase strictly from 85.9% up to 604.5%.

In contrast, the acceptance rates of the VNS solutions are above 80% for all test instances, even reaching 98% for instance set MIX50V5CS4MOI. At the same time, the cost per served trip is up to 42.8% below the cost of the CPLEX solutions, confirming the superior performance of VNS under all experimental settings investigated here. However, VNS also exhibits high computation times, especially for the CLE-instances with many charging stations. Based on the results of the VNS, it can be seen that the test instances of the vehicles with a higher battery capacity (MOI) provide results with better solution quality compared to the CLE-instances. The average acceptance rate of the MOI-instances is about 15% higher than for the CLE-instances. For the CLE-instances with the lower battery capacities, more charging processes (about 40) take place in the solutions (not shown in the table). For the MOI-instances MIX50V5CS4MOI and MIX50V5CS8MOI, just eight and two charging processes are required, respectively. Furthermore, for both strategies the number of charging processes decreases as the number of charging stations increases. From this, the average cost per trip served decreases for both strategies as the number of charging stations increases, which reveals the relevance of dense charging infrastructure.

In summary, it can be stated that the number of charging stations has no substantial impact on the acceptance rate but on the cost per served trip. The battery capacity, on the other hand, has a clear positive influence on the acceptance rate and, thus, a significant impact on the quality of the solutions. This finding is consistent with [30], who identified battery range as a critical component of SAEV service systems. Hence, based on the computational experiments, a strategy focusing on large battery capacity seems more advantageous with regards to the service rate of mobility requests, whereas additional charging stations can help reducing the operational cost of the system.

5 Conclusions

This paper has presented the electric autonomous dial-a-ride problem with interrelated trips (e-ADARP-IT). The associated mixed integer linear optimization model includes, in addition to the properties of the classical dial-a-ride problem, synchronization constraints on the interrelated trips and constraints on the battery charging management of electric, autonomous vehicles. A variable neighborhood search (VNS) algorithm has been applied for the efficient solution of larger instances of the e-ADARP-IT. For the computational experiments, test data from a rural area in the German federal state of Schleswig-Holstein was used. The results show that small test instances with ten requests can to some extent be solved optimally using CPLEX. With increasing problem size, the solution quality obtained by CPLEX decreases drastically, such that the share of served trips drops to 37% for instances with 50 requests. The limitations of the performance of CPLEX increase with a larger number of charging stations. In contrast, the VNS heuristic performs consistently good over all instance sets. It finds solutions that efficiently serve up to 99% of the trip requests at low operational cost. The experiments furthermore show that the battery capacity of vehicles is a crucial issue in SAEV service systems. Larger batteries allow to serve a much higher share of trip requests. Clearly, sufficient charging infrastructure needs to be available, too. Nevertheless, increasing the number of charging stations beyond that point merely reduced the operational service cost in our experiments but did not result in larger acceptance rates for the trip requests.

Altogether, this paper contributes to identifying the potential of electric autonomous vehicles for closing mobility gaps in rural areas. It also opens up opportunities for further research. The VNS has proven to be suitable for solving the e-ADARP-IT but it might be too slow for usage in large service systems. There are also further aspects at the operational level that require more research. As an example, if charging stations are occupied by other vehicles, it needs to be decided whether the SAEVs accept a waiting time or are rerouted to another charging station. A further area of future research could be to combine the ride sharing approach with public transport services. Here, an integration of school transport would be possible as well as an offer as feeder for rail commuter lines.