Solving school bus routing problem (SBRP) using gurobi solver in matlab interface

We have sbrp model to optimize:

min sum_{ij} D_{ij} . x_{ij}

subject to

for all i \in (1,2,...,n), sum_{j=1}^{n} x_{ji} <2 br="" column="" constraint="" linear="" matrix="" n="" nbsp="" of="" sum="" variable="">for all i \in (1,2,...,n), sum_{j=1}^{n} x_{ij} <2 br="" constraint="" linear="" matrix="" n="" nbsp="" of="" row="" sum="" variable="">for all i \in (1,2,...,n), sum_{j=1}^{n} x_{ji} + sum_{j=1}^{n} x_{ij} >=1 (row+column sum of variable matirx), n linear constraint
sum_{ij} x_{ij} = n-1 (matrix sum of variable matrix), 1 linear constraint

%so basically we have following for gurobi model:
        model.A = sparse(cm); % cm is a constraint matrix of 3n+1 linear constraint
        model.obj = ofun; % ofun is a vector of distance matrix
        model.rhs = rhs_val; % rhs_val is right hand side value of 3n+1 constraints
        for i=1:2*n
            sense_vec(i)='<'; %for first 2*n constraint
        end
        for i=2*n+1:3*n
            sense_vec(i)='>';% for next n constraint
        end
        sense_vec(num_cons)='='; for last 1 constraint
        model.sense = sense_vec;
        model.vtype = 'B';%Variable type is binary, x is either zero or one
        model.modelsense = 'min'; %minimization problem

        clear params;
        params.outputflag = 0;
        params.resultfile = 'gurobi_sbrp.lp';%save result        
        result = gurobi(model, params);%call gurobi optimizer
        disp(result)

% for given distance matrix D and bus stop numbered from 1 to 12 we have following output:

2 -> 1    3 -> 2    4 -> 3    5 -> 6    6 -> 5    7 -> 8    8 -> 4    9 -> 10    10 -> 9    11 -> 12    12 -> 11

% so here we are getting 3 cyclic route plus one acyclic e.i. 5->6->5, 9->10->9, 11->12->11, and 7->8->4->3->2->1

How to remove these cyclic routes (basically make active variables zero which are making cyclic route and search for another)

Please help me,

If anyone needs whole program and data set of this code, I will be happy to share it.

Thanking you,
Ajay
  

bengu

Jun 12

Pls look for sub-tour elimination constraints in vrp literature.