Abstract:

The Fixed-Charge Capacitated Multi-commodity Network Design (CMND) problem is the core "abstract" problem that one has to deal with when designing telecommunications or transportation networks. It consists in finding the optimal configuration, i.e., the arcs to include in the final design, of a network on which the flows of several products ("commodities") must be routed to satisfy given demands between origin-destination pairs. Each of the arcs that can possibly be included in the design is characterized by its capacity (the maximum amount of flow of all commodities it can support), a fixed cost to be incurred if the arc is selected, and a variable cost for each unit of flow that uses the arc. The objective of the problem is to minimize the total system cost, i.e., the sum of the fixed costs of selected arcs and variable routing costs, while respecting capacity limits.

In this talk, we will present heuristic approaches that we developed, with different coauthors, over the last fifteen years to tackle this problem. These encompass several different types of metaheuristics: Tabu Search, Path Relinking and Scatter Search. As far as we know, the most recent of these approaches are still the most effective approximate methods for the CMND. Computational results on a set of small and medium size benchmark instances will be reported and discussed

Joint work with Teodor Gabriel Crainic and others.