search

Kuifje02 / vrpy

A python framework for solving the VRP and its variants with column generation.
MIT License
179 stars 43 forks source link

Multi commodity pickup and delivery VRP #80

Closed vnramirez closed 3 years ago

vnramirez commented 3 years ago

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

Kuifje02 commented 3 years ago

Hi @vnramirez thanks for your feedback, much appreciated !

It looks like your problem is a multi-commodity flow problem. There are several problems :

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.

vnramirez commented 3 years ago

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.

vnramirez commented 3 years ago

(I also tried asking on or.stackexchange but didn't get a single reply :( )

Kuifje02 commented 3 years ago

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.