Multi commodity pickup and delivery VRP
Closed this issue · 4 comments
Hey guys,
Your framework is amazing, that's first and thanks a lot for that.
That said, I'm trying to solve a multidepot with multiple commodities problem. I found your pickup and delivery framework pretty familiar with what I'm trying to solve.
This is my issue, actually using the documentation example. There's a dictionary having {(from_node, to_node): amount}, right? The thing is that in my problem, the from_node should be able to dispatch to more than one node. For example: {(1,2): 1, (1,3): 1}, which is not allowed at the moment. Neither with vrpy or the ortools.
Context: I have multiple depots with specific SKU. Then I have "clients" demanding one of these SKU. I have a fleet of K vehicles and I want to generate routes.
Every help will be deeply appreciated.
Vicente
Hi @vnramirez thanks for your feedback, much appreciated !
It looks like your problem is a multi-commodity flow problem. There are several problems :
- there are multiple depots
- there is more than one dispatch node
These two items make your problem quite far away from the standard pickup and delivery problem. Although it may be possible to twist ortools (or vrpy) to solve it, I a think a dedicated solver for this specific problem would be more appropriate and efficient.
If your problem is not too big, you can solve your problem with a MIP. Use variables x(i,j,p), which represent the amount of flow of commodity p that travels on edge (i,j). Minimize Sum c(i,j)x(i,j,p) subject to flow conservation constraints, and capacity constraints.
Or even better : for each customer, for each sku, generate a set of "good" paths, for example the 3 or 4 shortest ones (this is easy to do with NetworkX). Then solve a set partitioning problem, that is, select exactly one path for each customer, subject to capacity constraints. This is a good way to solve multicommodity problems in my experience.
The or.stackexchange forum is a great place to ask questions if you need help.
Hi @Kuifje02 thanks a lot for the response.
I didn't get your second advice! (The one starting by "Or even better...")
Each customer demands an order that's only found on an specific depot. I can find the three best paths from this depot to the customer. This for each customer. And then, how do I merge them to get "clusters"? I mean, I need intelligent sets of customers - depots that fulfill customers' requests and minimize costs.
We can consider a fleet of K homogeneous vehicles with a capacity equal to Q.
Again, thanks, I'm trying to study and solve this but seems very NP-hard.
(I also tried asking on or.stackexchange but didn't get a single reply :( )
Be patient, you will get a reply soon ;) I will post a solution similar to the above with more details as soon as I can. In the mean time, I am closing here.