Time windows error and use all vehicles

[orlandombaa]

I just started to use Vrpy library. I used some of the examples that are in the documentation successfully. In order to generate my own scenarios, I am using Open Route Services to generate the impedance matrix of distance and duration. Using this I have run successfully some cases without time windows restrictions.

However, now that I added this restriction some errors start to appear. I have the following doubts:

• Units of the travel matrix and time windows restriction: I assume that these two variables must be in the same units. I generate my travel time matrix in seconds and then pass to hours and the arrays of lower and upper time windows I put it in hours too (now is lower 7 and upper 17 representing 7 am and 17 pm for all the nodes).

• When I run my code without time restrictions it works well, when I do it with time restriction but not using a number of vehicles It works more less good. It generates the optimization but it gives me a suggestion of total vehicles very high. In my particular case, there are 45 stops and it suggests 22 vehicles to do the job.
  On the other hand, when I add the num_vehicles it simply generates an error " Exception: problem Infeasible"

prob = vrpy.VehicleRoutingProblem(G, time_windows=True, num_vehicles=20, use_all_vehicles=True, num_stops=20) prob.solve(time_limit=30)

• Travel time windows (lower and upper): Do these arrays must be different in their length? I see that the lower array contains one more lecture than the total length of nodes (which is represented by 0:0). On the other hand, the upper array contains the actual number of nodes.

I hope someone can help me to understand these mistakes.

Best regards,
Orlando

[orlandombaa]

The following point now is the one that most generates me doubts:

• When I run my code using just time_windows=True it works well. The problem is that it generates a solution very impracticable it generates a solution of 23 routes for a total of 45 stops. When I add another restriction which is :
  prob = vrpy.VehicleRoutingProblem(G, time_windows=True, num_stops=10) it still generates me the 23 routes solution mention before which is understandable due to I just added a limited stops to the routes .

However, the real problem comes when I use prob = vrpy.VehicleRoutingProblem(G, time_windows=True, num_vehicles=2, use_all_vehicles=True), always that I add a certain number of vehicles and use it all the output is Exception: problem Infeasible
I am not sure if this come from a structural problem of the network

[Kuifje02]

Hi @orlandoandradeb, thanks for your feedback.

Units of the travel matrix and time windows restriction: I assume that these two variables must be in the same units. I generate my travel time matrix in seconds and then pass to hours and the arrays of lower and upper time windows I put it in hours too (now is lower 7 and upper 17 representing 7 am and 17 pm for all the nodes).

That seems right to me.

When I run my code without time restrictions it works well, when I do it with time restriction but not using a number of vehicles It works more less good. It generates the optimization but it gives me a suggestion of total vehicles very high. In my particular case, there are 45 stops and it suggests 22 vehicles to do the job.
On the other hand, when I add the num_vehicles it simply generates an error " Exception: problem Infeasible"

Would you have a minimal working example so that we can reproduce the issue ? Are you sure the problem is actually feasible when you do this ?

Travel time windows (lower and upper): Do these arrays must be different in their length? I see that the lower array contains one more lecture than the total length of nodes (which is represented by 0:0). On the other hand, the upper array contains the actual number of nodes.

Note sure I understand your question. The time windows should be entered as described here.
`

Note that we are currently dealing with an issue with the time windows #101.

When I run my code using just time_windows=True it works well. The problem is that it generates a solution very impracticable it generates a solution of 23 routes for a total of 45 stops. When I add another restriction which is :
prob = vrpy.VehicleRoutingProblem(G, time_windows=True, num_stops=10) it still generates me the 23 routes solution mention before which is understandable due to I just added a limited stops to the routes. However, the real problem comes when I use prob = vrpy.VehicleRoutingProblem(G, time_windows=True, num_vehicles=2, use_all_vehicles=True), always that I add a certain number of vehicles and use it all the output is Exception: problem Infeasible.

If you have a minimal working example it would help. But are you sure the solution is suboptimal ? A safe option is to run the code with ortools which is more robust.

[orlandombaa]

Hello @Kuifje02 thank you for your answer. I will put an example of the data and code here.....

The duration matrix that I generate has the following structure, it is in hours. Additionally, in this example I just selected 30 nodes or clients to visit:

My distance matrix in meters:

My lower and upper time windows have the following structure:

Lower (with a length of 31 and all nodes with value of 7 simulating 7 am):

Upper time windows with a length of 30 and all nodes with a value of 17 simulating 5:00 pm

Both impedance matrices I transform to an array in order to use it in the set up of the network which has the following code:

from numpy import array
import networkx as nx

# Transform distance matrix into DiGraph
A = array(distance, dtype=[("cost", int)])
G_d = nx.from_numpy_matrix(A, create_using=nx.DiGraph())

# Transform time matrix into DiGraph
A = array(duration, dtype=[("time", int)])
G_t = nx.from_numpy_matrix(A, create_using=nx.DiGraph())

# Merge
G = nx.compose(G_d, G_t)

# Set time windows
nx.set_node_attributes(G, values=TIME_WINDOWS_LOWER, name="lower")
nx.set_node_attributes(G, values=TIME_WINDOWS_UPPER, name="upper")

# The depot is relabeled as Source and Sink
G = nx.relabel_nodes(G, {0: "Source", len(distance)-1: "Sink"})

Visualization of the network created:

Execution 1 of the model without restrictions:

prob= vrpy.VehicleRoutingProblem(G)
prob.solve(time_limit=60)

Results total distances in km and stops sequence:

As it can be observed here there is no problem. It tells me 1 vehicle to all the stops

Execution 2 of the model with a maximum of stops per vehicle

prob= vrpy.VehicleRoutingProblem(G, num_stops=10)
prob.solve(time_limit=40)

Results of total distance (km) and sequence of stops:

As it can be observed in this case all works good too. The restriction was maximum 10 stops and was there were 30 nodes to visit, so the model proposed the use of 3 vehicles.

Execution 3 of the model with time windows = true

prob = vrpy.VehicleRoutingProblem(G, time_windows=True)
prob.solve(time_limit=30)

Here is where the problem starts. The model that it generates suggest 12 vehicles:

In theory, in this case, I would expect that suggestion of just 1 vehicle as it was seem in execution 1 because there are 30 stops and they can be visited with 1 vehicle in the period of time from 7 am to 5 pm, maximum with 2 vehicles. So I don't know if this is an internal problem or maybe it's because of the units, that is why my doubt about the units of the travel time matrix and the upper and lower time windows array.

Execution 4 of the model with time windows = true and maximum stops

prob = vrpy.VehicleRoutingProblem(G, time_windows=True, num_stops=10)
prob.solve(time_limit=30)

Results:

When I run it with time_windows=true and num_stops= n it generates a better model BUT it still suggests many vehicles. In this case 10 vehicles. I would wait that it suggest 3 vehicles because the maximum of stops is 10 and the total clients are 30.

I think that the problem can be in the units or some internal problem in the function. I hope you can help me.

Best regards,
Orlando

[orlandombaa]

I run now a code with duration which reading the documentation I understand as a restriction of the total time that the vehicle gives service. I give a value of 1 representing 1 hour of service.

prob= vrpy.VehicleRoutingProblem(G, duration=1)
prob.solve(time_limit=40)

In this case, It generates a suggestion of 1 vehicle that I think that is not possible due to 1 vehicle is not going to visit 30 clients in 1 hour.

If I add a drop penalty of 5 minutes that in hours will be 0.083 it just don't generate nothing:

prob= vrpy.VehicleRoutingProblem(G, duration=1, drop_penalty=0.0833)
prob.solve(time_limit=40)

In general terms, all the errors that I have show up when I involve time

[orlandombaa]

Hello @Kuifje02

Did you get a chance to see it?

Thank you!

[Kuifje02]

Hello @orlandoandradeb, not yet. Will do as soon as I find some time.

[orlandombaa]

@Kuifje02 Thank you !

[Kuifje02]

Hi @orlandoandradeb,
Thanks for posting such detailed feedback. It would be easier to help if the code was replicable (i cannot copy paste the screenshots). I suggest we try to fix the issues one by one. The first issue seems to be with the time windows, and to fix this we need to solve issue #101.

[orlandombaa]

Hello @Kuifje02 Thank you for you answer. I will send you the code, I am working on it to make it smaller and easy to navigate on it, is it ok if I share it with you tomorrow?

Best regards,
Orlando