Location of Income Tax Offices

Contents

Problem description

The income tax administration is planning to restructure the network of income tax offices in a region. The graph in the figure below shows the cities in the region and the major roads. The numbers within () close to the cities indicate the population in thousands of inhabitants. The arcs are labeled with the distances in kilometers. The income tax administration has determined that offices should be established in three cities to provide sufficient coverage. Where should these offices be located to minimize the average distance per inhabitant to the closest income tax office?

Graph of towns and roads of the region

  (15)   (10)   (12)   (18)
  1 -15- 2 -22- 3 -18- 4

   | \       / |     |
   |  24   16  |     |
  18   \   /   |     |
   |           20    12
   |     5(5)  |     |
   |           |     |
   |     | \   |     |
   |    12  24 |     |
   |     |   \ |     |

  7 -15- 8 -30- 9 -12- 6 (24)
(11)    (16)   (13)
   |     |   /  |   /
   22   25  19  19 22
   |     | /    | /

 10 -19- 11 -21- 12 (20)
 (22)    (19)

Variables

population           Population of each town
numloc               Number of offices to start
lengths              The length of the roads
in/out               A road i goes between towns
                     in(i) and out(i)

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

population = [15 10 12 18 5 24 11 16 13 22 19 20]';
numloc     = 3;
in         = [1 1 1 2 3 3 3 4 5 5 6  6 7  7 8  8  9  9 10 11]';
out        = [2 5 7 3 4 5 9 6 8 9 9 12 8 10 9 11 11 12 11 12]';
lengths    = [15 24 18 22 18 16 20 12 12 24 12 22 15 22 30 ...
    25 19 19 19 21]';

n1   = length(unique([in;out])); %Number of cities
n2   = length(in);
% Calculate distance matrix
d = inf*ones(n1,n1);
for i=1:n1
    d(i,i) = 0;
end
for i=1:n2
    d(in(i), out(i)) = lengths(i);
    d(out(i), in(i)) = lengths(i);
end
for i=1:n1 %b
    for j=1:n1 %c
        for k=1:n1 %d
            if j<k
                if d(j,k) > d(j,i)+d(i,k);
                    d(j,k) = d(j,i)+d(i,k);
                    d(k,j) = d(j,i)+d(i,k);
                end
            end
        end
    end
end

c = length(unique([in;out])); %Number of cities
depend = tom('depend',c,c,'int');
build = tom('build',c,1,'int');

% All variables are binary
bnds = {0 <= depend <= 1, 0 <= build <= 1};

% Building constraint
con1 = {sum(build) == numloc};

% Dependencies constraint
con2 = {sum(depend,2) == 1};

% Reality constraint
con3 = {depend <= repmat(build',c,1)};

% Objective
objective = sum(sum(repmat(population,1,c).*d.*depend));
constraints = {bnds, con1, con2, con3};
options = struct;
options.solver = 'cplex';
options.name   = 'Location of Income Tax Offices';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    cities = length(population);
    temp   = sol.build;
    build  = find(temp);
    goto   = sol.depend';
    disp(['Build the offices in towns ' num2str(build') ' and let'])
    for i = 1:length(build),
        disp(['   people from ' num2str(find(goto(build(i),:))) ...
            ' travel to ' num2str(build(i)) ])
    end
end

% MODIFICATION LOG
%
% 051206 med   Created
% 060118 per   Added documentation
% 060125 per   Moved disp to end
% 090325 med   Converted to tomSym

Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Location of Income Tax Offices  f_k    2438.000000000000000000
                                               f(x_0)      0.000000000000000000

Solver: CPLEX.  EXIT=0.  INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found

FuncEv   49 
CPU time: 0.015625 sec. Elapsed time: 0.016000 sec. 
Build the offices in towns 1   6  11 and let
   people from 1  2  5  7 travel to 1
   people from 3  4  6  9 travel to 6
   people from 8  10  11  12 travel to 11