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

**Authors:** Reza Atefi, Manuel Iori, Majid Salari, Dario Vezzali  
**arXiv:** [2202.02549](https://arxiv.org/abs/2202.02549)  
**Date:** 2022-02-05  
**Summary page:** https://www.summarizepaper.com/en/paper/2202.02549v2/

## Key points

- Generalization of the Vehicle Routing Problem (VRP) for monitoring Water Distribution Networks (WDNs)
- Involves multiple technicians visiting a sequence of nodes in the WDN for water quality tests
- Special nodes require collection and return of keys from a key center, introducing precedence constraints and multiple visits in routes
- Implemented three mathematical models and an Iterated Local Search (ILS) algorithm to solve the problem
- Computational tests on randomly created instances and real-world case study instances demonstrate efficiency of methods
- Proposed valid inequalities improve model performance by reducing average percentage gap and execution time while increasing optimal solutions
- Parameter tuning conducted for ILS procedure to optimize performance for larger instances
- Provides valuable insights into addressing routing problems in water distribution network monitoring applications through efficient models and algorithms that consider precedence constraints and multiple visits at specific nodes.

## Summary

We present a generalization of the well-known Vehicle Routing Problem (VRP) for monitoring Water Distribution Networks (WDNs). The problem involves multiple technicians who must visit a sequence of nodes in the WDN to perform water quality tests. Special nodes, such as wells, require technicians to first collect and return keys from a key center before and after the test, introducing precedence constraints and multiple visits in routes. To solve this problem, we implemented three mathematical models and an Iterated Local Search (ILS) algorithm. Computational tests on randomly created instances and real-world case study instances demonstrate the efficiency of these methods. We also assessed the performance of proposed valid inequalities by solving six small-size instances using all three models with and without them. Results show that adding valid inequalities improves model performance by reducing average percentage gap and execution time while increasing optimal solutions. Additionally, we conducted parameter tuning for the ILS procedure on six selected instances to optimize its performance for larger instances. This work provides valuable insights into addressing routing problems in water distribution network monitoring applications through efficient models and algorithms that consider precedence constraints and multiple visits at specific nodes.