Aesthetic considerations for the min-max K-Windy Rural Postman Problem

作者：Corberan Angel; Golden Bruce; Lum Oliver^*; Plana Isaac; Sanchis Jose M

来源：Networks, 2017, 70(3): 216-232.

DOI：10.1002/net.21748

• arc routing problems
• min-max objective
• aesthetic objective
• multi-objective problems

The aesthetic quality of routes is a feature of route planning that is of practical importance, but receives relatively little attention in the literature. Several practitioners have pointed out that the visual appeal of a proposed set of routes can have a strong influence on the willingness of a client to accept or reject a specific routing plan. While some work has analyzed algorithmic performance relative to traditional min-sum or min-max objective functions and aesthetic objective functions, we are not aware of any work that has considered a multi-objective approach. This work considers a multi-objective variant of the Min-Max K-Vehicles Windy Rural Postman Problem, discusses several formulations of the problem, and presents computational experiments with a heuristic algorithm. After exploring several formulations, we choose to study the problem with a bi-objective function that includes contributions from the route overlap index and average task distance aesthetic measures. The heuristic extends the cluster-first procedure presented in Lum et al. (Networks 69 (2017), 290-303) by incorporating the new objective function into the improvement phase and adding a perturbation routine.

• 出版日期2017-10