Multi‐Objective Real‐Time Dispatching Problem in Electric Utilities: An Application to Emergency Service Routing

Abstract

This chapter presents a novel application of real‐time dispatching problem to electric utilities when multi‐objective is involved. It is described how the problem related to emergency services in electric utilities is considered, with an aggregated objective function developed to handle the minimization of the waiting time, the total distance traveled, the sum of all delays related to already assigned orders, and the cost of non‐assigned emergency orders. After that, actual cases have shown the effectiveness of the proposed model to be adopted in real‐world applications either as a search for optimal solution or by applying a heuristic‐based algorithm developed.

1. Introduction

Electric power distribution utilities are charged of managing customer attendance and maintenance procedures in their network [1]. The consideration of emergency scenarios makes the problem even more complex especially by assuming resource constraints (human and material) and strict regulation policies that establish targets and indices related to this context [2].

Considering that repair crews help to maintain the network under normal conditions, that is, all the customers with power supply and non‐technical problems associated with the electric network, emergency orders are normally related to equipment failures, overload conditions, and interrupted conductors [3].

From this context, the most relevant aspect to be considered refers to the waiting time associated with the emergency orders, since the level of injury or danger of death imposes immediate response from the network operation centre (NOC). The decision‐making problem involves a considerable amount of data and several aspects and criteria, all of them related to network and equipment operation procedures. This context is close to that one described by Ribeiro et al. [4]: “decision making is a process of selecting ‘sufficiently good’ alternatives or course of actions in a set of available possibilities, to attain one or several goals.”

Such a decision‐making process when referring to emergency services in electric utility generally involves not only the waiting time (also referred as response time [5]) for emergency orders but also two even important aspects: the total distance traveled and the sum of all delays related to already assigned orders. The former sounds really intuitive, because the minimization of the total distance traveled by all crews improves their productivity by aggregating more time in their workday to complete the assigned orders. The latter aspect is that one more specific: the consideration of multitasked maintenance crews. They are always charged of pre‐established routes that include orders known a priori when a set or emergency orders come up. This criterion of minimizing the sum of all delays represents the desired trade‐off between the planning and actual scenarios, in such a way that they could be as similar as possible [6].

This chapter proposes a multi‐objective approach based on a mathematical model to handle emergency orders under real‐time conditions. It comprises four criteria related to this problem: the minimization of the waiting time for emergency services, the total distance traveled, the sum of all delays related to already assigned orders, and the cost of non‐assigned emergency orders.

2. Problem description

The electric NOC is charged of attending emergency calls for 24 hours a day and 7 days a week, all answered by maintenance teams. Since they involve critical situations such as lack of supply or even the possibility of injury to people, they are considered critical tasks that require immediate attention. In this context, a real‐time system is desirable and appropriate to support engineers to find the available teams that can meet these pending emergency work order (EWO) as soon as possible, thus defining what is called as the Emergency Dispatching and Routing Problem (EDRP).

Considering the urgency of these orders, the EDRP's main function is to reduce the waiting time, defined as the sum of travel time and execution times of service orders scheduled to be executed before the pending EWOs. The definition of EDRP assumed in this work comprises the problem of decision to allocate pending EWOs to maintenance crews available, adopting as a criterion of choice to minimize the waiting time. The problem becomes even more challenging from the consideration that these crews are multitasking: they serve not only the EWOS but also commercial services (customer demand orders). This characteristic gives the optimization problem a unique importance due to the associated complexity.

Such a conclusion comes from the fact that the EDRP corresponds to a dynamic vehicle routing problem [7, 8], which can be clearly distinguish from the static vehicle routing problem [9, 10] by assuming that at least some inputs to the problem can change during the execution of the previously defined routes. Therefore, there is a concurrence between the resolution of the EDRP and the dynamic generation of new EWOs [7] and the EDRP involves not only a dispatching decision (to which available crew a certain EWO will be assigned) but also a further routing decision: in which position of the existing routing a certain EWO should be inserted.

Some particular discussions about attributes related to dynamic vehicle routing problem addressed in this work will be introduced next.

2.1. Dynamic vehicle routing attributes

Particularly in the EDRP defined in this work, over the several aspects that may point the differences between the static and the dynamic fashion of vehicle routing problem described by Psaraftis [7], four of them must be highly considered:

1. Time dimension: It is important to keep track of geographic location of all vehicles, since that locations will be used to reach new EWO when they are made known, which means that it is also need to keep track of how vehicle schedules evolve over the time;

2. Near‐term decisions: In the dynamic context of the vehicle routing problem included in the EDRP, there is a trade‐off between take decisions based on near‐term information or wait more time to take a greater defined landscape in order to promote better choices; even assuming that future information may change and incurring on risk of taking “a restrict” policy, near‐term events are assumed more relevant in the formulation of the EDRP;

3. Faster computational times: The dynamic and also the emergency situation involved in the EDRP both require faster calculations for obtaining candidate solutions when comparing to the static context, since in this last one may be acceptable to wait for dozens of minutes or even hours; this requirement is that one that entails the real‐time behavior involved in this work;

4. Indefinite deferment mechanisms: A certain level of deferment is desired since it makes a role of counterbalancing the near‐term vision assumed; however, one has to describe some mechanisms to avoid that some particular EWOs, due to their unfavorable geographical characteristics when compared to other ones, may be postponed indefinitely.

From these specific characteristics emerge a combinatorial problem to construct several routes in order to meet customer demand in the context of an electric power distribution utility in Brazil, specifically with concern to the occurrence of EWO and thus describing a dynamic problem.

The main challenge when attending emergency services with multitasking maintenance crews refers to the trade‐off between static and dynamic scenarios. These crews may systematically change their a priori routes with commercial orders upon the occurrence of EWOs, remembering that the latter orders have precedence over the first ones.

From this consideration, two main course of action may be assumed in order to route pending EWOs: (1) the complete restructuring of existing routes and (2) only the insertion of EWOs in any position of existing routes. The first case relates to route all orders simultaneously, whether commercial or emergency, forgetting existing routes. The second case involves restricting the changes in the a priori route, allowing only the inclusion of EWOs in any position. The problem addressed in this paper considers these two cases.

The main issue involved in EDRP refers to the presence of several conflicting optimization criteria. The main one is the waiting time to perform the EWOs, representing a tentative to mitigate the risks to the security of the electricity distribution network.

Another important criterion, this with an economic impact, refers to reducing the cost of the routes as the time needed to complete them, involving both commercial orders and EWOS. One can note that, in this case, a conflict regarding the precedence of EWOS and total cost: the higher is the precedence of EWOS, the higher will be the cost of the routes.

The third and last aspect to be considered refers to minimizing the sum of all delays related to the previously assigned services, in order to maintain the desired trade‐off between the planning and actual scenarios.

All these questions will be discussed in details in the next section and further explained with practical examples for actual instances. The following section presents a simple example of EDRP instance.

2.2. A simple dispatching solution

Herein, there is an aspect that must be mentioned: all the repair crews have workday that may be different, thus affecting their availability to serve emergency services. An example of a possible EWO dispatching is given in Figure 1, which describes just one EWO (E0) and three crews available: crew 1, namely C1, 21 min far from E0; crew 2, namely C2, 60 min far from E0; and crew 3, namely C3, 30 min far from E0. With this information, one must decide that E0 must be dispatched to C1 since it has the smaller travel time, which in this case also corresponds to the smaller response time.

Figure 1.

Example of an EWO dispatching.

It is worth noting that the geographical position of each crew is permanently changing by assuming the dynamic behavior involved, always conducting to the consideration of a multi‐depot vehicle routing. Another aspect is that each crew has its proper working hours. As depicted in Figure 1, taking this assumption and considering that C1 has 9:00 am as its initial work time, C2 has 7:00 am as its initial work time, and C3 has 8:00 am as its initial work time, the time when the EWO comes up plays an important and definitive role on deciding which vehicle must be assigned to. If this time is 9:30 am, the previous analysis is appropriated, but if we consider 8:00 am, the following approaching time for each vehicle must be calculated: Vehicle 1 only will reach the EWO at 9:21 am; vehicle 2 will reach the EWO at 9:00 am; vehicle 3 will reach the EWO at 8:30 am. These results suggest that vehicle 3 must be dispatched to execute E0.

The next section is devoted to present the mathematical programming formulation developed to the EDRP.

3. Mathematical programming formulation for EDRP

The EDRP description presented in the previous section corresponds to a multi‐objective and multi‐attribute vehicle routing problem [11], with the most important ones stated as follow, according to the taxonomy of Eksioglu et al. [10]:

1. Real‐time solution method (1.2.4);

2. On‐site service—waiting times (2.5.2);

3. Customers on node (3.2.1);

4. Geographical location of customers—both urban and rural zones (3.3.3);

5. Multiple origins (3.4.2);

6. Time window restrictions on vehicles (3.6.4);

7. Exactly n vehicles—equivalent to TSP (3.7.1);

8. Uncapacitated vehicles (3.8.2);

9. Deterministic travel time (3.10.1);

10. Travel time dependent transportation cost (3.11.1);

11. Partially dynamic (4.1.2).

With all these attributes assumed, a mathematical programming formulation may be stated in order to define how to treat these characteristics and also to allow a further resolution by exact methods, when possible.

The following subsections are devoted to describe the formulation developed: First, the set of parameters and variables are presented, followed by the objective functions definition; finally, the constraints are defined in blocks in such a way to give a better understanding of how the previously defined attributes are related to.

3.1. Parameters and variables

All the conditions and information necessary to have a solution for an EDRP instance are presented in three tables: Tables 1–3. The first one is devoted to describe general parameters, the second defines crew‐related parameters, and the last one reports the service order‐related parameters. In all tables, the first column (“PARAM”) includes the parameter identification and the second one presents the corresponding description (“DESCRIPTION”).

PARAM	Description
Dij	Distance in hours between node i and node j
F	The set of all objective functions
Wi	Factor that weighs the objective function i, with ${\displaystyle \sum _{i\in F}{W}_i}=1$

Table 1.

General parameters.

PARAM	Description
CC	Cost per hour of any crew (in $/h)
PREDi	The set of predecessors nodes of node i in the initial route: $i\in V_s\cup V_c\cup V_e$
R	The set of routes
RTi	The initial route of node i
SEQi	The sequence number of node i, in the corresponding route
SUCi	The set of successors nodes of node i in the initial route: $i\in V_s\cup V_c\cup V_e$
T0r	The initial time of crew r
Tr	Time that the r crew should finalize its route
U	Maximum acceptable time to any crew finish its route
Vs	The set of starting nodes, corresponding to crew positions
Vt	The set of terminal nodes, corresponding to artificial nodes created to make easier the finishing route time calculations

Table 2.

Crew‐related parameters.

PARAM	Description
EC	Cost related to each non‐assigned emergency order (in $)
OCi	Cost of the service order i (in $/h)
PREDi	The set of all predecessor nodes of node i
STi	Service time of order i (in hours)
SUCi	The set of all successor nodes of node i
TAi	Expected arrival time for service order i on the initial route
TEi	Time when emergency order i was generated
TSi	Service time of order i, $i\in V\backslash V_s\backslash V_t$
V	The set of all programmed and emergency orders, including starting and terminal nodes: $V=V_c\cup V_e\cup V_s\cup V_t$
Va	The set of all assigned service orders: $V_a=\{i\in V_c\cup V_e|R{T}_i\ne -1\}$
Vb	The set of orders which are in the first position on the initial routes: $V_b=\{i\in V_{ce}|SE{Q}_i=1\}$
Vc	The set of programmed orders
Vce	$V_{ce}=V_c\cup V_e$
Ve	The set of emergency orders
Ven	The set of emergency orders which are unassigned to route crews: $V_{en}=\{i\in V_e|R{T}_i=-1\}$
Vens	$V_{ens}=V_{en}\cup V_s$
Vr	The set of all emergency orders that are already routed: $V_r=\{i\in V_e|R{T}_i=1\}$
Vsce	$V_{sce}=V_s\cup V_c\cup V_e$

Table 3.

Service order‐related parameters.

After parameter decryption, the set of variables must be introduced. Since this formulation refers to a mixed integer programming model [12], it includes both discrete and continuous variables. In addition, the set of discrete variables have two distinct subsets: the first comprising nonnegative integer variables and the latter referring to binary variables.

It is worth noting that the set of decision variables includes four main attributes: precedence between service orders, assignment of orders to routes, and finally, time information of when repair crews arrive at service orders or when these crews complete their workdays. Table 4 presents all the variable sets defined to the proposed formulation.

SET	Description
xijr	Binary variable indicating if the node i is preceding of node j on the route r: xijr = 1 if it is true and xijr = 0 otherwise
yir	Binary variable indicating if node i is included on the route r:yir = 1 if it is true and yir = 0 otherwise
si	Binary variable denoting the assignment of emergency order i to any available crew: si = 1 if it is true and si = 0 otherwise
ti	Real variable indicating the arrival time on node i
ui	Integer variable indicating the relative position of the node i

Table 4.

Variable sets defined for the proposed formulation.

3.2. Objective functions

Following the preceding definition on Section 2, about the criteria involved in the multi‐objective and real‐time approach for service‐order dispatching and routing, four objective functions are considered in this work: an objective function, Eq. (1), to denote the waiting time in hours involved in the solution proposed; an objective function, Eq. (2), to denote the total route cost, related to the sum of all travel times between any two nodes weighted by the hourly cost of the crews; an objective function, Eq. (3), to denote the number of hours related to the delay caused by the new assignment when compared to the initial routes; and finally, an objective function, Eq. (4), to denote the cost of non‐assigned emergency orders.

It is worth noting that in all criteria, the unit remains the same: the number of financial units involved per hour ($/h).

$Min{\displaystyle \sum _{i\in V_e}O{C}_i{t}_i}$E1

$MinCC.{\displaystyle \sum _{i\in V_{sce}}{\displaystyle \sum _{j\in V_{ce}}{\displaystyle \sum _{r\in R}{D}_{ij}}.\text{}{x}_{ijr}}}$E2

$Min{\displaystyle \sum _{i\in V_a}O{C}_i}.max\left\{0;t_i-T{A}_i\right\}$E3

$Min{\displaystyle \sum _{i\in V_e}O{C}_i.(1-s_i)}$E4

Since we are focus on a multi‐objective approach, all the four criteria must be considered together in the optimization process. In this work, it is assumed an a priori approach to address the multi‐objective problem [13], from the previous definition of all W_i factors before conducting the optimization process to dispatch and route. Eq. (5) presents the four criteria of Eqs. (1)–(4) weighted by corresponding W_i factors.

$\begin{array}{l}Min{W}_1.{\displaystyle \sum _{i\in V_e}O{C}_i{t}_i}+W_2.CC.{\displaystyle \sum _{i\in V_{sce}}{\displaystyle \sum _{j\in V_{ce}}{\displaystyle \sum _{r\in R}{D}_{ij}}.\text{}{x}_{ijr}}}+\\ +W_3.{\displaystyle \sum _{i\in V_a}O{C}_i}.max\left\{0;t_i-T{A}_i\right\}+W_4.{\displaystyle \sum _{i\in V_e}O{C}_i.(1-s_i)}\end{array}$E5

3.3. Basic constraints

After introducing all criteria put together with an unique objective function, there is a set of equations to define the constraints to be assumed in the formulation proposed. The first set of constraints are called just as “basic constraints,” since they are related to the assignment of already routed orders or referring conditions as precedence and non‐anomalous route construction: for instance, overlapping routes, service orders included in more than one route, etc.

$y_{ir}=1,\forall i\in V_{sce}\backslash V_{en},\forall r\in R,r=R{T}_i$E6

${\displaystyle \sum _{r\in R}{y}_{ir}\le 1,}\forall i\in V$E7

${\displaystyle \sum _{i\in V_s}{y}_{ir}=1,}\forall r\in R$E8

${\displaystyle \sum _{i\in V_t}{y}_{ir}=1,}\forall r\in R$E9

${\displaystyle \sum _{r\in R}{y}_{ir}=1-s_i,}\forall i\in V_{en}$E10

${\displaystyle \sum _{j\in V\backslash V_s,i\ne j}{\displaystyle \sum _{r\in R}{x}_{ijr}=1,}}\forall i\in V_s$E11

${\displaystyle \sum _{j\in V\backslash V_t,i\ne j}{\displaystyle \sum _{r\in R}{x}_{jir}=1,}}\forall i\in V_t$E12

${\displaystyle \sum _{j\in V_s}{\displaystyle \sum _{r\in R}{x}_{ijr}=1,}}\forall i\in V_t$E13

${\displaystyle \sum _{j\in V_{en}\cup V_t\cup SU{C}_i}{\displaystyle \sum _{r\in R}{x}_{ijr}=1,}}\forall i\in V_a$E14

${\displaystyle \sum _{j\in V_{ens}\cup PRE{D}_i}{\displaystyle \sum _{r\in R}{x}_{jir}=1,}}\forall i\in V_a$E15

${\displaystyle \sum _{j\in V_{en}\cup V_t\cup V_a,i\ne j}{\displaystyle \sum _{r\in R}{x}_{ijr}\le 1,}}\forall i\in V_{en}$E16

${\displaystyle \sum _{j\in V_{ens}\cup V_a,i\ne j}{\displaystyle \sum _{r\in R}{x}_{jir}\le 1,}}\forall i\in V_{en}$E17

${\displaystyle \sum _{j\in V,i\ne j}{x}_{ijr}=y_{ir},}\forall i\in V,\forall r\in R$E18

${\displaystyle \sum _{j\in V,i\ne j}{x}_{jir}=y_{ir},}\forall i\in V,\forall r\in R$E19

${\displaystyle \sum _{j\in V_s}{x}_{ijr}=y_{ir},}\forall i\in V_t,\forall r\in R$E20

$x_{iir}=0,\forall i\in V,\forall r\in R$E21

The assignment of all orders, with exception of the unassigned emergency ones (V_en set), is guaranteed by Eq. (6). Eq. (7) ensures that any order should be assigned to no more than one route and Eqs. (8) and (9) define the designation of all starting nodes and of all terminal nodes, respectively. Eq. (10) corresponds to the coupling constraints for variable sets y and s, which means that, for all unassigned emergency nodes, the value of s corresponding variable is equal to 1 if it remains unassigned, requiring y corresponding variable to take the value 0.

In Eq. (11), it is guaranteed that each starting node should have exactly one successor node in the set V\V_s, whereas the Eq. (12) ensures that the terminal nodes must have exactly one predecessor node belonging to the set V\V_t; Eq. (13) states that each terminal node should have exactly one starting node as its successor node. In this sense, with regarding to each assigned service order belonging to the set V_a, Eqs. (14) and (15) ensure exactly one successor and one predecessor node, respectively. With regarding to unassigned emergency nodes, Eqs. (16) and (17) ensure no more than one successor node and no more than one predecessor node, respectively.

Eqs. (18)–(20) correspond to the coupling constraints for variable sets x and y. If a certain node i is assigned to a route r (y_ir = 1), this node should have one successor and one predecessor node in this route, Eqs. (18) and (19), respectively. Eq. (20) requires that each terminal node should be predecessor node of exactly one starting one.

Finally, Eq. (21) forbids connections of a node to itself.

3.4. Subtour elimination constraints

In order to have crew routes without subtours, Miller–Tucker–Zemlin (MTZ) constraints [14, 15] are defined on Eqs. (22)–(25). These constraints arise from definition of extra integer variables for each node, in such a way to have defined the relative order of each one of these nodes in their corresponding routes. First, all the starting nodes (V_s set) are defined as the beginning of each route, Eq. (22), followed by definition of the remaining ones (V\V_s set) to be restricted on the range of [2, |V|], Eqs. (23) and (24). Eq. (25) corresponds to the coupling constraints for variable sets x and u, referring that if node j is successor of node i on the route r by defining x_ijr = 1, the following inequality holds: $u_i\le u_j-1.$

The last set of constraints, Eq. (26), refers to the assumption of the initial routes from the definition of parameter SEQ: if node j follows node i on initial routes, u_i < u_j.

$u_i=1,\forall i\in V_s$E22

$u_i\ge 2,\forall i\in V\backslash V_s$E23

$u_i\le \left|V\right|,\forall i\in V\backslash V_s$E24

$u_i-u_j+\left|V\right|x_{ijr}\le \left|V\right|-1,\forall i,j\in V\backslash V_s,\forall r\in R$E25

$u_i<u_j,\forall i,j\in V_a,SE{Q}_i\le SE{Q}_j$E26

3.5. Arrival time constraints

Computing the waiting time for all nodes is only possible by defining the values for the variable set t, described in Table 4 as the arrival time.

Since each crew has a starting node in the first position of its route, Eq. (27) defines that all nodes in the set V_s their arrival time is zero. The next set of constraints, Eq. (28), establishes properly how the arrival time is calculated by considering three main factors:

(1) the arrival time of the predecessor node i (t_i); (2) the service time at node i (TS_i); and (3) the traveled distance between the predecessor node i and the current node j (D_ij). By adopting the factor $-U$, one attempts to switch off the constraint whenever $x_{ijr}=0$, since $t_i+T{S}_i+D_{ij}<<U$ and allowing $t_j=0$. For $x_{ijr}=1$, the following inequality holds: $t_j\ge t_i+T{S}_i+D_{ij}$.

$t_i=0,\forall i\in V_s$E27

$t_j\ge t_i+T{S}_i+D_{ij}-U(1-x_{ijr}),\forall i\in V\backslash V_t,\forall j\in V\backslash V_s,\forall r\in R,i\ne j$E28

3.6. Domain constraints

Eqs. (29)–(33) present the domain of variable sets x, y, s, t, and u. The linear programming model is defined by assuming the continuous variables t, after aggregating the discrete ones: x, y, s, and u. Only this last set is not binary, and it is worth noting that the set s is only defined for emergency nodes: V_e.

$x_{ijr}\in \{0,1\},\forall i,j\in V,\forall r\in R$E29

$y_{ir}\in \{0,1\},\forall i\in V,\forall r\in R$E30

$s_i\in \{0,1\},\forall i\in V_e$E31

$t_i\in R^{+},\forall i\in V$E32

$u_i\in Z^{+},\forall i\in V$E33

4. Proposed algorithm

The composition of the objective function presented in the previous section was evaluated by testing the model performed with the IBM ILOG CPLEX 12.5 optimization environment. Even for small instances, read up some units outstanding emergency orders and a few dozen commercial orders in the schedule of teams, it was possible to obtain the optimal solution with adaptations in the model developed in practice to accurately resolution impediment for various reasons: (i) the dispatch issue emergency orders has combinatorial nature; (ii) the real‐time response requirements is very important; and (iii) variability in the characteristics of dispatch problem instances is very significant.

Given this perspective, a heuristic approach to the EDRP is developed carefully observing the mathematical model described in Section 3. The heuristic algorithm corresponds to a search in variable neighborhood with multiple restarts, allowing versatility adjustments and easy adaptation to different dispatch scenarios and also relative efficiency as the numeric result.

The compromise was found with the algorithm which refers to the need for real‐time response. This requirement may be relaxed in the case of a very large number of instances, such as in situations of extreme weather events that cause a very unusual number of EWOs. In these situations, what you want is to meet emergency orders as soon as possible, including completely passing over the planned orders. On the other hand, in more commonplace situations whether meet emergency orders as soon as possible but at the same time, minimizing the delay in the a priori routing planning with commercial orders.

The next sections describe both the decision support system architecture developed and the proposed heuristic algorithm to the EDRP described in Section 3.

4.1. Decision support system architecture

In order to deal with this dichotomy, the concept of dispatch scenarios was developed, exploiting basically the balance or imbalance between supply (availably of working hours) and demand (service time of pending emergency orders). In addition, the EDRP considered in this work should be able to handle real‐time automatic dispatch of EWOs.

Assuming this entire context, a computational approach based on decision support systems [16] is proposed, since these systems provide concepts, definitions, and techniques that help decision makers in the decision process, especially by analyzing and furnishing alternatives of mathematical models in a reasonable time. The key idea involved is the proper use of techniques inspired by the mathematical model presented in Section 3, combined with efficient heuristics to furnish reasonable solutions bearing in mind the real‐time requirements previously assumed [17]. Following these principles, it is proposed an architecture for the system as shown in Figure 2.

In order to provide real‐time capabilities in the proposed computational system, the great representation of multi‐core processors on most computers available suggests that this character may be exploited in parallelizable architectures. The first premise of the proposal is to divide the geographical of the electric utility into smaller areas that do not represent interconnection resources over a day, as if these areas were isolated from the point of view of the planning of calls in a day. For each one of these areas, there is a thread involving all the components of the architecture of Figure 2.

Another important constructive feature of the proposed architecture is to be event‐driven [17], due to the component “Checking event queue.” This queue contains all the operations related to the EDRP, whether logs or even actions to be taken: dispatch a given crew to attend a certain pending EWO.

Figure 2.

Proposed decision support system architecture.

Which is the best scenario? This answer is given by the component “Define a scenario,” which evaluates how is the relationship between supply and demand, in such a way that supply refers to the remaining working time hours and demand refers to the service time of pending EWO. Whenever the required service time is much greater than the number of working time hours available, it is possible one is facing a situation of extreme climate event, thus requiring at least disregard the commercial demands or even add more working time hours for triggering extra repair crews. When low demand occurs, that is, the number of crews is greater than the number of pending EWO; the assignment problem emerges [18], and an exact solution for this problem is suitable as a lower bound to the original problem described in Section 3.

The next step after defining a scenario to the EDRP refers to execute the most appropriated algorithm to solve it, component “Apply algorithm.” Afterwards, the component “Define crew scheduling” carries out final checking, since there may have been changes in the crews as non‐communication or temporary unavailability. A report of the whole process is in charged of the component “Warning and alerts.”

4.2. Proposed heuristic algorithm

The main reason for employing a “Variable Neighborhood Search”‐based algorithm [19] for the EDRP refers to the possibilities of including adaptation in the optimization process based on the instance, even by applying several types of neighborhoods or even by applying neighborhood reduction strategies when the search space appears to be huge. These possibilities of adaptation are especially important when facing with real‐time system approaches such as that proposed in this work.

Figure 3 presents the proposed algorithm developed to EDRP. There are three parameters: instance, with all the data entered in the mathematical model of Section 4.1.2, the number of permitted iterations (N), and the number of neighborhoods (T). The algorithm begins with a constructive procedure in step 1, which systematically creates a solution for the EDRP by checking the gain promoted by each insertion of a pending EWO on the already constructed routes, taking into observation the aggregated objective function of Eq. (5). Since it is a greedy procedure, the best choice is assumed and the next pending EWO is evaluated until all of them are designated.

Figure 3.

Proposed “Variable Neighborhood Search”‐based algorithm.

The loop structure between steps 3 and 22 is relates to the algorithm itself that has a number of repetitions given by the parameter N. Steps 4–19 are equal to the search itself, where the variable k is the neighborhood considered: k = 1 is equivalent to insertion neighborhood, and k = 2 corresponds to the 2‐opt neighborhood. Step 6 corresponds to a disturbance procedure applied to the current solution (sol), considering neighborhood defined by parameter k. This disturbance corresponds to changing the assignment of a given EWO or even changing the relative position in the corresponding route. From there, the repetition structure of the steps 8–14 is responsible for generating new neighbor solutions as they represent gains in the objective function (steps 10 and 11), which means lower values since the EDRP is defined for a minimization criterion—Eq. (5).

If the loop structure of steps 8–14 is over, it is checked if the solution generated by the search is better than the incumbent solution (sol), step 15. If so, one assumes the resulting solution search (newsol) as new incumbent and backup solution for the initial neighborhood (step 17). Otherwise, proceed to the next neighborhood (step 19) in an attempt to seek a minimum alternative and different location from the previous neighborhood.

The count of search iterations is performed in step 20, followed by the reset approach that is one of the advantages of this algorithm (steps 21 and 22). This process is performed by comparing the difference between the incumbent solution and the resulting solution search, along with the number of iterations. The actual reset (step 22) occurs only when the number of iterations indicates that the search has reached 50% of the effort and the search does not promote further improvement.

5. Computational results and analysis

Aiming to evaluate the developed algorithm presented in the previous section and also the associated computer system, two case studies were developed focusing on the variation in the cost of EWO, and the consequent impact in the dispatch defined.

The following are each of these studies and the exploited details:

• Case study 1 refers to the ratio of cost of emergency orders and travel time;

• Case Study 2 relates to the influence of the cost of an EWO on the sequence of orders existing commercial.

In addition, a set of instances of EDRP was used in order to evaluate the performance of the proposed methodology when observing the computation time required, that is, if the real‐time requirement is guaranteed. In all cases, the time required was less than a minute, and most were <10 s. The processor used is an Intel Core i5‐3230M, 2.6 GHz, running Windows 7 operating system. Table 5 summarizes these results.

Instance	Time (s)	No. of crews	No. of commercial orders	No. of emergency orders
c16	0.213	1	7	1
c24_1248	0.288	1	7	6
e1	0.370	5	30	6
e4	0.455	9	30	6
e2	0.471	6	30	6
a1_3108	0.669	4	26	9
a1_2229	0.703	4	26	11
a1_2130	0.805	4	26	11
a1_1210	1.090	4	26	12
a1_2027	1.876	4	26	15
j2	8.643	8	0	49

Table 5.

General results for the proposed algorithm.

5.1. Case study 1

This study explored the first and fundamental characteristic of a review of a dispatch solution: the impact of the cost of EWO on travel time associated with.

Table 6 presents 11 test cases that were developed with one team and two EWO. One can see that the O4863657 cost has not changed, just O4863663 has changed from $100.00/h in case 11 to $2.00/h in the case 0. Three last columns of Table 6 represent the components of the objective function that is impacted in this case study: expected cost of emergencies, travel costs, and the overall cost.

Instance	O4863657 cost	O4863663 cost	f emergency	f displacement	f global
r11	100	100	81	61	142
r10	100	90	80	61	141
r9	100	80	78	61	139
r8	100	70	77	61	138
r7	100	60	76	61	137
r6	100	50	74	61	135
r5	100	40	73	61	134
r4	100	30	71	61	132
r3	100	20	70	61	131
r2	100	10	43	86	129
r1	100	5	39	86	125
r0	100	2	36	86	122

Table 6.

Results for test case 1.

From Figure 4, one can note that for O4863663 cost values ≥$20/h, corresponding to test cases r3–r11, this order is always chosen to be in the first route position by promoting the smallest displacement. When O4863663 cost is reduced to <$20/h, the cost of waiting time becomes more representative than displacement cost, causing the advance of the order with the greatest cost (O4863657) in the corresponding route. In addition, one can see the evolution of these components of the objective function and also the evolution of the costs of each of the orders considered in the study: (i) “F Emergency” is the portion corresponding to the cost of waiting time for emergency orders; (ii) “f displacement time” is the cost of the displacement performed;(iii) “f global” is the sum of two parts.

The highlight in Figure 4 is given to the time when there is a reversal in the route sequence due to the change in the O4863663 cost: The cost of waiting for EWO was above the travel cost up to the test case r3, after it, the most appropriate decision to reduce “f global” is to choose that sequence with less waiting time. The result of this transition on the route of the team is illustrated in Figure 5.

Figure 4.

Results for all instances of case study 1.

Figure 5.

Analysis of the emergence of postponing on case study 1.

5.2. Case study 2

In this case study, it is verified the influence that EWO costs have on the relative position of these orders on the existing route.

Eight test cases were developed, always assuming only an emergency order and six commercial orders: two with priority 0 and 4 with priority 2.

Table 7 summarizes the results for each test case, and the columns contain the identification of test case, the cost of the E4354201 order, the expected cost of the emergency order (“f Emergency”), the delay cost on commercial orders (“f commercial”), the cost of displacement (“f displacement”), and the overall cost (“f global”), which equals the sum “f Emergency” + “f Commercial” + “f displacement”. The cost E4354201 ranges from $24/h (test case “pr12”) to $ 1/h (“pr5”).

Instance	E4354201; cost	f; emergency	f; commercial	f; displacement	f; global
pr12	24	2.7	-209.8	33.1	-174.04
pr11	18	2.0	-209.8	33.1	-174.7
pr10	12	8.0	-219.5	35.1	-176.34
pr9	8	5.3	-219.5	35.1	-178.99
pr8	4	2.7	-219.5	35.1	-181.65
pr7	3	2.0	-219.5	35.1	-182.32
pr6	2	2.5	-229.6	43.7	-183.36
pr5	1	3.4	-232.0	43.1	-185.53

Table 7.

Results for test case 2.

With the help of Figure 6, it is possible to identify the three areas highlighted in the chart that corresponds to changes in the route:

• First region: between transition from test case pr11 to test case pr10;

• Second region: between transition from test case pr7 to test case pr6;

• Third region: between transition from test case pr6 to test case pr5.

Transition costs of the first region causes the emergency order pass from the first to the second position on the route; second transition region makes the emergency order to be is only the third on the route; and finally, the last transition (third region) leads the emergency order to be in the last position of the route. Such events are highlighted in Figure 6, which illustrates the routes for test cases pr12, pr10, pr6, and pr5.

Figure 6.

Analysis of the commercial orders delay on test case 2.

6. Conclusions

This work presents a heuristic approach to solve the emergency dispatching and routing problem, inspired by a newly developed mathematical formulation also presented. Some attributes of vehicle routing problem are addressed, particularly: the real‐time solution; on‐site service; multiple origins; time window restrictions on vehicles; and partially dynamic problem (Figure 7).

Figure 7.

Analysis of the emergence of postponing on test case 1.

Several criteria and constraints are involved from that attributes assumed, basically considering the minimization of both the waiting time, travel times, the delay caused by the assignment of pending EWOs, and the cost of non‐assigning them. The set of constraints include besides the general ones, those related to the partially dynamic problem addressed and the arrival time constraints due to the minimization of waiting time and to the assumption of on‐site service.

The proposed methodology, traduced in a heuristic approach that carefully observes the mathematical programming formulation, comprises decision support system techniques deriving a specially architecture developed, with the important requirement to promote better efficiency on multi‐processors systems in order to handle real‐time conditions. Practical results based on actual cases show how suitable is the proposed system to be applied in real‐time conditions and demonstrates the proper response to system parameters defined.

Acknowledgments

The authors would like to thank the technical and financial support of AES Sul Distribuidora Gaúcha de Energia SA.