Pickup and Delivery Problem
frozeniceblue opened this issue · 8 comments
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!
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 @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"]= v1andG.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.
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.
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.
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.
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.
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.
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.