Pickup and Delivery Problem

[frozeniceblue]

Thank you for your great project! I have a small question and I would like to know that if I want to set up the constraints that for example pickups_deliveries = {(2, 4): 1, (2, 1): 2, (3, 1): 3} we pick up from node 2,3 and deliveries to node 1,4 and we go to every node only once. But now we only setup G.nodes[u]["request"] = v for one node has one request. So I want to know that how to setup that one node has more than one request? Thank you very much!

[Kuifje02]

Thanks @frozeniceblue for reaching out!

In this case you can create as many copies of node v as necessary. For example, if node v as two requests, create v1 and v2 so that you can have G.nodes[u]["request"]= v1 and G.nodes[u]["request"] = v2.

[frozeniceblue]

Thanks @frozeniceblue for reaching out!

In this case you can create as many copies of node v as necessary. For example, if node v as two requests, create v1 and v2 so that you can have G.nodes[u]["request"]= v1 and G.nodes[u]["request"] = v2.

Thanks for your reply. In this case, as you said above, PICKUPS_DELIVERIES = {(2, 4): 1, (2, 1): 2} G.nodes[2]["request"] = 4 G.nodes[2]["demand"] = PICKUPS_DELIVERIES[(2, 4)] G.nodes[4]["demand"] = -PICKUPS_DELIVERIES[(2, 4)] G.nodes[2]["request"] = 1 G.nodes[2]["demand"] = G.nodes[2]["demand"] + PICKUPS_DELIVERIES[(2, 1)] G.nodes[1]["demand"] = -PICKUPS_DELIVERIES[(2, 1)]

the result that G.nodes[2]["request"] =1 will cover the result G.nodes[2]["request"] = 4 before, so that we print G.nodes[2] {'request': 1, 'demand': 5, 'collect': 0, 'service_time': 0, 'lower': 0, 'upper': 0, 'frequency': 1} The 'request': 4 is missing. Could you help me with that? Thank you very much.

[Kuifje02]

Here is how I would do it:

PICKUPS_DELIVERIES = {(2a, 4): 1, (2b, 1): 2}

G.nodes[2a]["request"] = 4
G.nodes[2a]["demand"] = PICKUPS_DELIVERIES[(2a, 4)]
G.nodes[4]["demand"] = -PICKUPS_DELIVERIES[(2a, 4)]

G.nodes[2b]["request"] = 1
G.nodes[2b]["demand"] = PICKUPS_DELIVERIES[(2b, 1)]
G.nodes[1]["demand"] = -PICKUPS_DELIVERIES[(2b, 1)]

So instead of working with node 2, duplicate it into 2a and 2b.

[frozeniceblue]

Here is how I would do it:

PICKUPS_DELIVERIES = {(2a, 4): 1, (2b, 1): 2}

G.nodes[2a]["request"] = 4
G.nodes[2a]["demand"] = PICKUPS_DELIVERIES[(2a, 4)]
G.nodes[4]["demand"] = -PICKUPS_DELIVERIES[(2a, 4)]

G.nodes[2b]["request"] = 1
G.nodes[2b]["demand"] = PICKUPS_DELIVERIES[(2b, 1)]
G.nodes[1]["demand"] = -PICKUPS_DELIVERIES[(2b, 1)]

So instead of working with node 2, duplicate it into 2a and 2b.

Thank you for your reply again. But I am still a little puzzle. You mean just like this below or change the distances matrix? a = 2 b = 2 PICKUPS_DELIVERIES = {(a, 4): 1, (b, 1): 2}

G.nodes[a]["request"] = 4 G.nodes[a]["demand"] = PICKUPS_DELIVERIES[(a, 4)] G.nodes[4]["demand"] = -PICKUPS_DELIVERIES[(a, 4)]

G.nodes[b]["request"] = 1 G.nodes[b]["demand"] = PICKUPS_DELIVERIES[(b, 1)] G.nodes[1]["demand"] = -PICKUPS_DELIVERIES[(b, 1)]

But it still means G.nodes[2] and G.nodes[a]["request"] = 4 will be covered. Could you help me again? How to duplicate it and solve? Thank you very much.

[Kuifje02]

Yes you have to "physically" duplicate the nodes, and adapt the distance matrix accordingly. Consider that node 2 is in a set of two buildings (2a and 2b) that have the same location, but that must be separate in the network.

But it still means G.nodes[2] and G.nodes[a]["request"] = 4 will be covered.

I am not sure I understand this statement.

[frozeniceblue]

Yes you have to "physically" duplicate the nodes, and adapt the distance matrix accordingly. Consider that node 2 is in a set of two buildings (2a and 2b) that have the same location, but that must be separate in the network.

But it still means G.nodes[2] and G.nodes[a]["request"] = 4 will be covered.

I am not sure I understand this statement.

Thank you. I understood that I need to change the distance matrix first. Just like this below: DISTANCES = [ [0,10,4,4,7,0], [0,0,6,6,7,10], [0,6,0,0.1,5,4], [0,6,0.1,0,5,4], [0,7,5,5,0,7], [0,0,0,0,0,0] ] PICKUPS_DELIVERIES = {(2, 4): 1, (3, 4): 2} we duplicated [0,6,0,0,5,4] to the next line and only change point 2 to point 3 distance from 0 to 0.1 [0,6,0,0.1,5,4], [0,6,0.1,0,5,4], because two points distances are 0, they cannot travel from one to another.

[frozeniceblue]

Yes you have to "physically" duplicate the nodes, and adapt the distance matrix accordingly. Consider that node 2 is in a set of two buildings (2a and 2b) that have the same location, but that must be separate in the network.

But it still means G.nodes[2] and G.nodes[a]["request"] = 4 will be covered.

I am not sure I understand this statement.

Another question is about open vrp. The definition is below: The open VRP refers to the case where vehicles can start and/or end their trip anywhere, instead of having to leave from the depot, and to return there after service. This is straightforward to model : setting distances (or costs) to on every edge outgoing from the Source and incoming to the Sink achieves this. You mean just like this? DISTANCES = [ [0,0,0,0,0,0], [0,0,6,6,7,0], [0,6,0,0.1,5,0], [0,6,0.1,0,5,0], [0,7,5,5,0,0], [0,0,0,0,0,0] ] Or any other change to satisfy the open vrp problem? I know I take you lots of time to help me solve the problem. Thank you very much.

[Kuifje02]

we duplicated [0,6,0,0,5,4] to the next line and only change point 2 to point 3 distance from 0 to 0.1 [0,6,0,0.1,5,4], [0,6,0.1,0,5,4], because two points distances are 0, they cannot travel from one to another.

Yes indeed, that is a good point. It is a good idea to use 0.1 in this case. It looks like you got it right, although I cannot validate it 100% without having more knowledge of the problem and data. But it looks correct.

For the open vrp, what you wrote is correct ! But you might need to use the same trick : use 0.1 and not 0 otherwise the edge might not be created at all.