Question about Vehicle Routing Problem with Time Windows

[Claire]

Hello, 

 

I am doing an Vehicle Routing Problem with Time Windows and I have a question about this. 

 

I formulated two decision variables: 

 }

    Variable X {

        IndexDomain: (iLocations,jLocations,k) | iLocations<>jLocations | iLocations<>Numberoflocations+1 | jLocations<>0;

        Range: binary;

    }

    Variable S {

        IndexDomain: (iLocations,k);

        Range: nonnegative;

 

X(iLocations,jLocations,k) represents whether vehicle k goes from location i to location j, where i cannot be equal to the returning depot and j cannot be equal to the home depot. 

S(iLocations,k) represents the time vehicle k starts to serve location i. 

 

I also have the following parameters and constraints: 

  }

    Parameter A {

        IndexDomain: iCustomerlocations;

        Range: nonnegative;

    }

    Parameter B {

        IndexDomain: iCustomerlocations;

        Range: nonnegative;

    }

    Parameter t {

        IndexDomain: (iLocations,jLocations)| iLocations<>jLocations | iLocations<>Numberoflocations+1 | jLocations<>0;

        Range: nonnegative;

  }

    Constraint Arrivaltime {

        IndexDomain: (iLocations,jLocations,k);

        Definition: (S(iLocations,k) + t(iLocations,jLocations) - Largenumber * (1-X(iLocations,jLocations,k))) <= S(jLocations,k);

    }

    Constraint Timewindow {

        IndexDomain: (iCustomerlocations, k);

        Definition: A(iCustomerlocations) <= S(iCustomerlocations,k) <= B(iCustomerlocations);

    }

    Constraint Workinghours {

        IndexDomain: (iLocations,k)| iLocations=Numberoflocations+1;

        Definition: S(iLocations,k)<=10;

 

A and B are the lower bound and upper bound of the time window in which customer i has to be served. 

T(iLocations,jLocations) represents the time it takes to go from location i to location j. 

Constraint Arrivaltime means that the time vehicle k arrives at location j is greater or equal to S(iLocations,k)+t(iLocations,jLocations), when the vehicle goes from i to j. 

Constraint Timewindow means that the time vehicle k starts with the service at customer i is between the time window of that specific customer. 

Constraint Workinghours means that vehicle k has to be back at the returning at the latest at 10 hours, because this is the maximum number of working hours. 

 

The model is working, but the results for variable S are not how I want them to be. 

My question: which formula do I have to add or which adjustments to the formulas do I have to make such that the vehicles leave the customer locations immediately after they have visited them. 

For example, one route is as follows: home depot -> location 2 -> location 3 -> returning depot

The time window of customer2 is [0,3] and the time window of customer 3 is [0,6]. 

T(0,2)=2, T(2,3)=2, T(3,4)=3.

The results for variable S are: S(2,k)=2, S(3,k)=6 and S(4,k)=9. However, this should be S(2,k)=2, S(3,k)=4, S(4,k)=7. 

 

Thank you in advance!

Kind regards, 

Claire 

 

 

[Mohan]

Hello Claire,

You essentially need something which will make

S(i, k) + t(i, j) = S(j, k) if X(i, j, k) = 1

You can add another constraint similar to the ArrivalTime one you have, say ArrivalTime_2 as below.

   

Constraint Arrivaltime {
        IndexDomain: (iLocations,jLocations,k);
        Definition: (S(iLocations,k) + t(iLocations,jLocations) - Largenumber * (1-X(iLocations,jLocations,k))) <= S(jLocations,k);
    }

Constraint Arrivaltime_2 {
        IndexDomain: (iLocations,jLocations,k);
        Definition: (S(iLocations,k) + t(iLocations,jLocations) + Largenumber * (1-X(iLocations,jLocations,k))) >= S(jLocations,k);
    }

When X(i, j, k) = 1, the above constraints will become

S(iLocations,k) + t(iLocations,jLocations) - Largenumber * (0) <= S(jLocations,k)
S(iLocations,k) + t(iLocations,jLocations) + Largenumber * (0) >= S(jLocations,k)

Which is equivalent to

S(iLocations,k) + t(iLocations,jLocations) = S(jLocations,k)

When X(i, j, k) = 0, these constraints will become

S(iLocations,k) + t(iLocations,jLocations) - Largenumber * (1) <= S(jLocations,k)
S(iLocations,k) + t(iLocations,jLocations) + Largenumber * (1) >= S(jLocations,k)

Which will be equivalent to the below and these will be always true if Largenumber is sufficiently large compared to the ranges of S and t.

- Largenumber * (1) <= S(jLocations,k)- S(iLocations, k) - t(iLocations, jLocations)
  Largenumber * (1) >= S(jLocations,k) + S(iLocations,k) + t(iLocations,jLocations)


This should solve your problem.

You might also want to add an additional constraint that says a truck can go to only one jLocation from iLocation.

Constraint OneDestination {
        IndexDomain: (iLocations,k);
        Definition: sum[jLocations, X(iLocations, jLocations, k)] <= 1;
    }

This will ensure that the only one of X(2, 3, k1) and X(2, 4, k1) will be 1. Truck k1 cannot go to both locations 3 and 4 from 2 right ? It can only go to one location from 2.

[Claire]

Hello Mohan, 

Thank you for your quick reply. 

It is working now! 

Kind regards, 

Claire

Op zaterdag 4 mei 2019 01:29:33 UTC+2 schreef Mohan: