Multiple delivery points

[gabtorr]

Hi guys,
Im facing an issue, i was using some code developed for my team to solve the mdPnD problem. We decide to move to your tool, because.. well its google. Anyway, im facing the problem for add more than one delivery point for each pickup on the example code in the site. I tried trying to add the same pickup and nothing happen, like this:

data['pickups_deliveries'] = [
        [1, 10],
        [1, 6],
        [1, 3],
        [5, 9],
        [7, 8],
        [15, 11],
        [13, 12],
        [16, 14],
    ]

And this way throw error because its a tuple:

data['pickups_deliveries'] = [
        [(1,10), (1,3)],
        [2, 6],
        [5, 9],
        [7, 8],
        [15, 11],
        [13, 12],
        [16, 14],
    ]

Probably is a syntax error or something that im not seeing. Thanks in advance :) .

[Killajam]

I had the same problem.I tried your first method, but the solver couldn't find a solution.
I found a similar problem on Google, but I don't understand it, I don't know if I can help you.Can you tell me the solution if you understand?
https://stackoverflow.com/questions/63761021/multi-pickup-per-delivery-with-disjunction-fails-to-find-partial-solution

[Killajam]

Hey bros,
I tried another approach, where you split the same point in half, for example, and you have two requirements: 1-3,1-4.
Then you put the loading point split into 1, 2, then you can be in accordance with the method of case 1-3, 2-4 join PickupandDelivery, like:

routing. AddPickupAndDelivery (1, 3),
routing. AddPickupAndDelivery (2, 4).

The last step is to add 1 and 2 to the same car,
routing.solver().Add(routing.VehicleVar(1) == routing.VehicleVar(2))
I have succeeded in this way. My English is not very good and I wonder if you can understand it. If there is any problem, we can communicate with each other.

[gabtorr]

When you say "split point" in two rows on the matrix, you are saying split the distance or just duplicate the row? I tried duplicating rows but i don't think that is the correct approach because the solution is not efficient for more than one pickup with multiple drop offs.
The matrix (on the approach that i took) looks like this:

data['distance_matrix'] = [ 
        [0.0, 3.8755, 5.8384, 2.5037],
        [0.0, 3.8755, 5.8384, 2.5037],
        [0.0, 3.8755, 5.8384, 2.5037],
        [0.0, 3.8755, 5.8384, 2.5037],
        [3.8755, 0.0, 9.6633, 1.8155],
        [5.8384, 9.6633, 0.0, 8.0376],
        [2.5037, 1.8155, 8.0376, 0.0],
        [0.0, 3.8755064092579734, 5.838486587012245, 2.5037344385273412],
        [0.0, 3.8755064092579734, 5.838486587012245, 2.5037344385273412],
        [0.0, 3.8755064092579734, 5.838486587012245, 2.5037344385273412],
        [3.8755064092579734, 0.0, 9.663317933350793, 1.8155862596813435],
        [5.838486587012245, 9.663317933350793, 0.0, 8.037608977792793],
        [2.5037344385273412, 1.8155862596813435, 8.037608977792793, 0.0]
    ]

And the pickup and delivery pairs are:

data['pickups_deliveries'] = [
        [1, 4],
        [2, 5],
        [3, 6],
        [7, 10],
        [8, 11],
        [9, 12],
    ]

As you can see also i use the depot (row 0) as a delivery point.

[Mizux]

your distance matrix should be square here you have a 13x4 matrix...
note: or you may have some hack in the callback method...

[gabtorr]

Hi, as @Mizux says the matrix should be sqare, so then i faced another problem, when i have more than 40 drop offs for each pickup, and in a hypothetical case of 3 pickups, the matrix will have 14400 numbers (120 * 120 ). That leads to an unoptimal process, imo, besides its necessary to add 120 delivery points, and of course 39 restrictions (routing.solver().Add(routing.VehicleVar(1) == routing.VehicleVar(2)), etc. ), at least, for each pickup. So i was looking if is there any other restriction that could help improve this kind of problems?, like asume that if you passed for one pick up point you passed for the other 40 repeated or use just three rows and then hack something on resolver in order to reduce the data on matrix (43*43).
Thanks in advance :)

[lperron]

Exactly. Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53 00 Le jeu. 7 janv. 2021 à 09:30, Killajam <[email protected]> a écrit :

…

Hey bros, I tried another approach, where you split the same point in half, for example, and you have two requirements: 1-3,1-4. Then you put the loading point split into 1, 2, then you can be in accordance with the method of case 1-3, 2-4 join PickupandDelivery, like: routing. AddPickupAndDelivery (1, 3), routing. AddPickupAndDelivery (2, 4). The last step is to add 1 and 2 to the same car, routing.solver().Add(routing.VehicleVar(1) == routing.VehicleVar(2)) I have succeeded in this way. My English is not very good and I wonder if you can understand it. If there is any problem, we can communicate with each other. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2313 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3OTK476M7D54VCZHWDSYVWLNANCNFSM4VTJHP3Q> .

[lperron]

Distances must be integral. Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53 00 Le jeu. 7 janv. 2021 à 14:17, gabtorr <[email protected]> a écrit :

…

When you say "split point" in two rows on the matrix, you are saying split the distance or just duplicate the row? I tried duplicating rows but i don't think that is the correct approach because the solution is not efficient for more than one pickup with multiple drop offs. The matrix (on the approach that i took) looks like this: data['distance_matrix'] = [ [0.0, 3.8755, 5.8384, 2.5037], [0.0, 3.8755, 5.8384, 2.5037], [0.0, 3.8755, 5.8384, 2.5037], [0.0, 3.8755, 5.8384, 2.5037], [3.8755, 0.0, 9.6633, 1.8155], [5.8384, 9.6633, 0.0, 8.0376], [2.5037, 1.8155, 8.0376, 0.0], [0.0, 3.8755064092579734, 5.838486587012245, 2.5037344385273412], [0.0, 3.8755064092579734, 5.838486587012245, 2.5037344385273412], [0.0, 3.8755064092579734, 5.838486587012245, 2.5037344385273412], [3.8755064092579734, 0.0, 9.663317933350793, 1.8155862596813435], [5.838486587012245, 9.663317933350793, 0.0, 8.037608977792793], [2.5037344385273412, 1.8155862596813435, 8.037608977792793, 0.0] ] And the pickup and delivery pairs are: data['pickups_deliveries'] = [ [1, 4], [2, 5], [3, 6], [7, 10], [8, 11], [9, 12], ] As you can see also i use the depot (row 0) as a delivery point. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2313 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MOAMAI75LYTFWSN23SYWYALANCNFSM4VTJHP3Q> .