You are here

Constraint-based Local Search for Designing Optimal Networks


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 talk, we focus on the CableRouting 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 real instances from Ireland, Italy, and the UK.

Speaker Name: 
Alejandro Arbelaez
Speaker Bio: 
Postdoctoral researcher
Speaker Photo: 
Seminar Date: 
Wednesday, 18 January, 2017 - 15:00 to 16:00
Seminar Location: 
WGB 2.16