Originally posted by: MWojcicki001

Hi,

This discussion is a continuation of "Use of sequence variable for specific VRP problem".

The previous model has been extended by:

1. Time windows for some points (e. g.  point 4 - a visit possible only after 1PM)
2. Weekly schedule - some points have to be visited twice a week, rest of points only once
3. Added variable UnloadDuration - time needed to unload the truck

// (1.) Collection point can have time window for loading
int start[Collection_points] = ...;
int end[Collection_points] = ...;

// (2.) In the initial model we plan for a period of 5 days
range Days = 1..5;

// (2.) Information on which points we have to collect load twice a week, and of which points once a week
int schedule[Collection_points] = ...;

// (3.) Every truck have the same unload duration
// (!?) The chanege in UnloadDuration strongly affects the result of the solution, 
// if LoadDuration = UnloadDuration then the solution is more sensible
int UnloadDuration = 10;

There is no need for trucks to drive every day so interval variables have been change from:

dvar interval itvs[c in Collection_points] size LoadDuration;
dvar interval itvsT[c in Collection_points][t in Trucks] optional(c>1); // LOADING (OPTIONAL) INTERVAL VARIABLES FOR TRUCK t
dvar interval unloadingT[u in 1..NbUnloadMax][t in Trucks] optional size LoadDuration; // UNLOADING (OPTIONAL) INTERVAL VARIABLES FOR TRUCK t
dvar interval truck[t in Trucks];

To:

dvar interval itvs[c in Collection_points][d in Days] optional in start[c]..end[c] size LoadDuration;
dvar interval itvsT[c in Collection_points][t in Trucks][d in Days] optional(c>1); // LOADING (OPTIONAL) INTERVAL VARIABLES FOR TRUCK t
dvar interval unloadingT[u in 1..NbUnloadMax][t in Trucks][d in Days] optional in 0..28800 size UnloadDuration; // UNLOADING (OPTIONAL) INTERVAL VARIABLES FOR TRUCK t
dvar interval truck[t in Trucks][d in Days] optional;

After these changes the model is very unstable. It is easy to see after changing number_of_trucks from 2 to 3 or UnloadDuration from 10 to 30.

// We have a certain number of trucks
//(!?) The change in the number of trucks strongly affects the result of the solution
int number_of_trucks = 2;
range Trucks = 1..number_of_trucks;

// (3.) Every truck have the same unload duration
// (!?) The chanege in UnloadDuration strongly affects the result of the solution, 
// if LoadDuration = UnloadDuration then the solution is more sensible
int UnloadDuration = 10;

What could be the reason of that? 

Originally posted by: PhilippeLaborie

Hello,

What do you mean by "the model is very unstable"? Could you be more precise?

Philippe

Originally posted by: MWojcicki001

Hi,

When I run this model in basic configuration I will get objective function equal 11_452. After changing number_of_trucks from 2 to 3 the objective function is equal 24_833. In my understanding objective function should be at most 11_452, because if model can have result 11_452 with 2 trucks then when he can't get better result with 3 trucks he should use only 2 trucks.

Overall result is correlated with number_of_truck, but I can't find place where this is connected. I would like a model that will decide on the amount of trucks and if using 2 out of 3 trucks is more profitable, then model should use only 2 trucks.

Second issue:

I start the model in basic configuration once again and I will get objective function equal 11_452. Then I change UnloadDuration from 10 to 11. The objective function is now 31_489. After that small change the objective function is almost 3 times bigger.

Kamil

Originally posted by: PhilippeLaborie

I think the problem is mostly related with the fact that when you use 3 trucks, the model is larger (it grows from around 1000 interval variables for 2 trucks to around 1500 variables for 3 trucks) and thus, the convergence is globally slower. If you look at the convergence curve for 2 trucks (using 1 worker to simplify the analysis, and I'm using the last version 12.9), it looks like this (fig1.png)

There is a big improvement between 5s and 10s.

If you only change the number of trucks and increase it to value 3 and let the search run you get: (fig2.png)

You see that here, the big improvements occurs a bit later between 7 and 15s.

When the search uses several workers in parallel (default behavior), the behavior is a bit similar.

The problem is that in the case of 3 trucks, with a time limit of 15s as you have, the search probably  stops before the big improvements.

Here is the convergence curve with automatic search using 12.9 on my laptop (8 parallel workers): (fig3.png)

As you see, getting to solutions close to 11000 just requires a bit longer than 15s.

Note that I made a small change to you model by removing :

forall(d in Days, t in Trucks)   max(c in Collection_points: c>1) presenceOf(itvsT[c][t][d]) == presenceOf(truck[t][d]);

and instead adding the intervals itcsT into the span constraint of the trucks:

span(truck[t][d], append(all(u in 1..NbUnloadMax) unloadingT[u][t][d], all(c in Collection_points: c!=1) itvsT[c][t][d]));

It seems to me this formulation is better as the engine will see the individual implications itvsT=>truck and furthermore, the interval variables truck will really represent the use of the truck including the 'load' intervals.

Originally posted by: MWojcicki001

Thank you for your answer, it is really helpful for me. Issue with number of truck is clear for me now. But what about the second issue:

"Second issue:

I start the model in basic configuration once again and I will get objective function equal 11_452. Then I change UnloadDuration from 10 to 11. The objective function is now 31_489. After that small change the objective function is almost 3 times bigger."

In this case the model don't have any extra variables but the result is surprisingly bigger.

Could you also share the .mod file after changes please?

Originally posted by: Petr Vilím

Hello,

regarding the second issue, the problem is indeed surprisingly harder with UnloadDuration 11 and LoadDuration 10. I don't know where this additional complexity comes from, maybe you understand the model more deeply and may have an idea. It is an NP problem, sometimes even small change in data can lead to quite different results. For this reason it is always a good practice to evaluate a model on multiple data sets (or at least with multiple setting of RandomSeed parameter).

I edited the model file according to the suggestions by Philippe and I attach it.

Best regards, Petr

Originally posted by: MWojcicki001

Hi,

thank you very much Philippe and Petr. Your answers and tips have helped me a lot.

Regards 😉