Received: September 23, 2018
Accepted: December 17, 2018

Abstract

Logistics companies are strongly encouraged to make their operations greener through efficient solutions implementing electric vehicles (EVs). However, driving range is one of the aspects that restricts the introduction of EVs in logistics fleets, due to the limited capacity of their batteries to complete the routes. In this regard, a framework should be developed to virtually increase said battery capacity by locating EV charging stations (EVCSs) along the transportation network to the completion of their routes. On the other hand, Distribution Network Operators (DNOs) express a concern associated with the inclusion of new power demands to be satisfied (installation of EVCSs) in the Distribution Network (DN), without reducing the optimal power supply management for the end-users. Under these circumstances, this paper introduces an Electric Vehicle Routing Problem with Backhauls and an optimal operation of the Distribution Network (EVRPB-DN), which is formulated as a mixed-integer linear programming model that considers the operation of the DN in conditions of maximum power demand. Different candidate points are considered to recharge EVs’ batteries at the end of the linehaul or during backhaul routes. This problem is formulated adopting a multi-objective approach where transportation and the operation of power distribution networks are modeled. The performance and effectiveness of the proposed formulation is tested in instances of the VRPB (Vehicle Routing Problem with Backhauls) along with distribution test systems in the specialized literature. Pareto fronts are presented for each instance using the ε-constraint method.

Resumen

Las compañías logísticas están altamente motivadas en hacer que sus operaciones sean menos contaminantes a través de una solución eficiente con vehículos eléctricos (VEs). Sin embargo, el rango de conducción es uno de los aspectos limitantes en la inserción de los vehículos eléctricos en las flotas logísticas, debido a la baja capacidad proporcionada por las baterías para completar las rutas. En este sentido, es necesario desarrollar un marco de trabajo para incrementar de forma virtual la capacidad de la batería, por medio de la ubicación de estaciones de recarga a lo largo de la red de transporte, y completar las rutas satisfactoriamente. Por otro lado, los operadores de redes de distribución expresan su preocupación asociada a la inclusión de nuevas cargas eléctricas (estaciones de recarga de VEs), sin desmejorar la gestión óptima de suministro de energía a los usuarios finales. Bajo estas circunstancias, en este artículo se introduce el problema de ruteamiento de vehículos eléctricos con recogidas, formulado como un modelo de programación lineal entera mixta y considerando la operación del sistema de distribución en condiciones de máxima demanda. Se consideran diferentes puntos candidatos a estaciones de recarga de VEs para recargar la batería al final de una ruta linehaul o durante la ruta backhaul. El problema se formula con un enfoque multiobjetivo, donde se modela la operación de las redes de transporte y de distribución de energía eléctrica. El modelo propuesto es evaluado en instancias del VRPB (Vehicle Routing Problem with Backhauls) junto con sistemas de prueba de distribución de la literatura especializada. Para cada prueba, se presentan los correspondientes frentes de Pareto usando el método ε-constraint.

1. INTRODUCTION

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 re-charging 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 fast-charging.

Despite the benefits of EVs in the transportation sector outlined above, their main issues stem from the high cost of EVCS implementation, the non-standardization 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.

2. MATHEMATICAL MODEL FOR EVRPB-DN

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 𝐺 = (𝑉,𝐴) 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, p_n^v, is a variable that must be considered in the power balance.

2.1 Nomenclature

The Hass Avocados were collected during the harvest season of October 2018. Seven samples were collected, which were cut from the peduncle, three millimeters away from the base of the avocado (see Fig. 1). The avocado farm is located in the town of Tona, Santander, Colombia (7° 15° north latitude, 73° 03' west longitude) in the village Montechiquito. Such avocados were cut from the same crop and the same tree, and classified by the farmer, via visual and tactile inspection, into three different states: unripe, close-to-ripe and ripen.

The basic version of the VRPB must satisfy the following conditions:

Each vertex must be visited exactly once during a single route. That is, each vertex is grade 2.

Each route starts and ends at the depot.

Each customer must be fully served when visited.

All customers are served from a single depot.

The vehicle’s capacity should never be exceeded in the linehaul or backhaul routes, and all the vehicles have the same cargo capacity.

In each circuit, linehaul vertices precede backhaul vertices (precedence constraint).

In the EVRPB, when the electric vehi-cle completes the linehaul route, the driver can consider several alternatives: (i) starting the backhaul route, (ii) return-ing directly to the depot, or (iii) resting at the charging point and recharging the battery in slow mode until the next day. The EVRPB must, additionally, satisfy the following conditions:

Each charging point (CP) must be vis-ited by one or more routes or never be visited at all. The electrical capacity of the battery is assumed to depend on the distance traveled. The EVs are fully charged in the depot and at the charging points.

The charging points in a route are used, if necessary, in order to recharge the battery of EVs after linehaul custom-ers or during the course of the backhaul route.

In the EVRPB-DN, EVs are supposed to start working at the same time; there-fore, the charging will be carried out in the same time interval considering the following aspects:

The costs associated with DN plan-ning are ignored in the long term; only the operation of the DN is considered.

The DN will be affected by the EV re-charge during just an interval of time, according to the recharge mode [17]. In this case, a fast charging mode with a duration of 2 to 3 hours is considered.

The candidate charging points are known; the installation of all of them costs the same, which is not considered in the operation model.

The transformer at the substation is equipped with TAPS to keep the voltage at 1 pu.

The power flow to obtain the DN’s op-erating point corresponds to a one-phase equivalent circuit; therefore, the network is considered to be symmetric and bal-anced.

The EVCSs can be public; this is, they are private for the freight EVs and public when said vehicles are not recharging. The chargeability limit of the lines and transformers in the substation is 100%. The voltage regulation should be in the ±10 V range. The active power losses associated with Joule effect due to the wire heating are computed with resistance R_mn. Likewise, it is proceeded with the reactive power losses using X_mn.

The power consumed by the EVs, p_i^v, is a variable that must be considered in the power balance along with the proportions for active and reactive power λ and φ, respectively.

The operation of the DN must be ensured with the current and voltage limits I^max and U_max, respectively. The DN operation is evaluated with the costs of power losses, which are found using a linearized power flow proposed in the method described by Franco et al. [21]. This approach is also used by Pozos et al. in their expansion plan for distribution systems [24].

The following linear mathematical model describes the evaluation of the transportation and distribution networks with objective functions Ω₁ and Ω₂, respectively.

This mathematical model corresponds to a multi-objective approach, which is comprised of two objective functions, (Ω₁, Ω₂). The first objective function (1) minimizes the distance traveled, composed of two terms. The first term corresponds to the sum of the total travelling cost of the routes used to deliver and collect the goods and visit the charging points. The second term corresponds to the use of tie-arcs connecting the last customer of a linehaul route with the backhaul customer, the charging point or the depot.

The second objective function (2), quantifies the energy losses through the distribution lines during T, i.e., the period of time (in hours) the EV will be connected.

The set of constraints (3)-(7) allow to model the OVRP for linehaul routes, where (3) imposes the connectivity re-quirements. In the optimal solution of the OVRP, each route has an arborescent configuration formed by a minimum spanning tree starting from the depot, spanning all the nodes, and ending at a customer. This subproblem has been called the Linehaul Open Vehicle Routing Problem (LOVRP).

In the context of the vehicle routing problem, the necessary condition to ob-tain a minimum spanning tree is that the number of arcs be equal to the number of customer nodes. However, this constraint is necessary but not sufficient because there may be customer nodes with a greater-than-two degree, and disconnect-ed solutions can be obtained.

A spanning tree becomes a subgraph formed only by Hamiltonian paths if each customer node has a degree equal to or less than two. Therefore, another neces-sary condition is given by the set of de-gree constraints (4) and (5). The indegree constraints (4) dictate that exactly one arc directs to each customer node and, conse-quently, the outdegree constraints (5) impose that exactly one arc leaves each LC, considering two situations: (i) from a LC, a tier-arc can go to a BC or to the depot and (ii) an arc can only reach a LC from another LC or the depot. Constraint (6) is an upper limit defined by the capac-ity of the vehicle to transport a quantity of product over any linehaul-arc, while (7) limits the minimum number of vehicles used in linehaul routes. However, the addition of these degree constraints in directed graphs may not represent a spanning tree, because a disconnected graph can be obtained.

The addition of a flow balance con-straint by each customer node avoids finding disconnected solutions, since an infeasible solution is obtained when the goods leaving the depot cannot reach the LCs. Thus, the set of constraints reported in (3) guarantees network connectivity through the flow conservation constraint for each LC, so that they are fully served when visited. Similarly, constraints (14) and (25) guarantee network connectivity through the balance of the demand flow by each BC and charging point, respec-tively. Note that, in constraint (25), the demand for the CP is considered to be zero.

Similar to (3)-(7), the set of constraints (14)-(18) are established for modeling the OVRP for backhaul routes. Note that constraint (19) ensures that the number of arcs leaving the depot is equal to the number of arcs entering the same. A comparison of inequalities (19) and (7) reveals that the number of linehaul arcs leaving the depot may be different to the number of backhaul arcs arriving there. This case occurs when there are tie-arcs between a linehaul route and the depot. Besides that, parameter K_L limits the quantity of vehicles needed to serve the BCs.

The set of constraints (8)-(13) represents the limitations of EVs when they cross a route of LCs. Constraints (8) and (9) guarantee the fulfillment of the distance balance constraint on a LC route, which is necessary for the calculation of the accumulated distance at the moment of crossing every arc (i, j) of the optimal solution. These equations are written in a similar way to the balance of power flow but, in this case, the balance is with the distance; that is, at each node (j ∈ L), the distance of the activated arc s_ij is concentrated in p_j^L, similar to parameter D_j. A balance with variable p_ij ensures that the distance is accumulated, which is the same as variable l_ij. Similarly, the constraints in (20) guarantee the fulfillment of the distance balance constraint over a BC route; (26) and (27) do the same for the set of vertices that are CPs.

Constraints (10) and (11) ensure that, when an arc between LCs or a tie-arc is crossed, respectively, the maximum ca-pacity of the vehicle’s battery, in terms of distance, is not exceeded. Similarly, con-straints (22) and (28) verify the compli-ance with said electrical capacity re-striction when an arc between BCs or between a CP and a BC is crossed, re-spectively.

Equation (12) ensures that the EV leaves the depot with the battery fully charged. The return to the depot is al-ways done through a tie-arc or an arc coming out of a backhaul node. Therefore, constraint (13) ensures that the battery charge is sufficient to return to the depot via a tie-arc. Constraint (23) does this same verification when it is returned to the depot through an arc that leaves a backhaul node.

Equation (24) imposes that exactly one arc leaves each CP used, considering two situations: (i) that a tie-arc from an LC or BC can arrive at a CP and (ii) that, from a CP, an arc can only be connected to a BC. The direct return from a CP to the depot is not allowed since the objective is to make the most of the total charge of the EV to make a backhaul route, and not only to return to the depot. Note that this constraint is similar to (16), which impos-es that exactly one arc leaves each BC visited. Two situations are considered in constraint (16): (i) an arc that arrives at a BC can only come from another BC, from a tie-arc that leaves an LC or from a CP, and (ii) an arc coming from a BC can only be connected to another BC or to the depot.

In constraint (29), γ_j works as a variable that recognizes the charging stations already visited. This allows to develop a mapping between the DN nodes and the transportation network vertices.

The constraints that represent the DN operation when batteries are recharged are presented in the set of equations (30)-(45). Constraint (30) is linked with (45), allowing a mapping between the physical nodes (j ∈ K) stored in variable γ_j and the electrical nodes (i ∈ O), to be recognized as demand points for vehicles with value (Φ*E^max[W]), in the DN. Constraints (31) and (32) keep the balance of active and reactive power at each node (n ∈ N), considering the power generated at the node as well as the power that is taken and demanded from the node. Note, in both constraints, that the consumption p_n^v of the vehicles is distributed with the factor (λ), according to the quantity of active and reactive power that is needed.

Constraint (33) represents the voltage drop in the network segment between the nodes (m,n). The set of constraints (34)-(41) is the linearization, with intervals of discretization, of the expression that relates the square of the apparent power with the summation of the square of active and reactive power. This linearization can be consulted in detail in [21]. In expression (34), the variable U_nom is valid since the voltage drop lies within the range of the respective energy regulation law of the country. The relation on the right side of the equation is summation (p_mn^f)²+ (q_mn^f )².

In the set of constraints (35)-(36), the real variables (p_mn^f and q _mn^f) are represented by using auxiliary positive variables. Depending on the power flow, this variable can be positive or negative, and it will be taken by p_mn⁺ or p_mn^-, respectively, for active power, and by q_mn⁺ or q_mn^- for reactive power. In addition to this, constraints (37) and (38) guarantee that the absolute value of variables |p_mn^f | and |q_mn^f | be the summation of the discretization variables. The latter are limited by constraints (39) and (40) for active and reactive power, respectively. Parameter Δ_mn is calculated via equation (41), which relates the nominal parameters of the system with the quantity of discretization |Y|.

Finally, constraint (42) ensures that the only nodes able to supply power to the EVs are those selected in set O, and the set of constraints (43)-(46) allow the normal operation of the system regarding maximum allowable currents for each network segment, voltage regulation and substation capacity.

4. RESULTS

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. 16-node distribution test system. Source: Authors' own work

Table 1 . Demand of the 16-node distribution test system. Source: Authors' own work

The power losses in this distribution test system equal 0.5347 MW, with a power/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. Optimal Pareto front for instance B3. (L= 20; B=10; k=7; E^max=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. 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. Solution (b) of the Pareto front. Source: Authors' own work

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. 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. Solution to the EVRPB-DN for two instances taken from [3]

5. CONCLUSIONS

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.

6. FUTURE WORKS

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.

7. REFERENCES

• arrow_upward [1] P. Toth and D. Vigo, Vehicle routing: problems, methods, and applications, vol. 18. Society for Industrial and Applied Mathematics, 2014.
• arrow_upward [2] Mathematics, 2014. [2] S. Ropke and D. Pisinger, “A unified heuristic for a large class of Vehicle RoutingPproblems with Backhauls,“ Eur. J. Oper. Res., vol. 171, no. 3, pp. 750–775, 2006.
• arrow_upward [3] M. Goetschalckx and C. Jacobs-Blecha, “The vehicle routing problem with backhauls,” Eur. J. Oper. Res., vol. 42, no. 1, pp. 39–51, 1989.
• arrow_upward [4] M. L. Fisher, R. Jaikumar, and L. N. Van Wassenhove, “A multiplier adjustment method for the generalized assignment problem,” Manage. Sci., vol. 32, no. 9, pp. 1095–1103, 1986.
• arrow_upward [5] P. Toth and D. Vigo, “An exact algorithm for the vehicle routing problem with backhauls,” Transp. Sci., vol. 31, no. 4, pp. 372–385, 1997.

• arrow_upward [6] A. Mingozzi, S. Giorgi, and R. Baldacci, “An exact method for the vehicle routing problem with backhauls,” Transp. Sci., vol. 33, no. 3, pp. 315–329, 1999.
• arrow_upward [7] C. H. Dharmakeerthi, N. Mithulananthan, and T. K. Saha, “Modeling and planning of EV fast charging station in power grid,” in 2012 IEEE Power and Energy Society General Meeting, 2012, pp. 1–8.
• arrow_upward [8] Z. Liu, F. Wen, and G. Ledwich, “Optimal Planning of Electric-Vehicle Charging Stations in Distribution Systems,” IEEE Trans. Power Deliv., vol. 28, no. 1, pp. 102–110, Jan. 2013.
• arrow_upward [9] E. G. Wang, Z. Xu, F. Wen, and K. P. Wong, “Traffic-Constrained Multiobjective Planning of Electric-Vehicle Charging Stations,”IEEE Trans. Power Deliv., vol. 28, no. 4, pp. 2363–2372, Oct. 2013.
• arrow_upward [10] J. C. Paz, M. Granada-Echeverri, and J. Willmer Escobar, “The multi-depot electric vehicle location routing problem with time windows,” Int. J. Ind. Eng. Comput., vol. 9, no. 1, pp. 123–136, 2018.
• arrow_upward[11] A. Arias, M. Granada, and C. A. Castro, “Optimal probabilistic charging of electric vehicles in distribution systems,” IET Electr. Syst. Transp., vol. 7, no. 3, pp. 246–251, Sep. 2017..

• arrow_upward [12] R. G. Conrad and M. A. Figliozzi, “The recharging vehicle routing problem,” in Proceedings of the 2011 Industrial Engineering Research Conference, 2011, p. 8.
• arrow_upward[13] D. Goeke and M. Schneider, “Routing a mixed fleet of electric and conventional vehicles,” Eur. J. Oper. Res., vol. 245, no. 1, pp. 81–99, Aug. 2015.
• arrow_upward [14] W. Feng and M. Figliozzi, “An economic and technological analysis of the key factors affecting the competitiveness of electric commercial vehicles: A case study from the USA market,” Transp. Res. Part C Emerg. Technol., vol. 26, pp. 135–145, Jan. 2013.
• arrow_upward [15] M. Schiffer and G. Walther, “The electric location routing problem with time windows and partial recharging,” Eur. J. Oper. Res., vol. 260, no. 3, pp. 995–1013, Aug. 2017.
• arrow_upward [16] D. M. Pfriem and F. Gauterin, “Less range as a possible solution for the market success of electric vehicles in commercial fleets,” in 2013 World Electric Vehicle Symposium and Exhibition (EVS27), 2013, pp. 1–8.
• arrow_upward [17] J. Martínez-Lao, F. G. Montoya, M. G. Montoya, and F. Manzano-Agugliaro, “Electric vehicles in Spain: An overview of charging systems,” Renew. Sustain. Energy Rev., vol. 77, pp. 970–983, Sep. 2017.
• arrow_upward [18] A. R. AbulaWafa, A. ElaGarably, and W. A. F. Mohamed, “Impacts of uncoordinated and coordinated integration of electric vehicles on distribution systems performance,” in 2017 Nineteenth International Middle East Power Systems Conference (MEPCON), 2017, pp. 337–364.
• arrow_upward [19] J. F. Franco, M. Sanchez, M. J. Rider, and others, “Un modelo de optimización no lineal para el problema de la recarga de vehículos eléctricos híbridos en sistemas de distribución,” in The 10-Th Latin-American Congress On Electricity Generation and Transmission - CLAGTEE 2013, 2013, pp. 1–6.
• arrow_upward [20] N. Z. Xu and C. Y. Chung, “Reliability Evaluation of Distribution Systems Including Vehicle-to-Home and Vehicle-to-Grid,” IEEE Trans. Power Syst., vol. 31, no. 1, pp. 759–768, Jan. 2016.
• arrow_upward[21] J. F. Franco, M. J. Rider, M. Lavorato, and R. Romero, “Optimal Conductor Size Selection and Reconductoring in Radial Distribution Systems Using a Mixed-Integer LP Approach,” IEEE Trans. Power Syst., vol. 28, no. 1, pp. 10–20, Feb. 2013.
• arrow_upward [22] Y. Shi, T. Sun, and D. Feng, “The economic impact of electric vehicle routing and charging strategy on traffic-power integrated networks,” in IECON 2017 - 43rd Annual Conference of the IEEE Industrial Electronics Society, 2017, pp. 453–458.
• arrow_upward [23] Y. V Haimes, “On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization,” IEEE Trans. Syst. Man. Cybern., vol. SMC-1, no. 3, pp. 296–297, Jul. 1971.
• arrow_upward [24] A. T. Pozos, M. L. de Oliveira, J. F. F. Baquero, and M. J. R. Flores, “A mixed-binary linear formulation for the distribution system expansion planning problem,” in 2014 IEEE PES Transmission & Distribution Conference and Exposition - Latin America (PES T&D-LA), 2014, pp. 1–6.
• arrow_upward [25] Latin America (PES T&D-LA), 2014, pp. 1–6. [25] R. Fourer, D. M. Gay, and B. W. Kernighan, “A Modeling Language for Mathematical Programming,” Manage. Sci., vol. 36, no. 5, pp. 519–554, May 1990.
• arrow_upward [26] S. Civanlar, J. J. Grainger, H. Yin, and S. S. H. Lee, “Distribution feeder reconfiguration for loss reduction,” IEEE Trans. Power Deliv., vol. 3, no. 3, pp. 1217–1223, Jul. 1988.