Routing Telephone Calls

Contents

Problem description

A private telephone company exploits a network, represented in the figure below, between five cities: Paris, Nantes, Nice, Troyes, and Valenciennes.

Structure of the network of the company

Nantes --(300)-- Paris --(200)-- Valenciennes
    \            /                |
   (120)      (300)              (70)
      \        /                  |
         Nice   ----(80)----  Troyes

The number beside each edge (connection) is the capacity of the link in terms of circuits. This issue is worth some further explanation. Suppose that a person A at Nantes calls a person B at Nice. The company needs to find a path formed by non-saturated edges from Nantes to Nice to route the binary flow corresponding to the digitized voice of A. But the conversation is only possible if a flow from Nice to Nantes is established so that B may answer A. In digital telephone networks, the binary flows all have the same throughput standard (often 64 kbps). The associated capacity is called a channel. The return channel uses the same edges as the first channel, but in the opposite direction. This linked pair of channels necessary for a telephone conversation is a circuit.

The routing of the return channel through the same edges is due to the fact that the call could fail if one waited until the callee picked up the phone before searching for a non-saturated return path. This is why, at the moment of the call, the routing system constructs the path edge by edge and immediately reserves the edges of the return channel. As a consequence, as the capacity of an edge is consumed in increments of a bidirectional circuit, we do not consider any directed flows. For example, there may be 10 persons calling from Nantes to Nice and 20 from Nice to Nantes, or the opposite: in both cases, 30 circuits are used.

At a given moment, the company is facing demands for circuits given in the following table. Is it possible to satisfy the demands entirely? If this is not possible, try to transmit as much as possible. In every case, indicate the corresponding routing, that is, the access paths used.

Demand of circuits

+-------------------+--------+
|Cities             |Circuits|
+-------------------+--------+
|Nantes-Nice        |  100   |
|Nantes-Troyes      |   80   |
|Nantes-Valenciennes|   75   |
|Nice-Valenciennes  |  100   |
|Paris-Troyes       |   70   |
+-------------------+--------+

Variables

arcs_out/in          For an arc i arcs_out(i) is its starting node
                     and arcs_in(i) ts target node
capacity             Capacity of arcs
demand_out/in        For a demand i demand_out(i) is its starting node
                     and demand_in(i) its target node
demands              Demand
path_mat             Possible paths
paths                In/Out of possible paths

Reference

Applications of optimization... Gueret, Prins, Seveaux

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Oct 7, 2005.   Last modified Apr 8, 2009.

Problem setup

Nantes, Paris, Nice, Valenciennes, Troyes

arcs_in    = [1 1 2 2 3 4]';
arcs_out   = [2 3 3 4 5 5]';
capacity   = [300 120 300 200 80 70]';

demand_in  = [1 1 1 3 2]';
demand_out = [3 5 4 4 5]';
demands    = [100 80 75 100 70]';

path_mat    = [1 3 0 0 0;...
    1 2 3 0 0;...
    1 2 4 5 3;...
    1 2 4 5 0;...
    1 2 3 5 0;...
    1 3 5 0 0;...
    1 3 2 4 5;...
    1 2 4 0 0;...
    1 3 2 4 0;...
    1 2 3 5 4;...
    1 3 5 4 0;...
    3 1 2 4 0;...
    3 2 4 0 0;...
    3 5 4 0 0;...
    2 4 5 0 0;...
    2 1 3 5 0;...
    2 3 5 0 0];

paths = [1 3;...
    1 3;...
    1 3;...
    1 5;...
    1 5;...
    1 5;...
    1 5;...
    1 4;...
    1 4;...
    1 4;...
    1 4;...
    3 4;...
    3 4;...
    3 4;...
    2 5;...
    2 5;...
    2 5];

n  = size(paths,1);   % paths

flow = tom('flow',n,1);

% No variables are binary.
bnds = {0 <= flow};

% Capacity constraint on arc
n1 = length(arcs_in);
con1 = cell(n1,1);
for i=1:n1
    [idx_i, idx_j] = find(path_mat(1:end,1:end-1) == arcs_in(i));
    next_nodes = path_mat(idx_i+n*idx_j);
    idx2 = find(next_nodes == arcs_out(i));
    new_idx = idx_i(idx2);
    con1{i} = {sum(flow(new_idx)) <= capacity(i)};
end

% Demand constraint
n2 = length(demands);
con2 = cell(n2,1);
for i=1:n2
    [idx_i, idx_j] = find(paths(1:end,1) == demand_in(i));
    next_nodes = paths(idx_i+n*idx_j);
    idx2 = find(next_nodes == demand_out(i));
    new_idx = idx_i(idx2);
    con2{i} = {sum(flow(new_idx)) <= demands(i)};
end

% Objective
objective = -sum(flow);

constraints = {bnds, con1, con2};
options = struct;
options.solver = 'cplex';
options.name   = 'Routing Telephone Calls';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    paths  = sol.flow;
    idx = find(paths);
    load = [];
    cities = ['Nant'; 'Pari'; 'Nice'; 'Vale'; 'Troy'];
    disp('INCOMING AND OUTGOING CIRCUITS')
    for i = 1:length(idx),
        id = idx(i);
        temp_path = path_mat(id,:);
        temp_path = temp_path(find(temp_path));
        city_path = [];
        for city = 1:length(temp_path),
            city = temp_path(city);
            city_path = [city_path cities(city,:) ' ' ];
        end
        disp(['   ' num2str(paths(id)) ' circuits ' ...
            cities(temp_path(1),:) '-' cities(temp_path(end),:) ...
            ' using the following path: ' num2str(city_path)])
        for j = 2:length(temp_path),
            out = temp_path(j-1);
            in  = temp_path(j);
            if in < out,
                in_temp = in;
                in = out;
                out = in_temp;
            end
            if (size(load) > [out in]),
                load(out,in) = load(out,in) + paths(id);
            else
                load(out,in) = paths(id);
            end
        end
    end
    disp('LOAD BETWEEN CITIES')
    for i = 1:length(cities)-1,
        for j = 1:length(cities),
            if load(i,j) > 0,
                disp(['   between ' cities(i,:) ' and ' cities(j,:) ': ' ...
                    num2str(load(i,j)) ' circuits.' ])
            end
        end
    end
end

% MODIFICATION LOG
%
% 051122 med   Created.
% 060116 per   Added documentation.
% 060126 per   Moved disp to end
% 090308 med   Converted to tomSym
Problem type appears to be: lp
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Routing Telephone Calls        f_k    -380.000000000000000000
                                              f(x_0)      0.000000000000000000

Solver: CPLEX.  EXIT=0.  INFORM=1.
CPLEX Dual Simplex LP solver
Optimal solution found

FuncEv    7 Iter    7 
INCOMING AND OUTGOING CIRCUITS
   100 circuits Nant-Nice using the following path: Nant Nice 
   80 circuits Nant-Troy using the following path: Nant Pari Nice Troy 
   75 circuits Nant-Vale using the following path: Nant Pari Vale 
   100 circuits Nice-Vale using the following path: Nice Pari Vale 
   25 circuits Pari-Troy using the following path: Pari Vale Troy 
LOAD BETWEEN CITIES
   between Nant and Pari: 155 circuits.
   between Nant and Nice: 100 circuits.
   between Pari and Nice: 180 circuits.
   between Pari and Vale: 200 circuits.
   between Nice and Troy: 80 circuits.
   between Vale and Troy: 25 circuits.