Transportation: Minimizing Cost

Question

I am trying to solve this problem, but I have had no luck. I have tried to set this up in MS Excel, so I could use Solver to find the solution, but I don't really know how to form this problem. As far as I know, I calculate the Euclidean distance from 1 location to another and that tells me how much the cost of shipment is per unit ton of trash from one location to another. Then I am clueless...

Answer 1

The following untested MiniZinc model tackles your problem:

% Number of districts
int: ndistricts = 10;
set of int: Districts = 1 .. ndistricts;

%  Coordinates
array[Districts] of int: x            = [  4,   2,  10,   2,   5,   4,  10,   5,   5,   1];
array[Districts] of int: y            = [  3,   5,   8,   8,   3,   5,   5,   1,   8,   7];

%  Distances between locations
array[Districts, Districts] of int: squared    
  = array2d(Districts, Districts, 
            [(x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) | 
            i, j in Districts]);
array[Districts, Districts] of int: distance 
  = array2d(Districts, Districts, 
            [ceil(sqrt(int2float((squared[i, j])))) | 
            i, j in Districts]);

%  Dump tons
array[Districts] of int: tons         = [ 49, 874, 555, 352, 381, 428, 985, 105, 258, 210];
int: maxTons = 985;

%  Cost [million $]
array[Districts] of int: fixedCost    = [  2,   1,   1,   1,   3,   2,   1,   2,   4,   2];
array[Districts] of int: variableCost = [310,  40,  51, 341, 131, 182,  20,  40, 177,  75];
int: costFactor = 1000000;

int: costPerTonAndMile  = 1000;  % $
int: maxTonsPerDumpSite = 1500;

%  Variables
array[Districts] of var Districts: dumpTo;
array[Districts] of var bool: isDumpSite;

%  Constraints

%  dump tonnage has to stay below capacity
constraint forall (ds in Districts) (
  maxTonsPerDumpSite >= sum(d in Districts where dumpTo[d] == ds)(tons[d])
);

constraint forall (ds in Districts) (
  isDumpSite[ds] == (0 < sum(d in Districts where dumpTo[d] == ds)(1))
);

solve minimize sum(ds in Districts where isDumpSite[ds])(
%    fixed cost for dump site
     fixedCost[ds] * costFactor +
%    variable cost to transport dump to this site
     sum(d in Districts where dumpTo[d] == ds)(
        tons[d] * (distance[d, ds] * costPerTonAndMile + variableCost[ds])
     )
);

%  Solution

output ["\nDump allocation from District " ++ show(d) ++
        " to site " ++ show(dumpTo[d]) ++ ": " ++
        show(tons[d]) | 
        d in Districts 
];

The printed solution:

Dump allocation from District 1 to site 1: 49
Dump allocation from District 2 to site 3: 874
Dump allocation from District 3 to site 3: 555
Dump allocation from District 4 to site 2: 352
Dump allocation from District 5 to site 1: 381
Dump allocation from District 6 to site 1: 428
Dump allocation from District 7 to site 2: 985
Dump allocation from District 8 to site 1: 105
Dump allocation from District 9 to site 1: 258
Dump allocation from District 10 to site 1: 210
----------
==========
Finished in 119msec

Answer 2

Let $\mathcal S = \{1,2,3,4,5,6,7,8,9,10\}$ be the set of districts. Define the decision variables $$s_i = \begin{cases}1,& \text{dump site opened in district $i$}\\ 0,& \text{otherwise.} \end{cases}$$ for $i\in\mathcal S$, and $$t_{ij} = \begin{cases}1,& \text{district $i$ sends waste to district $j$}\\ 0,& \text{otherwise.}\end{cases} $$ for $i,j\in\mathcal S$. We have the parameters \begin{align} D_{ij} &= \text{Distance between districts $i$ and $j$ ($D_{ii}=0$)},\\ F_i &= \text{Fixed cost of opening dump site at district $i$}, S\\ V_i &= \text{Variable cost of processing one ton of waste in district $i$}, i\in\mathcal S\\ W_i &= \text{Tons of waste at site $i$}. \end{align} We can model this problem by the following integer program: \begin{align} \min & \quad\sum_{i\in\mathcal S}F_is_i + \sum_{i,j\in\mathcal S}D_{ij}W_it_{ij} + \sum_{i,j\in\mathcal S}V_it_{ij} \tag 1\\ \mathrm{s.t.} & \quad \sum_{j\in\mathcal S} t_{ij} = 1,\quad\forall i\in\mathcal S\tag 2\\ &\quad t_{ij}\leqslant s_j,\quad \forall i,j\in\mathcal S\tag 3\\ &\quad s_i\in\{0,1\},\quad \forall i\in \mathcal S\\ &\quad t_{ij}\in\{0,1\},\quad \forall i,j\in\mathcal S. \end{align}

We want to minimize the total cost, which is reflected in the objective function $(1)$. The first sum is the fixed cost of opening dump sites. The second sum is the cost of transporting waste. The third sum is the cost of processing waste.

Constraints $(2)$ ensure that every district sends its waste to exactly one district.

Constraints $(3)$ ensure that waste cannot be sent to a district unless a dump site is opened there