Districting for Arc Routing
Districting for Arc Routing
复制标题
DOI：
10.1287/ijoc.2014.0600
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Alex Butsch;J. Kalcsics;G. Laporte
中科院分区：
文献类型：
--
作者：
Alex Butsch;J. Kalcsics;G. Laporte
本文提出了一种在弧线路由背景下引起的区域问题的启发式方法。目的是通过与细胞相反的图形边缘合并边缘来设计区。解决方案必须满足两个硬标准（完整的，独家的分配以及连接性）和几个软标准（平衡，小的挂钩，局部紧凑性和全球紧凑性）。后一个标准被合并为一个加权目标。拟议的启发式方法采用了施工程序，然后采用禁忌搜索改进阶段，在该阶段中，根据轮盘架机制定义并选择了几个子例程，如自适应大型邻里搜索。对从实际街道数据得出的实例进行的广泛测试证实了拟议方法的效率。
This paper proposes a heuristic for districting problems arising in an arc routing context. The aim is to design districts by amalgamating edges of a graph as opposed to cells. Solutions must satisfy two hard criteria (complete and exclusive assignment as well as connectedness) and several soft criteria (balance, small deadheading, local compactness, and global compactness). The latter criteria are amalgamated into a weighted objective. The proposed heuristic applies a construction procedure followed by a tabu search improvement phase in which several subroutines are defined and selected according to a roulette wheel mechanism, as in adaptive large neighborhood search. Extensive tests conducted on instances derived from real-world street data confirm the efficiency of the proposed methodology.