Need help understanding time windows and some concepts, and why I have no solutions

[Iban Rodriguez]

Hi,

I’m trying to solve a “basic” VRP problem with time windows, but I think I don’t fully understand how these matrices work, because I either get “out of range” error, or “no solutions”.

I need to go step by step in my development and testings, first because I’m new to Python (I’ve beeng a developer for 25 years but in other languages), and second because I never did anything related to TSP/VRP or OR-Tools before so most concepts are new to me.

The first problem I tried was a simple distance VRP problem. I used the example from the OR-Tools website, and modified it to call Google Matrix, get a distance matrix from 10 real addresses, and then return a visit order for 2 vehicles. Up to what I tested, it looks like it worked fine, as it returned a correct visit order for each vehicle.

I then wanted to add time window constraint, because my “next step” is to limit the route length to the available time. So I though on either setting specific times to certain addresses to force the solver to reorder based on that, or setting a “visit duration” for each address (our company delivers home furniture and each visit can be 30 minutes or 2 hours, depending on what’s to assemble or do).

I found an example from Mizux that I think does something like this:
https://gist.github.com/Mizux/e737be82013ed787820309bca6de8c6e

Executing the example as is, it works perfectly. But I needed to see what happens when I change the matrices with my own values.

And here comes the trouble.

Here’s what I tried step by step, with the explanations (uploaded to one of our domains, secure https, raw text file):

0- Mizux’s original example:

https://oiartzunwebservices.com/20231110-mizux-original.txt

1- Added my own matrices right behind his, to show that I’m just overwriting those values (the numbers come from a real request to Google, so they represent real distance in meters and times in minutes.

This example doesn’t give any errors and shows a solution, even if only 2 of 4 vehicles do something. One problem is that total distances are shown as “0”, but I’m not worried yet because I know there’s other data to adjuts.

https://oiartzunwebservices.com/20231110-mizux-modified-1.txt

2- Next thing I do is add a 10th row to time_windows and demands matrices, because I’m using 10 addresses.

This change alone, results in “None” as output. No solutions.

https://oiartzunwebservices.com/20231110-mizux-modified-2.txt

3- I then tried increasing the “maximum travel distance”:

500000,  # vehicle maximum travel distance

Same result: “None”

4- I also tried to adjust time_windows values from (0, 1000) to (480, 960), because I’m trying to set the route to 8 hours, from 8AM to 4PM.

Same result: “None”

Conclusion:

I’m not sure where I’m getting lost, or what I don’t understand about this, but I certainly need some enlightenment here.

I probably need to adjust something else in the example, but I simply don't know what... I'm completely blind here, changing numbers here and there, and that is frustrating because I don't know where I'm at.

Our goal as the tests work is to start adding more variables, like specific times for certain addresses (because a customer is available only at an specific hour), add the time needed to stop in each address (deliver, assembly, etc.), and set a vehicle load capacity directly linked to each address (it’s not the same a smal drawer, than a big couch) so the system knows that if 4 addresses use “300 capacity” but the vehicle is “200”, it has to return to depot, for example.

But first, I need to know and understand what I’m doing…

Thanks in advance for any help.

[Rummel]

Hello!

there is a mistake in the original example.

In line 160 you need to add:

time_callback_index = routing.RegisterTransitCallback(time_callback)

And in line 164 you should use this time_callback_index instead of the transit_callback_index. Seems to be a copy and paste error to me...

Best Johannes

[Iban Rodriguez]

Hi Rummel,

Thanks for taking the time to reply, appreciated.

I'm not sure Mizux's example has a mistake. It works and gives solutions.

I've tried what you suggested just in case, but weird things happen. And as I don't quite understand yet Python, I rather not change the code too much without knowing what I'm doing.

My problem is that when I try apply real distances, it stops giving solutions.

I've created a new example where you can see my struggle:

https://oiartzunwebservices.com/20231110-mizux-modified-3.txt

- When using "DM-3", it works.

- Commending "DM-3" and activating "DM-2", it doesn't give any solution.

I added comments on the arrays I changed, but just switching between using DM-3 or DM-2 you can see what happens.

I'm still reading and re-reading the code, but I don't quite understand what is the reason for no solutions.

Thanks again

[Rummel]

Hello iban,

I commented to Mizux this error and he already corrected it (see the comment in his example:  Small Problem (github.com)). So, yes I am sure, that this is (still) the problem in your code.

DM-2 is not working, because the values have another scale than the TM and thus now shows the error in the code.

If you want to add a new dimension for the time, you need to use the time_callback(_index) defined before instead of the transit_callback that relates to the DM.

I hope, you understand, what I mean.

Best Johannes

[Iban Rodriguez]

Hi Rummel,

Thanks again for your help.

I started from scratch using the fixed example, as it seems I wasn't able to change what you suggested (I'm still walking on quicksand here).

I used my real values for distances and times. Then I changed the values for max time, max distance, and vehicle capacity, and now the solver returned a solution that looks promising.

Now I need to play a bit with different values and settings and see what happens, and I hope I can reach my first milestone, which is to solve a problem with distance + 8 hours working time.

Thanks!

Regards.