Solution of a practical vehicle routing problem for monitoring water distribution networks
研究了供水管网监测中技术人员需取还钥匙的车辆路径问题，提出了混合整数线性规划模型和迭代局部搜索算法，并通过随机和真实实例验证了效率。
In this work, we introduce a generalisation of the 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 centre. The key must then be returned to the same key centre after the test has been performed, thus introducing precedence constraints and multiple visits in the routes. To solve the problem, a Mixed Integer Linear Programming model 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 and real-world instances.