An equi-model matheuristic for the multi-depot ring star problem

In the multi-depot ring star problem (MDRSP) a set of customers has to be connected to a set of given depots by ring stars. Such a ring star is a cycle graph, also called a ring, with some additional nodes assigned to its nodes by single star edges. Optional Steiner nodes can be used in the network as intermediate nodes on the rings. Depot dependant capacity limits apply to both, the number of customers in each ring star and the number of ring stars connected to a depot. The MDRSP asks for a network such that the sum of the edge costs is minimized. In this paper we present a matheuristic that iteratively refines a solution network in a locally exact fashion. In contrast to existing approaches the optimization model that is used to explore the various structural multi-exchange neighborhoods in our algorithm is the MDRSP itself. A first class of neighborhoods considers local sub-networks for optimal improvements. Through an advanced modeling technique we are able to refine arbitrary sub-networks of suitable size induced by simple node sets. A second class aims at globally restructuring the current network after the application of different contraction techniques. For both purposes we develop an exact branch & cut algorithm for the MDRSP that efficiently solves the local optimization problems to optimality, if they are chosen reasonably in terms of size and complexity. The eciency of the approach is shown by computational results improving known upper bounds for instance classes from the literature containing up to 1000 nodes. 91% of the known best objective values are improved up to 13% in competitive computational time.