Publisher DOI: 10.1002/net.21674
Title: An equi-model matheuristic for the multi-depot ring star problem
Language: English
Authors: Hill, Alessandro 
Voß, Stefan 
Keywords: hybrid heuristic;·branch & cut;local refinement;matheuristic;multi-depot ring star problem;network design
Issue Date: 1-May-2016
Source: Networks 3 (67): 222-237 (2016-05-01)
Journal or Series Name: Networks 
Abstract (english): 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 article, we present a matheuristic that iteratively refines a solution network in a locally exact fashion. In contrast to existing approaches, we define an equi-model matheuristic. That is a refinement method in which the subproblems are modeled as smaller instances of the global problem. Hence 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 subnetworks for optimal improvements. Through an advanced modeling technique, we are able to refine arbitrary subnetworks 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. Ninety-one percent of the known best objective values are improved up to 13% in competitive computational time.
ISSN: 1097-0037
Institute: Maritime Logistik W-12 
Type: (wissenschaftlicher) Artikel
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on May 30, 2020

Google ScholarTM


Add Files to Item

Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.