Wagon Load Balancing

Contents

Problem description

Three railway wagons with a carrying capacity of 100 quintals (1 quintal = 100 kg) have been reserved to transport sixteen boxes. The weight of the boxes in quintals is given in the following table. How shall the boxes be assigned to the wagons in order to keep to the limits on the maximum carrying capacity and to minimize the heaviest wagon load?

Weight of boxes

+------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|Box   | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|
+------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|Weight|34| 6| 8|17|16| 5|13|21|25|31|14|13|33| 9|25|25|
+------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Before implementing a Mathematical Programming solution, one may wish to try to see whether it is possible to solve this problem instance with the following simple heuristic: until all boxes are distributed to the wagons we choose in turn the heaviest unassigned box and put it onto the wagon with the least load.

Variables

minload         Minimal load accepted per wagon
maxload         Maximal load accepted per wagon
weights         Weight of each box

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

minload = [  0;  0;  0;];
maxload = [100;100;100;];
weights = [34;6;8;17;16;5;13;21;25;31;14;13;33;9;25;25];

w = length(minload);
b = length(weights);

load = tom('load',b,w,'int');
maxweight = tom('maxweight',1,1,'int');

% Bounds
bnds = {0 <= load <= 1, sum(weights)/3 <= maxweight <= 100};

% Load constraint, exactly one box per wagon
con1 = {sum(load,2) == 1};

% Wagon constraint
con2 = {sum(load.*repmat(weights,1,3),1) <= maxweight};

% Objective
objective = maxweight;

constraints = {bnds, con1, con2};
options = struct;
options.solver = 'cplex';
options.name   = 'Wagon Load Balancing';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    wagons = length(minload);
    temp   = sol.load;
    for w = 1:wagons,
        idx = find(temp(:,w) > 0.5);
        disp(['wagon ' num2str(w) ...
            ' has a total load of ' num2str(sum(weights(idx))) ...
            ' by carrying the boxes: ' num2str(idx') ])
    end
end

% MODIFICATION LOG
%
% 051007 med   Created.
% 060111 per   Added documentation.
% 060125 per   Moved disp to end
% 060203 med   Printing updated
% 090308 med   Converted to tomSym

Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Wagon Load Balancing           f_k      99.000000000000000000
                                              f(x_0)      0.000000000000000000

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

FuncEv   27 
CPU time: 0.015625 sec. Elapsed time: 0.015000 sec. 
wagon 1 has a total load of 98 by carrying the boxes: 2   4   6   7   8  11  12  14
wagon 2 has a total load of 99 by carrying the boxes: 5   9  13  15
wagon 3 has a total load of 98 by carrying the boxes: 1   3  10  16