betaFeedback

WorksMathematics

Solution of a Practical Vehicle Routing Problem for Monitoring Water Distribution Networks

Abstract

In this work, we introduce a generalization of the well-known Vehicle Routing Problem for a specific application in the monitoring of a Water Distribution Network (WDN). In this problem, multiple technicians must visit a sequence of nodes in the WDN and perform a series of tests to check the quality of water. Some special nodes (i.e., wells) require technicians to first collect a key from a key center. The key must then be returned to the same key center after the test has been performed, thus introducing precedence constraints and multiple visits in the routes. To solve the problem, three mathematical models and an Iterated Local Search have been implemented. The efficiency of the proposed methods is demonstrated by means of extensive computational tests on randomly created instances, as well as on instances derived from a real-world case study.

Introduction

Water contamination is related to the presence of one or more chemical compounds or pathogens to the extent that they become dangerous to the consumer and might lead to diseases ([24]). The risk of accidental contamination of drinking water is a well-known issue, and, recently, concerns regarding the deliberate contamination of urban water networks have called for additional safeguards.

In general, any threat to urban water networks directly affects the users in the community [28]. Indeed, according to a report recently released by the World Health Organization, contaminated drinking water is estimated to cause 485,000 diarrhoeal deaths each year [39]. The safety of water distribution networks has always been an important issue for the communities. However, many distribution systems in cities around the world face the threat of accidental or intentional contamination during the transportation from treatment plants to consumers due to reverse flows (i.e., the return of contaminated water flows from facilities), old infrastructures, insufficient use of disinfectants, and so forth. Consequently, water contamination in distribution networks is considered as the most diffused cause behind the spread of water-borne diseases [20].

In recent years, several studies have been conducted to identify the main sources of water pollution and improve the quality of water thanks to innovative treatment methods and plants, but still an accidental event, such as a large-scale contamination or a destructive attack to the transmission system, can significantly affect both the economy and the society. In 2014, for example, 300,000 consumers in West Virginia were affected by the accidental contamination of their drinking water distribution system caused by 4-Methylcyclohexanemethanol [32]. During the same year, as reported by Mukherjee et al. [22], a spill of benzene from a chemical plant in China accidentally reached the water distribution network. More recently, 27,000 Norwegian consumers were exposed to water contaminated with Clostridium [8].

Supply, treatment, transmission and distribution of drinking water in urban distribution networks require substantial expenses; therefore, not only water in urban distribution networks is considered an essential resource, but also an economic commodity. The results of a study conducted by the World Bank show that nearly 15% of treated water is wasted annually in developed countries. This amount arises to a range of 35-60% for developing countries [40]. Timely control of Water Distribution Networks (WDNs) is thus of fundamental importance, both from an economical and public health point of view.

In this paper, a new variant of the well-known Vehicle Routing Problem (VRP) in the context of WDNs is proposed. In this problem, a set of technicians must visit a set of nodes, including wells, reservoirs and treatment plants, within a network to evaluate the water quality. When visiting a well, the technicians need a key to open the well and perform the required tests. Since the technicians do not have the key, they have to visit a specified node at which the key is located, called key center in the following, to acquire it. As a result, they need to visit this node before reaching the well. After the tests have been performed, they have to take the key back to its original key center before returning to the depot where they started their route.

In addition to that, it is imposed that all nodes are visited and that the duration of any route performed by a technician does not exceed a maximum traveling time. The aim of the problem is to minimize the sum of the traveled times.

The problem originates from a real-world application that we encountered in Mashhad (Iran), where 5 technicians daily inspect a WDN comprising 3,124 households/shops, 293 reservoirs/tanks, 356 wells and 14 treatment plants. To solve the problem, we propose three Mixed Integer Linear Programming (MILP) models, and an Iterated Local Search (ILS) algorithm. While the models managed to solve small-size instances with up to 20 nodes, the ILS efficiently tackled cases with up to 200 nodes, allowing us to produce good-quality solutions for randomly created instances, as well as for realistic instances derived from the case study, in short computing times.

The remainder of the paper is organized as follows. In Section 2, the relevant literature is revised. The problem is formally described in Section 3. Sections 4 and 5 present the mathematical models and the ILS algorithm, respectively. Computational results are described in Section 6, and final conclusions and future research directions are discussed in Section 7.

Literature Review

The VRP is an iconic class of problems in operations research, with applications in the fields of transportation, distribution, logistics and services. We refer the interested reader to Toth and Vigo [36] for an extensive overview, and to Mor and Speranza [21] for a recent survey. The problem we face generalizes the VRP by considering precedence constraints and multiple visits. In this section, we only revise routing problems involving these two features, with a particular focus on real-world applications.

In the context of the Traveling Salesman Problem (TSP), precedence constraints were first addressed in the seminal work by Balas et al. [4], and, since then, have been widely investigated. In Moon et al. [20], the authors proposed a formulation for the TSP with precedence constraints using a two-commodity network flow model and developed a genetic algorithm based on a topological sorting of customers. In Sarin et al. [31], novel formulations for the asymmetric TSP and the precedence constrained asymmetric TSP were proposed. To tighten the formulations, the authors proposed and tested valid inequalities. Sun et al. [35] presented a new model for the time-dependent capacitated profitable tour problem, a generalization of the TSP with time windows and precedence constraints, and developed a tailored labeling algorithm. Salman et al. [30] describe the precedence constrained generalized TSP, in which customers are partitioned into groups and exactly one visit per group must be performed. They presented a novel branching technique and compared several bounding methods.

Precedence constraints have also been widely studied for problems involving multiple vehicles. Razali [28] developed a genetic algorithm based on a topological sorting of customers to solve the VRP with precedence constraints. The algorithm includes a route repair method to generate feasible offspring. A VRP variant with time windows, synchronization and precedence constraints was introduced by Haddadene et al. [13]. The authors focused on an attended home health care application, and proposed some exact and heuristic solution methods, including a novel MILP formulation, a greedy heuristic, and three metaheuristics.

Precedence constraints naturally arise in the context of Pickup-and-Delivery Problems (PDP), where each demand must be first collected at an origin node before being delivered at a destination node. We refer the reader to Battarra et al. [5] and Doerner and Salazar-González [11] for detailed surveys on PDPs for goods transportation and PDPs for people transportation, respectively, and to Koç et al. (2020) for a recent survey on simultaneous PDPs. Recently, Aziez et al. [3] studied a multi-PDP with time windows. They defined a 2-index formulation, an asymmetric representatives formulation, and a 3-index formulation improved by preprocessing and valid inequalities. The problem was solved exactly using a branch-and-cut algorithm. Dedicated branch-and-cut algorithms were also developed by Hernández-Pérez et al. [15], to solve the single-vehicle two-echelon one-commodity PDP, and by Wolfinger and Salazar-González [38], to solve a PDP with split loads and transshipments. The problem addressed in the latter work includes multiple visits to the same node. This is common when split deliveries are allowed, or multiple pickup and delivery operations can be performed at a single node. These generalizations were considered by Bruck and Iori [7], where non-elementary formulations were proposed for a single-vehicle PDP and then extended to the cases of split deliveries, intermediate drop-offs, and multiple vehicles.

Overall, we may find many routing problems that are inspired by real-world applications and involve precedence constraints and multiple visits. Sigurd et al. [33] studied an application of a PDP with time windows and precedence constraints arising in the transportation of live animals. In this case, the precedence constraints are given by veterinary rules, imposing that the livestock holdings are visited in a predefined sequence to avoid the spread of potential diseases. The authors proposed a tight formulation of the problem based on a Dantzig-Wolfe decomposition. Quttineh et al. [26] presented an application in the context of military operations, that was modeled as a generalized VRP with synchronization and precedence constraints. The peculiarity of the problem is due to the nature of the attack, which may require aircraft synchronization, multiple attacks to the same target, and precedence constraints among different targets. The problem was solved by a MILP model.

Furtado et al. [12] addressed a particular PDP with time windows originating from the oil industry. The aim of the problem is to determine the routing and scheduling of vessels that collect crude oil from offshore platforms and transport it to terminals on the coast. The authors proposed a MILP model, solving it by means of two different branch-and-cut algorithms. Another valuable example of routing and scheduling in the context of large-scale disaster relief operations was examined by Sabouhi et al. [29]. The authors solved a PDP arising from a case study in the city of Tehran (Iran). They proposed an integrated logistic system to evacuate people from areas affected by natural or man-made disasters. The problem was formulated as a MILP model, and a memetic algorithm was developed to solve large-scale instances. Pereira et al. [25] studied a particular Workforce Scheduling and Routing Problem (WSRP), called multiperiod WSRP with dependent tasks, in which the requested services consist of tasks to be executed along one or more days by teams of workers having different skills. Each customer can be visited more than once in a day, as long as precedence constraints are not violated. A MILP model, a constructive algorithm and an ant colony metaheuristic were proposed.

Recently, an interesting variant of the Team Orienteering Problem (TOP), named multi-visit TOP with precedence constraints, was investigated by Hanafi et al. [14]. In this problem, a set of tasks has to be accomplished in a predetermined order by possibly different vehicles. To solve the problem, the authors proposed a compact MILP formulation and a kernel search heuristic.

For what concerns WDNs, the literature mainly contains works on the location of sensors (see, e.g., Rathi and Gupta [27]). The VRP has been applied in many areas, but, to the best of our knowledge, not yet to the inspection of WDNs. In this paper, we fill this lack in the literature and propose exact and heuristic solution methods for a real-world VRP on a WDN.

Problem Description

The WDN is an essential infrastructure that consists of many elements, including reservoirs, wells, pipes and treatment plants.

An effective way to constantly monitor a WDN is by means of water quality sensors, which can be positioned all over the network. In cities where these sensor systems have not been installed, technicians are required to regularly visit nodes of the WDN and perform tests. The nodes to be visited, called for simplicity demand nodes in the following, are divided into two types:

  1. Type I: households, shops, reservoirs, tanks and treatment plants. For this kind of nodes, the technicians can directly go on site and perform the required tests. Reservoirs, tanks and treatment plants are characterized by larger service times than households and shops, due to the larger amount of tests that have to be performed;

  1. Type II: wells. For these nodes, the technicians need a key to access the well and perform the tests. So, they have to visit first a specified key center, and

take the key. Once all tests have been completed at the well, the key needs to be returned to its original key center, thus imposing a second visit.

A simple illustrative example derived from the real-world application we are facing is depicted in Figure 1. It comprises three routes starting and ending at the depot. Two of them (top and left part of the figure) visit just reservoirs and treatment plants, so demand nodes of type I. The third (right part of the figure) also visits a well, and is thus forced to pass twice by the corresponding key center.

An illustrative example of a VRPWDN solution in Mashhad (Iran)

Figure 1. An illustrative example of a VRPWDN solution in Mashhad (Iran)

Formally, we are given a directed graph G=(V,A)G = (V,A), where the node set is V={0,1,…,n,n+1}V = \{0,1,\ldots,n,n+1\} and is partitioned as V=V1∪V2∪V3∪{0,n+1}V = V_1 \cup V_2 \cup V_3 \cup\{0,n+1\}. Nodes 00 and n+1n+1 represent, respectively, the beginning and end of all routes, and in our application coincide with a unique central depot. Sets V1V_1 and V2V_2 are associated with, respectively, the demand nodes of types I and II. Set V3V_3 comprises nodes associated with all key centers. With each node i∈V2i \in V_2, we associate a predecessor pi∈V3p_i \in V_3 and a successor node di∈V3d_i \in V_3. In our application, pip_i and did_i correspond to a unique key center, so they have the same geographical location, but the models and algorithms that we propose below can also solve the case in which they correspond to different locations.

Each demand node has to be visited exactly once, while each vehicle visits a particular key center at most once for picking up all the keys, and then another single time for delivering all the keys that were previously collected. This implies that, in case a center has the keys for multiple demand nodes and these nodes are visited by a unique vehicle, then such keys must be collected all together in a unique visit (to pip_i), and then later delivered all together in another visit (to did_i). Note that it is not compulsory to visit pip_i immediately before ii. In other words, the vehicle can collect the key for ii but then visit other nodes before reaching ii. The same holds for did_i, which is not required to be visited immediately after ii.

The graph is complete, and with each arc (i,j)∈A(i,j) \in A we associate a traveling time cijc_{ij}. A service time viv_i is associated with each node i∈Vi \in V. We suppose that triangle inequality holds for all our instances (i.e., cij≤cik+vk+ckjc_{ij} \leq c_{ik} + v_k + c_{kj} for all i,j,k∈Vi,j,k \in V). We are also given a set KK of homogeneous vehicles based at the central depot. Each vehicle performs a single route.

A route starts and ends at the depot. Its duration is given by the sum of the service and traveling times of the nodes and arcs covered by the vehicle, and it should not exceed a maximum duration LL. Whenever a route visits a node ii of type II, then it should also visit pip_i and did_i. The aim of the Vehicle Routing Problem for Water Distribution Networks (VRPWDN) is to visit all demand nodes, while satisfying all constraints and minimizing the sum of the route durations.

The VRPWDN is NP-hard in the strong sense, because it generalizes the well-known VRP. In the next sections, we attempt its solution through mathematical models and heuristic algorithms.

Mathematical Models

In this section, we investigate three mathematical models that describe the VRPWDN and are derived from the literature. The first model is based on a time representation of the problem and is inspired by the formulation proposed by Desaulniers et al. [9] for the VRP with time windows. The second is a flow-based model that builds upon the formulation presented by Kara [16] and later used by, among others, [17, 23, 1]. The third is a node-based model that we derive from the classical Miller, Tucker and Zemlin formulation (see, e.g., [6]).

Time-based Model

Let yiky_{ik} be a binary variable taking value 1 if node ii is visited by vehicle kk and 0 otherwise, xijkx_{ijk} be another binary variable taking value 1 if arc (i,j)(i,j) is covered by vehicle kk and 0 otherwise, and tikt_{ik} be a continuous variable corresponding to the time at which vehicle kk arrives at node ii. The time-based model for the VRPWDN can be formulated as follows:

(VRPWDNtb)min⁡∑k∈K∑i∈V∖{n+1}∑j∈V∖{0}(cij+vi)xijk(1)(\mathrm{VRPWDN}_{\mathrm{tb}})\quad\min\sum_{k\in K}\sum_{i\in V\setminus\{n+1\}}\sum_{j\in V\setminus\{0\}}(c_{ij}+v_i)x_{ijk} \tag*{(1)}

subject to

∑k∈K∑j∈V∖{0}xijk=1(2)\sum_{k\in K}\sum_{j\in V\setminus\{0\}} x_{ijk}=1 \tag*{(2)}
∑j∈V∖{0}x0jk=1(3)\sum_{j\in V\setminus\{0\}} x_{0jk}=1 \tag*{(3)}
yik=∑j∈V∖{0}xijk=∑j∈V∖{n+1}xjik(4)y_{ik}=\sum_{j\in V\setminus\{0\}}x_{ijk}=\sum_{j\in V\setminus\{n+1\}}x_{jik} \tag*{(4)}
∑i∈V∖{n+1}xi,n+1,k=1(5)\sum_{i\in V\setminus\{n+1\}}x_{i,n+1,k}=1 \tag*{(5)}
∑k∈Kt0k=0(6)\sum_{k\in K}t_{0k}=0 \tag*{(6)}
0≤tik≤Lyik(7)0\leq t_{ik}\leq Ly_{ik} \tag*{(7)}
tjk≥tik+vi+cij−Mij(1−xijk)(8)t_{jk}\geq t_{ik}+v_i+c_{ij}-M_{ij}(1-x_{ijk}) \tag*{(8)}
ypik+ydik≥2yik(9)y_{p_i k}+y_{d_i k}\geq2y_{ik} \tag*{(9)}
tpik+vpi+cpii−Mi′(1−yik)≤tik≤tdik−(cidi+vi)yik(10)t_{p_i k}+v_{p_i}+c_{p_i i}-M'_i(1-y_{ik})\leq t_{ik}\leq t_{d_i k}-(c_{i d_i}+v_i)y_{ik} \tag*{(10)}
xijk∈{0,1}(11)x_{ijk}\in\{0,1\} \tag*{(11)}
yik∈{0,1}(12)y_{ik}\in\{0,1\} \tag*{(12)}

Objective function (1) is to minimize the total duration of the routes. Constraints (2) impose that each node i∈V1∪V2i\in V_1\cup V_2 has exactly one outgoing arc. Each vehicle starts its route from the depot and such condition is imposed by means of constraints (3). Constraints (4) and (5) ensure that each node ii has exactly one incoming and one outgoing arc and that each vehicle kk end its route at the depot. Constraints (6) impose that all routes start at time 0. Constraints (7) impose that arrival times are non-negative and limit the duration of each route to be at most LL. The time at which vehicle kk arrives at node jj is modeled by means of constraints (8), in which we set Mij=L+vi+cij−cj,n+1M_{ij}=L+v_i+c_{ij}-c_{j,n+1}. Constraints (9) impose that if vehicle kk visits node ii, then it also visits nodes pip_i and did_i. Since pip_i may contain keys not only for ii but for other nodes, vehicle kk may visit pip_i but not ii, and the same holds for did_i. For this reason, the equation cannot be an equality. Constraints (10), in which we set Mi′=L+vpi+cpi,i−ci,n+1M'_i=L+v_{p_i}+c_{p_i,i}-c_{i,n+1}, guarantee the respect of precedence constraints, by forcing time dependency between visits to pip_i, ii and did_i. Note that if yiky_{ik} is equal to 0, constraints (10) become redundant with respect to constraints (7). Constraints (11) and (12) define the domain of the xijkx_{ijk} and yiky_{ik} variables.

Furthermore, the aforementioned model can be enhanced with the addition of the following valid inequalities

(c0pi+vpi+cpii)yik≤tik(13)(c_{0p_i}+v_{p_i}+c_{p_i i})y_{ik}\leq t_{ik} \tag*{(13)}
(c0pi+vpi+cpii+vi+cidi)yik≤tdik(14)(c_{0p_i}+v_{p_i}+c_{p_i i}+v_i+c_{i d_i})y_{ik}\leq t_{d_i k} \tag*{(14)}
tjk≥(c0i+vi+cij)xijk(15)t_{jk}\geq(c_{0i}+v_i+c_{ij})x_{ijk} \tag*{(15)}

which strengthen the values taken by the arrival time variables.

Flow-based Model

Let fijkf_{ijk} be a variable representing the “load” of vehicle kk when traveling along arc (i,j)∈A(i,j) \in A. The load represents the number of nodes visited by vehicle kk before it travels along arc (i,j)(i,j). We can model the VRPWDN as follows:

(VRPWDNfb)min⁡ ∑k∈K∑i∈V∖{n+1}∑j∈V∖{0}(cij+vi)xijk(16)\begin{aligned} (\mathrm{VRPWDN}_{\mathrm{fb}})\quad\min\ &\sum_{k\in K}\sum_{i\in V\setminus\{n+1\}}\sum_{j\in V\setminus\{0\}}(c_{ij}+v_i)x_{ijk} \tag*{(16)} \end{aligned}

subject to (2), (3), (11) and

∑j∈V∖{0}xijk=∑j∈V∖{n+1}xjiki∈V,k∈K(17)\sum_{j\in V\setminus\{0\}}x_{ijk}=\sum_{j\in V\setminus\{n+1\}}x_{jik}\qquad i\in V,k\in K \tag*{(17)}
∑i∈V∖{n+1}∑j∈V∖{0}(cij+vi)xijk≤Lk∈K(18)\sum_{i\in V\setminus\{n+1\}}\sum_{j\in V\setminus\{0\}}(c_{ij}+v_i)x_{ijk}\leq L\qquad k\in K \tag*{(18)}
∑j∈V∖{0}f0jk=0k∈K(19)\sum_{j\in V\setminus\{0\}}f_{0jk}=0\qquad k\in K \tag*{(19)}
∑i∈V∖{n+1}fi,n+1,k=∑i∈V∖{n+1}∑j∈V∖{0}xijk−1k∈K(20)\sum_{i\in V\setminus\{n+1\}}f_{i,n+1,k}=\sum_{i\in V\setminus\{n+1\}}\sum_{j\in V\setminus\{0\}}x_{ijk}-1\qquad k\in K \tag*{(20)}
∑j∈V∖{0}fijk≥∑j∈V∖{n+1}(fjik+xjik)i∈V∖{0,n+1},k∈K(21)\sum_{j\in V\setminus\{0\}}f_{ijk}\geq\sum_{j\in V\setminus\{n+1\}}(f_{jik}+x_{jik})\qquad i\in V\setminus\{0,n+1\},k\in K \tag*{(21)}
∑j∈V∖{0}(fpjik−fijk+xijk)≤(n−1)(1−∑j∈V∖{0}xijk)i∈V2,k∈K(22)\sum_{j\in V\setminus\{0\}}(f_{p_jik}-f_{ijk}+x_{ijk})\leq(n-1)\left(1-\sum_{j\in V\setminus\{0\}}x_{ijk}\right)\qquad i\in V_2,k\in K \tag*{(22)}
∑j∈V∖{0}fpjik≥∑j∈V∖{0}xijki∈V2,k∈K(23)\sum_{j\in V\setminus\{0\}}f_{p_jik}\geq\sum_{j\in V\setminus\{0\}}x_{ijk}\qquad i\in V_2,k\in K \tag*{(23)}
∑j∈V∖{0}(fdijk−fijk)≥∑j∈V∖{0}xijki∈V2,k∈K(24)\sum_{j\in V\setminus\{0\}}(f_{d_ijk}-f_{ijk})\geq\sum_{j\in V\setminus\{0\}}x_{ijk}\qquad i\in V_2,k\in K \tag*{(24)}
0≤fijk≤(n−1)xijki,j∈V,k∈K(25)0\leq f_{ijk}\leq(n-1)x_{ijk}\qquad i,j\in V,k\in K \tag*{(25)}

As in the previous model, objective function (16) minimizes the total route duration. Constraints (17) correspond to the previous constraints (4) except for the yiky_{ik} term. The maximum duration of each route is bounded by means of constraints (18). Constraints (19) and (20) impose the load on vehicle kk when leaving 0 and entering n+1n+1, respectively. Constraints (21) impose the load conservation at node ii. Constraints (22)–(24) guarantee the respect of precedence constraints. Constraints (25) impose lower and upper bounds on the fijkf_{ijk} variables.

The above model can be improved by the addition of the following constraints:

∑j∈V∖{n+1}xjpik+∑j∈V∖{0}xdijk≥2∑j∈V∖{n+1}xjiki∈V2,k∈K(26)\sum_{j\in V\setminus\{n+1\}}x_{jp_ik}+\sum_{j\in V\setminus\{0\}}x_{d_ijk}\geq2\sum_{j\in V\setminus\{n+1\}}x_{jik}\qquad i\in V_2,k\in K \tag*{(26)}
∑j∈V∖{0}(fdijk−fpjik)≥∑l∈V∖{n+1}:pi=pl∑j∈V∖{0}xljki∈V2,k∈K(27)\sum_{j\in V\setminus\{0\}}(f_{d_ijk}-f_{p_ jik})\geq\sum_{l\in V\setminus\{n+1\}:p_i=p_l}\sum_{j\in V\setminus\{0\}}x_{ljk}\qquad i\in V_2,k\in K \tag*{(27)}
∑l∈V∖{n+1}(flik−fljk)+nxijk+(n−2)xjik≤(n−1)i,j∈V∖{0,n+1},k∈K(28)\sum_{l\in V\setminus\{n+1\}}(f_{lik}-f_{ljk})+nx_{ijk}+(n-2)x_{jik}\leq(n-1)\qquad i,j\in V\setminus\{0,n+1\},k\in K \tag*{(28)}

Constraints (26) are equivalent to (9). Constraints (27) enforce an additional relation between the flows leaving pip_i and did_i. Constraints (28) are derived from the lifted constraints proposed by Desrochers and Laporte (1991).

Node-based Model

Let uiku_{ik} be a variable representing the load on vehicle kk after leaving node ii. With respect to the previous model, this implies setting uik=∑j∈Vfijku_{ik} = \sum_{j \in V} f_{ijk}. We can model the VRPWDN as follows:

(VRPWDNnb)min⁡∑k∈K∑i∈V∖{n+1}∑j∈V∖{0}(cij+vi)xijk(29)(\mathrm{VRPWDN}_{\mathrm{nb}})\quad\min\sum_{k \in K}\sum_{i \in V \setminus\{n+1\}}\sum_{j \in V \setminus\{0\}}(c_{ij}+v_i)x_{ijk} \tag*{(29)}

subject to (2), (3), (11), (17), (18) and

u0k=0k∈K(30)u_{0k}=0 \qquad k \in K \tag*{(30)}
un+1,k=∑i∈V∖{n+1}∑j∈V∖{0}xijkk∈K(31)u_{n+1,k}=\sum_{i \in V \setminus\{n+1\}}\sum_{j \in V \setminus\{0\}}x_{ijk} \qquad k \in K \tag*{(31)}
uik−ujk+nxijk≤(n−1)i∈V∖{n+1},j∈V∖{0},k∈K(32)u_{ik}-u_{jk}+nx_{ijk}\leq(n-1) \qquad i \in V \setminus\{n+1\},j \in V \setminus\{0\},k \in K \tag*{(32)}
upik−uik+∑j∈V∖{0}xijk≤n(1−∑j∈V∖{0}xijk)i∈V2,k∈K(33)u_{p_i k}-u_{ik}+\sum_{j \in V \setminus\{0\}}x_{ijk}\leq n\left(1-\sum_{j \in V \setminus\{0\}}x_{ijk}\right) \qquad i \in V_2,k \in K \tag*{(33)}
upik≥∑j∈{0}xijki∈V2,k∈K(34)u_{p_i k}\geq\sum_{j \in\{0\}}x_{ijk} \qquad i \in V_2,k \in K \tag*{(34)}
udik−uik≥∑j∈V∖{0}xijki∈V2,k∈K(35)u_{d_i k}-u_{ik}\geq\sum_{j \in V \setminus\{0\}}x_{ijk} \qquad i \in V_2,k \in K \tag*{(35)}
0≤uik≤n∑j∈V∖{0}xijki∈V,k∈K(36)0\leq u_{ik}\leq n\sum_{j \in V \setminus\{0\}}x_{ijk} \qquad i \in V,k \in K \tag*{(36)}

For each vehicle kk, constraints (30) set the load after leaving node 0, while constraints (31) define the load when arriving at node n+1n+1. Constraints (32) impose the load conservation when traveling from node ii to node jj. Constraints (33)–(35) guarantee the respect of precedence constraints. Constraints (36) impose both the non-negativity of the uiku_{ik} variables and their relation with the xijkx_{ijk} variables.

The model can be improved by the addition of (26) and of

udik−upik≥∑l∈V∖{n+1}:pi=pl∑j∈V∖{0}xljki∈V2,k∈K(37)u_{d_i k}-u_{p_i k}\geq\sum_{\substack{l\in V\setminus\{n+1\}:p_i=p_l}}\sum_{j\in V\setminus\{0\}}x_{ljk} \qquad i\in V_2,k\in K \tag*{(37)}
uik−ujk+nxijk+(n−2)xjik≤(n−1)i,j∈V∖{0,n+1},k∈K(38)u_{ik}-u_{jk}+nx_{ijk}+(n-2)x_{jik}\leq(n-1) \qquad i,j\in V\setminus\{0,n+1\},k\in K \tag*{(38)}

which correspond to the above (27) and (28), respectively.

Iterated Local Search

We developed an ILS algorithm with the purpose of finding good-quality VRPWDN solutions in short computing times. The choice of this metaheuristic is motivated by its simplicity and effectiveness, in addition to the wide applicability it has found on related VRPs (see, e.g., Vansteenwegen et al. [37], Silva et al. [34], Haddadene et al. [13] and Atefi et al. [2]). On the other hand, the need for short computing times is justified by the number of visits usually scheduled in a day in our real-world application, and by the fact that candidate locations might change at the beginning or in the course of a day. Two examples which typically cause a re-scheduling of visits can be a new warning for potential water contamination coming from a household or shop or, when visiting a well, the unfortunate event that the well’s door is broken and it is not possible to open it.

Following the general framework proposed by Lourenço et al. [19], the ILS starts from an initial solution and then improves it by iteratively invoking local search and perturbation procedures. The pseudo-code of the proposed ILS is provided in Algorithm 1. First, we generate an initial solution x0x_0 by means of a heuristic algorithm (line 1), and then we improve it with a local search procedure (line 2). The current solution, xx, is stored as the incumbent, x∗x^*, and inserted in the set of best known solutions obtained during the search, called BKSetBKSet (lines 3 and 4). Next, we execute two phases, one after the other.

In the first phase, by applying a perturbation on xx followed by a call to the local search (lines 6–8), the algorithm tries to escape from local optima. The perturbation is randomly selected between two tailored procedures. Let z(x)z(x) and l(x)l(x) be the cost of xx and the maximum duration of a route in xx, respectively. In case xx has better cost than x∗x^*, or same cost but lower maximum duration, then we use it to update x∗x^*. In such a case, we also insert xx in BKSetBKSet. This set contains the β\beta different solutions found during the search and having the smallest z(x)z(x) costs, breaking ties by smallest l(x)l(x) value. If, instead, xx does not improve x∗x^*, then we set x←x∗x \leftarrow x^* as starting solution to be shaken at the next iteration. This loop is repeated until no improvement is found for maxitermax_{iter} iterations.

With the aim of further improving the solution obtained, at line 16 we enter the second ILS phase, in which a new series of improving attempts is performed. The idea is to intensify the search around the solutions contained in BKSetBKSet. For each such solution, we perform once more a loop of shaking and local search procedures, which is repeated until the same termination condition used above is met. Should one of these attempts manage to improve the incumbent solution, this time only in terms of costs, then the search restarts from the beginning of the first phase.

In the following, we provide the details of the main elements of the algorithm.

Initialization Procedure

Algorithm 2 gives the Initialization procedure that is used to generate an initial solution. At the beginning, ∣K∣|K| routes are built in parallel by randomly selecting a first node i∈V1∪V2i \in V_1 \cup V_2 per route. In case ii belongs to V2V_2, then the predecessor

Algorithm 1 Iterated Local Search (ILS)
1: $x_0 \leftarrow \texttt{Initialization}()$                         ▷ Generate an initial solution
2: $x \leftarrow \texttt{LocalSearch}(x_0)$
3: $x^* \leftarrow x$
4: $BKSet \leftarrow \{x^*\}$                                         ▷ $BKSet$: set of best known solutions
5: repeat                                                             ▷ Phase 1
6:     $\texttt{Shake}() \leftarrow \texttt{Rand}\{S_1,S_2\}$         ▷ Randomly select a shaking procedures
7:     $x \leftarrow \texttt{Shake}(x)$
8:     $x \leftarrow \texttt{LocalSearch}(x)$
9:     $\texttt{Insert}(x,BKSet)$
10:    if $z(x) < z(x^*)$ OR $(z(x) = z(x^*)$ AND $l(x) < l(x^*))$ then
11:        $x^* \leftarrow x$
12:    else
13:        $x \leftarrow x^*$
14:    end if
15: until no improvement is found for $max_{iter}$ iterations
16: for $j \leftarrow 1$ to $|BKSet|$ do                           ▷ Phase 2
17:     $x \leftarrow BKSet_j$                                         ▷ Select the $j^{th}$ solution $\in BKSet$
18:     repeat
19:         $\texttt{Shake}() \leftarrow \texttt{Rand}\{S_1,S_2\}$
20:         $x \leftarrow \texttt{Shake}(x)$
21:         $x \leftarrow \texttt{LocalSearch}(x)$
22:         if $z(x) < z(x^*)$ then
23:             $x^* \leftarrow x$
24:             $\texttt{Insert}(x^*,BKSet)$
25:             Go to line 5
26:         end if
27:     until no improvement is found for $max_{iter}$ iterations
28: end for
29: return $x^*$

and the successor of ii (i.e., pip_i and did_i) are also inserted into the route. In the next ∣V1∪V2∣−∣K∣|V_1 \cup V_2| - |K| iterations, a new node is randomly selected and inserted into an existing route. In these iterations, both the node and, in case i∈V2i \in V_2, its predecessor and successor are inserted in the route in the positions that lead to the minimum extra mileage cost. Note that the insertion of node ii or tuple (pi,i,di)(p_i,i,d_i) into an existing route is led by procedure CheapestInsertion, which evaluates among the ∣K∣|K| routes the best candidate for the expansion. At line 22, the algorithm checks whether the solution is feasible. If not, then the whole procedure is repeated from scratch.

Algorithm 2 Initialization Procedure

1: S,V←∅S,\mathcal{V} \leftarrow\emptyset

2: for k←1k \leftarrow1 to ∣K∣|K| do ▷ Initialization of ∣K∣|K| routes in parallel

3: i←Rand⁡{1,…,∣V1∪V2∣}i \leftarrow\operatorname{Rand}\{1,\ldots,|V_1 \cup V_2|\}

4: V←V∪{i}\mathcal{V} \leftarrow\mathcal{V} \cup\{i\} ▷ Add ii to the set of visited nodes

5: if i∈V2i \in V_2 then

6: rk←(0,pi,i,di,n+1)r_k \leftarrow(0,p_i,i,d_i,n+1)

7: Insert⁡(rk,S)\operatorname{Insert}(r_k,S)

8: else

9: rk←(0,i,n+1)r_k \leftarrow(0,i,n+1)

10: Insert⁡(rk,S)\operatorname{Insert}(r_k,S)

11: end if

12: end for

13: for j←1j \leftarrow1 to ∣V1∪V2∣−∣K∣|V_1 \cup V_2|-|K| do ▷ Expansion of existing routes

14: i←Rand⁡{{1,…,∣V1∪V2∣}∖V}i \leftarrow\operatorname{Rand}\{\{1,\ldots,|V_1 \cup V_2|\}\setminus\mathcal{V}\}

15: V←V∪{i}\mathcal{V} \leftarrow\mathcal{V} \cup\{i\}

16: if i∈V2i \in V_2 then

17: CheapestInsertion⁡((pi,i,di),rk∈S)\operatorname{CheapestInsertion}((p_i,i,d_i),r_k \in S)

18: else

19: CheapestInsertion⁡(i,rk∈S)\operatorname{CheapestInsertion}(i,r_k \in S)

20: end if

21: end for

22: if Feasible⁡(S)=1\operatorname{Feasible}(S)=1 then

23: continue

24: else

25: Go to line 1

26: end if

27: return SS

Local Search

The LocalSearch procedure invokes, one after the other, the following neighborhood searches:

LS1 Swap intra-route: swap two sequences with up to three consecutive nodes in the same route. Potential nodes belonging to V3V_3 are extracted from the two sequences and reinserted after the swap following the minimum extra mileage cost and respecting the precedence constraints;

LS2 Swap inter-route: swap two sequences with up to three consecutive nodes from different routes, taking care of nodes belonging to V3V_3;

LS3 Relocate intra-route: remove a sequence with up to three consecutive nodes and reinsert it in a different position within the same route, taking care of nodes belonging to V3V_3;

LS4 Relocate inter-route: remove a sequence with up to three consecutive nodes and reinsert it in a different route, taking care of nodes belonging to V3V_3;

LS5 3-opt: in a preliminary step, select a route and remove potential nodes belonging to V3V_3. Following this step, apply the standard 3-opt algorithm to the remaining nodes. After each iteration of the 3-opt algorithm update the solution by reinserting the previously extracted nodes belonging to V3V_3.

Procedures from LS1 to LS4 have all complexity O(n2)O(n^2), whereas LS5 has complexity O(n3)O(n^3). To limit the computational effort required by LS5, a random logic search is added. In particular, a candidate route kk is selected randomly and potential nodes belonging to V3V_3 are removed as follows. For each node ii in the route, the saving sis_i that could be obtained by removing ii and directly connecting the predecessor and successor nodes of ii in the route is computed. Then, the probability of removing ii is set to pi=si/∑jsjp_i=s_i/\sum_j s_j. By means of the roulette wheel mechanism, three non-adjacent nodes are selected for removal, and then the resulting route is optimized by a 3-opt algorithm. A threshold of γ\gamma iterations is set to limit the number of attempts.

The calls to LS1–LS5 are repeated as long as an improvement is found. Procedure LocalSearch hence returns a solution which is a local optimum with respect to all five neighborhoods.

Shaking Procedure

To perturb a solution, we randomly select, with same probability, one of the two following procedures.

S1 Shaking 1: randomly select a route kk and execute a random iteration of the 3-opt algorithm to update the order of visits. If the cost of the current solution is not worse than αz(x∗)\alpha z(x^*), with α\alpha being an input parameter, randomly select a second route k′k' and perform another 3-opt iteration. The procedure is iterated as long as the cost of the perturbed solution is not worse than αz(x∗)\alpha z(x^*);

S2 Shaking 2: compute the cost saving obtained by removing any node from the solution, similarly to what is done in LS5. Then use the roulette wheel mechanism to select a node i∈V∖{0,n+1}i \in V \setminus\{0,n+1\}, and remove ii from its route. The removal procedure is iterated until at least α\alpha percent of all nodes have been removed. If the selected node belongs to V2V_2, then its saving is computed as the average cost saving obtained by removing ii, pip_i, and did_i. At the end of this step, the algorithm invokes the Initialization procedure to rebuild a feasible solution.

Computational Results

In this section, we present the results of extensive computational tests performed with the aim of assessing the performance of the proposed methods. The mathematical models and the ILS were coded in C++ using Microsoft Visual Studio 2010. The computational tests were executed on a PC equipped with an Intel Core i7 CPU processor @ 2.70 GHz and 6 GB of RAM, using CPLEX 12.3 as MILP solver. In § 6.1, we describe the sets of randomly-created instances that we used for our tests. The comparison among the mathematical models is reported in § 6.2, while the behavior of the ILS is analyzed in § 6.3 and § 6.4. In § 6.5, we report the results of additional computational experiments performed on a set of realistic instances derived from the case study.

Randomly-created Instances

We created several random instances with the aim of assessing the performance of the algorithms under different situations. In detail, we created two sets of instances, each comprising different subsets having homogeneous values of ∣V1∪V2∣|V_1 \cup V_2|, (∣V2∣,∣V3∣)(|V_2|, |V_3|) and ∣K∣|K|, and composed by three random instances per subset. We obtained the following sets:

  • Small-size: 18 instances with ∣V1∪V2∣=10|V_1 \cup V_2|=10, (∣V2∣,∣V3∣)∈{(1,1),(2,1),(2,2)}(|V_2|, |V_3|) \in\{(1, 1), (2, 1), (2, 2)\}, and ∣K∣∈{1,2}|K| \in\{1, 2\}; 24 instances with ∣V1∪V2∣=15|V_1 \cup V_2|=15, (∣V2∣,∣V3∣)∈{(3,2),(3,3),(4,2),(4,3)}(|V_2|, |V_3|) \in\{(3, 2), (3, 3), (4, 2), (4, 3)\}, and ∣K∣∈{2,3}|K| \in\{2, 3\}; 24 instances with ∣V1∪V2∣=20|V_1 \cup V_2|=20, (∣V2∣,∣V3∣)∈{(2,2),(3,2),(3,3),(5,3)}(|V_2|, |V_3|) \in\{(2, 2), (3, 2), (3, 3), (5, 3)\}, and ∣K∣∈{2,3}|K| \in\{2, 3\};

  • Medium- and large-size: 24 instances with ∣V1∪V2∣=50|V_1 \cup V_2|=50, (∣V2∣,∣V3∣)∈{(5,5),(8,8),(10,5),(10,8)}(|V_2|, |V_3|) \in\{(5, 5), (8, 8), (10, 5), (10, 8)\}, and ∣K∣∈{5,8}|K| \in\{5, 8\}; 24 instances with ∣V1∪V2∣=100|V_1 \cup V_2|=100, (∣V2∣,∣V3∣)∈{(5,5),(10,5),(10,10),(15,10)}(|V_2|, |V_3|) \in\{(5, 5), (10, 5), (10, 10), (15, 10)\}, and ∣K∣∈{10,15}|K| \in\{10, 15\}; 24 instances with ∣V1∪V2∣=200|V_1 \cup V_2|=200, (∣V2∣,∣V3∣)∈{(10,10),(20,10),(20,20),(30,20)}(|V_2|, |V_3|) \in\{(10, 10), (20, 10), (20, 20), (30, 20)\}, and ∣K∣∈{15,20}|K| \in\{15, 20\}.

For each instance, the coordinates of the nodes are integer values randomly selected between 0 and 100. The distances between the nodes are computed as the Euclidean ones, rounded to the second closest digit. The maximum duration is set to L=1.5(∑i∈V1∪V2cˉi+∣K∣∑i∈V3∪{0}cˉi)/∣K∣L = 1.5(\sum_{i \in V_1 \cup V_2} \bar{c}_i + |K|\sum_{i \in V_3 \cup\{0\}} \bar{c}_i)/|K|, where cˉi\bar{c}_i is the average travel time of the arcs leaving ii, computed as cˉi=∑j∈V∖{i}cij/(∣V∣−1)\bar{c}_i = \sum_{j \in V \setminus\{i\}} c_{ij}/(|V| - 1) for each node i∈V∖{n+1}i \in V \setminus\{n+1\}. The service time viv_i for each node i∈V1∪V2∪V3i \in V_1 \cup V_2 \cup V_3 is set to a random integer value between 20 and 40.

In the following, a subset of instances is identified by the tuple (∣V1∪V2∣,∣V2∣,∣V3∣,∣K∣)(|V_1 \cup V_2|, |V_2|, |V_3|, |K|), while a single instance is identified by (∣V1∪V2∣,∣V2∣,∣V3∣,∣K∣,u)(|V_1 \cup V_2|, |V_2|, |V_3|, |K|, u), where uu is a numerical index going from 1 to 3.

To favor future research on the problem, the randomly-created instances have been made publicly available at https://github.com/DarioVezzali/VRPWDN.

Comparison among the Mathematical Models

In this section, the performance of the three mathematical models from § 4 is investigated. A time limit of 3,600 CPU seconds was imposed on each execution. The aggregated results that we obtained are reported in Table 1. Each line reports average/total values for a group of three instances having the same numbers of vertices and vehicles. For each group, columns “zlbz_{lb}” and “zubz_{ub}” give the average lower and upper bound values, respectively, column “%gap” gives the average percentage gap and column “t(s)” the average run time. An entry “tlim” indicates that the time limit was reached for all the three instances in the group. Column “opt” gives the total number of instances solved to proven optimality.

∣V1∪V2∣|V_1 \cup V_2|∣V2∣|V_2|∣V3∣|V_3|∣K∣|K|time-based zlbz_{lb}time-based zubz_{ub}time-based %gaptime-based tt (s)time-based optflow-based zlbz_{lb}flow-based zubz_{ub}flow-based %gapflow-based tt (s)flow-based optnode-based zlbz_{lb}node-based zubz_{ub}node-based %gapnode-based tt (s)node-based opt
10111706.39706.390.000.873706.39706.390.001.133706.39706.390.001.423
10112730.91730.910.007.453730.91730.910.003.263730.91730.910.0012.203
10211743.25743.250.006.543743.25743.250.003.133743.25743.250.0010.663
10212793.75793.750.0023.123793.75793.750.009.453793.75793.750.0010.963
10221803.96803.960.00177.593803.96803.960.0016.733803.96803.960.0044.803
10222833.78833.780.00110.683833.78833.780.0075.013833.78833.780.00436.673
sum/avg (10)768.67768.670.0054.3818768.67768.670.0018.1218768.67768.670.0084.4518
153221036.611036.610.001811.6431036.611036.610.00509.7131036.611036.610.00823.413
153231014.041049.452.882054.3521049.451049.450.001325.6831021.591049.452.412419.871
153321065.961114.684.39tlim01114.681114.680.001104.1031067.191114.684.282973.831
153331101.811160.325.05tlim01153.101160.740.651358.6021096.701160.325.49tlim0
154221036.611036.610.001822.0031036.611036.610.00510.8131036.611036.610.00825.533
154231081.471084.120.282439.7021084.121084.120.001108.5631084.121084.120.001637.683
154321073.811150.816.81tlim01142.241149.800.691420.9821082.751150.816.03tlim0
154331111.811203.227.72tlim01190.641202.401.031430.5121113.291204.857.73tlim0
sum/avg (15)1065.271104.483.392815.96101100.931104.300.301096.12211067.361104.683.242435.6411
202221225.521275.443.873274.9811243.731277.822.611354.8621228.481275.443.622266.042
202231262.371330.875.14tlim01294.951329.122.561458.5321251.591332.916.09tlim0
203221197.441269.715.60tlim01243.521269.712.021271.0721236.211269.712.581531.302
203231220.351301.736.13tlim01301.731301.730.001127.6331253.861301.733.582510.732
203321210.011289.025.94tlim01260.691296.612.602661.6411215.651295.675.95tlim0
203331223.851321.847.26tlim01281.301321.842.97tlim01204.511337.039.69tlim0
205321200.101280.166.12tlim01241.981280.432.912986.7911235.591278.323.242739.771
205331228.581324.167.12tlim01270.111324.164.08tlim01234.641324.166.76tlim0
sum/avg (20)1221.031299.115.903559.3711267.251300.002.442165.51121234.641311.675.522842.598
overall sum/avg1041.021088.673.382333.13291070.801083.930.991190.99511046.731088.313.191942.3937

Table 1. Comparison of mathematical models (three inst. per line). Best average lower and upper bound values in boldface

From Table 1, we can observe that just on a few large-size instances the time-based model and the node-based model find better results in terms of average upper bound. Overall, the flow-based model outperforms the other two models in terms of average lower bound, average percentage gap, average run time, and number of optimal solutions obtained. Consequently, we adopted this model to assess the quality of the solutions obtained by the ILS (see § 6.3).

For all the instances belonging to the medium- and large-size sets, the mathematical models could not obtain proven optimal solutions and the computer frequently ran out of memory because of the large model size. Overall, we can conclude that the results prove the need of a good heuristic for these instances. This need is further motivated by the dimension of the original real-world problem, where the number of visits per day (i.e., around 70) is out of scale if compared to the size of instances solved to optimality within the time limit.

To assess the performance of the proposed valid inequalities, six small-size instances were selected and solved running the three models with and without the addition of the valid inequalities. The results are reported in Table 2. We can notice that the inequalities help improve the performance of all models, by reducing the average percentage gap and execution time, and increasing the number of proven optimal solutions.

mathematical model| without valid inequalitieswith valid inequalities
zlbz_{lb}zubz_{ub}%gapt(s)optzlbz_{lb}zubz_{ub}%gapt(s)opt
time-based1036.251077.493.242484.5121040.671076.852.812288.633
flow-based1062.791076.851.00953.6951064.431076.850.88751.285
node-based1033.411084.993.861912.6331037.931068.092.381745.364

Table 2. Effect of valid inequalities on six small-size instances.

ILS Parameter Tuning

The ILS procedure adopts four main parameters (i.e., α\alpha, β\beta, γ\gamma and maxitermaxiter). To set their values, we randomly selected six instances (two with $0 \le n \le 20$, two with 50≤n≤10050 \le n \le100, and two with n=200n = 200). We then tested the ILS on these instances by attempting all possible combinations of parameter values chosen in the sets α∈{0.05,0.10,0.15,0.25}\alpha\in\{0.05, 0.10, 0.15, 0.25\}, β∈{2,5,10,20}\beta\in\{2, 5, 10, 20\}, γ∈{50,100}\gamma\in\{50, 100\} and $maxiter \in

{200, 500, 1000, 5000}. The results are reported in Table 3. For each combination of parameters, column “t(s)” gives the average ILS run time on the six instances, and column “%gap” gives the average gap computed as the average over the six instances of 100(z−z∗)/z∗100(z-z^*)/z^*. Here, zz is the value of the solution obtained by the given configuration and z∗z^* is the value of the best solution obtained by all configurations.

(α,β)(\alpha,\beta)\multicolumn{2}{c}{(50, 200)}\multicolumn{2}{c}{(50, 500)}\multicolumn{2}{c}{(50, 1000)}\multicolumn{2}{c}{(50, 5000)}\multicolumn{2}{c}{(100, 200)}\multicolumn{2}{c}{(100, 500)}\multicolumn{2}{c}{(100, 1000)}\multicolumn{2}{c}{(100, 5000)}
t(s)%gapt(s)%gapt(s)%gapt(s)%gapt(s)%gapt(s)%gapt(s)%gapt(s)%gap
(0.05,2)1.530.911.790.872.130.842.790.821.560.831.800.791.890.783.280.77
(0.05,5)1.670.761.830.752.270.732.910.721.790.751.900.742.020.743.490.73
(0.05,10)1.910.762.180.742.660.733.410.722.080.732.190.732.260.733.910.71
(0.05,20)1.730.761.930.742.340.732.860.722.200.732.350.722.430.694.670.69
(0.10,2)2.090.082.330.032.680.023.580.011.910.131.970.112.090.102.580.10
(0.10,5)2.740.083.250.024.020.005.440.002.060.112.380.072.890.063.280.05
(0.10,10)3.130.084.060.025.040.006.470.002.490.072.610.073.050.063.390.05
(0.10,20)3.570.084.530.025.230.008.020.002.840.073.110.063.240.063.460.05
(0.15,2)1.830.432.060.392.300.383.120.352.040.382.370.352.490.353.120.35
(0.15,5)2.490.402.860.383.130.355.080.352.330.362.590.353.200.344.850.33
(0.15,10)3.350.403.880.384.160.356.370.352.480.353.790.334.110.335.090.33
(0.15,20)4.550.405.020.385.230.358.640.352.710.354.260.334.820.335.940.32
(0.25,2)2.251.342.641.073.300.944.560.922.210.882.270.862.840.864.190.86
(0.25,5)2.541.182.930.914.050.895.620.892.680.863.160.853.740.854.800.83
(0.25,10)3.001.163.940.904.940.867.330.863.520.834.860.826.070.827.830.82
(0.25,20)3.721.165.120.906.310.868.890.864.670.836.130.826.630.828.460.82

Table 3. ILS parameter tuning. Best configuration in boldface.

The configuration with α=0.10\alpha= 0.10, β=5\beta= 5, γ=50\gamma= 50 and maxiter=1000maxiter = 1000 is the one that obtained the best results (highlighted in bold in the table). It could always achieve the best solution values, at the expense of a limited increase in the computing time with respect to configurations adopting a smaller number of iterations. This configuration was thus adopted for all successive ILS tests.

ILS Evaluation

In this section, we investigate the performance of the ILS. In Table 4, the results of the ILS are compared with those obtained by the best mathematical model (i.e., the flow-based one) on groups of three instances per line. We recall that column “zubz_{ub}” gives the average upper bound value, column “opt” the number of proven optimal solutions, and column “t(s)” the average run time. The ILS was executed

∣V1∪V2∣|V_1 \cup V_2|∣V2∣|V_2|∣V3∣|V_3|∣K∣|K|zubz_{ub}t(s)optzbestz_{best}zavgz_{avg}zworstz_{worst}σz\sigma_zt(s)
10111706.391.133706.39706.39706.390.000.00
10112730.913.263730.91730.91730.910.000.00
10211743.253.133743.25743.25743.250.000.00
10212793.759.453793.75793.75793.750.000.00
10221803.9616.733803.96803.96803.960.000.00
10222833.7875.013833.78833.78833.780.000.00
sum/avg (10)768.6718.1218768.67768.67768.670.000.00
153221036.61509.7131036.611036.611036.610.000.14
153231049.451325.6831049.451049.451049.450.000.22
153321114.681104.1031114.681114.681114.680.000.14
153331160.741358.6021155.961155.961155.960.000.24
154221036.61510.8131036.611036.611036.610.000.16
154231084.121108.5631084.121084.121084.120.000.22
154321149.801420.9821146.561146.561146.560.000.20
154331202.401430.5121202.401202.401202.400.000.27
sum/avg (15)1104.301096.12211103.301103.301103.300.000.20
202221277.821354.8621275.441275.441275.440.000.26
202231329.121458.5321316.031316.031316.030.000.33
203221269.711271.0721262.521262.521262.520.000.35
203231301.731127.6331301.731301.731301.730.000.41
203321296.612661.6411277.251277.251277.250.000.35
203331321.84tlim01301.371301.371301.370.000.61
205321280.432986.7911265.461265.461265.460.000.33
205331322.702863.5711303.931303.931303.930.000.73
sum/avg (20)1300.002165.51121287.971287.971287.970.000.42
overall sum/avg1083.931190.99511079.191079.191079.190.000.23

Table 4. Computational results on small-size instances (three inst. per line). The flow-based method was run five times on each instance. We report the best, average and worst solution values achieved, as well as their standard deviation, in columns “zbestz_{best}”, “zavgz_{avg}”, “zworstz_{worst}” and “σz\sigma_z”, respectively. More in detail, zbestz_{best} gives the average of the best solution values produced on the three instances, zavgz_{avg} the average of the average values, and zworstz_{worst} the average of the worst values. The average computational time is shown in column “t(s)”.

According to the results, for those groups of three instances that were all solved to optimality by the flow-based model, the ILS obtained the same optimal values in a shorter computational time. For all the remaining small-size sets, the ILS achieved better values than the flow-based model (without proof of their optimality). In addition, the constantly null average standard deviation among the different runs indicates the robustness of the algorithm on these very simple instances. When comparing the average run times, we can notice that the ILS needed an overall average time of just 0.23 seconds against the 1,190.99 seconds of the flow-based model.

In Table 5, we report the results of the ILS on medium- and large-size instances. On instances having ∣V1∪V2∣=50|V_1 \cup V_2| = 50 the average standard deviation is 0.00, on those having ∣V1∪V2∣=100|V_1 \cup V_2| = 100 it becomes 0.50, while on those having ∣V1∪V2∣=200|V_1 \cup V_2| = 200 it increases to 0.92, thus resulting in an overall average standard deviation of 0.47. This confirms the robustness of the algorithm. Concerning the run time, the ILS took on average 1.91 seconds to solve instances having ∣V1∪V2∣=50|V_1 \cup V_2| = 50, 8.60 seconds for those having ∣V1∪V2∣=100|V_1 \cup V_2| = 100, and 13.02 seconds for those having ∣V1∪V2∣=200|V_1 \cup V_2| = 200. The overall average run time is 7.84 seconds, proving that the method is suitable for a quick use in practical situations.

∣V1∪V2∣|V_1 \cup V_2|∣V2∣|V_2|∣V3∣|V_3|∣K∣|K|zbestz_{\mathrm{best}}zavgz_{\mathrm{avg}}zworstz_{\mathrm{worst}}σz\sigma_zt(s)
505552583.272583.272583.270.001.17
505582721.902721.902721.900.001.59
508852883.072883.072883.070.001.67
508883001.703001.703001.700.002.10
5010552664.022664.022664.020.002.09
5010582807.412807.412807.410.002.19
5010852863.642863.642863.640.001.91
5010883003.073003.073003.070.002.52
avg (50)2816.012816.012816.010.001.91
10055104430.654430.924431.530.407.61
10055154642.244642.454643.130.398.29
100105104507.074507.274508.070.457.19
100105154750.734750.924751.650.418.17
1001010104856.944857.164857.990.479.03
1001010155062.415062.625063.430.459.43
1001510104826.284826.624827.960.759.18
1001510155070.195070.505071.740.699.90
avg (100)4768.314768.564769.440.508.60
2001010158244.398244.978246.120.829.86
2001010208636.538637.118638.330.8410.34
2002010158550.638551.328552.620.9812.27
2002010208814.418815.008816.050.8213.29
2002020159128.909129.639130.630.8213.66
2002020209305.359305.989307.130.8114.96
2003020159372.609373.869375.171.1614.05
2003020209497.209498.209499.671.1015.70
avg (200)8943.758944.518945.720.9213.02
overall avg5509.365509.695510.390.477.84

Table 5. Computational results on medium- and large-size instances (three inst. per line)

Finally, Table 6 reports a sensitivity analysis on the average percentage of computational time needed by each ILS component, grouped by set of instances. On the small-size sets, LS2 and LS3 are the most time-consuming local search procedures, while for medium- and large-size sets the largest effort is required by LS1 and LS4.

SetLS1LS2LS3LS4LS5S1S2
Small-size3.63%39.41%28.65%6.37%20.50%0.37%1.07%
Medium-size59.50%9.02%1.30%18.36%10.69%0.23%0.89%
Large-size50.03%3.48%3.33%32.35%9.98%0.13%0.71%

Table 6. Percentage of the computational time needed by each ILS component

Results on Realistic Instances

The flow-based model and the ILS were also tested on a set of realistic instances generated from the WDN in the city of Mashhad (Iran). Our real case study consists of 3,124 households/shops, 293 reservoirs/tanks, 356 wells and 14 treatment plants. For all of these nodes the exact locations were collected.

Following the same rationale described in § 6.1, we generated 108 realistic instances divided into two sets of small-size and medium- and large-size instances, each comprising different subsets having homogeneous values of ∣V1∪V2∣|V_1 \cup V_2|, (∣V2∣,∣V3∣)(|V_2|, |V_3|), and ∣K∣|K|, and composed by three random instances per subset. The resulting sets are:

  • Small-size: 12 instances with ∣V1∪V2∣=10|V_1 \cup V_2|=10, (∣V2∣,∣V3∣)∈{(1,1),(2,1),(2,2)}(|V_2|, |V_3|) \in\{(1,1), (2,1), (2,2)\}, and ∣K∣∈{1,2}|K| \in\{1,2\}; 12 instances with ∣V1∪V2∣=15|V_1 \cup V_2|=15, (∣V2∣,∣V3∣)∈{(1,1),(2,1),(2,2)}(|V_2|, |V_3|) \in\{(1,1), (2,1), (2,2)\}, and ∣K∣∈{1,2,3}|K| \in\{1,2,3\}; 12 instances with ∣V1∪V2∣=20|V_1 \cup V_2|=20, (∣V2∣,∣V3∣)∈{(1,1),(2,1),(2,2)}(|V_2|, |V_3|) \in\{(1,1), (2,1), (2,2)\}, and ∣K∣∈{2,3}|K| \in\{2,3\};

  • Medium- and large-size: 12 instances with ∣V1∪V2∣=40|V_1 \cup V_2|=40, (∣V2∣,∣V3∣)∈{(4,2),(4,3),(6,2),(6,3)}(|V_2|, |V_3|) \in\{(4,2), (4,3), (6,2), (6,3)\}, and ∣K∣∈{2,3}|K| \in\{2,3\}; 12 instances with ∣V1∪V2∣=50|V_1 \cup V_2|=50, (∣V2∣,∣V3∣)∈{(4,2),(4,3),(6,2),(6,3)}(|V_2|, |V_3|) \in\{(4,2), (4,3), (6,2), (6,3)\}, and ∣K∣∈{2,3}|K| \in\{2,3\}; 12 instances with ∣V1∪V2∣=60|V_1 \cup V_2|=60, (∣V2∣,∣V3∣)∈{(4,2),(4,3),(6,2),(6,3)}(|V_2|, |V_3|) \in\{(4,2), (4,3), (6,2), (6,3)\}, and ∣K∣∈{2,3}|K| \in\{2,3\}; 12 instances with ∣V1∪V2∣=100|V_1 \cup V_2|=100, (∣V2∣,∣V3∣)∈{(8,4),(8,5),(10,4),(10,5)}(|V_2|, |V_3|) \in\{(8,4), (8,5), (10,4), (10,5)\}, and ∣K∣∈{4,5}|K| \in\{4,5\}; 12 instances with ∣V1∪V2∣=150|V_1 \cup V_2|=150, (∣V2∣,∣V3∣)∈{(8,4),(8,5),(10,4),(10,5)}(|V_2|, |V_3|) \in\{(8,4), (8,5), (10,4), (10,5)\}, and ∣K∣∈{4,5}|K| \in\{4,5\}; 12 instances with ∣V1∪V2∣=200|V_1 \cup V_2|=200, (∣V2∣,∣V3∣)∈{(8,4),(8,5),(10,4),(10,5)}(|V_2|, |V_3|) \in\{(8,4), (8,5), (10,4), (10,5)\}, and ∣K∣∈{4,5}|K| \in\{4,5\}.

For each instance, the coordinates of the nodes were randomly selected among the given real locations. The flow-based model and the ILS were used to run the experiments. The results are reported in the Table 7 and Table 8. In Table 7, the results of the ILS are compared with those obtained by the flow-based model. We recall that columns “zub”, “t(s)” and “opt” give the average upper bound value, the average run time and the total number of instances solved to proven optimality by the mathematical model, respectively. Note that an entry “tlim” indicates that the time limit of 3,600 CPU seconds was reached for all the three instances in the group. Conversely, columns “zbest”, “zavg”, “zworst”, “σz” and “t(s)” give the best, average and worst solution values, the standard deviation and the computational time of the ILS, respectively.

∣V1∪V2∣|V_1 \cup V_2|∣V2∣|V_2|∣V3∣|V_3|∣K∣|K|zubz_{ub}t(s)optzbestz_{best}zavgz_{avg}zworstz_{worst}σz\sigma_zt(s)
1011182475.7512.69382475.7582475.7582475.750.000.00
1011280629.798.95380629.7980629.7980629.790.000.00
10211121874.445.533121874.44121874.44121874.440.000.00
10222116649.98135.453116649.98116649.98116649.980.000.00
sum/avg (10)100407.4940.6612100407.49100407.49100407.490.000.00
1511197874.841218.80297874.8497874.8497874.840.000.05
15112186943.9846.033186943.98186943.98186943.980.000.08
15212126742.541204.462126742.54126742.54126742.540.000.12
15223135254.032437.791135254.03135254.03135254.030.000.12
sum/avg (15)136703.851226.778136703.85136703.85136703.850.000.09
20112158682.881205.872158588.73158588.73158588.730.000.18
20113175830.703342.991175655.43175655.43175655.430.000.20
20212170015.901466.863170015.90170015.90170015.900.000.20
20223188935.98tlim0187949.09187949.09187949.090.000.26
sum/avg (20)173366.362403.936173052.29173052.29173052.290.000.21
overall sum/avg136825.901223.7926136721.21136721.21136721.210.000.10

Table 7. Computational results on realistic small-size instances (three inst. per line)

∣V1∪V2∣|V_1 \cup V_2|∣V2∣|V_2|∣V3∣|V_3|∣K∣|K|zbestz_{best}zavgz_{avg}zworstz_{worst}σz\sigma_zt(s)
40422180613.80180613.80180613.800.000.78
40433219227.54219227.54219227.540.000.79
40622195113.71195113.71195113.710.000.85
40633201338.25201338.25201338.250.000.84
avg (40)199073.33199073.33199073.330.000.82
50422250479.23250479.23250479.230.000.97
50433278476.01278476.01278476.010.000.97
50622263769.77263769.77263769.770.001.18
50633293179.73293179.73293179.730.001.28
avg (50)271476.19271476.19271476.190.001.10
60422263976.92263976.92263976.920.001.67
60433264029.28264029.28264029.280.001.73
60622222473.25222473.25222473.250.002.07
60633291979.18291979.18291979.180.002.35
avg (60)260614.66260614.66260614.660.001.96
100844399442.47399442.63399443.140.306.41
100855438923.85438923.90438924.050.097.38
1001044344216.84344217.11344217.640.387.72
1001055376473.23376473.42376473.860.287.78
avg (100)389764.10389764.27389764.670.267.32
150844438156.93438157.42438158.640.729.64
150855440416.07440416.44440417.480.618.85
1501044466864.57466864.99466866.190.7010.54
1501055569988.53569988.92569990.110.6810.17
avg (150)478856.53478856.94478858.110.689.80
200844491986.12491986.81491988.100.8610.76
200855495553.12495553.59495555.140.889.82
2001044646227.25646227.71646228.810.7111.93
2001055696373.63696374.24696375.290.7311.80
avg (200)582535.03582535.58582536.830.7911.08
overall avg363719.97363720.16363720.630.295.35

Table 8. Comp. results on realistic medium- and large-size instances (three inst. per line)

We can notice that on small-size instances, the flow-based model and the ILS obtained the same optimal values on instances having ∣V1∪V2∣∈{10,15}|V_1 \cup V_2| \in\{10,15\}, and on one subset out of four of instances having ∣V1∪V2∣=20|V_1 \cup V_2|=20. For the remaining subsets, the ILS achieved better values than the flow-based model (again, without proof of their optimality).

On medium- and large-size instances, the ILS achieved very robust results on instances having ∣V1∪V2∣∈{40,50,60}|V_1 \cup V_2| \in\{40, 50, 60\}. Indeed, the standard deviation is constantly null for all the subgroups, and the run times are very short. The robustness of the ILS slightly decreases for instances having ∣V1∪V2∣∈{100,150,200}|V_1 \cup V_2| \in\{100, 150, 200\}, however remaining acceptable for a practical use. For these instances, the average run times are around 7.32, 9.80 and 11.08 seconds, respectively, thus confirming that the algorithm could efficiently solve realistic instances having a considerable number of nodes in a few seconds.

Conclusions

In this paper, we introduced a generalization of the well-known Vehicle Routing Problem (VRP), called VRP for Water Distribution Networks (VRPWDN), that includes precedence constraints among nodes and multiple visits to some of the nodes. The problem is NP-hard in the strong sense and, to the best of our knowledge, has not yet been applied in the context of distribution networks where regular inspections have to be performed to detect potential sources of contamination. To solve the VRPWDN, three alternative mathematical models (time-based, flow-based and node-based) were proposed, and an Iterated Local Search (ILS) algorithm was developed.

Extensive computational tests on randomly generated small-size instances were

performed to compare the performance of the three mathematical models, showing that the flow-based model outperforms the other two in terms of solution quality and speed. On the same instances, the accuracy of the ILS in finding good-quality solutions in a short time was proved. The ILS was also used to perform a series of tests on randomly generated medium- and large-size instances with up to 200 nodes, confirming its efficacy and robustness.

Additional computational tests were executed on small-, medium-, and large-size realistic instances derived from the Mashhad (Iran) distribution network, proving that our methods can be applied with profit even in a practical case.

Interesting future research directions include the application of the developed techniques to other related VRPs with precedence constraints and multiple visits. In addition, we are interested in studying the generalization of the VRPWDN to the case of multiple periods. In this generalization, one should first of all determine in which day inspecting the given nodes, and then creating the routes for each day.

Acknowledgements

This work was supported in part by Research Deputy of Ferdowsi University of Mashhad, under Grant No. 48185, and by University of Modena and Reggio Emilia, under grant FAR 2021. This support is gratefully acknowledged.

References

  1. [1]Allahyari, S., Salari, M., and Vigo, D. (2015). A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem. European Journal of Operational Research, 242(3):756–768.DOI
  2. [2]Atefi, R., Salari, M., Coelho, L. C., and Renaud, J. (2018). The open vehicle routing problem with decoupling points. European Journal of Operational Research, 265(1):316–327.DOI
  3. [3]Aziez, I., Côté, J.-F., and Coelho, L. C. (2020). Exact algorithms for the multi-pickup and delivery problem with time windows. European Journal of Operational Research, 284(3):906–919.
  4. [4]Balas, E., Fischetti, M., and Pulleyblank, W. R. (1995). The precedence-constrained asymmetric traveling salesman polytope. Mathematical Programming, 68(1):241–265.DOI
  5. [5]Battarra, M., Cordeau, J.-F., and Iori, M. (2014). Chapter 6: Pickup-and-delivery problems for goods transportation. In Toth, P. and Vigo, D., editors, Vehicle Routing: Problems, Methods, and Applications, Second Edition, pages 161–191. SIAM.DOI
  6. [6]Bektaş, T. and Gouveia, L. (2014). Requiem for the Miller–Tucker–Zemlin subtour elimination constraints? European Journal of Operational Research, 236(3):820–832.DOI
  7. [7]Bruck, B. P. and Iori, M. (2017). Non-elementary formulations for single vehicle routing problems with pickups and deliveries. Operations Research, 65(6):1597–1614.DOI
  8. [8]de Winter, C., Palleti, V., Worm, D., and Kooij, R. (2019). Optimal placement of imperfect water quality sensors in water distribution networks. Computers & Chemical Engineering, 121:200–211.
  9. [9]Desaulniers, G., Madsen, O. B., and Ropke, S. (2014). Chapter 5: The vehicle routing problem with time windows. In Toth, P. and Vigo, D., editors, Vehicle Routing: Problems, Methods, and Applications, Second Edition, pages 119–159. SIAM.DOI
  10. [11]Doerner, K. F. and Salazar-González, J.-J. (2014). Chapter 7: Pickup-and-delivery problems for people transportation. In Toth, P. and Vigo, D., editors, Vehicle Routing: Problems, Methods, and Applications, Second Edition, pages 193–212. SIAM.DOI
  11. [12]Furtado, M. G. S., Munari, P., and Morabito, R. (2017). The pickup and delivery problem with time windows in the oil industry: model and branch-and-cut methods. Gestão & Produção, 24:501–513.
  12. [13]Haddadene, S. R. A., Labadie, N., and Prodhon, C. (2016). A GRASP × ILS for the vehicle routing problem with time windows, synchronization and precedence constraints. Expert Systems with Applications, 66:274–294.DOI
  13. [14]Hanafi, S., Mansini, R., and Zanotti, R. (2020). The multi-visit team orienteering problem with precedence constraints. European Journal of Operational Research, 282(2):515–529.DOI
  14. [15]Hernández-Pérez, H., Landete, M., and Rodriguez-Martin, I. (2021). The single-vehicle two-echelon one-commodity pickup and delivery problem. Computers & Operations Research, 127:105152.DOI
  15. [16]Kara, I. (2011). Arc based integer programming formulations for the distance constrained vehicle routing problem. In 3rd IEEE International Symposium on Logistics and Industrial Informatics, pages 33–38. IEEE.DOI
  16. [17]Karaoglan, I., Altıparmak, F., Kara, I., and Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4):465–477.DOI
  17. [19]Lourenço, H. R., Martin, O. C., and Stützle, T. (2019). Iterated local search: Framework and applications. In Potvin, J.-Y. and Gendreau, M., editors, Handbook of Metaheuristics, Third Edition, pages 129–168. Springer.
  18. [20]Moon, C., Kim, J., Choi, G., and Seo, Y. (2002). An efficient genetic algorithm for the traveling salesman problem with precedence constraints. European Journal of Operational Research, 140(3):606–617.
  19. [21]Mor, A. and Speranza, M. G. (2022). Vehicle routing problems over time: a survey. Annals of Operations Research, pages 1–21.
  20. [22]Mukherjee, R., Diwekar, U. M., and Vaseashta, A. (2017). Optimal sensor placement with mitigation strategy for water network systems under uncertainty. Computers & Chemical Engineering, 103:91–102.DOI
  21. [23]Naji-Azimi, Z. and Salari, M. (2014). The time constrained maximal covering salesman problem. Applied Mathematical Modelling, 38(15-16):3945–3957.
  22. [24]Naserizade, S. S., Nikoo, M. R., and Montaseri, H. (2018). A risk-based multi-objective model for optimal placement of sensors in water distribution system. Journal of Hydrology, 557:147–159.DOI
  23. [25]Pereira, D. L., Alves, J. C., and Moreira, M. C. d. O. (2020). A multiperiod workforce scheduling and routing problem with dependent tasks. Computers & Operations Research, 118:104930.DOI
  24. [26]Quttineh, N.-H., Larsson, T., Lundberg, K., and Holmberg, K. (2013). Military aircraft mission planning: a generalized vehicle routing model with synchronization and precedence. EURO Journal on Transportation and Logistics, 2(1-2):109–127.DOI
  25. [27]Rathi, S. and Gupta, R. (2014). Sensor placement methods for contamination detection in water distribution networks: A review. Procedia Engineering, 89:181–188.DOI
  26. [28]Razali, N. M. (2015). An efficient genetic algorithm for large scale vehicle routing problem subject to precedence constraints. Procedia - Social and Behavioral Sciences, 195:1922–1931.
  27. [29]Sabouhi, F., Bozorgi-Amiri, A., Moshref-Javadi, M., and Heydari, M. (2019). An integrated routing and scheduling model for evacuation and commodity distribution in large-scale disaster relief operations: a case study. Annals of Operations Research, 283(1):643–677.DOI
  28. [30]Salman, R., Ekstedt, F., and Damaschke, P. (2020). Branch-and-bound for the precedence constrained generalized traveling salesman problem. Operations Research Letters, 48(2):163–166.
  29. [31]Sarin, S. C., Sherali, H. D., and Bhootra, A. (2005). New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Operations Research Letters, 33(1):62–70.DOI
  30. [32]Seok Jeong, H. and Abraham, D. M. (2006). Operational response model for physically attacked water networks using NSGA-II. Journal of Computing in Civil Engineering, 20(5):328–338.DOI
  31. [33]Sigurd, M., Pisinger, D., and Sig, M. (2004). Scheduling transportation of live animals to avoid the spread of diseases. Transportation Science, 38(2):197–209.DOI
  32. [34]Silva, M. M., Subramanian, A., and Ochi, L. S. (2015). An iterated local search heuristic for the split delivery vehicle routing problem. Computers & Operations Research, 53:234–249.
  33. [35]Sun, P., Veelenturf, L. P., Dabia, S., and Van Woensel, T. (2018). The time-dependent capacitated profitable tour problem with time windows and precedence constraints. European Journal of Operational Research, 264(3):1058–1073.DOI
  34. [36]Toth, P. and Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. SIAM, 2nd edition.
  35. [37]Vansteenwegen, P., Souffriau, W., Berghe, G. V., and Van Oudheusden, D. (2009). Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36(12):3281–3290.
  36. [38]Wolfinger, D. and Salazar-González, J.-J. (2021). The pickup and delivery problem with split loads and transshipments: A branch-and-cut solution approach. European Journal of Operational Research, 289(2):470–484.DOI
  37. [39]World Health Organization (2019). Drinking-water fact sheet.
  38. [40]Zhang, Q., Wu, Z. Y., Zhao, M., Qi, J., Huang, Y., and Zhao, H. (2016). Leakage zone identification in large-scale water distribution systems using multiclass support vector machines. Journal of Water Resources Planning and Management, 142(11):04016042.

Paper details

vlnc:W_hdf8d4ve
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents