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

Alessandro Hill and Stefan VOß

Working Papers from University of Antwerp, Faculty of Business and Economics

Abstract: 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 dependent 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 efficiency 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.

Keywords: Multi-depot ring star problem; Hybrid heuristic; Branch & cut; Local refinement; Network design; Matheuristic (search for similar items in EconPapers)
Pages: 31 pages
Date: 2014-08
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://repository.uantwerpen.be/docman/irua/869471/145285.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ant:wpaper:2014015

Access Statistics for this paper

More papers in Working Papers from University of Antwerp, Faculty of Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().