Trying to solve integer programming problem, trouble with defining constraints that are not well defined

I am trying to implement an example of Bektas's experiment, whose paper I will attach, but am having trouble with some constraints. The problem is SBRP, which tries to minimize the cost of designing bus routes for a given school. Referring to the paper, constraints 9, 10, and 11 has a variable u(i), which is the total amount of students picked up after leaving node i, and is not well defined. These constraints are the capacity constraints, i.e. how many students a bus can pick up before reaching max capacity.

Solution is via integer programming with branch and bound techniques. I have used Sherif A. Tawfik's code to try and solve my example, which I will also attach.

Finally, my code. I did my best trying to explain my code in the file itself. So my problem is that I feed my code a matrix, in this case

 d = [0 20 15 10 12
      20 0 21 13 15
      15 21 0 12 50
      10 13 12 0 1
      12 15 50 1 0];

this refers to the distance between the stops of a school bus route, so element (1,2) is the distance from the school and the 1st stop, (3,4) refers to the distance from stop 2 to stop 3. Note, think of this matrix with the first row as the zeroth row and the first column as the zeroth column; this is for convenience of interpreting the results. What I get is

Solution_Matrix =

     0     0     0     0     0
     0     0     0     0     1
     0     1     0     0     0
     0     0     1     0     0
     0     0     0     1     0

which is wrong. This refers to the path taken by the bus(es), i.e. our solution routes. The problem is that any route must start from the school, so there should be a 1 in the first row/column. Another thing is that this does not satisfy the capacity constraints. I have that

q = [0 12 13 14 20];

which are the number of students per stop, so the first element is the number of students at the school, which should be zero, the second element is the number of students at stop 1 waiting to be picked up, etc. The solution suggests I take the route, (3,2) -> (2,5) -> (5,4) -> (4,3) (does not have to be in this order), so my bus is starting from one of the nodes and makes a sweeping effort to collect everyone and returns to the starting point. I specified my carry capacity to be Q = 33. This obviously violates the constraint, where my one bus carried 12+13+14+20 = 59 students.

I am not sure what is wrong. My guess is that my implementation of the variable u(i) is wrong. I have not put in the distance constraints because I feel that this should work without them for the time being, since those constraints are similar to the capacity constraints I am currently tackling. I also do not think the solver is the culprit; I have used Opti Toolbox to solve my problem and received exactly the same results. Please let me know if there are any questions, any help is appreciated!

Answer 1

[Hari]

Hi,

I understand that you're solving a School Bus Routing Problem (SBRP) using integer programming and are facing issues with capacity constraints and ensuring routes start from the school.

I assume your issue stems from incorrect implementation of the cumulative load variable u(i) and missing constraints that ensure each route starts and ends at the depot (school node).

In order to correctly model capacity constraints and ensure valid routes, follow these steps:

Step 1: Define variables

x(i,j): binary variable = 1 if bus travels from node i to j.

u(i): load after leaving node i. Set u(0) = 0 and q(i) ≤ u(i) ≤ Q for i ≠ 0.

Step 2: Add load constraints (adapted MTZ)

For all i ≠ j, and i,j ≠ 0:

u(i) - u(j) + Q * x(i,j) ≤ Q - q(j)

This ensures load is tracked correctly and prevents sub-tours.

Step 3: Enforce depot constraints

sum(x(0, :)) == k;  % Number of routes starting at school
sum(x(:, 0)) == k;  % Routes must return to school

Step 4: Verify solution

After solving, ensure no u(i) exceeds Q.

Check each route starts/ends at node 0 and the solution matrix reflects that.

References:

https://www.mathworks.com/help/optim/ug/intlinprog.html

https://www.mathworks.com/help/matlab/ref/sum.html

Hope this helps!