Title: A tabu search algorithm for a capacitated clustering problem

Authors: Sudha Khambhampati; Prasad Calyam; Xinhui Zhang

Addresses: Department of Biomedical, Industrial and Human Factors Engineering, Wright State University, 3640 Colonel Glenn Hwy, Dayton, OH 45435, USA ' Department of Computer Science, University of Missouri, 221 Engineering Building West, Columbia, MO 65211, USA ' Department of Biomedical, Industrial and Human Factors Engineering, Wright State University, 3640 Colonel Glenn Hwy, Dayton, OH 45435, USA

Abstract: This paper investigates a clustering problem in a production and routing environment where a centralised facility uses a fleet of vehicles to serve a set of customers. A multi-period capacitated clustering problem is solved to partition customer into clusters with constraints that the accumulated customer demand in every period of the planning horizon is satisfied. The resulting mathematical model is hard to solve exactly and efficient heuristics are thus developed in this paper. The heuristics are based on the tabu search but include two novel features in the design of neighbourhood search; the first one is the dynamic combination of customers with close proximity into supernodes to eliminate ineffective moves and the second one is an ejection chain approach to perform composite moves of variable length from a series of simple moves. Computational results showed that they were able to provide superior solutions, especially in certain cases of tight capacity constraints.

Keywords: capacitated clustering; heuristics; supernode; ejection chain; tabu search.

DOI: 10.1504/IJOR.2018.095627

International Journal of Operational Research, 2018 Vol.33 No.3, pp.387 - 412

Received: 24 Jul 2015
Accepted: 04 Dec 2015
Published online: 16 Oct 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article