A Heuristic Algorithm for solving a large-scale real-world territory design problem. (September 2021) - Zhou, Lin; Zhen, Lu; Baldacci, Roberto; Boschetti, Marco; Dai, Ying; Lim, Andrew
Highlights: We consider a territory design problem in the dairy industry. We design an efficient, iterated hybrid genetic algorithm. We present extensive computational results involving more than 1000 customers. We explore managerial findings by studying trade-offs between service requirements. Abstract: In this work, we present and evaluate heuristic techniques for a real-world territory design problem of a major dairy company which produces and distributes perishable products. The problem calls for grouping customers into geographic districts, with the objective of minimising the total operational cost, computed as a function of the fixed costs of the districts and the routing costs. Two inter-connected decision levels have to be tackled: partitioning customers into districts and routing vehicles according to complex operational constraints. To solve the problem, a hybrid multi-population genetic algorithm is designed, enhanced with several evolution and search techniques. The proposed design is extensively tested on instances derived from the literature and on real-world large-scale instances, involving more than 1000 customers. The results show the effectiveness of the different components of the algorithm and the feedback from the company's planners confirms that it produces high-quality, operational solutions. Additionally, we explore some managerial findings with respect to the adoption of alternative objectives and service requirements.