Electrifying road-based long-haul transportation is an intricate task. Given the current state of battery technology, either the driving ranges of electric commercial vehicles (ECVs) are too short or high-capacity batteries are costly and so heavy that payloads are limited. An old, yet recently revitalized, charging infrastructure currently evaluated on multiple test tracks around the globe alternatively suggests charging of electric trucks while driving. Analogously to trams, trolley buses, or trains, ECVs are powered by an electric motor connected to overhead wires via a movable contact arm and supported by a battery or an extra conventional drive, which steps in on non-electrified road segments. This paper is dedicated to the routing of a single ECV executing full-truckload point-to-point deliveries along a highway main line where charge-while-drive infrastructure is fixedly installed along some but not all parts of the road. We formulate the resulting optimization problem, investigate computational complexity, and provide suitable solution procedures based on decomposition. Once all this is available, we explore the induction effect of charge-while-drive technology, i.e., the amount of charging detours required to gather enough energy for the next job. Our results show that the induction effect can be considerable and may lead to substantial extra traffic compared to conventional charge-while-park technology.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Electrification of vehicle fleets has proved successful in urban logistics where many customers live in a restricted area, and thus tour lengths are comparatively small (Oliveira et al., 2017). Given the current state of battery technology, electrifying road-based long-haul transportation, on the other hand, is an intricate task. The batteries of electric commercial vehicles (ECVs) employed in urban logistics with driving ranging between 130 and 160 km (Davis & Figliozzi, 2013) are too small for long-haul transportation, where they would require frequent recharging stops, impeding on-time deliveries (Liimatainen et al., 2019). Larger batteries enabling sufficient driving ranges exist, but are very costly and so heavy that they reduce the maximum payloads of ECVs considerably (Mareev et al., 2017). These limitations have triggered a recent (re-)consideration of charge-while-drive technology for road-based long-haul transportation.
Overhead wires are an old established technology to transmit electrical energy to trams, trolleybuses, and trains via roof-mounted current collectors, also denoted as pantographs or trolley poles. Even in truck-based freight transportation, catenary trucks, also known as trolley trucks (Plötz et al., 2019), have a long tradition and are still used in large mining projects (Cruzat & Valenzuela, 2018). In 2012, Germany’s largest industrial manufacturing company Siemens announced its eHighway concept, which transfers these previous approaches to public-road freight transportation (Siemens AG, 2019). In addition to an electric motor, powered via overhead wiring and connected by an automatic contact arm, a conventional engine or a battery with a range of about 50 to 100 km is applied to allow overtaking and to access non-electrified road segments (Plötz et al., 2019). Driving under overhead wiring not only powers the ECV, but additionally enables recharging of the battery.
Fig. 1
Examples for test tracks equipped with overhead wiring in Germany (left; source: Siemens AG), Sweden (middle; source: Scania CV AB), and the USA (right; source: Siemens AG)
×
Anzeige
Currently, a handful of test tracks on public or private roads all around the world exist (Siemens AG, 2019). Figure 1 depicts three examples from Germany, Sweden, and the USA. Note that other projects evaluate charge-while-drive infrastructure embedded into the road where a movable contact arm mounted under the vehicles connects to the power line grouted into the tarmac (Schwerdfeger et al., 2021). Moreover, one day, even inductive charge-while-drive technology without direct contact may be available on public roads (Deflorio et al., 2015). While our vehicle scheduling approach presented in this paper generally also covers these alternative charge-while-drive technologies, we stick to the case of overhead wiring, which seems closest to making it into daily operations.
In addition to all remaining technological problems to be solved until the power supply of trucks via overhead wiring reaches a market-ready state, there are two challenges in particular related to charge-while-drive infrastructure.
High investment costs: First, the investment costs for overhead wiring are huge. In addition to poles and wires, substations, analogously to those applied for tram and train systems (Rufer et al., 2004), are required every 1.5–3 km to convert the high-voltage alternating current of the power main line into the low-voltage direct current suited for ECVs. Kühnel et al. (2018) estimate the investment costs for each electrified (bidirectional) km to range between €1.7 and 3.1 million. Due to these huge infrastructure costs, it seems impossible to electrify a complete highway network. For Germany, Kühnel et al. (2018) estimate that electrifying about 30% of the German autobahn is sufficient to electrify the majority of long-haul transportation. Similar results are obtained by Schwerdfeger et al. (2021) for the largest German highway, the A7, when minimizing the investment costs for charge-while-drive infrastructure while still enabling ECV drives between all major German cities. Thus, it seems safe to assume that on a highway main line, only some segments will be electrified, interspersed with non-electrified segments where the ECV’s battery has to take over. This adds the challenging aspect of gathering enough electric energy for the drives along non-electrified highway segments and roads beyond the highway to the routing problem.
Induced traffic: The second challenge that might be associated with charge-while-drive technology that has not yet been publicly discussed is induced traffic. Traditionally, this term has referred to the frequently observed phenomenon that once additional capacity is added to a road network, latent demand materializes and the streets are loaded to capacity just as before (Goodwin, 1996). In the context of charge-while-drive technology, we borrow this term to denominate the additional traffic generated by charging detours that are required to gather enough energy for reaching the next customer without energy shortage. Whereas conventional ECVs charge while parking, charge-while-drive technology may incentivize the oscillation of ECVs between different customer regions to charge their batteries. Such behavior can be even more pronounced in the ramp-up phase when power obtained via overhead wiring is subsidized by public authorities to attract participants. One contribution of this paper is the investigation and quantification of the induction effect of charge-while-drive infrastructure, which we quantify with the help of our routing approach.
To do so, we formulate a basic electric vehicle routing problem with overhead wiring. Given a single ECV and a highway with predefined electrified and non-electrified segments, we aim to execute a given set of transport jobs each defining a full-truckload point-to-point delivery with a given start and end point along the highway and a predefined target charge level to reach each job’s actual origin and destination beyond the highway on non-electrified roads. Our objective is to minimize the makespan to execute all jobs without ECV battery shortage. We define this problem, investigate its computational complexity, and provide suitable exact and heuristic solution approaches. Once these solution approaches are available (and have proven their performance in a computational study), we switch to our research question elaborated above and explore the induction effect of charge-while-drive infrastructure. Specifically, we obtain the solutions of our solution approaches if the ECV is charged via overhead wiring and solve the same data instances for ECVs charged while parking at charging stations or when applying conventional trucks. This allows us not only to compare the resulting makespans of these alternatives, but also to benchmark the driven distances, which allows us to quantify the resulting induction effect of charge-while-drive infrastructure.
The remainder of the paper is structured as follows: Section 2 reviews the related literature. Section 3 defines our basic electric vehicle routing problem with overhead wiring and investigates its computational complexity. Solution approaches, namely, a mixed-integer program and two heuristic decomposition approaches, are presented in Sect. 4. Our computational study in Sect. 5 first investigates the computational performance of our solution approaches and then explores the induction effect. Finally, Sect. 7 concludes the paper.
2 Literature review
Our basic optimization problem, which we apply to quantify the induction effect of charge-while-drive infrastructure, belongs to the (vast) field of vehicle routing problems. Naturally, we cannot survey the huge number of papers published in this area. For an overview and introduction, we refer instead to Golden et al. (2008) and Vidal et al. (2020). Our optimization problem, however, is a very specific vehicle routing problem that has the following peculiarities: The vehicle to be routed (i) is an ECV that is charged with charge-while-drive infrastructure, (ii) only executes full-truckload point-to-point deliveries along a single highway constituting (iii) a routing problem on the line. Each of these peculiarities is addressed in the following paragraphs.
(i)
As electric vehicles in general, and freight transportation with ECVs in particular, have gained momentum, it is not surprising that a a large strand of scientific literature on green and electric vehicle routing has accumulated in recent years. For surveys, we refer to the literature reviews provided by Pelletier et al. (2016) and Lin et al. (2014). The vast majority of the literature, however, treats either battery swapping or charge-while-park infrastructure. Vehicle routing approaches related to charge-while-drive infrastructure are rare. The survey paper on inductive charging provided by Jang (2018) supports this finding. The vast majority of papers summarized there treat infrastructure planning. We assume that this decision has already been made, and take the placement of electrified and non-electrified road segments as an input. The only operations research papers related to vehicle routing with charge-while-drive infrastructure are by Deflorio et al. (2015), Kosmanos et al. (2018), and Li et al. (2018). Li et al. (2018) consider inductive charging and, due to lower power efficiency, assume higher energy costs for it. Given both charge-while-drive energy, which is more costly but enables movement while charging, and charge-while-park energy, which is cheaper but requires a vehicle standstill, they solve a bi-objective vehicle routing problem and provide a mixed-integer program. Deflorio et al. (2015) simulate the traffic flow along multilane streets where charging zones for inductive charging are located at given positions. In this way, they estimate the amount of energy received by each vehicle. Finally, route optimization to reach the destination of a single ECV with given charge-while-drive infrastructure in the most efficient way is treated by Kosmanos et al. (2018).
(ii)
Full-truckload transportation is an important logistics branch and has been shown to be the most efficient strategy if the economic lot size of customers is close to the vehicle capacity (Gallego & Simchi-Levi, 1990). Truckload carriers face the problem of efficiently transporting full-truckload point-to-point transport requests of customers with their truck fleets. The vehicle routing problem in the full-truckload context has received considerable attention; important contributions are, for instance, provided by Arunapuram et al. (2003), Ball et al. (1983), and Gschwind et al. (2019). In the context of parts supply for automotive assembly lines, full-truckload transportation with electric vehicles (i.e., tow trains executing milk runs) and their need to recharge has also been investigated by Emde et al. (2018), although not with charge-while-drive infrastructure.
(iii)
Due to their manifold applications, routing problems along a single line—for example, representing a river, a driving lane in a container yard, or a highway—have a long-standing tradition. First and foremost, there is the seminal paper of Gilmore and Gomory (1964), who solve the routing of a single vehicle executing full-truckload point-to-point transport requests along a line in polynomial time. Note that we apply their algorithm to sequence the transport jobs in our heuristic decomposition approaches elaborated in Sect. 4.3. Further studies investigate routing on the line under additional extensions, such as release dates (Psaraftis et al., 1990), release dates and/or deadlines (Tsitsiklis, 1992), multiple vehicles (Simchi-Levi & Berman, 1991; Yu & Liu, 2009), and capacity for multiple jobs at a time and/or preemption (Atallah & Kosaraju, 1988; Guan, 1998). Routing on the line of electric vehicles has been treated by Boysen et al. (2018). They optimize point-to-point job sequences if the single ECV has to visit charging stations intermediately at given positions. We, however, consider a charge-while-drive infrastructure for which no routing problems on the line yet exist.
To conclude, neither our specific vehicle routing problem nor the quantification of induced traffic caused by charge-while-drive infrastructure has yet been treated in the scientific literature. This finding is also supported by the recent literature survey on electric vehicles by Pelletier et al. (2016). They also mention overhead wiring as an upcoming future research issue with no literature coverage so far.
Anzeige
3 Problem description
3.1 Problem characterization
Our electric vehicle routing problem on a line with full truckloads and overhead wiring consists of the following basic ingredients:
Highway: We have a bidirectional highway of given length to be accessed and exited via ramps at given positions. The highway is equipped with overhead wiring in specific parts, so that we have fixed electrified and non-electrified segments along the highway.
ECV: Our single ECV is equipped with an electric engine, a movable contact arm to connect to the overhead wires in electrified segments, and a battery to power the engine in non-electrified segments. Driving with a constant velocity along a (non-)electrified segment adds (consumes) a fixed amount of charge to (from) the battery, which has a given maximum charge capacity that cannot be exceeded. Naturally, the ECV’s charge level may not fall below zero. Initially, the ECV is positioned at a given start position along the highway and has a given initial charge level at the start. We require the ECV to return to its initial position, e.g., the depot of the truckload carrier, after conducting all jobs.
Jobs: We have a given set of jobs each representing a point-to-point transport that loads our ECV to capacity. Each job has to be picked up and successfully delivered before the next job can be processed. Each job has an actual origin and destination beyond the highway, so that when leaving the highway at the closest ramp toward the origin (destination), our ECV requires a minimum charge level to ensure a successful pickup (delivery) of the associated load at the actual origin (destination) and the return to the closest ramp afterwards without energy shortage.
Given this setting, we aim to minimize the total travel distance of the ECV while successfully executing all jobs along the highway. Note that we omit from the objective the drives beyond the highway, because they are fixed once the job set is determined. They are, however, relevant to ensuring the minimum energy levels when leaving the highway toward a customer.
Fig. 2
Example instance with three solutions for two job sequences
×
Example Consider a bidirectional highway connecting positions 0 and 1. Five ramps and their positions along the highway are depicted as upward arrows within Fig. 2a. Our single ECV has an initial and maximum charge level of 0.5 and 1.0, respectively. It starts at position 0.5 and has to process the four jobs, whose start and end positions along the highway are given in Fig. 2a. Note that the job indices are given by the white numbers within the truck icons. For this example, we assume that the actual origins and destinations of these jobs are immediately at the indicated ramps, so that no additional energy is consumed to drive beyond the highway. We have a single electrified segment (accessible for both directions) between 0.3 and 0.6. When driving 0.1 length units along an electrified segment, the ECV receives 0.2 charge units and consumes 0.1 when driving along non-electrified segments. The solution depicted in Fig. 2b is the optimal solution for our example, which leads to a total driving distance of 2.0. This solution starts with an empty drive from initial position 0.5 to the start point of job 1. Then, this solution subsequently processes jobs 1, 2, 3, and 4. The charge levels when starting and completing each job are given by the numbers above the arrows in Fig. 2b. Two solutions for alternative job sequence \(\langle 3,4,1,2]\) are depicted in Fig. 2c, d. Solution (c) is infeasible, because directly approaching job 3 cannot charge enough energy to successfully complete second job 4 without energy shortage. Instead, our ECV has to drive empty in the opposite direction to charge sufficient energy before turning at the ramp at position 0.2 and heading back toward job 3. This allows us to derive feasible solution (d), but the charging detour increases the total driving distance to 2.6. Note that our example shows that in the best case, charge-while-drive technology produces no induced traffic compared to a conventional truck (or an ECV charging at a charging station on the way). However, if even the optimal solution requires charging detours, or if a truck route is badly planned, induced traffic may arise. The solution depicted in Fig. 2d, for instance, increases the traffic on our highway for processing our job set by \((2.6-2.0)/2.0=30\%\).
In the following, we list the (simplifying) assumptions made in our problem setting that we have not addressed before and provide some justification:
We consider a single highway but not a network of multiple interconnected streets. This may be a simplification once charge-while-drive infrastructure is well established. But since the investment costs for overhead wiring are substantial (see Sect. 1), especially during the ramp-up phase, only the most frequented highway main lines will be candidates for electrification. Moreover, a fast and reliable solution method for the single-highway case could also be applicable for solving this subproblem in a larger algorithmic framework dedicated to the general-network case.
A strictly parallel layout of electrified and non-electrified segments in both driving directions is economically advisable, because this policy saves extra substations (Kühnel et al., 2018). However, the terrain does not always allow this. We take the positions of the electrified and non-electrified segments of both driving directions as inputs, so that both cases can be modeled.
To isolate the impact of charge-while-drive infrastructure, we assume that for our ECV, neither the alternative charging options (e.g., charge-while-park infrastructure at charging stations along the highway) nor an additional conventional engine is available. Thus, our ECV is powered either via overhead wires in electrified segments or via the additional battery in non-electrified segments. Note that the type of ECV currently applied on the test tracks in Germany actually has a battery without additional plug-in function (to charge while parked), but is equipped with an additional diesel engine (Grüning, 2019). In our case study in Sect. 6, however, we benchmark different vehicle setups.
We assume constant charging and consumption rates per length unit on electrified and non-electrified highway segments, respectively. Although an approximation of reality, where these parameters vary with the charge level (Pelletier et al., 2016), this is an assumption frequently made in the electric vehicle routing community. One of the few exceptions is Froger et al. (2019).
On the demand side, fixed charging and consumption rates are based on the assumption of a constant average driving speed of our ECV. In the real world, the ECV’s speed is rather a decision variable or can vary over the day depending on the current traffic situation. However, since our main intention is to quantify the additional traffic induced by charge-while-drive infrastructure, constant driving velocities, which are already desired to save costs and energy, seem a pardonable simplification.
We assume that the ECV’s energy consumption on drives via exit- and on-ramps when changing the driving direction is negligible compared to the much longer drives along the highway. Thus, changing the direction is assumed to consume no energy. Note, however, that extending our solution approaches by this issue is straightforward.
Our (actual) objective is to minimize the makespan of processing the given set of transport jobs. This objective releases our ECV as early as possible and allows the system to start processing subsequent jobs earlier. Since the drives beyond the highway are fixed once the job set is determined, we simplify the problem and only address the driving distance of our ECV along the highway. Naturally, there are many other potential objectives (e.g., related to due dates); we, however, opted for the most basic one.
3.2 Problem definition
We consider a highway with end points at one-dimensional integer coordinates 0 to L. We have a set R of ramps with an integer position \(p_r\) for each ramp \(r\in R\) on the highway. These ramps are the only option to access and exit the highway, which is divided into electrified segments with overhead wiring and non-electrified segments without. This segmentation is represented by points \(q_1,\ldots ,q_{2W}\) of positions with \(0\le q_1<\ldots <q_{2W}\le L\). We interpret positions \(q_{2w-1}\) and \(q_{2w}\) with \(w=1,\ldots ,W\) as the start position and the end position of the wth electrified segment. Hence, it has a length of \(q_{2w}-q_{2w-1}\). We assume all these positions to be integers, that is, \(p_r\in \mathbb {N}\) for each \(r\in R\) and \(q_{2w-1},q_{2w}\in \mathbb {N}\) for each \(w=1,\ldots ,W\). Furthermore, we have a set J of jobs, and each job \(j\in J\) is specified by
Two ramps \(r^o_j\in R\) and \(r^d_j\in R\) with \(r^o_j\ne r^d_j\) representing the ramps where our ECV leaves the highway to pick up job j at its actual origin beyond the highway and to deliver job j at its actual destination, respectively, and
Numbers \(l^o_j\) and \(l^d_j\) representing the total travel distance beyond the highway when leaving the highway at the closest ramp to pick up job j and to deliver job j, respectively, and returning to the highway.
For each pair of jobs j and \(j'\) with \(r^d_j=r^o_{j'}\), we additionally have the total travel distance \(l^{d,o}_{j,j'}\) of the tour between leaving the line to, first, deliver job j, and second, pick up job \(j'\) and return to the line. This information is required whenever the pickup of a successor job directly follows the delivery of its predecessor via the same ramp without returning to the highway in between. We presuppose that \(l^{d,o}_{j,j'}\ge \max \{l^d_j,l^o_{j'}\}\) throughout the remainder.
We consider a single ECV with an initial position at ramp \(r^0\in R\), a battery capacity \(C\in \mathbb {N}\), and an initial battery charge \(c^0\in \mathbb {N}\) with \(0\le c^0\le C\). Finally, once all jobs have been processed, we require that the ECV returns to its initial position at ramp \(r^0\). Note that it is also possible to end the schedule once the last job is completed. Integrating this into our solutions concepts is straightforward, but we abstain from a detailed description. The ECV can travel the highway in both directions, but can change the travel direction at ramps only. Figure 3 illustrates the notation using the same instance as depicted in Fig. 2a (rescaled such that relevant positions are integers).
Fig. 3
Notation
×
The battery’s charge level is altered along the ECV’s route when it travels segments on the highway or picks up or delivers jobs.
The ECV, passing a part of the highway of length l which lies within an electrified segment, increases the charge of its battery by \(\min \{C-c,l\cdot \delta ^+\}\), where c is the battery’s charge at the beginning of that part, and \(\delta ^+\in \mathbb {N}\) is the constant charging rate. Hence, its battery’s charge is \(\min \{C,c+l\cdot \delta ^+\}\) at the end of the part. When passing a part of the highway of length l within a non-electrified segment or when driving a distance of l beyond the highway, our ECV’s battery charge decreases by \(l\cdot \delta ^-\). Here, \(\delta ^-\in \mathbb {N}\) is the constant consumption rate. Hence, the charge level is \(c-l\cdot \delta ^-\) at the end of the part.
The ECV, either picking up j or delivering j beyond the highway, decreases the charge of its battery by \(l^o_j\cdot \delta ^-\) or \(l^d_j\cdot \delta ^-\), respectively. Hence, its battery’s charge is \(c-l^o_j\cdot \delta ^-\) and \(c-l^d_j\cdot \delta ^-\), respectively, when returning to the highway afterwards. If, however, job j is delivered at the same ramp as job \(j'\) is picked up, and both operations are conducted while leaving the highway only once, then the ECV’s battery charge decreases by \(l^{d,o}_{j,j'}\cdot \delta ^-\) and is \(c-l^{d,o}_{j,j'}\cdot \delta ^-\) when returning to the highway afterwards.
Note that this definition accounts for negative charge levels of the battery, which will later be labeled as infeasible. A solution consists of two parts.
We have a sequence \(\sigma \) of all jobs in J specifying the order in which they are processed by the ECV. This sequence implies the order in which ramps are headed from where the line is left for picking up or delivering a job. We refer to the kth entry of \(\sigma \) by \(\sigma (k)\).
We have a sequence of ramps visited in between picking up or delivering jobs. More formally, this part of a solution is defined as follows:
For each job \(\sigma (k)\), with \(k=1,\ldots ,|J|\), of job sequence \(\sigma \), we have a sequence of all ramps passed along the highway after returning to the highway at \(r^o_{\sigma (k)}\in R\) after picking up job \(\sigma (k)\) and before leaving at ramp \(r^d_{\sigma (k)}\in R\) for delivering this job.
For each job \(\sigma (k)\), with \(k=2,\ldots ,|J|\), of job sequence \(\sigma \), we have a sequence of all ramps passed along the highway after returning to the highway at \(r^d_{\sigma (k-1)}\in R\) after delivering predecessor job \(\sigma (k-1)\) and before leaving at ramp \(r^o_{\sigma (k)}\in R\) for picking up successor job \(\sigma (k)\).
We have a sequence of all ramps passed along the highway before leaving the highway for the first time at \(r^o_{\sigma (1)}\in R\), and we have a sequence of all ramps passed after entering the highway for the last time at \(r^d_{\sigma (|J|)}\in R\).
Since the ECV can change its direction of travel only at ramps, a solution thus specifies the exact routing and hence its battery’s charge as a function of the total distance traveled up to a certain point of its route.
A solution is position-feasible if the ECV is located at its initial position at the start and the end of the routing, respectively, and any pair of ramps that are consecutive in the routing are consecutive along the highway as well.
A position-feasible solution is furthermore charge-feasible if the battery level does not drop below zero at any position along the route.
In a charge-feasible solution, the ECV can travel any segment between two ramps an arbitrary number of times to charge the vehicle. Note that such a charging detour occurs in solution (d) of Fig. 2. Zigzag routes where the ECV travels multiple charging loops, which might even be nested, seem counterintuitive, but can be the optimal choice to minimize the makespan. In order to obtain a lever with regard to the occurrence of charging detours, we enrich the problem by an additional parameter. Integer parameter \(\Pi \) imposes an upper bound on the number of charging detours allowed between any pair of consecutive pickups and deliveries (and before the first pickup and after the last delivery). We identify a charging detour by a change of travel direction at a ramp where the highway is not left for picking up or delivering a job.
A charge-feasible solution is feasible if the number of detours taken between any pair of consecutive pickups and deliveries (and before the first pickup and after the last delivery) does not exceed \(\Pi \).
The electric vehicle routing problem on a line with full-truckloads and overhead wiring (EVRP-LFO) is to find a feasible solution with minimum total travel distance along the highway.
3.3 Computational complexity
In this section, we will analyze the computational complexity of EVRP-LFO. More specifically, we show that two rather restricted special cases of the problem are \(\mathcal{N}\mathcal{P}\)-hard. Furthermore, our problem is also shown to be hard to approximate within an arbitrarily small factor.
First, we consider the special case of EVRP-LFO, where we have only a single electrified segment.
Theorem 1
EVRP-LFO is strongly \(\mathcal{N}\mathcal{P}\)-hard, even if \(W=1\), \(\delta ^+=\delta ^-=1\), \(l^o_j=l^d_j=0\) for each \(j\in J\), and \(\Pi \ge 1\) is fixed.
Proof
See Appendix. \(\square \)
Not only is our EVRP-LFO with a single electrified segment hard to solve, but it is also hard to approximate within arbitrarily small factors, as we will see in the following.
Theorem 2
There is no polynomial-time approximation algorithm for EVRP-LFO with a factor of less than 1.5 unless \(\mathcal {P}=\mathcal{N}\mathcal{P}\).
Proof
See Appendix. \(\square \)
Finally, we show that solving EVRP-LFO remains a complex matter, even if we have only a single job. Note that this finding directly implies that even if the job sequence is already given (e.g., determined by some metaheuristic), a complex optimization task remains as a subproblem.
Theorem 3
EVRP-LFO is \(\mathcal{N}\mathcal{P}\)-hard even if \(|J|=1\), \(C=\infty \), and \(\delta ^+=\delta ^-=1\).
Proof
See Appendix. \(\square \)
We can summarize that at least two aspects render EVRP-LFO inherently hard to solve. As stated by Theorem 1, determining the optimum sequence of jobs is hard even if choosing the electrified segment for recharging is not an issue. On the other hand, choosing the optimum electrified segments for recharging is also hard even if finding the job sequence is not an issue; see Theorem 3.
4 Solution approaches
This section is dedicated to our solution approaches. Section 4.1 provides a mixed-integer program that can be fed into an off-the-shelf solver. Section 4.2 presents a dynamic programming (DP) scheme for the subproblem that remains once the job sequence is already specified. This scheme is then applied in Sect. 4.3 to derive heuristic decomposition approaches.
4.1 A mixed-integer program
We summarize the notation used in our mixed-integer programming (MIP) formulation, which we dub EVRP-LFO-MIP, in Table 1. EVRP-LFO-MIP consists of objective (1) and constraints (2) to (27).
Table 1
Notation for EVRP-LFO-MIP
\(R=\{1,\ldots ,|R|\}\)
Set of ramps (numbered according to increasing positions)
\(J=\{1,\ldots ,|J|\}\)
Set of jobs
F
Set of ramp pairs with \((r,r')\in F\) among which a direct drive from \(p_r\) to \(p_{r'}\) is possible
\(\Pi \)
Upper bound on the number of charging detours between any pair of consecutive pickups and deliveries
M
Length of the sequence, with \(M=2|J|+(2|J|+1)\Pi +1\)
S
Set of sequence positions, with \(S=\{1,\ldots ,M\}\)
\(p_r\)
Position of ramp \(r\in R\)
\(r^o_j (r^d_j)\in R\)
Ramp where the ECV leaves the highway to pick up (deliver) job \(j\in J\)
\(d_{r,r'}=|p_{r'}-p_r|\)
Travel distance from \(p_r\) to \(p_{r'}\)
\(c^{\min }_{r,r'}\ge 0\)
Minimum charge level required for driving from \(p_r\) straight to \(p_{r'}\) without leaving the highway
\(c^{\max }_{r,r'}\le C\)
Maximum charge level achievable after driving from \(p_r\) straight to \(p_{r'}\) without leaving the highway
\(\delta _{r,r'}\in \mathbb {R}\)
Net change of charge level when driving from \(p_r\) straight to \(p_{r'}\) without leaving the highway
\(l^o_j\ge 0\) (\(l^d_j\ge 0\))
Total travel distance beyond the highway for picking up (delivering) job \(j\in J\)
\(l^{d,o}_{j,j'}\ge 0\)
Total travel distance beyond the highway for delivering job \(j\in J\) and picking up \(j'\in J\) with \(r^d_j=r^o_{j'}\)
\(\delta ^+,\delta ^-\ge 0\)
Charging and consumption rate
\(r^0\in R\), \(r^d= r^0\)
Initial and final position
\(C\ge 0\)
Maximum charge level
\(0\le c^0\le C\)
Initial charge level
\(x_{k,r}\in \{0,1\}\)
Binary variables: 1, if \(p_r\) is the kth position in the sequence; 0, otherwise [\(x_{1,r}\) (\(x_{M,r^d}\)) is a parameter reflecting the initial (final) position]
\(y_{k,j} (z_{k,j})\in \{0,1\}\)
Binary variables: 1, if j is picked up (delivered) at the kth position in the sequence; 0, otherwise
\(0\le c^a_{k} (c^d_{k})\le C\)
Continuous variables: charge level when arriving at (leaving) the kth position (\(c^a_1=c^0\) is a parameter reflecting the initial charge level)
\(0\le X_{k,r,r'}\)
Continuous variables with binary value in optimal solution: 1, if the \(k-1\)th position is \(p_r\) and the kth position is \(p_{r'}\); 0, otherwise
The basic idea for the modeling approach is to have a sequence of ramps being visited by the ECV. Binary variable \(x_{k,r}\) specifies whether ramp r is the one in the kth position of the sequence (\(x_{k,r}=1\)) or not (\(x_{k,r}=0\)). Note that ramps r and \(r'\) with \(x_{k,r}=x_{k+1,r'}=1\) are not necessarily consecutive, and \(x_{k,r}=x_{k+1,r'}=1\) implies all ramps in between r and \(r'\) being passed by. Binary variables \(y_{k,j}\) and \(z_{k,j}\) specify whether job j is picked up or delivered (\(y_{k,j}=1\) or \(z_{k,j}=1\)) via the kth ramp visit or not (\(y_{k,j}=0\) or \(z_{k,j}=0\)). Auxiliary continuous variables \(c^a_{k}\) and \(c^d_{k}\) track (a lower bound of) the charge level when arriving at the kth ramp and when leaving the kth ramp, respectively. Finally, auxiliary continuous variables \(X_{k,r,r'}\) signal whether the \(k-1\)th ramp is r and the kth ramp is \(r'\). Note that although \(X_{k,r,r'}\) is defined to be continuous, it only takes binary values in a feasible solution. Furthermore, we introduce dummy end position \(r^d\) and set F, which contains all ramp pairs among which feasible drives are possible, that is
$$\begin{aligned} F=\left\{ (r,r') \text { with } r\in R, r'\in R{\setminus }\{r\}\cup \{r^d\}:c^{\min }_{r,r'}\le C \right\} . \end{aligned}$$
The dummy end position is introduced merely for modeling purposes and coincides in its position with \(r^0\) (the dedicated final position of the ECV). A pair \((r,r')\) qualifies for F if a constant movement between two ramps r and \(r'\) without intermediate direction change does not necessarily drain the battery; that is, \(c^{\min }_{r,r'}\le C\) must hold, where \(c^{\min }_{r,r'}\) is the minimum charge level required for driving from \(p_r\) straight to \(p_{r'}\) without leaving the highway.
Objective function (1) reflects the goal to minimize the total driving distance along the highway. Constraints (2) to (10) altogether establish proper sequences of visited ramps with all jobs being processed. Specifically, constraints (2) and (3) ensure that each job is picked up and delivered. Due to constraints (4) and (5), at most one job can be picked up and delivered in each slot of the sequence, respectively. Constraints (6), (7), and (8) establish that there is exactly one position in each slot of the sequence and that positions are compatible with pickups and deliveries. Constraints (9) and (10) ensure that at most one job is processed at each moment and that jobs are delivered only after being picked up, respectively.
Constraints (11) to (20) establish the feasibility of solutions with respect to charge levels. Constraints (11) to (13) connect auxiliary variable \(X_{k,r,r'}\) to variables \(x_{k-1,r}\) and \(x_{k,r'}\). Constraints (14) bound the charge level when arriving at the kth ramp from above, depending on the charge level when leaving the previous ramp and the net change in the charge level on travel. In addition, constraints (15) impose an upper bound on the charge level when arriving at the kth ramp depending only on the kth ramp \(r'\) and the previous ramp r. We can predetermine \(c^{\max }_{r,r'}\) under the assumption that the ECV starts at r with a fully charged battery. Note that the resulting charge level at \(r'\) does not depend on the specific charge level when leaving r as long as at some point of the travel from r to \(r'\) the battery is fully charged. Constraints (16) to (19) bound the charge level when leaving a ramp from above depending on the charge level when arriving at this ramp and jobs picked up or delivered in between. Note that only \(c_k^d\le c_k^a\) is enforced if no job is picked up or delivered and that (18) dominates both (16) and (17) if \(z_{k,j}=y_{k,j'}=1\) due to \(l^{d,o}_{j,j'}\ge \max \left\{ l^d_j,l^o_{j'}\right\} \). Finally, constraints (20) ensure that the charge level when leaving the previous ramp is sufficient to reach the current one. Again, we can preprocess \(c^{\min }_{r,r'}\).
Furthermore, constraints (21) ensure that in a sequence of \(\Pi +1\) consecutive slots, at least one pickup or delivery occurs, or the final position has been ultimately reached, which establishes the upper bound on the number of charging detours that is allowed between any pair of consecutive pickups and deliveries. Finally, the variables’ domains are defined in (22) to (27).
While the model specified by (1) to (27) precisely captures problem EVRP-LFO, we can reduce symmetry and exclude dominated solutions from the solution space using the following valid inequalities.
In the model as introduced above, there are probably multiple solutions representing the same route taken by the ECV. For any pair of nonconsecutive ramps r and \(r'\) in positions k and \(k+1\) of the sequence, we can prolong the sequence by inserting a visit of a ramp in between r and \(r'\) between positions k and \(k+1\) of the sequence (unless we violate constraints (21) when doing so). By adding constraints (28) to the model, we enforce a ramp visit, which lies between the previous ramp and the next one, to imply a pickup or delivery. Hence, we allow only those ramp visits in a sequence that signal a charging detour or correspond to a pickup or a delivery.
So far, the model allows arbitrary detours. Some of them clearly cannot be beneficial and are excluded by the following restrictions. Constraints (29) state that if the tour leads from ramp r to \(r'\) with \(\delta _{r,r'}+ \delta _{r',r}\le 0\), then a job is picked up or delivered in r or the ramp \(r''\) visited before r lies in between r and \(r'\). Assume that no job is picked up or delivered in r. Due to (28), r cannot lie in between \(r''\) and \(r'\). Now, furthermore, assume that \(r''\) does not lie in between r and \(r'\). Then, our ECV travels from \(r''\) to r passing \(r'\) and then back to \(r'\). Since \(\delta _{r,r'}+ \delta _{r',r}\le 0\), we can drop the travel back and forth between r and \(r'\) without violating any constraints and without increasing the total travel distance. Constraints (30) establish the same if no pickup or delivery occurs in \(r'\) concerning the ramp visited after \(r'\).
Naturally, feeding model EVRP-LFO-MIP into a default solver is one approach to solve our EVRP-LFO problem. Due to our complexity results (see Sect. 3.3), however, it is to be expected that this approach is not able to solve large-sized problem instances. Therefore, we present a DP approach for a given job sequence in Sect. 4.2. This scheme is then applied in the heuristic decomposition approaches presented in Sect. 4.3.
4.2 Dynamic programming for given job sequences
We consider the problem of finding a routing for a given job sequence \(\sigma \), such that the former is optimal among all solutions with given job sequence \(\sigma \). Theorem 3 implies that this problem is \(\mathcal{N}\mathcal{P}\)-hard. Here, we propose a DP approach that runs in pseudo-polynomial time.
We consider a state \((r,c,v,\pi )\) for each \(r=1,\ldots ,|R|\), \(c=0,\ldots ,C\), \(v=0,\ldots ,2|J|\), and \(\pi =0,\ldots ,\Pi \) representing the ECV being in position \(p_r\) along the highway with charge level c after having conducted v pickups and deliveries, and after \(\pi \) charging detours since the last pickup or delivery. We have a transition from state \((r,c,v,\pi )\) to state \((r',c',v',\pi ')\) if
\(v'=v\), \(c^{\min }_{r,r'}\le c\), \(c'=\min \{c+\delta _{r,r'},c^{\max }_{r,r'}\}\), and \(\pi '=\pi +1\) (reflecting a charging detour to \(r'\)),
\(v'=v+1\) is odd, \(c^{\min }_{r,r'}\le c\), \(r'=r^o_j\) with \(j=\sigma ((v'+1)/2)\), \(c'=\min \{c+\delta _{r,r'},c^{\max }_{r,r'}\}-\delta ^-\cdot l^o_j\), and \(\pi '=0\) (reflecting the pickup of job j via ramp \(r'\)),
\(v'=v+1\) is even, \(c^{\min }_{r,r'}\le c\), \(r'=r^d_j\) with \(j=\sigma (v'/2)\), \(c'=\min \{c+\delta _{r,r'},c^{\max }_{r,r'}\}-\delta ^-\cdot l^d_j\), and \(\pi '=0\) (reflecting the delivery of job j via ramp \(r'\)), or
\(v'=v+2\) is odd, \(c^{\min }_{r,r'}\le c\), \(r'=r^d_j=r^o_{j'}\) with \(j=\sigma ((v'-1)/2)\) and \(j'=\sigma ((v'+1)/2)\), \(c'=\min \{c+\delta _{r,r'},c^{\max }_{r,r'}\}-\delta ^-\cdot l^{d,v}_{j,j'}\), and \(\pi '=0\) (reflecting both, the delivery of job j and the pickup of \(j'\) via ramp \(r'\) without intermediate return to the highway).
Costs \(c((r,c,v,\pi ),(r',c',v',\pi '))\) of a transition from \((r,c,v,\pi )\) to \((r',c',v',\pi ')\) reflect the total travel distance after leaving ramp r and before being ready to leave ramp \(r'\). We evaluate each state \((r,c,v,\pi )\) by \(d(r,c,v,\pi )\), which is the total travel distance for reaching \((r,c,v,\pi )\). We set \(d(r^0,c^0,0,0)=0\) and \(d(r,c,0,0)=\infty \) for each \(r\ne r^0\) or \(c\ne c^0\). For all other states, we formulate the following Bellman function:
where \(P(r,c,v,\pi )\) is the set of states that have a transition leading to \((r,c,v,\pi )\). The problem is then to determine \(\min \left\{ d(r^0,c,2|J|,\pi )\mid c=0,\ldots ,C; \pi =0,\ldots ,\Pi \right\} \), that is, the state with all jobs completed and the ECV returned to its initial position, implying minimum total travel distance.
Fig. 4
DP graph for \(\Pi =0\) and job sequence \(\langle 1,2,3,4]\) of our example
×
We have \(\mathcal {O}(|R|\cdot C\cdot |J|\cdot \Pi )\) states and \(\mathcal {O}(|R|^2\cdot C\cdot |J|\cdot \Pi )\) transitions. Checking whether a particular transition exists and, if so, determining its associated costs can be accomplished in constant time (after having predetermined each \(c^{\min }_{r,r'}\), \(c^{\max }_{r,r'}\), and \(\delta _{r,r'}\)). Hence, we end up with an overall computational effort of \(\mathcal {O}(|R|^2\cdot C\cdot |J|\cdot \Pi )\).
To reduce the number of states, we further apply the following extensions:
Dominance: A state \((r,c,v,\pi )\) dominates another state \((r,c',v,\pi ')\) if \(c\ge c', \pi \le \pi '\) and \(d(r,c,v,\pi )\le d(r,c',v,\pi ')\) holds. In both states, the ECV has reached the same position after conducting the same operations. In the dominated state, however, the current battery charge is lower (or equal), and there is less (or the same) freedom for charging. We then do not need to further consider the dominated state.
Fathoming: State \((r,c,v,\pi )\) can be fathomed if \(d(r,c,v,\pi )+\Theta (r,v)\ge UB\) holds. Here, UB denotes a valid upper bound, such as \(d(r^0,c,2|J|,\pi )\), and \(\Theta (r,v)\) reflects the total driving distance from r necessary to conduct the remaining operations \(v+1,\ldots ,2|J|\) and to eventually reach position \(r^0\) while ignoring the need to recharge.
Example (cont.) For our example introduced in Fig. 2a, the resulting DP graph for \(\Pi =0\) and given job sequence \(\langle 1,2,3,4]\) is depicted in Fig. 4. The bold path corresponds to the optimal solution depicted in Fig. 2b.
4.3 Decomposition approaches
This section introduces two alternative decomposition approaches that both derive one or multiple job sequences on a first stage and solve the remaining subproblem, i.e., the optimal sequencing of ramp visits for the given job sequence, with our DP approach of Sect. 4.2.
Construction heuristic for a single job sequence (GG) We employ the seminal approach of Gilmore and Gomory (1964) for determining a single job sequence on the first stage. Their solution procedure determines a minimum makespan schedule in polynomial time for a single vehicle executing full-truckload point-to-point deliveries without charging restrictions. To apply this approach, we only have to remove all charging information for a data instance. The resulting job sequence \(\sigma \), obtained by the approach of Gilmore and Gomory (1964), is then handed over to the second stage of our decomposition procedure, where we apply our DP approach to determine the optimal sequence of ramp visits for the given job sequence. The resulting solution is the solution of our first decomposition approach GG.
Example (cont.) For our example introduced in Fig. 2, job sequences \(\langle 1,2,3,4]\) and \(\langle 3,4,1,2]\) both lead to an optimal objective value of 2.0, if charging is a non-issue. Thus, it depends on the implementation with regard to which of these two optimal job sequences is returned by the procedure of Gilmore and Gomory (1964) and whether applying our DP approach leads to overall optimal solution (b) with a total distance of 2.0 or nonoptimal solution (d) with total distance 2.6.
Multi-start Tabu search for a multiple job sequences (TABU) Applying only a single job sequence is very fast, but we cannot rule out considerable optimality gaps (see our example). Therefore, we also introduce a second decomposition approach that applies a straightforward multi-start Tabu search scheme to derive multiple job sequences on the first stage and to evaluate a selected job sequence applying our DP procedure on stage two. Tabu search is a metaheuristic that was introduced by Glover (1989). To diversify its local search process, Tabu search applies a memory mechanism for identifying solutions already evaluated. Specifically, our TABU decomposition approach proceeds as follows. Note that the line referenced in the following description refer to the pseudo-code of Algorithm 1.
We follow a multi-start approach and generate \(\kappa \) initial job sequences first. One job sequence \(\sigma _1\) is obtained with the solution procedure of Gilmore and Gomory (1964) (line 1). With \(\sigma _1\) on hand, we generate \(\kappa -1\) additional sequences \(\sigma _i\), with \(i=2,\ldots ,\kappa \), by randomly reassigning \(\phi _1\) percent of the positions of job sequence \(\sigma _1\) (line 2). For each sequence \(\sigma _i\), with \(i=1,\ldots ,\kappa \), we determine both \(Z(\sigma )\), which represents the optimal objective value obtained by our DP, and \(Z_{NC}(\sigma )\), which equals the distance of the direct drive along the given job sequence without charging.
These solutions are handed over to the iterative part of our first stage, where the following Tabu search approach is performed in parallel for each single initial solution on a separate processor core (line 4). Starting with the initial solution, each iteration replaces the current solution with the best (non-Tabu) neighboring solution (lines 11, 17, and 18), even if the objective value of the latter is worse (best-fit approach) (lines 10 and 16). The neighborhood is defined by swapping any two job pairs in the job sequence (line 9). To avoid cycling, a Tabu list is applied that forbids performing certain moves for a minimum number \(it_{tabu}\) of iterations (also known as “Tabu tenure”) (lines 10, 16, and 19). In our Tabu list, we store the positions in the sequence that were swapped. A prohibited move is performed nonetheless if it provides a new best solution (also known as “aspiration criterion”) (lines 13 and 14). This approach is repeated until our stop criterion is met, which is reached once a maximum number \(it_{fail}\) of subsequent iterations without a new best solution have been executed (line 7). To save computational effort, we do not evaluate each neighboring solution by our DP on the second stage, but only those where \(Z_{NC}(\sigma )\) does not exceed \(\phi _2\) percent of the length of the initial sequence \(Z_{NC}(\sigma _i)\) (lines 3 and 12). If none of the neighboring solutions fulfills this condition, the non-Tabu solution with the best value of our surrogate objective \(Z_{NC}(\sigma )\) is applied as the new current solution instead (lines 11 and 18).
The solution process of TABU is steered by five basic steering parameters. Preliminary tests (that for a matter of conciseness are not reported in this paper) have shown that the following parameter setting delivers a reasonably good compromise between solution time and quality: \(\kappa =6\), \(\phi _1=10\)%, \(\phi _2=105\)%, \(it_{tabu}=5\), and \(it_{fail}=15\).
×
5 Computational performance
This section explores the performance of our solution approaches. To ensure systematic tests, we benchmark our solution procedures on generated data. The data generator that obtains our test data is elaborated on in Sect. 5.1. Then we discuss the performance results in Sect. 5.2.
5.1 Test data and setup of study
This section reports on our data generator, which is based on that applied by Schwerdfeger et al. (2021) for placing the electrified and non-electrified segments of charge-while-drive infrastructure. To test the performance of our solution approaches, we vary the number of jobs |J|, the number of ramps |R|, the percentage of highway electrification \(\overline{l}\), and the maximum number \(\Pi \) of charging detours that we allow our ECV. Given this input data, a single instance is obtained as follows.
Highway: Each instance considers a highway of length \(L=100\) km, where |R| ramps are randomly spread along the line using a uniform distribution. Recall that we consider a bidirectional highway where the ramps for both driving directions are strictly symmetric.
Electrification: According to Kühnel et al. (2018), substations, to supply the overhead wire system with energy, have to be erected every 3 km. Therefore, for each direction, we randomly spread electrified sections of 3-km length until at least \(\overline{l}\)% of the highway is equipped with electrified segments. Note that we randomly draw each starting point of an electrified segment along the highway according to a uniform distribution. If a starting point falls within an already existing electrified segment, we prolong the latter by the overlap. Further note that we do not assume strictly symmetrical electrified and non-electrified segments in both driving directions, so that the overhead wiring is placed for each direction separately.
ECV: In line with (Davis & Figliozzi, 2013), we assume a maximum battery capacity of \(C=160\) km for the truck. Thus, the consumption rate in non-electrified sections is \(\delta ^-=1\). Furthermore, Wietschel et al. (2017) report that an ECV charges energy for a driving range between 10 and 30 km when driving 2 or 3 km along an electrified section. Thus, we assume a default charging rate of \(\delta ^+=5\) per km. The origin (and destination) of the truck is randomly drawn among the available ramps along the highway, with \(r^0=r^d\). The initial charge level \(c^0\) is set to a uniformly distributed random integer between 0 and battery capacity C. To reduce the chance of infeasible solutions, we repeat the instance generation until there exists at least one ramp \(r\in R\) with \(c^{\min }_{r^0,r}\le c^0\), \(c^{\min }_{r,r^0}\le \min \{c^{\max }_{r,r^0},c^0+\delta _{r^0,r}\}\), and \(\delta _{r^0,r}+\delta _{r,r^0}>0\), so that there exists a cycle \(r^0-r-r^0\) the ECV can reach without energy shortage and that suffices to charge the battery.
Jobs: Analogously to the ECV, jobs are generated by randomly drawing their pickup and drop-off positions among the available ramps along the highway with \(r^o_j\ne r^d_j\) for each \(j\in J\). Furthermore, we have to determine the actual starting point and destination for each job \(j\in J\) beyond the highway. To compute \(l^o_j\), \(l^d_j\), and \(l^{d,o}_{j,j'}\), we determine polar coordinates \((\alpha ^2,\beta )\), where \(\alpha \) and \(\beta \) are uniformly distributed random numbers (i.e., \(\alpha \in \mathcal U(0,1)\) and \(\beta \in \mathcal U(0,360)\)). Applying the Euclidean distance, \(\alpha ^2\) reflects the distance between the ramp and the actual starting point and destination. Specifically, we set \(l^o_j\) and \(l^d_j\) to \(2\left\lceil \alpha ^2\cdot C/2\right\rceil \). Thus, each job has its actual start and destination up to 80 km beyond the highway, so that our ECV can travel the way back and forth the highway without intermediate charging. To determine travel distances \(l^{d,o}_{j,j'}\) for jobs \(j,j'\in J\), with \(r^d_j=r^o_{j'}\), we apply the Euclidean distance between the two locations \(d^e_{j,j'}\) and set \(l^{d,o}_{j,j'}=l^o_j/2+l^d_j/2+\left\lceil d^e_{j,j'}\cdot C/2\right\rceil \). To reduce the probability of infeasible solutions, we repeat instance generation until there exists at least one ramp \(r\in R\) satisfying \(c^{\max }_{r,r^o_j}\ge \delta ^-l^o_{j}\) and \(\delta _{r^o_j,r}+\delta _{r,r^o_j}>0\) or one ramp \(r'\in R\) satisfying \(c^{\max }_{r',r^d_j}\ge \delta ^-l^d_{j}\) and \(\delta _{r^d_j,r'}+\delta _{r',r^d_j}>0\).
The data generator and all our procedures have been implemented in C# (using Microsoft Visual Studio 2019). The tests have been carried out on an x64 PC with an Intel Core i7-3770 3.40-GHz CPU and 16.0 GB of RAM. As a default solver, we have applied Gurobi (version 9.0.0). If not stated otherwise, we have applied a general time limit of 1800 seconds.
Fig. 5
Impact of parameter \(\Pi \in \{1,2,3,5,10,20\}\) on the performance of our DP approach in terms of solution quality (left) and computational time (right)
×
5.2 Computational results
First, we investigate the impact of input parameter \(\Pi \), i.e., the maximum number of charging detours allowed between two subsequent jobs, on the performance of our dynamic programming approach (see Sect. 4.2). Recall that a direct drive between two subsequent jobs may not gather the ECV enough energy to successfully accomplish the drive beyond the highway on non-electrified roads. In this case, a charging detour, in the worst case consisting of multiple zigzag turns along electrified highway segments, may be inevitable to either reach feasibility or an optimal solution. However, charging detours are counterintuitive for human planners used to the advantageousness of direct drives, and parameter \(\Pi \) allows us to restrict the number of charging detours between two subsequent jobs. Beyond its impact on the plausibility and acceptability of solutions for human planners, parameter \(\Pi \) also impacts the performance: the greater the number of charging detours allowed (and thus the larger \(\Pi \)), the larger the solution space.
To explore the impact of parameter \(\Pi \), Fig. 5(left) reports on the gap (dubbed gap\(_b\)) of a specific parameter value of \(\Pi \) related to the best solution found with the largest \(\Pi =20\). Figure 5(right) indicates the resulting computational time in CPU seconds. For this test, we assume \(|J|=50\) jobs, \(|R|=20\) ramps, and a share of highway electrification of \(\overline{l}=50\%\). With these parameters, our instance generator (see Sect. 5.1) has been applied to generate ten instances. Furthermore, 100 randomly generated job sequences per instance were obtained, and the optimum solution for each of these sequences was determined with our DP approach (see Sect. 4.2). Note that for each single instance and each job sequence, a feasible solution could be obtained.
Figure 5 brings good news. The loss of solution quality for low values of \(\Pi \) is small. Even if we allow at most a single charging detour between any two subsequent jobs, the gap is well below 3.2%. For even larger values of \(\Pi \), the positive effect quickly diminishes. Thus, the price for having more plausible tours for human planners is low. Even if we allow more zigzagging, however, the solution time of our DP is not that strongly effected by increasing values of \(\Pi \). Even instances with larger values of \(\Pi \) can be solved quite rapidly.
Next, we turn to our holistic EVRP-LFO problem, which includes deriving a job sequence. Specifically, we compare off-the-shelf solver Gurobi solving EVRP-LFO-MIP (see Sect. 4.1) with our two heuristic decomposition approaches (see Sect. 4.3) denoted as GG (i.e., a single job sequence obtained using the algorithm by Gilmore and Gomory (1964) handed over to our DP) and TABU (i.e., Tabu search procedure applying our DP for evaluating neighboring job sequences). When comparing the performances of these solution approaches in Table 2, we report on the average optimality gap in percent determined by Gurobi (column “Gap”), the average gap in percent to the best solution found among all competitors (column “Gap\(_b\)”), the number of times the respective approach determined the best solution among all competitors (column “Best”), the number of solutions proven to be optimal (column “Opt”), the number of instances proven infeasible without energy shortage of the ECV (column “Inf”), the number of instances where at least one feasible solution was obtained (column “Sol”), and the average CPU seconds (column “Sec”). Note that our two gaps can only be reported if at least a single feasible solution has been found by the respective solution approach. If it failed in all ten repetitions, we mark this case by “–”. For each combination of number of jobs |J|, number of ramps |R|, share of highway electrification \(\overline{l}\), and the maximum number of allowed charging detours \(\Pi \), ten instances as described in Sect. 5.1 have been obtained, so that a total of 360 instances constitute this test bed. The instances (specifying all parameters but \(\Pi \)) can be found in an online repository at https://doi.org/10.5281/zenodo.6554110. Note that \(\overline{l}=100\) represents a full electrification, whereas \(\overline{l}=50\) means that at least 50% of the highway is equipped with overhead wires. While lower values for \(\overline{l}\) are reasonable in the real world, preliminary computational studies have indicated that Gurobi struggles even more for lower values. This is why we do not consider any of these values when comparing our algorithmic approaches. The results summarized in Table 2 suggest the following conclusions.
Table 2
Computational results comparing the performance of Gurobi solving EVRP-LFO-MIP and our two decomposition heuristics GG and TABU
|J|
|R|
\(\overline{l}\)
\(\Pi \)
EVRP-LFO-MIP
GG
TABU
Gap
Gap\(_b\)
Best
Opt
Inf
Sol
Sec
Gap\(_b\)
Best
Opt
Sol
Sec
Gap\(_b\)
Best
Opt
Sol
Sec
5
10
50
1
4.2
0.0
10
7
0
10
922.6
5.5
3
2
10
0.0
0.0
10
7
10
0.0
5
10
50
3
34.1
0.6
8
0
0
10
1800.6
4.5
3
0
10
0.0
0.0
10
0
10
0.0
5
10
50
5
37.7
0.5
7
0
0
10
1801.2
3.9
3
0
10
0.0
0.0
10
0
10
0.0
5
10
100
1
6.2
0.0
10
8
0
10
675.1
4.4
6
4
10
0.0
0.0
10
8
10
0.0
5
10
100
3
25.1
0.0
10
3
0
10
1420.1
3.6
6
0
10
0.0
0.0
10
3
10
0.0
5
10
100
5
31.1
0.0
10
0
0
10
1800.6
3.6
6
0
10
0.0
0.0
10
0
10
0.0
5
20
50
1
19.4
0.6
8
3
0
10
1495.1
4.6
5
1
10
0.0
0.0
10
3
10
0.0
5
20
50
3
52.5
17.6
0
0
0
10
1800.3
2.5
5
0
10
0.0
0.0
10
0
10
0.3
5
20
50
5
57.1
22.1
1
0
0
9
1800.5
2.3
6
0
10
0.0
0.0
10
0
10
0.4
5
20
100
1
25.2
0.0
10
4
0
10
1335.2
1.7
8
3
10
0.0
0.0
10
4
10
0.0
5
20
100
3
58.4
4.0
5
0
0
10
1800.3
1.4
8
0
10
0.0
0.0
10
0
10
0.0
5
20
100
5
60.1
1.2
3
0
0
10
1800.5
1.4
8
0
10
0.0
0.0
10
0
10
0.0
10
10
50
1
48.7
12.9
0
0
1
8
1625.6
6.5
0
0
8
0.0
0.0
9
0
9
0.1
10
10
50
3
62.4
29.7
0
0
1
5
1680.4
5.3
0
0
9
0.0
0.0
9
0
9
0.5
10
10
50
5
63.1
29.0
0
0
0
4
1800.3
4.7
0
0
9
0.0
0.0
9
0
9
0.7
10
10
100
1
47.8
3.7
1
0
0
10
1800.2
2.9
4
0
10
0.0
0.0
10
0
10
0.0
10
10
100
3
52.8
6.5
1
0
0
9
1800.3
1.7
5
0
10
0.0
0.0
10
0
10
0.0
10
10
100
5
52.4
6.0
1
0
0
6
1800.3
1.7
5
0
10
0.0
0.0
10
0
10
0.0
10
20
50
1
–
–
0
0
0
0
1800.3
3.0
2
0
8
0.0
0.0
9
0
9
0.2
10
20
50
3
72.7
42.7
0
0
0
1
1800.5
2.3
2
0
10
0.0
0.0
10
0
10
5.0
10
20
50
5
70.5
26.9
0
0
0
2
1800.6
2.3
2
0
10
0.0
0.0
10
0
10
6.2
10
20
100
1
78.1
21.4
0
0
0
1
1800.3
1.7
5
0
10
0.0
0.0
10
0
10
0.0
10
20
100
3
82.0
21.9
0
0
0
4
1800.4
1.4
5
0
10
0.0
0.0
10
0
10
0.1
10
20
100
5
81.0
35.1
1
0
0
6
1800.7
1.4
5
0
10
0.0
0.0
10
0
10
0.1
20
10
50
1
–
–
0
0
0
0
1800.2
10.0
0
0
8
0.0
0.0
8
0
8
1.2
20
10
50
3
–
–
0
0
0
0
1800.4
7.8
0
0
9
0.0
0.0
9
0
9
10.2
20
10
50
5
–
–
0
0
0
0
1800.7
7.4
0
0
9
0.0
0.0
9
0
9
15.7
20
10
100
1
–
–
0
0
0
0
1800.2
4.8
1
0
10
0.0
0.0
10
0
10
0.3
20
10
100
3
–
–
0
0
0
0
1800.4
3.8
1
0
10
0.0
0.0
10
0
10
0.5
20
10
100
5
–
–
0
0
0
0
1800.7
3.9
1
0
10
0.0
0.0
10
0
10
0.5
20
20
50
1
–
–
0
0
0
0
1800.5
7.1
0
0
9
0.0
0.0
9
0
9
6.0
20
20
50
3
–
–
0
0
0
0
1801.1
5.1
0
0
10
0.1
0.0
10
0
10
70.8
20
20
50
5
–
–
0
0
0
0
1801.8
5.3
0
0
10
0.1
0.0
10
0
10
97.0
20
20
100
1
–
–
0
0
0
0
1800.5
3.6
1
0
10
0.0
0.0
10
0
10
0.6
20
20
100
3
–
–
0
0
0
0
1800.9
2.9
1
0
10
0.0
0.0
10
0
10
1.6
20
20
100
5
–
–
0
0
0
0
1801.4
2.8
1
0
10
0.0
0.0
10
0
10
1.8
Avg
42.2
7.8
23.9
6.9
0.6
48.6
1704.8
3.8
30.0
2.8
96.9
0.0
0.0
97.5
6.9
97.5
6.1
Default solver: Obviously, the default solver Gurobi struggles with our MIP formulation. Even for the smallest instances with only \(|J|=5\) jobs, Gurobi is not able to verify optimal solutions or prove infeasibility within the given time frame of 1800 CPU seconds in all cases. For \(|J|=10\) jobs, either feasible solutions cannot be found at all, or the gaps (i.e., both the optimality gap reported by Gurobi and gap\(_b\) to the best solution) are substantial. For larger instances with \(|J|=20\) jobs, Gurobi is not able to obtain a single feasible instance.
GG: Straightforward decomposition heuristic GG performs significantly better than the standard solver. Feasible solutions are obtained for 96.9% of all instances within a negligible amount of time. Note that if we report a computational time of 0.0, we actually mean that it is below 0.05 CPU seconds. The overall gap to the best solutions found is just 3.8%. Furthermore, this gap exceeds 10% for no class of instances, and it exceeds 6% for only five classes of instances.
Tabu: The best solution quality is obtained by our TABU decomposition approach. In 97.5% of all cases, it finds a feasible solution and always delivers the best solution value. Thus, it also finds all optimal solutions verified by the default solver. Although the computational times are higher than those of GG, they are still fairly small for most instances and never exceed 100 seconds even for the most complex instances.
We conclude that our decomposition approaches seem well suited for solving EVRP-LFO. If enough time is at hand, TABU should be applied. For very large instances or if time is a pressing concern, such as in a real-time environment, GG delivers reasonably good solutions very .
6 Managerial issues
In this section, we quantify the induction effect of charge-while-drive infrastructure and benchmark our ECV exclusively charged via overhead wiring with alternative vehicle setups.
To quantify the induction effect, we apply the blueprint of the Autobahn A7, Germany’s longest highway and one of Europe’s most important north–south main lines. The A7 has a total length of 963 km (598 mi) and leads from Handewitt at the border to Denmark to Füssen, a Bavarian town near the border to Austria. In total, the A7 has 140 on-ramps and exits, which we recorded with the help of Scholl (2020) and Google Maps. For all remaining parameters, we apply our data generator defined in Sect. 5.1. Specifically, we assume \(|J|=50\) jobs and vary two parameters: the percentage of highway electrification \(\overline{l}\in \{20,30,40,50\}\) and charging efficiency \(\delta ^+ \in \{1,2,\ldots ,9\}\). Recall that both Kühnel et al. (2018) and Schwerdfeger et al. (2021) assume that electrifying about \(\overline{l}=30\)% of the highway network is a reasonable compromise in the trade-off between service level and investment costs. Furthermore, Wietschel et al. (2017) report that the status quo charging rate of current-generation overhead wiring is \(\delta ^+=5\). Thus, we vary our parameters around these default values. For each parameter setting, we generate ten instances, so that a total of 360 instances have been obtained. Each of these instances has been solved with our GG approach (see Sect. 4.3), which was able to find feasible solutions for 305 instances. The obtained travel distances of GG are related to the optimal routes determined by the exact approach of Gilmore and Gomory (1964) if charging is a nonissue. Note that the drives from start to destination ramp along the highway are constant, so that we only report on the empty drives on the highway from the previous customer’s delivery to the subsequent customer’s pickup plus the (potential) charging detours of our ECV. The results of this test (i.e., for detour parameters \(\Pi =1\) and \(\Pi =5\)) are reported in Fig. 6. The following conclusions can be drawn from these results.
Fig. 6
Induction effect of charge-while-drive infrastructure: additional driving distances of the ECV in % charged via overhead wires related to the optimal solutions if charging is a nonissue depending on the share of highway electrification \(\overline{l}\) and charging efficiency \(\delta ^+\)
×
Largest induction effect: First, we can conclude that the induction effect of charge-while-drive infrastructure can be substantial, especially if (to save investment costs) large parts of the highway remain un-electrified (small \(\overline{l}\)) and the charging efficiency of the overhead wiring is low (small \(\delta ^+\)). If both are given, up to 84% and 49% extra traffic for \(\Pi =1\) and \(\Pi =5\), respectively, threatens if full-truckload logistics providers tailor their ECV routes for the usage overhead wiring.
Impact of\(\Pi \): If we allow more zigzagging (\(\Pi =5\)), gathering enough energy to make the drives to the customers beyond the highway can be achieved within a shorter total distance. Thus, the induction effect reduces with larger \(\Pi \). However, in particular in areas close to large urban populations with numerous potential customers, additional charging traffic may concentrate on central electrified segments.
Average and smallest induction effect: If we assume the most plausible values and presuppose that \(\overline{l}=30\)% of the highway is electrified (see Kühnel et al., 2018) and that the charging efficiency is \(\delta ^+=5\) (see Wietschel et al., 2017), then we still witness an induction effect of about 5 to 6% extra traffic for charging detours. An even higher level of electrification and a more efficient charging reduce the induction effect to a minimum between 2 and 3% in our experiments.
It can be concluded that the induction effect of charge-while-drive infrastructure should not be neglected when evaluating the pros and cons of this charging alternative. When deciding on the layout of charge-while-drive infrastructure within a highway network, naturally, the most frequented parts are the first candidates for electrification. Once realized, however, these central segments of the highway will then also attract the most charging detours, so that the induction effect in these segments can be especially pronounced. Thus, when neglecting this effect, central and well-frequented highway segments are especially at risk of being burdened with even more traffic. This effect may be even more pronounced in the ramp-up phase when power obtained via overhead wiring is subsidized by public authorities to attract participants. In this case, even more extra traffic threatens, because ECVs having an additional plug-in option or a diesel engine are also nudged toward taking charging detours in order to save energy costs.
Next, we benchmark our ECV setup exclusively obtaining energy from overhead wires with alternative vehicle types. For this benchmark test, applying the same instances as before, we record not only the total travel distances, but also the total travel time (makespan) to supply all customers, including charging times, and the resulting CO\(_2\) emissions. Specifically, we compare the following five vehicle types:
Diesel truck: Today’s status quo is certainly still the conventional truck exclusively powered by a diesel-fueled combustion engine. For this vehicle setup, charging is a nonissue, so that its optimal route can be determined by the algorithm of Gilmore and Gomory (1964).
ECV-plug-in: This vehicle type exclusively charges its battery while plugged in at a stationary charging station. The route for this case is also determined by the procedure of Gilmore and Gomory (1964), but we have to add charging stops to avoid energy shortages. To specify the efficiency of stationary charging, we redefine parameter \(\delta ^+\), so that stationary charging is as efficient as the charge-while-drive technology. In this interpretation, a value of \(\delta ^+=9\), for instance, means that a range of 12 km is added per minute of charging, which equals the superfast charging times announced for the Tesla Semi (Howard, 2017). We assume that charging stations are available at any ramp, so that the ECV can charge exactly the amount required for reaching the next customer or filling the battery to capacity whenever needed.
Vehicle type ECV-overhead: denotes the case where an ECV charges its battery for driving along non-electrified road segments via only overhead wiring. Neither an additional plug-in option for charging stationary nor an additional combustion engine is available. This equals our previous vehicle setup producing the induction effect. To emulate the behavior of this vehicle, we solve each data instance with our decomposition approach GG (see Sect. 4.3) and allow \(\Pi =1\) charging detour between subsequent jobs.
ECV-overhead-diesel: In this setup, our previous ECV is additionally equipped with a conventional diesel engine, which automatically steps in if the battery charged via the overhead wires is depleted. This allows the vehicle to strictly follow the shortest route obtained by the procedure of Gilmore and Gomory (1964).
ECV-overhead-plug-in: Finally, an ECV charged via overhead wires can also have an additional plug-in option to charge while parking at a charging station. We assume that in this case, charging detours are not accepted, so that the truck follows the shortest route determined by the approach of Gilmore and Gomory (1964). The battery is charged via the overhead wiring whenever the ECV travels along an electrified segment of the given route. But if these gains of energy are not sufficient, we fall back on the stationary charging opportunities also offered in the ECV-plug-in case.
Note that for each of the five vehicle types, we assume an underlying job sequence according to the algorithm of Gilmore and Gomory (1964), which makes the resulting routes easier to compare. For each of these vehicle setups, we determine the routes for all our 360 instances elaborated above. In each case, we record the following three performance indicators. The total length of the routes of these vehicle types directly corresponds to one important performance measure denominated “distance” in Table 3. Note, however, that the total travel distance from each job’s origin to its destination is constant, and as all vehicles apply the same job sequence, those drives from the highway to jobs’ origins and from jobs’ destination back to the highway are almost equal. Thus, we only report on the remaining variable parts of the route, i.e., the empty travel distance from the previous job’s destination ramp to the subsequent job’s origin ramp plus the (potential) charging detours of an ECV. For calculating the total delivery time (dubbed “time” in Table 3) for such a travel distance, we assume a constant driving speed of 80 km/h and add the charging times for those ECVs applying the plug-in alternative based on the respective charging efficiency \(\delta ^+\). Finally, to derive the total CO\(_2\) emissions that a vehicle (permanently or part-time) powered by its diesel engine emits on its route, we presuppose an emission rate of 700 g/km of CO\(_2\) (Dresden, 2014; Kühnel et al., 2018), whereas we assume only 50 g/km of emitted CO\(_2\) for ECVs powered by 100% renewable electric energy (Dresden, 2014). Thus, our CO\(_2\) emissions reported below have to be adapted if the fraction of renewable energy is actually lower.
In Table 3, we again vary the share of highway electrification \(\overline{l}\) and charging rates \(\delta ^+\). The outcomes of the four ECV-based vehicle concepts, averaged over all ten instances obtained for each parameter setting, are related to the status quo of a conventional diesel truck, which constitutes 100% of each measure. Note that a parameter setting marked with “–” indicates that we were not able to find any feasible solution for the “ECV-overhead” case, so that a benchmarking is not possible here. The following conclusions can be drawn from the results reported in Table 3.
Table 3
Evaluation of different vehicle types in terms of driving distance, total delivery time, and CO\(_2\) emissions related to a conventional diesel truck constituting 100%
\(\overline{l}\)
\(\delta ^+\)
ECV-plug-in
ECV-overhead
ECV-overhead-diesel
ECV-overhead-plug-in
Distance
Time
CO\(_2\)
Distance
Time
CO\(_2\)
Distance
Time
CO\(_2\)
Distance
Time
CO\(_2\)
20
1
–
–
–
–
–
–
–
–
–
–
–
–
20
2
–
–
–
–
–
–
–
–
–
–
–
–
20
3
100.0
396.9
7.1
184.7
184.7
7.8
100.0
100.0
14.6
100.0
125.3
7.1
20
4
100.0
314.8
7.1
122.4
122.4
7.3
100.0
100.0
9.6
100.0
105.7
7.1
20
5
100.0
265.0
7.1
112.2
112.2
7.3
100.0
100.0
8.8
100.0
102.8
7.1
20
6
100.0
237.5
7.1
108.7
108.7
7.2
100.0
100.0
8.4
100.0
101.8
7.1
20
7
100.0
214.9
7.1
108.0
108.0
7.2
100.0
100.0
8.9
100.0
101.9
7.1
20
8
100.0
200.5
7.1
106.5
106.5
7.2
100.0
100.0
8.6
100.0
101.4
7.1
20
9
100.0
189.4
7.1
105.8
105.8
7.2
100.0
100.0
8.4
100.0
101.1
7.1
30
1
–
–
–
–
–
–
–
–
–
–
–
–
30
2
100.0
526.1
7.1
178.3
178.3
7.8
100.0
100.0
12.3
100.0
126.4
7.1
30
3
100.0
371.6
7.1
119.3
119.3
7.3
100.0
100.0
9.8
100.0
107.2
7.1
30
4
100.0
303.7
7.1
109.3
109.3
7.2
100.0
100.0
8.9
100.0
103.6
7.1
30
5
100.0
263.0
7.1
106.1
106.1
7.2
100.0
100.0
8.5
100.0
102.2
7.1
30
6
100.0
235.8
7.1
104.6
104.6
7.2
100.0
100.0
8.2
100.0
101.4
7.1
30
7
100.0
216.4
7.1
103.6
103.6
7.2
100.0
100.0
7.9
100.0
100.9
7.1
30
8
100.0
201.8
7.1
103.0
103.0
7.2
100.0
100.0
7.8
100.0
100.7
7.1
30
9
100.0
190.5
7.1
102.7
102.7
7.2
100.0
100.0
7.7
100.0
100.5
7.1
40
1
100.0
930.6
7.1
157.9
157.9
7.7
100.0
100.0
11.4
100.0
136.8
7.1
40
2
100.0
507.4
7.1
116.5
116.5
7.3
100.0
100.0
9.4
100.0
109.8
7.1
40
3
100.0
371.6
7.1
108.5
108.5
7.2
100.0
100.0
8.8
100.0
104.7
7.1
40
4
100.0
303.7
7.1
106.0
106.0
7.2
100.0
100.0
8.4
100.0
102.7
7.1
40
5
100.0
263.0
7.1
104.3
104.3
7.2
100.0
100.0
8.1
100.0
101.7
7.1
40
6
100.0
235.8
7.1
103.6
103.6
7.2
100.0
100.0
7.9
100.0
101.1
7.1
40
7
100.0
216.4
7.1
103.1
103.1
7.2
100.0
100.0
7.8
100.0
100.8
7.1
40
8
100.0
201.8
7.1
102.7
102.7
7.2
100.0
100.0
7.7
100.0
100.6
7.1
40
9
100.0
190.5
7.1
102.5
102.5
7.2
100.0
100.0
7.7
100.0
100.5
7.1
50
1
100.0
914.8
7.1
141.1
141.1
7.5
100.0
100.0
10.4
100.0
128.3
7.1
50
2
100.0
507.4
7.1
113.4
113.4
7.3
100.0
100.0
9.2
100.0
108.8
7.1
50
3
100.0
371.6
7.1
107.7
107.7
7.2
100.0
100.0
8.7
100.0
104.4
7.1
50
4
100.0
303.7
7.1
105.2
105.2
7.2
100.0
100.0
8.3
100.0
102.5
7.1
50
5
100.0
263.0
7.1
104.2
104.2
7.2
100.0
100.0
8.0
100.0
101.6
7.1
50
6
100.0
235.8
7.1
103.4
103.4
7.2
100.0
100.0
7.9
100.0
101.1
7.1
50
7
100.0
216.4
7.1
102.9
102.9
7.2
100.0
100.0
7.8
100.0
100.8
7.1
50
8
100.0
201.8
7.1
102.5
102.5
7.2
100.0
100.0
7.7
100.0
100.6
7.1
50
9
100.0
190.5
7.1
102.4
102.4
7.2
100.0
100.0
7.6
100.0
100.5
7.1
Distance: When comparing the total driving distances, we can conclude that all vehicle types except for our ECV-overhead setup can follow the optimal solution obtained by the approach of Gilmore and Gomory (1964) without charging detours. Naturally, this holds true for the diesel truck and ECV-overhead-diesel, because they have the (additional) diesel engine to realize this solution. Vehicle types ECV-plug-in and ECV-overhead-plug-in can also follow this solution, which is interrupted only by charging stops at stationary charging stations. Only our ECV-overhead vehicle has to make charging detours along electrified segments in order to gather enough energy for the drives toward customers beyond the highway. The induction effect ranges between 84% (for a low share of highway electrification and a low charging efficiency) and 2.4% (for a high electrification share and a high efficiency).
Time: Since we neglect the duration of refuel stops, the diesel truck completes all jobs the fastest (i.e., makespans of all approaches are outlined in relation to it). The same delivery time is reached by the ECV-overhead-diesel, because the additional diesel engine allows the vehicle to steadily move onward even if the battery is depleted. The makespan of vehicle type ECV-overhead-plug-in is between 0.5% and 36.4% higher. Although this vehicle recharges its battery while driving along electrified segments, additional recharging stops at charging stations are required from time to time whenever there is not sufficient energy for the drives beyond the highway. ECV-overhead has to make charging detours for gathering enough energy, which increase the makespans even more. Note that performance measures “distance” and “time” are directly equivalent and only rescaled by the fixed driving velocity, so that both percentile outcomes related to the diesel truck are identical. Finally, we have ECV-plug-in. This vehicle type is exclusively dependent on time-consuming charging stops to gather its energy, during which no further movement onward is possible. Consequently, the increase of delivery times is considerable, and ECV-plug-in is clearly outperformed by all alternatives when it comes to timely deliveries.
CO\(_{2}\): With regard to the CO\(_2\) emissions, the diesel truck is by far the worst alternative. Compared to this status quo, which again constitutes 100%, all other vehicle types produce only about one-tenth or lower emissions. The lowest level of emissions, i.e., only 7.1% of that of the diesel truck, is produced by ECV-plug-in and ECV-overhead-plug-in. Emissions are only slightly higher for ECV-overhead, which is due to the charging detours. The emissions of ECV-overhead-diesel are even higher, especially if the diesel engine has to step in quite often (i.e., in case of a low share of highway electrification and a low charging efficiency). Obviously, however, for most drives the electric energy received via the overhead wiring is sufficient, since even in the worst case, ECV-overhead-diesel only produces 14.6% of the diesel truck’s CO\(_2\) emissions.
We have to openly admit that our benchmark test lacks elementary aspects. Foremost, the differences in vehicle acquisition costs and especially infrastructure costs should not be neglected when deciding on the allocation of R &D budgets for alternative vehicle types and charging technologies. Detailed information on these two cost types are, for instance, provided by Wietschel et al. (2017). When mainly focusing on the three evaluation criteria investigated in this paper, however, we come to the following conclusions. The frequent recharging stops of plug-in ECVs considerably prolong their delivery times. An electric vehicle charging its battery via charge-while-drive technology resolves this problem, because the vehicle can steadily move onward while charging via overhead wires. To gather enough energy for the drives beyond the highway on non-electrified streets, however, a non-negligible induction effect may arise, which consumes parts of the improvement in terms of delivery times. An ECV chargeable via overhead wires, but also having the plug-in option to charge while parked, eliminates the induction effect and thus further accelerates the delivery process. On the other hand, it requires both kinds of costly charging infrastructure, overhead wires and charging stations. Thus, a hybrid ECV equipped with access to overhead wires and an additional diesel engine, which steps in once the battery is depleted, seems the best compromise. It is neither slowed down by charging stops nor charging detours and can rely on the existing network of filling stations. Nonetheless, this vehicle type still powers most drives via the charge-while-drive infrastructure in our tests, even if just parts of the highway are electrified. The diesel engine is only exceptionally applied, and the CO\(_2\) emissions still amount to only a fraction of those produced by a conventional diesel-only truck. However, pushing the overhead wire technology requires a huge public investment in the infrastructure and probably additional tax rebates to outweigh the higher acquisition costs of a hybrid truck compared to its combustion-engine-only counterpart, so it will be interesting to see whether charge-while-drive infrastructure will indeed make it into daily operations.
7 Conclusions and outlook
In this paper, we treat the impact of charge-while-drive infrastructure on routing decisions. Given a set of full-truckload point-to-point deliveries along a single highway, where some but not all road segments are equipped with overhead wires, we seek a minimum makespan route of a single ECV receiving energy via the overhead wires. While driving on electrified road segments, the vehicle can obtain additional energy to charge its battery, which has to step in on non-electrified road segments. We formulate the resulting optimization problem as a mixed-integer program, provide an analysis of computational complexity, and present two decomposition heuristics applying a dynamic programming scheme for a subproblem with given job sequence. Our computational study investigates the computational performance of our solution approaches and shows that our decomposition procedures derive reasonably good solutions quickly. Specifically, our Tabu search algorithm has determined the best solution among all competitors in each single instance and required an average running time of only 6 seconds. Off-the-shelf solver Gurobi, instead, has found a feasible solution in only 48.5% of the instances and best solutions in only 23.9%, and had to be aborted when reaching the time limit of 30 minutes in 93.1% of our instances. Furthermore, our computational study explores the induction effect of charge-while-drive infrastructure. An ECV receiving energy only via overhead wires has to make charging detours from time to time in order to obtain enough energy for reaching the next customer on the non-electrified roads beyond the highway and returning from there to the main line. Our computational results reveal that the induction effect can be considerable, especially if only a few road segments are electrified in order to save investment costs for the charge-while-drive infrastructure and the charging efficiency via the wires is low. A hybrid vehicle equipped with an additional diesel engine, which steps in when the battery is depleted, avoids the induction effect.
Since charge-while-drive infrastructure is a novel and interesting technology, there are plenty of possibilities to build up on our research. Alternative street network topologies (e.g., general graphs), other job characteristics (e.g., less-than-truckload transport jobs), and varying objective functions (e.g., related to due dates or energy consumption) are just some examples for the manifold possible extensions of our problem setting. In addition, there is a strong interdependence between the strategic decision on the electrification of the highway and operational route planning. The more highway parts are equipped with this charge-while-drive infrastructure, the fewer detours for ECVs are required (and vice versa). Thus, further exploring the trade-off between operational and strategic costs is another interesting subject of future research.
Acknowledgements
The second author has been supported by the German Science Foundation (DFG) through the grant “State Dependent Maintenance Scheduling” (BR 3873/14-1).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This appendix contains the proofs for our analysis of computational complexity provided in Sect. 3.3. We start with the proof of Theorem 1 and show that EVRP-LFO is strongly \(\mathcal{N}\mathcal{P}\)-hard, even if we have only a single electrified segment.
Theorem 1
EVRP-LFO is strongly \(\mathcal{N}\mathcal{P}\)-hard, even if \(W=1\), \(\delta ^+=\delta ^-=1\), and \(l^o_j=l^d_j=0\) for each \(j\in J\), and \(\Pi \ge 1\) is fixed.
The proof is based on a reduction from the 3-partition problem, which is well known to be strongly \(\mathcal{N}\mathcal{P}\)-complete (see Garey & Johnson, 1979), to the decision version of EVRP-LFO. The latter asks whether a feasible solution with a certain total travel distance exists. 3-Partition can be stated as follows.
3-Partition Given 3t positive integers \(a_1,\ldots ,a_{3t}\) with \(\frac{B}{4}< a_q < \frac{B}{2}\) for each \(q=1,\ldots ,3t\), does there exist a partition of set \(\{1,2,\ldots ,3t\}\) into t subsets \(A_1,\ldots ,A_t\), such that \(\sum _{q \in A_i} a_q = B\) for each \(i=1,\ldots ,t\)?
Proof
Given an instance I of 3-partition, we construct an instance \(I'\) of EVRP-LFO as follows. We have \(R=\{1,\ldots ,2+B/2\}\), \(p_1=0\), and \(p_r=B+r-2\) for each \(r=2,\ldots ,2+B/2\), and \(L=3B/2\). Furthermore, there is a single electrified segment of length B positioned directly at the start of the highway, i.e., \(W=1\), \(q_1=0\), and \(q_{2}=B\).
For each integer value \(a_q\), \(q=1,\ldots ,3t\), we introduce a job, so that \(J=\{1,\ldots ,3t\}\). The ramps associated with each job \(j=1,\ldots ,3t\) are given as \(r^o_j=2+a_j\) and \(r^d_j=2\). Finally, we set \(l^o_j=l^d_j=0\) for each \(j\in J\), \(C=2B\), \(c^0=0\), \(r^0=2\), and \(\delta ^+=\delta ^-=1\). The reduction is in pseudo-polynomial time.
We claim that there is a feasible solution to \(I'\) with total driving distance of no more than 4tB if and only if the answer to I is YES.
Constructing such a feasible solution to \(I'\) from a YES certificate of I is straightforward. We simply have to execute the jobs corresponding to each subset of I in direct succession, and before each three-set of jobs we return to ramp \(r=1\) and back to ramp \(r=2\) to recharge the battery to capacity. It is easy to see that the schedule is feasible and implies a total driving distance of 4tB.
On the other hand, a feasible solution to \(I'\) also constitutes a YES instance of I. First, we note that whenever the ECV travels between ramps 1 and 2 (positions 0 and B), it returns to ramp 2 after 2B with a fully charged battery. Second, conducting all jobs implies a total travel distance of 2tB moving back and forth between varying pickup positions and unique delivery position \(p_2=B\) (if initially starting from ramp 2 in position \(p_2=B\)). Hence, the total consumption of battery charge is 2tB and thus implies at least t charging detours to ramp 1. On the other hand, more than t charging detours to ramp 1 imply a total travel distance between ramps 1 and 2 of more than 2tB and thus an overall travel distance of more than 4tB. Third, t travels to ramp 1 suffice only if the charge level is zero each time a travel from ramp 2 to ramp 1 is started; otherwise, less than a battery charge of 2B is gained. Fourth, we can reach a charge level of zero at ramp 2 only if, after the last trip to ramp 1, exactly three jobs with total consumption of 2B, and thus the sum of pickup positions of \(3B+B\), have been processed. These subsets of jobs correspond directly to the integer subsets of I, and we have a one-to-one mapping between the two problems. \(\square \)
Next, we provide the proof for Theorem 2 and show that EVRP-LFO is also hard to approximate within arbitrarily small factors.
Theorem 2
There is no polynomial-time approximation algorithm for EVRP-LFO with a factor of less than 1.5 unless \(\mathcal {P}=\mathcal{N}\mathcal{P}\).
The proof is based on a reduction from the partition problem, which is well known to be binary NP-complete (see Garey & Johnson, 1979) and can be stated as follows.
Partition Given \(t'\) positive integers \(a'_1,\ldots ,a'_{t'}\), does there exist a partition of set \(\{1,2,\ldots ,t'\}\) into subsets \(A'_1\) and \(A'_2\), such that \(\sum _{q \in A'_1} a'_j = \sum _{q \in A'_2} a'_j=B'\)?
Proof
Given an instance I of partition, we construct an instance \(I'\) of EVRP-OW as follows. We have \(L=gB'+2B'\) with an arbitrary positive integer g and \(R=\{1,\ldots ,t'+2\}\), \(p_1=0\), \(p_2=gB'\), and \(p_r=gB'+a'_{r-2}\) for each \(r=3,\ldots ,t'+2\). Furthermore, there is a single electrified segment of length \(gB'\) positioned directly at the start of the highway, i.e., \(W=1\), \(q_1=0\), and \(q_{2}=gB'\).
For each integer value \(a'_q\), \(q=1,\ldots ,t'\), we introduce a job, so that \(J=\{1,\ldots ,t'\}\). The ramps associated with each job \(j=1,\ldots ,t'\) are given as \(r^o_j=2+j\) with position \(p_{r^o_j}=gB'+a'_j\) and \(r^d_j=2\) with position \(p_{r^d_j}=gB'\). Finally, we set \(l^o_j=l^d_j=0\) for each \(j\in J\), \(C=2gB'\), \(c^0=0\), \(r^0=2\), \(\delta ^+=1\), and \(\delta ^-=g\).
We claim that there is a schedule with total travel distance of no more than \(4gB'+4B'\) if and only if the answer to I is YES. The argument is strictly analogous to the one in the proof of Theorem 1.
Now, consider a feasible schedule with a total travel distance of more than \(4gB'+4B'\). Then, the ECV visits ramp 1 at least three times, since the total travel distance of the ECV going back and forth between pickup positions and the unique delivery position is fixed. Hence, the total travel distance is at least \(6gB'+4B'\). For sufficiently large \(g\ge 1/(2\epsilon )\), an algorithm that guarantees an approximation factor of \(1.5-\epsilon \) with \(\epsilon >0\) therefore signals the answer to I, since it yields a schedule with total travel distance of
if and only if the answer to I is YES. Thus, the algorithm cannot run in polynomial time unless \(\mathcal {P}=\mathcal{N}\mathcal{P}\). \(\square \)
Note that the proofs of Theorems 1 and 2 are similar to those provided in Boysen et al. (2018), when scheduling an ECV along a line with charge-while-park infrastructure. Finally, we prove Theorem 3 and show that solving EVRP-LFO remains a complex matter, even if we have only a single job.
Theorem 3
EVRP-LFO is \(\mathcal{N}\mathcal{P}\)-hard, even if \(|J|=1\), \(C=\infty \), and \(\delta ^+=\delta ^-=1\).
The proof is based on a reduction from the change-making problem (CMP), which is known to be \(\mathcal{N}\mathcal{P}\)-complete (see Lueker, 1975; Martello & Toth, 1990) to the decision version of EVRP-LFO, where we ask whether a feasible schedule with a certain total travel distance exists. The CMP, which aims to realize a change value with a given set of coins, is defined as follows.
CMP Given \(t''\) non-negative integers \(a''_1,\ldots ,a''_{t''}\) and an additional integer number \(B''\), are there non-negative integers \(x_1,\ldots ,x_{t''}\), such that \(\sum _{q=1}^{t''}x_qa''_q=B''\)?
Proof
Given an instance I of CMP, we construct an instance of \(I'\) of EVRP-LFO as follows. We have \(R=\{1,\ldots ,t''+1\}\), \(p_1=0\), and \(p_r=\sum _{r'=1}^{r-1} a''_{r'}\) for each \(r=2,\ldots ,t''+1\), and \(L=\sum _{q=1}^{t''} a''_{q}\). Note that ramps are numbered in increasing positions. Furthermore, there is a single electrified segment of length L spanning the whole highway, i.e., \(W=1\), \(q_1=0\), and \(q_{2}=L\).
We have a single job j, so that \(J=\{j\}\), with \(r^o_j=t''+1\), \(r^d_j=1\), \(l^o_j=L+2B''\), and \(l^d_j=0\). Finally, we set \(C=\infty \), \(c^0=0\), \(r^0=1\), and \(\delta ^+=\delta ^-=1\). The reduction is in polynomial time.
We claim that there is a feasible solution to \(I'\) with a total driving distance of no more than \(2L+2B''+l^o_j\) if and only if the answer to I is YES.
Constructing such a feasible solution to \(I'\) from a YES certificate of I can be done quite easily. The ECV travels between \(p_{r}\) and \(p_{r+1}\), \(r=1,\ldots ,t''\), \(2x_{r}+1\) times before moving to \(p_{r+2}\) for the first time (or picking up job j if \(r=t''\)). The route is to essentially sweep the line from position \(p_1=0\) to \(p_{t''+1}=L\) with \(x_{r}\) additional loops between \(p_{r}\) and \(p_{r+1}\). Since \(\sum _{q=1}^{t''}x_qa''_q=B''\), the charge level drops to zero just when returning to the highway after picking up j. The ECV then returns to ramp \(r=1\), delivers job j, and returns to the highway. The total travel distance is \(2L+2B''+l^o_j\).
On the other hand, a feasible solution to \(I'\) with a total driving distance of no more than \(2L+2B''+l^o_j\) also constitutes a YES instance of I. First, we note that the total travel distance of the ECV before leaving the highway at position L for picking up job j is \(L+2B''+\epsilon \) with \(\epsilon \ge 0\), which brings the charge level to \(L+2B''+\epsilon \). Note that the remaining total travel distance of the ECV after leaving the highway at position L is at least \(L+l^o_j\). Hence, if the total driving distance is \(2L+2B''+l^o_j\), then we have \(\epsilon =0\). Let \(x'_r\ge 1\), \(r=1,\ldots ,t''\), be the number of times the ECV travels between \(p_{r}\) and \(p_{r+1}\) before leaving the highway at L. Note that \(x'_r\) is odd for each \(r=1,\ldots ,t''\). We have
