Title
Multi-exchange neighborhoods for the capacitated ring tree problem Multi-exchange neighborhoods for the capacitated ring tree problem
Author
Faculty/Department
Faculty of Applied Economics
Publication type
conferenceObject
Publication
Berlin :Springer-verlag berlin ,
Subject
Mathematics
Computer. Automation
Source (journal)
NUMERICAL METHODS AND APPLICATIONS (NMA 2014)
Source (book)
8th International Conference on Numerical Methods and Applications (NMA), AUG 20-24, 2014, Borovets, BULGARIA
Volume/pages
8962(2015) , p. 85-94
ISSN
0302-9743
ISBN
978-3-319-15584-5
ISI
000355827600010
ISBN
978-3-319-15585-2
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
A ring tree is a tree graph with an optional additional edge that closes a unique cycle. Such a cycle is called a ring and the nodes on it are called ring nodes. The capacitated ring tree problem (CRTP) asks for a network of minimal overall edge cost that connects given customers to a depot by ring trees. Ring trees are required to intersect in the depot which has to be either a ring node of degree two in a ring tree or a node of degree one if the ring tree does not contain a ring. Customers are predefined as of type 1 or type 2. The type 2 customers have to be ring nodes, whereas type 1 customers can be either ring nodes or nodes in tree sub-structures. Additionally, optional Steiner nodes are given which can be used as intermediate network nodes if advantageous. Capacity constraints bound both the number of the ring trees as well as the number of customers allowed in each ring tree. In this paper we present first advanced neighborhood structures for the CRTP. Some of them generalize existing concepts for the TSP and the Steiner tree problem, others are CRTP-specific. We also describe models to explore these multinode and multi-edge exchange neighborhoods in one or more ring trees efficiently. Moreover, we embed these techniques in a heuristic multi-start framework and show that it produces high quality results for small and medium size literature instances.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000355827600010&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000355827600010&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
https://repository.uantwerpen.be/docman/iruaauth/f0a2ad/127004.pdf
Handle