search

inria-UFF / VRPSolverEasy

A simple Python interface for VRPSolver, a state-of-the-art Branch-Cut-and-Price exact solver for vehicle routing problems
https://vrpsolvereasy.readthedocs.io/en/latest/
MIT License
111 stars 10 forks source link

Directed Graph Issue #19

Closed yjpak0608 closed 2 weeks ago

yjpak0608 commented 8 months ago

Hi, I am working on a special type CVRP problem. And allmost done. But at last step, I found a big problem. Is it impossible to solve CVRP on a directed graph? add_link() method has a parameter "is_directed". But looking a final solution, it seems that this parameter was ignored. I am using a free version.

yjpak0608 commented 8 months ago

When we solve the example problem, the results are follows.

Solution cost : 1479.6800000008684

Route for vehicle 1: ID : 0 --> 2 --> 5 --> 0 Name : D1 --> Vermont, USA --> Rhode Island, the US --> D1 End time : 0.0 --> 16.807 --> 19.259 --> 37.230000000000004 Load : 0.0 --> 300.0 --> 1041.0 --> 1041.0 Total cost : 372.29999999999995

Route for vehicle 1: ID : 0 --> 1 --> 3 --> 0 Name : D1 --> West Virginia, USA --> Texas, the USA --> D1 End time : 0.0 --> 10.548 --> 31.625 --> 48.728 Load : 0.0 --> 500.0 --> 1100.0 --> 1100.0 Total cost : 487.2800000000001

Route for vehicle 1: ID : 0 --> 4 --> 6 --> 0 Name : D1 --> South Dakota, the US --> Oregon, the US --> D1 End time : 0.0 --> 10.5 --> 31.006 --> 62.010000000000005 Load : 0.0 --> 658.0 --> 1094.0 --> 1094.0 Total cost : 620.1

For the test, I added two lines before model.solve().

model.delete_link(0,2) model.add_link(2,0,is_directed=True)

But the result is that there is no change in the route. (0 --> 2 --> 5 --> 0)

Solution cost : 1311.6100000004874

Route for vehicle 1: ID : 0 --> 2 --> 5 --> 0 Name : D1 --> Vermont, USA --> Rhode Island, the US --> D1 End time : 0.0 --> 0.0 --> 2.452 --> 20.423000000000002 Load : 0.0 --> 300.0 --> 1041.0 --> 1041.0 Total cost : 204.23000000000002

Route for vehicle 1: ID : 0 --> 4 --> 6 --> 0 Name : D1 --> South Dakota, the US --> Oregon, the US --> D1 End time : 0.0 --> 10.5 --> 31.006 --> 62.010000000000005 Load : 0.0 --> 658.0 --> 1094.0 --> 1094.0 Total cost : 620.1

Route for vehicle 1: ID : 0 --> 1 --> 3 --> 0 Name : D1 --> West Virginia, USA --> Texas, the USA --> D1 End time : 0.0 --> 10.548 --> 31.625 --> 48.728 Load : 0.0 --> 500.0 --> 1100.0 --> 1100.0 Total cost : 487.2800000000001

instance-issue.json

rrsadykov commented 8 months ago

Thanks for reporting this issue. Can you also please share the JSON file for this instance?

@najibprog Can you please check whether this issue is caused by the Python library or by the C++ code?

najibprog commented 7 months ago

I checked this issue, and it seems to be coming from the cpp part because we are sending the correct information in json.

Best regards, Najib

rrsadykov commented 7 months ago

@najibprog, I have found a bug in the C++ code related to this issue, and pushed correction for it (BaPCod version 0.82.7), can you update the file in the BaPCod web-site? After that, you can close this issue.

rrsadykov commented 5 months ago

@najibprog, it seems that the version available on BaPCod web-site is still 0.82.5. Is it possible to update it to 0.82.7?

najibprog commented 4 months ago

@rrsadykov, the version is awaiting validation, I will deploy it when the arm test is validated.

Best regards, Najib

rrsadykov commented 4 months ago

@najibprog ARM test is ok, I have sent you an e-mail.

najibprog commented 2 weeks ago

The ARM version is available in latest Bapcod release