Aesthetic Considerations for the Min-Max K-Windy Rural Postman Problem

摘要

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 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 216-232 2017