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.
翻译:在这项工作中,我们为监测供水网(WDN)的特定应用而将众所周知的车辆路由问题加以概括化。在此问题上,多名技术人员必须访问WDN的节点序列,并进行一系列测试以检查水质。一些特殊节点(即井)要求技术人员首先从一个关键中心收集钥匙。然后,在进行测试之后,钥匙必须返回同一关键中心,从而在线路上引入优先限制和多次访问。为了解决问题,已经实施了三个数学模型和一个迭代本地搜索。建议的方法的效率通过对随机生成的事例以及从现实世界案例研究中得出的事例进行广泛的计算测试得到证明。