[SOLVED] Vehicle routing with time windows minizinc example

Vehicle routing with time windows minizinc example

I would like to express the vehicle routing problem with time windows (https://ir.cwi.nl/pub/2036) in the minizinc modeling language in order to solve it using constraint programming.

Since I am new to that modeling language and to constraint programming overall I would like to know if anybody already expressed this problem into this language. I have found the following example benchmark for the "vrp (without time windows) https://github.com/MiniZinc/minizinc-benchmarks/blob/master/vrp/vrp.mzn

How can the model modified to include time windows for deliveries?

Solution

I modified that model to include time windows. I removed capacity-related logic, since I don't need it in my case.

Basically you'll need to add these constraints:

    % Departure time constraints
constraint
    forall(i in 1..N, j in 1..N)(
        DepartureTimes[i] + TravelTimes[i, j] - DepartureTimes[j] <= (1 - x[i, j]) * 1000000
    );

    % Time windows constraints
constraint
    forall(i in 1..N)(
        TimeWindows[i, 1] <= DepartureTimes[i]
    );

constraint
    forall(i in 1..N)(
        DepartureTimes[i] <= TimeWindows[i, 2]
    );

Here's the full code: https://github.com/jlhonora/vrp-minizinc

And the reference paper: Desrochers, Martin, et al. "Vehicle routing with time windows: optimization and approximation." Vehicle routing: Methods and studies 16 (1988): 65-84.