Time limit not working with HFCVRP

[YueCastillo]

I set up a VehicleRoutingProblem with mixed fleet and load capacity parameters, I also added a time limit (to prob.solve) equals to 1 minute. Nevertheless, the solver does not stop. In other cases, for example in the CVRP with resource constraints, it works just fine and stops iterations once the time has been reached.

[Kuifje02]

Hi ! Could you please provide a minimum working example that we could reproduce ? I suspect that the instance has a lot of vertices ;)

[YueCastillo]

Thanks for replying so fast, and for sure, I'm gonna describe what I'm doing.

I've got this matrix: costs_matrix.csv and 5 different types of vehicles:

vehicles_cap = [{'type': 'Bicicleta', 'capacity': 10}, {'type': 'Motocicleta', 'capacity': 20}, {'type': 'Automovil', 'capacity': 80}, {'type': 'Van_electrica', 'capacity': 80}, {'type': 'Camioneta', 'capacity': 1}]

So I'm creating the net as: [gnet.add_edge(i, j, cost=[dt.loc[i, j]] * n_vehicle_types) for i in dt.index for j in dt.columns] where dt is a Pandas data frame containing the matrix from the attached file and n_vehicle_types is five -the length of vehicles_cap. Please note that I'm not setting any differences in the costs, I'm just replicating it, so the length of the costs list matches that of the capacities.

I forgot to describe the nodes from the net, it simply is: [gnet.add_node(i, demand=1) for i in dt.index]

Having the net, I'm passing it to the VehicleRoutingProblem as: prob = VehicleRoutingProblem(net, mixed_fleet=mx_fleet, load_capacity=lcapacity). Here net is the net I just created above, mx_fleet is a bool set to True and lcapacity is the list of capacities from vehicles_cap.

And finally, I'm adding the following to the problem:

1. prob.duration = max_time, with max_time equal to 8.
2. prob.num_stops = nstops, with nstops set as the length of the cost matrix, 101 for this example.
3. prob.solve(time_limit=limit_time), limit_time is one minute

The solver starts and one, two, or three iterations results are presented, my problem is that when the time limit is reached the process does not stop.

Hope it helps to clarify.

[Kuifje02]

Yes, I think it is because with 101 nodes, the solver does not have time to finish. Try 1/ increasing the time limit 2/ constraining the problem a bit more to help convergence, e.g., set prob.num_stops to 5, just to see if it helps 3/ return the solution from the heuristic with prob.solve(heuristic_only=True).

[YueCastillo]

Ok, I'll try with 1 and 2 since prob.solve(heuristic_only=True) returns ValueError: Clarke & Wright heuristic not compatible with time windows, pickup and delivery, simultaneous distribution and collection, mixed fleet, frequencies. and I'm working with mixed fleet.

[YueCastillo]

Well, I guess the problem is not the number of nodes. Sometimes the solver works fine, meaning, it iterates and stops once the time is reached (shows Time's up message), but in some other cases it does not. My most recent test was with 155 nodes, it generates 208 iterations but for some reason it gets stuck (does not present the Time's up message, does not show an error, and the console freezes -everything else continues up and running)

[torressa]

What version of cspy are you on? Try cspy=False when calling solve. Also, the csv you provided does not contain a valid network. There is no Source node.

KeyError: 'Input graph requires Source and Sink nodes.'

Code to reproduce

import pandas as pd
from networkx import DiGraph, relabel_nodes
from vrpy import VehicleRoutingProblem

vehicles_cap = [
    {"type": "Bicicleta", "capacity": 10},
    {"type": "Motocicleta", "capacity": 20},
    {"type": "Automovil", "capacity": 80},
    {"type": "Van_electrica", "capacity": 80},
    {"type": "Camioneta", "capacity": 1},
]

dt = pd.read_csv("tests/costs_matrix.csv")
G = DiGraph()
n_vehicle_types = 5

[
    G.add_edge(i, j, cost=[dt.loc[i, j]] * n_vehicle_types)
    for i in dt.index
    for j in dt.columns
]
prob = VehicleRoutingProblem(
    G,
    mixed_fleet=True,
    duration=8,
    load_capacity=[v["capacity"] for v in vehicles_cap],
)

[YueCastillo]

@torressa My cspy version is 1.0.1. About the source and sink nodes, there's a function that creates them using the mean of lat and long -because those nodes do not exist in my database and the vehicles should start and return from/to those dummy nodes. Now, I tried with cspy=False but I'm getting:

pulp.apis.core.PulpSolverError: Pulp: Error while executing /home/alberto/.local/lib/python3.8/site-packages/pulp/apis/../solverdir/cbc/linux/64/cbc

I reinstalled puLp and tried what is suggested here but nothing changed.

[YueCastillo]

Anyway, I think the problem is not how we solve or the problem size. If I increase the time limit I get a lot more iterations (523 in my last attempt) but once the time's up it is not returning the last solution, there's no output at all. I just noticed that even though it's not generating more iterations, the CPU usage remains at 100%

[Kuifje02]

@YueCastillo Please provide the complete code so that we can reproduce the error. Right now, we cannot.

[YueCastillo]

@Kuifje02 I do not use Jupyter in my project, but I was able to replicate the issue in a notebook. A sample of the data frames I'm working with were exported and are attached, as well as the notebook, here: replicated.zip.

When the limit was reached, I had 213 iterations in the notebook and 166 in Pycharm:

For both scenarios, it did not show Time's up message, and it kept demanding computational resources.

Pd: Please, let me know if that's enough or if you need anything else from my side.

[Kuifje02]

Hi, I am sorry but still cannot replicate your example. Amongst other problems, I cannot install the datatable module. But above all, this is not really a minimal working example. For the communicty to be able to help you more efficiently, please provide simple self contained code, that can be copied and pasted. For example, you could export your distance matrix, and use the code from here (or similar) to create your minimal working example.

[YueCastillo]

Hi, @Kuifje02 About datatable, it can be easily replaced by pandas (pd.read_csv) but anyway, I'll upload a script for you as soon as I can.

[YueCastillo]

Hi there, @Kuifje02 I'm closing this. I got to understand that the issue occurs if the floats in the distance or time matrix have a decimal part different to zero, so after rounding all of my floats (meaning I use 25.00 instead of 25.2687) it works just fine.