Arc routing with trip-balancing and attractiveness measures — A waste collection case study
研究了葡萄牙塞沙尔市的门到门垃圾收集问题，将其建模为混合容量弧路径问题，提出结合GIS和数学启发式的方法生成平衡且紧凑的行程，并用新提出的加权外壳重叠度量评估解的实际吸引力。
This work focuses on a household (or door to door) waste collection problem in the Portuguese municipality of Seixal, which is modelled as a generalisation of a mixed capacitated arc routing problem (MCARP). The MCARP is known to be NP-hard. The proposed methodology uses: i) a GIS (geographic information system), for input/output and to reduce problem dimensions; ii) a matheuristic that iteratively solves a new hybrid model; and iii) two versions of a two-phase matheuristic. The latter pursues the generation of connected and compacted trips. During the first phase, called initial assignment, some links requiring service are assigned to vehicle services. In the second phase, the hybrid model finishes the assignment and generates a feasible set of trips. The quality of the generated solutions is assessed through the total time, as well as by some attractiveness measures. These measures evaluate the adequacy of the solutions for the real case-study, a crucial aspect for trips that need to be accepted by practitioners. With this purpose, a new attractiveness measure that introduces space dependent penalisation of overlaps, named weighted hull overlap, is also proposed. Computational results with 18 Seixal instances, with 265–1223 nodes and 492–2254 links, point to the good performance of the proposed methodology.