Constraint-Based Local Search for the Distance- and Capacity-Bounded Network Design Problem
Publication Type:
Refereed Conference Meeting Proceeding
Abstract:
Many network design problems arising in the fields of transportation, distribution and logistics require clients to be connected to facilities through a set of carriers subject to distance and capacity constraints. Here a carrier could be a cable, vehicle, salesman etc. The distance from a facility to client using a carrier could be expressed as signal loss, time spent, path length, etc. The capacity of a carrier could be interpreted as the maximum number of commodities that a carrier can carry, the maximum number of clients or links that a single carrier can visit, etc. The main decisions are to determine the number of carriers, assign clients to carriers, and design a network for each carrier subject to distance, capacity and some side constraints. In this paper, we focus on the Cable Routing Problem (CRP), which is NP-hard. We present a constraint-based local search algorithm and two efficient local move operators. The effectiveness of our approach is demonstrated by experimenting with 300 instances of the CRP taken from real-world passive optical network deployments in Ireland. The results show that our algorithm can scale to very large problem instances and it can compute good quality solutions in a very limited time.
Conference Name:
26th IEEE International Conference on Tools with Artificial Intelligence
Proceedings:
Proceedings of the 26th IEEE International Conference on Tools with Artificial Intelligence
Digital Object Identifer (DOI):
10.1109/ICTAI.2014.35
Publication Date:
10/11/2014
Pages:
178 - 185
Conference Location:
Cyprus
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Open access repository:
No
Publication document: