num_vehicles

[egh312]

Hello!

I'm not convinced the num_vehicles parameter is working as expected.
Running a network with 95 nodes and 8 vehicles.
Total demand is 95 (1 per node), load_capacity is 13 (13*8 =104 so some slack)

Solver doesn't appear to restrict to the 8 vehicles and repeats nodes:

I have attached the graph pikle file too, if needed for debug:
EH_graph.txt

Best.
Ed

[Kuifje02]

Thanks for your feedback.

This is a problem indeed. The EH_graph.txt is not readable, could you try another format ?

I am pretty sure this is because the graph is starting to be big.. The solver is violating the "num vehicles" constraint at the expense of a high penalty (~120000000000) We'll see how we can try and make this work.

[egh312]

Ok - that makes sense.

For the file i think if you were to save the EH_graph file and use "nx.read_gpickle" to read the path it should work
https://networkx.github.io/documentation/stable/reference/readwrite/gpickle.html

I've attached a zipped YAML file if not
EH_graph2.zip

Best.
Ed

[Kuifje02]

Nice, I didn't know this read_gpickle existed, very handy !

So indeed, this is what is happening: the initial solution that is computed is not feasible as it is using more than 8 vehicles. As the algorithm converges, it should 1) improve the objective function 2) repair this infeasibility, but right now it is too slow and fails to repair with the given time limit.

This is on our top priority items to improve ! But it is not really a bug, just a lack of efficiency. It would have been easier to fix if it were a bug!

As a quick fix, simple heuristics will be implemented to have a feasible starting point. Coming soon.

[Kuifje02]

This data set is interesting. After playing around with it, I observed that from one heuristic to another, the solution is quite different. In particular, the Clarke & Wright heuristic used by vrpy to find an initial solution performs very poorly compared to other simple heuristics.

How was this data generated (the costs) ?

[egh312]

Costs relate to actual distances/durations derived from the Open Source Routing Machine (OSRM).
http://project-osrm.org/docs/v5.22.0/api/#general-options

I'm currently doing my Masters thesis on vehicle routing within the context of a small service company - comparing what they do today with an analytically/programmatically driven routing. Nodes are customer locations and costs are the distances/durations between them as determined by OSRM

[Kuifje02]

If you git clone the current master branch and run the algorithm with the above data, a feasible initial solution is computed (8 vehicles). This feature will be in the next release, but in the mean time, the master branch works. Please let me know everything works fine so I can close the issue.
PS: good luck on the masters thesis, and don't hesitate using vrpy and asking for relevant features that could help.

[egh312]

Thank you!