An exact and computationally efficient algorithm for balanced customer clustering under relocation constraints

Abstract In logistics, customer clusters are often predefined based on geographic locations to optimize resource management and workload distribution. However, this approach frequently leads to significant cluster imbalance, particularly when not all customers require daily service or when operational constraints restrict the possibility of reallocating customers across clusters. These imbalances may affect workload equity, routing efficiency, and overall service performance. This paper addresses the problem of balancing customer clusters under relocation constraints by introducing two alternative criteria for measuring imbalance and enforcing them within a constrained reassignment framework. Our goal is to redistribute the set of customers so as to construct new clusters whose cardinalities are as balanced as possible while fully respecting the reassignment limitations. After formulating both nonlinear optimization models, we propose an exact algorithm that systematically reallocates customers through sequences of feasible moves, thereby ensuring progress toward a balanced configuration. We provide formal proofs showing that the algorithm always converges to an optimal solution for both imbalance criteria after a finite number of iterations. From these results, it follows that both models yield the same optimal solution. In addition, computational experiments demonstrate the efficiency of the method, showing that optimal solutions are obtained with very low running times for large-scale instances.