Negative and possitive demand in CVRP

[Angela García Mínguez]

Hello,

I have to solve a problem related with capacitated vehicle routing problem  (https://developers.google.com/optimization/routing/cvrp). Let's say that in this case the vehicle has to pick up and deliver items in different locations. The items to pick up of deliver are always the same, it could be, for example, bicycles in different points of a city. So, my initial input is the number of items left over or missing at each point, and also the capacity of the vehicle. (I haven't thought about solve it with pick-up delivery or-tools approach because I don't have pairs points of pick up and deliver, as the items are the same it does not matter)

I tried to solve the problem with CVRP, just writing some demands in negative, for example:

data['demands'] = [0, 1, -1, 2, 4, -2, -4, 8, 8, 1, -2, 1, -2, 4, 4, 8, -8]

When I execute the code, I have a result, but I don't know if is correct because the documentation says that it is for one case or the other, but not for delivery and pick up together.

Can you tell me if this approach is correct? , and if I can use CVRP in this use case? Thank you very much. 

[youssef kaichouh]

Hello, i think u need to a add a constraint such that for a given vehicle, the sum of loads is 0 for each type of items 

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/86feef60-9cf0-4a98-be1d-589ecea0cff8n%40googlegroups.com.

[Angela García Mínguez]

Hello, 

Sorry, I am not sure if I understand you. I just have one vehicle (I could add more, but the thing I mentioned before would be for any vehicle); and also I just have one type of items: as I said an example could be the distribution of bicycles among different bike stations in a city , where different points could have a positive or negative demand.

[Priidik Vilumaa]

Hi Angela,

I understand you're trying to rebalance something (say bikes) by taking them from some locations to another location without caring how the pickup-delivery pair is formed.

I've used the +x and -x demands for pickup and delivery and it works, and I believe it would work for your case as well. If I'm not mistaken, then dimensions in OR-Tools can't be negative, hence the vehicle always needs to pick something up before dropping it off.

But obviously you should check the solution yourself. A good practice imo is to write a separate piece of code that verifies all constraints. Then, by having 2 implementations you'll often find issues. 

Best,

Priidik

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/57b389e9-ba84-4618-8566-cd042ab9b253n%40googlegroups.com.

[Angela García Mínguez]

Hello, 

Many thanks for your answer. 

In the end I solved the problem, I made the vehicle to pick up in the depot as many bikes at it is necessary to not make the total number negative (pick-ups - deliveries).  And it worked :-)

Regards, Ángela