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
106 stars 10 forks source link

Insufficient time to serve a node in CVRPTW problem #11

Closed taox142 closed 8 months ago

taox142 commented 9 months ago

Hello there,

First, thank you for the great work on the vrp solver. It is quite easy to use and really fast in many cases.

But I just came across this weird issue, that the route seems to be feasible, but the solver says "There is insufficient tiem to serve a node." I've attached the model details below. It is quite small, only ONE node.

Thank you in advance for looking into this. Please let me know if I need to clarify the issue clearer.

Best regards, Tao

{ "MaxTotalVehiclesNumber": 10000, "Points": [ { "id": 0, "name": "0", "idCustomer": 0, "serviceTime": 0.0, "twBegin": 0, "twEnd": 1821, "penaltyOrCost": 0.0, "demandOrCapacity": 0, "incompatibleVehicles": [] }, { "id": 1, "name": "1", "idCustomer": 1, "serviceTime": 1023.6245850412403, "twBegin": 212.37541495875976, "twEnd": 1236.0, "penaltyOrCost": 0.0, "demandOrCapacity": 199, "incompatibleVehicles": [] } ], "VehicleTypes": [ { "id": 1, "startPointId": 0, "endPointId": 0, "name": "VEH1", "capacity": 200, "fixedCost": 0.0, "varCostDist": 1, "varCostTime": 0.0, "maxNumber": 90, "twBegin": 0.0, "twEnd": 1821 } ], "Links": [ { "startPointId": 0, "endPointId": 1, "name": "", "isDirected": true, "distance": 171.40595088852663, "time": 171.40595088852663, "fixedCost": 0.0 }, { "startPointId": 1, "endPointId": 0, "name": "", "isDirected": true, "distance": 244.24782496472716, "time": 244.24782496472716, "fixedCost": 0.0 } ], "Parameters": { "timeLimit": 3600, "action": "solve", "upperBound": 1000000, "heuristicUsed": false, "timeLimitHeuristic": 20, "configFile": "", "solverName": "CLP", "printLevel": -1 } }

rrsadykov commented 9 months ago

@najibprog, can you check this issue?

najibprog commented 9 months ago

Dear @taox142 thank you for your interest in our solver, the solver returns an error because for the first node, twBegin + serviceTime(1,236.00000000000006) > twEnd (1,236).

Best regards, Najib

taox142 commented 8 months ago

@najibprog, thank you for looking into the issue.

Yes, you are right. Even though I computed twEnd by twBegin + serviceTime, somehow, the computer messed up with the accuracy. I fixed the issue by setting twEnd = twBegin + serviceTime + 0.000001. Works now.

najibprog commented 8 months ago

Great! Thank you for taking the time to test, we think it will be better in the future to introduce rounding to 10^-(6) to avoid this kind of issue.

Best regards, Najib