Cómo citar / How to cite

L. C. Cubides, A. A. Londoño, y M. Granada Echeverri, Electric vehicle routing problem with backhauls considering charging station location and distribution system operation. TecnoLógicas, vol. 22, no. 44, pp.120, 2019. https://doi.org/10.22430/22565337.1186

The Vehicle Routing Problem with Backhauls (VRPB) can be defined as the problem of determining a set of vehicle routes visiting all customer vertices, which are partitioned into two subsets. The first subset contains the vertices of the linehaul customers (LCs), each requiring a given quantity of product to be delivered. The second subset contains the backhaul customers (BCs), where a given quantity of inbound product must be picked up and transported to the depot. The objective of the VRPB is to determine a set of routes visiting all the customers in order to satisfy the demand for goods. In such case, the vehicles must first serve customers with delivery requirements before those with collection requirements. This customer partition is extremely frequent in practical situations in which a permanent reorganization of the transported goods is avoided and linehaul customers have a higher priority.

Because the VRPB is a NP-hard problem [1], many heuristic processes are appropriate to solve it and, therefore, most existing literature on the VRPB is related to heuristic and metaheuristic methods with high-quality results. Two comprehensive reviews of metaheuristic techniques for the VRPB are found in [2].

Goestschalck and Jacobs-Blecha [3] developed an integer programming formulation for the VRPB by extending the Fisher and Jaikumar formulation [4] to include pickup points. They develop a heuristic solution algorithm for this problem which, in turn, is split up into three subproblems. The first two subproblems correspond to clustering decisions for delivery and pickup customers, which are independent, generalized assignment problems. The third subproblem solves the K-independent TSP composed of delivery and pickup customers, considering the preceding constraints. The latter impose a dependency relationship on all the model’s components.

The first exact method was reported by Toth and Vigo in [5]. They introduced an effective Lagrangian bound that extends the methods previously proposed for the capacitated VRP (CVRP). The resulting Branch-and-Bound algorithm is able to solve problems with up to 70 customers in total. The second exact method was proposed by Mingozzi, Giorgi, and Baldacci in [6]. They presented a set-partitioning-based approach, and the resulting mixed-integer linear programming (MIP) is solved through a complex procedure. The results show that the approach solves undirected problems with up to 70 customers. Toth and Vigo state that no exact approaches have been proposed for VRPB in the last decade [1]. In our review, we have reached the same conclusion, and new proposals for unified exact models of VRPB have not been found, since the only two existing proposals are used to derive the relaxations on which the exact approaches are based [5].

With the progress of technology and ecological concerns, electricity has become a solid option to replace fuel. Electric Vehicles (EVs) are considered an alternative to be implemented in the transportation sector because of their numerous advantages, such as the decrease of the emission of greenhouse gases, the reduction of the dependence on fossil fuels and the little noise they generate. However, EVs still have some issues associated with battery autonomy, since this technology needs to be more mature and charging stations are not yet massively installed. Thus, the problem of the integrated planning of routes and charging stations has grown in importance in the transportation industry in recent years ([7][8][9][10] [11]).

Several companies have already deployed electric delivery truck fleets. Generally, such fleets are made up of the kind of medium-duty commercial delivery trucks that are often used to deliver supplies to customers within one locality. This job is particularly well-suited for electric trucks for several reasons: daily routes are often exactly the same (which means that range needs are fixed and predictable) and the vehicles always return to a charging station at night (making recharging easier).

In the context of VRP, Conrad and Figliozzi [12] introduced the recharging vehicle routing problem (RVRP), where vehicles with limited range are allowed to recharge at customer locations mid-tour. The problem is introduced as a capacitated recharging vehicle routing problem (CRVRP) and as a capacitated recharging vehicle routing problem with time windows (CRVRP-TW). Goeke and Schneider [13] proposed the Electric Vehicle Routing Problem with Time Windows and Mixed Fleet (E-VRPTWMF) to optimize the routing of a mixed fleet of electric commercial vehicles (ECVs), which assumes energy consumption to be a linear function of the distance traveled and the recharging times at stations by time windows. Arias et al. [11] presented a probabilistic approach for the optimal charging of electric vehicles (EVs) in distribution systems, where the costs of both demand and energy losses in the system are minimized subject to a set of constraints that consider EVs’ smart charging characteristics and operational aspects of the electric network. The costs of electric delivery trucks and their conventional diesel counterparts were compared by Feng and Figliozzi [14]. They developed a model that integrates routing constraints, speed profiles, energy consumption and vehicle ownership costs. The location of charging stations is presented by Schiffer and Walther in [15], where an objective function is taken into account to minimize not only the traveled distance but also the number of vehicles needed, the number of charging stations and total costs.

Some studies analyze the actual use of EVs in commercial fleets from the standpoint of maximum necessary range autonomy of the battery to cover most trips. The data in another work [16] suggests that about 90% of the mobile days could be covered with an EV range of 60 km and nightly recharging. They show a daily mobility far below their maximum range with long parking hours at night. Consequently, there is no need for fastcharging.

Despite the benefits of EVs in the transportation sector outlined above, their main issues stem from the high cost of EVCS implementation, the nonstandardization of the battery models and their rent cost (in the case of battery swap stations), which can be more expensive than using vehicles powered by internal combustion engines [17]. Additionally, these new loads have an impact on the existing distribution network (DN), as the latter was not primarily designed to support them. Some of the problems of EVCS installation in the DN are associated with outages, load shedding, overloading wires and transformers, power loss increase and degradation in the voltage profile.

Due to the considerations described above, network operators have two options to implement. The first one addresses a load management control for EVs. The second alternative is related to the distribution planning for the normal support of the new loads [18]. This study is more suitable to contribute to the second approach, as the optimal location of charging stations and the evaluation of the DN operation in terms of the power losses constitutes a relevant tool for future investments in the DN.

Multiple works have been developed around EVs and their impact on DNs in the context of stability, chargeability, power electronics and power quality. These problems have emerged from the wrong sizing and siting of the EVCSs. In 2014, Franco et al. [19] proposed a non-linear programming model to represent hybrid EVs charging in distribution systems, with the consequent reduction of power losses. Xu and Chung [20] presented an improvement in the reliability of the DN with the incorporation of EVs and their contribution in different performance models. They proposed two load topologies: centralized and disperse. In the context of ensuring the operation of the DN (minimizing power losses), Franco et al. [21] presented a linear model for radial power distribution system planning, locating and upgrading substations and wires along the planning stages, keeping the normal system operation and complying with the limits nodes voltage, chargeability and minimum losses. Shi et al. [22] studied an integrated model for EV charging and routing taking into account the congestion of power and transportation networks.

The increase in the economic benefit for the logistics company and the distribution operator could imply a conflict around their own interests, as the former aims to serve its customers in such a way that operational costs are minimized regarding the distance traveled. Furthermore, the location of the EVCSs, electrically far from substations, can cause more power losses and technical problems in the system. Therefore, it is necessary to find a set of alternatives to maximize the profit of both companies.

This paper proposes a multi-objective problem that models the conflict between two operators: transportation and power distribution companies. The objective of this approach is to find a set of optimal solutions (Pareto front) that minimizes the power losses in the DN and the operational cost of the VRPB with a fleet exclusively composed of EVs and using the constraint method proposed by Haimes in 1971 [23]. The customers with delivery requirements should not be affected by the recharge time of the battery at charging stations because the delivery of goods is the top priority. EVs must be recharged at the end of the linehaul route or in the course of the backhaul route. Additionally, the recharge should take place after the EV has covered a predefined minimum distance in order to make the most of the initial state of charge of the battery. We have called this the Electric Vehicle Routing Problem with Backhaul and optimal operation of DN (EVRPB-DN). Said problem is formulated as a mixed-integer linear programming (MILP). The main characteristic of the proposed model is that the topological configuration of the solution is taken into account to efficiently eliminate the possibility of generating solutions composed of subtours, and the operation of the network model is evaluated by means of a linear power flow.

The rest of the paper is organized as follows. Section 2 presents the formulation of the problem along with the corresponding nomenclature for the variables and parameters used in the mathematical model; also, we describe the new mixed-integer linear programming (MILP) formulation model considering some development conditions. Section 3 contains a computational study conducted in new proposed instances for the EVRPB-DN. Finally, the conclusions are presented in Section 4.

This section outlines the mathematical model proposed for the EVRPB. Its objective is to minimize the distance traveled by the freight EVs to visit customers in a transportation network. As there is a restriction provided by the battery capacity, charging points (CPs) are located to virtually increase EVs’ travel range and be able to meet customers. The EVRPB can be defined as the following graph theoretic problem. Let G = (V,A) be a complete and directed graph, where V = {0} ∪ C_u is the vertex set and A is the arc set. The vertex 0 denotes the depot and set C_u represents the feasible customers that the EV can visit once it leaves the depot. Customers include the set of linehaul customers (LCs), backhaul customers (BCs), and the charging points (CPs), represented by { L,B,K}, respectively. Thus, in C_u = L ∪ B ∪ K$.

Each vertex j ∈ C_u is associated with a known non-negative demand of goods D_j to be delivered or collected. The depot has an unlimited fleet of identical vehicles with the same positive load capacity, denoted as Q, and the same electric capacity, denoted as E^max .

In the EVRPB-DN, the DN is defined by an electrical system represented by a single-line diagram H = (N,Ln), where N is the set of electrical nodes and Ln, the set of lines. Nodal voltages and currents through the lines are the state variables for the evaluation of the Kirchhoff laws. In the proposed model, the square of these variables is used to guarantee the linearity of the objective function (network losses).

The active power losses associated with the Joule effect due to wire heating are computed with the resistance R_mn. Likewise, it is proceeded with the reactive power losses using X_mn. The power consumed by the EVs, , is a variable that must be considered in the power balance.

One of the most widely used techniques to solve multi-objective problems is the epsilon-constraint approach, proposed by Haimes in 1971 [23]; it consists in the transformation of a multi-objective model into a mono-objective counterpart. The Pareto front is formed as follows:

First, each objective is individually optimized using the original constraints, thus obtaining the extreme points of the Pareto front.

The intermediate points in the Pareto front are obtained with discrete steps, varying the value ε between the minimum and maximum range of one of the objective functions that must be taken as a restriction . The other function it is optimized in the same way.

The proposed model corresponds to a MILP formulation, implemented in AMPL [25] and solved with GUROBI 6.5 (calculated with an optimal gap option equal to 0%), with a computation time limit of 14400 seconds in a 2.4-Ghz 4-GB RAM Intel core i5-4210 computer.

To validate the proposed mathematical model using different characteristics, a modified test system was created from the set of instances in the GJ dataset published in [3]. Such modification corresponds to the addition of the set of charging stations K.

The proposed method is implemented in the modified 16-node DN presented in Fig. 1 [26]. The nominal voltage of this DN is 23 kV. The concentrated demand for each feeder is presented in Table 1.

Fig. 1. Fig. 1. 16-node distribution test system. Source: Authors’ own work.

Table 1. Table 1. Demand of the 16-node distribution test system.

Node	P (MW)	Q (MVar)
1	0	0
2	0	0
3	0	0
4	2	1.6
5	3	0.4
6	2	-0.4
7	1.5	1.2
8	4	2.7
9	5	1.8
10	1	0.9
11	0.6	-0.4
12	4.5	-1.7
13	1	0.9
14	1	-1.1
15	1	0.9
16	2.1	-0.8

Source: Authors’ own work.

The power losses in this distribution test system equal 0.5347 MW, with a pow-er/distance ratio of φ = 10. The limits of chargeability in the network are randomly included (1.5 to 3 times the nominal current without the EVs). In the power flow, the demand drawn by the EVs is only active power, i.e., λ = 1.

The Pareto front shown in Fig. 2 presents the solution for the instance B3 using the DN of 3 feeders and 16 nodes. Four solutions (a, b, c and d) are highlighted and described in terms of routes and the value of the objective function. The blue circles represent linehaul customers; red squares, backhaul customers; and magenta rhombuses, candidate points for EVCS installation.

Fig.2. Fig.2. Optimal Pareto front for instance B3. (L= 20; B=10; k=7; Emax = 45000 m). Source: Authors’ own work.

Fig. 3 shows the routes in solution (a). Two EVCSs (big red circles) located in the DN, at nodes 5 and 12, are visited; they correspond to vertices 32 and 36 of the transportation network, respectively. In this case, the DN has its worst objective function value in terms of power losses. This is due to the fact that the EVCSs are located at nodes relatively far from the electrical substation, causing an increase of 6.7% in power losses with respect to the benchmark case.

Fig.3. Fig.3. Solution (a) of the Pareto front. Source: Authors’ own work.

The routes of points (b) and (c) are described in Figs. 4 and 5, respectively. The charging points installed in them are closer to the electrical substations, but the distance of the routes to meet the demand for merchandise is greater than in point (a). This causes the increase in the objective function of the VRPB.

Fig. 4. Fig. 4. Solution (b) of the Pareto front. Source: Authors’ own work.

Fig. 5. Fig. 5. Solution (c) of the Pareto front. Source: Authors’ own work.

Lastly, Fig. 6 presents another extreme point of the Pareto front with no EVCSs installed. Consequently, the VRPB objective function value is the largest of the four solutions, but the power losses are maintained at the same level of benchmark cases.

Fig. 6. Fig. 6. Solution (d) of the Pareto front. Source: Authors’ own work.

The Pareto front for other VRPB instances, using the same 16-node test system, can be observed in Table 2. NC are the mapped nodes of the distribution system that were selected for CP in the EVRPB solution. As shown, the proposed model works for different sizes of instances and it is efficient due to the low GAP. Furthermore, for other VRPB instances with more than 45 customers (instances identified as F, K, L, M, N in the literature), the solution for each objective can only be obtained with the ε-constraint method. In other words, the extreme points of the Pareto front are obtained, but the method fails to obtain the intermediate points.

Table 2. Table 2. Solution to the EVRPB-DN for two instances taken from [3].

This paper proposed a novel mathematical model for the Electric Vehicle Routing Problem with Backhauls and optimal operation of the Distribution Network (EVRPB-DN) to minimize the costs associated with the operation of the transportation (adopting the VRPB approach) and distribution networks. In that sense, the two objective functions of said networks are in conflict, which is solved by using a multi-objective approach to determine the set of solutions in a Pareto front, which allows decision makers to select the most appropriate point based on their needs. The results of the EVRPB-DN in this work show good quality solutions for instances with 45 customers, 8 charge points (instance E3) and the same DN of 16 nodes.

The EVRPB-DN is a highly interesting approach for logistics companies that require pickup and delivery services. Nevertheless, the operator of the distribution network must ensure a normal power supply for end users in spite of the additional loads that EVCSs represent. Such EVCSs should be installed in accordance with the expansion plans to overcome likely operational problems. The selection of one point in the Pareto front is determined by a possible negotiation between the parties (network operator and logistics company), taking into account that the extreme points in the front are much more beneficial for one or the other.

The mathematical model proposed in this article combines robust approaches from the perspectives of the power distribution system and the transportation network. Georeferenced models including driving patterns and traffic flows can be considered in future works for a more realistic focus. In that sense, a solution technique based on metaheuristics should be adopted as the complexity of the model increases.