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.