You are here

Constraint-Based Local Search for the Distance- and Capacity-Bounded Network Design Problem

Publication Type: 
Refereed Conference Meeting Proceeding
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 of the 26th IEEE International Conference on Tools with Artificial Intelligence
Digital Object Identifer (DOI): 
Publication Date: 
178 - 185
Conference Location: 
Research Group: 
National University of Ireland, Cork (UCC)
Open access repository: 
Publication document: