VRP with starting points but no ending points

[Kejvi Doko]

I am trying to solve a VRP problem with pickup and delivery with starting points but no ending points. 

I have fleet of drivers (starting points gps locations)  who do food delivery. I also got restaurants ( that will act as pickup locations) and clients ( that will act as delivery points).

Is there a way to model this problem so I supply the starting points, pickup and delivery but not ending points. Algorithm now return No Solution.

Regards 

Kejvi

[Priidik Vilumaa]

Did not check your code, but implementing "no ending points" is well described here:

https://developers.google.com/optimization/routing/routing_tasks#allowing-arbitrary-start-and-end-locations

Best,

Priidik

[Kejvi Doko]

yeas I have seen this, but the problem with this example is that it works on 1 depot, in my case all the pickup locations are depots 

[Kejvi Doko]

so I have a case of VRP with Pickup (depots) & Delivery, with arbitrary start and end locations

[Priidik Vilumaa]

I don't see why multiple depots would be a problem.  For arbitrary ends set the values in the distance matrix from anywhere to these locations to 0. That way it doesn't really matter where the routes will end "before heading back to the depot".

Btw you are using location 4 as a pickup for multiple pickups-deliveries. This does not work and you have to duplicate the node. This could a be a cause for infeasibility. Additionally, I'm not sure if a "depot" or starting location can be a pickup.

Best,

Priidik

[youssef kaichouh]

Hello, you can set distance(point->depot) = 0 for every point and depot in your probleme 

--
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/ed8417d9-ba06-4d2d-9cf7-24ba312a4658n%40googlegroups.com.

[Kejvi Doko]

thanks, I was able to fix the issue, tried with some other data points and it was able to solve it but, it included another point that wasn't needed 

data['distance_matrix'] = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[2265, 0, 5442, 7472, 7344, 8140, 10112, 11045, 7340, 8844, 8453, 6039, 6474, 8523, 1998, 2907, 3387, 1466, 5136, 4466],
[4626, 3134, 0, 4806, 4678, 5474, 7446, 8378, 5555, 9014, 6668, 5987, 6259, 9862, 1709, 993, 1546, 2184, 3351, 5795],
[8384, 6892, 3694, 0, 1925, 3013, 4216, 5148, 3561, 4821, 4675, 6049, 6809, 13621, 5468, 4751, 3834, 5942, 3870, 7458],
[8519, 7027, 3829, 1849, 0, 1218, 2420, 3353, 3838, 4019, 5159, 6534, 7293, 13755, 5602, 4886, 3969, 6077, 4355, 7942],
[9044, 7552, 4353, 2815, 1218, 0, 1736, 2585, 4800, 4981, 6126, 7501, 8260, 14280, 6127, 5411, 4494, 6602, 5321, 8909],
[11012, 9520, 6322, 4018, 2420, 1737, 0, 1544, 5358, 5539, 7289, 8664, 9463, 16249, 8096, 7379, 6462, 8570, 6524, 10112],
[11944, 10453, 7254, 4595, 3148, 2585, 1465, 0, 4682, 4863, 6613, 7988, 8887, 17181, 9028, 8312, 7395, 9502, 5948, 9536],
[8581, 6909, 6643, 3561, 4001, 4800, 5358, 4682, 0, 1071, 2737, 4112, 4976, 7134, 8417, 7700, 6783, 8891, 2187, 5775],
[9576, 7903, 7902, 4821, 4019, 4981, 5539, 4863, 1071, 0, 1943, 3317, 4181, 7911, 9676, 8960, 8043, 10151, 3182, 6041],
[9703, 8030, 7764, 4683, 5122, 6089, 6711, 6761, 2746, 1922, 0, 2117, 2981, 6711, 9538, 8822, 7905, 10012, 3309, 4840],
[7664, 5992, 6557, 5875, 6315, 7281, 7903, 7953, 3938, 3115, 1934, 0, 1608, 4066, 5966, 7614, 6697, 6552, 3401, 2850],
[7810, 6138, 6931, 6802, 7241, 8208, 8830, 8880, 5119, 4617, 3436, 1648, 0, 3786, 6112, 7021, 7071, 6698, 4304, 2140],
[10263, 8591, 12039, 8171, 13941, 14737, 16709, 17641, 6488, 7992, 6649, 4381, 3796, 0, 8595, 9504, 9984, 9626, 5673, 1398],
[3870, 2378, 3842, 5872, 5744, 6539, 8512, 9444, 5740, 7244, 6853, 6171, 6444, 9106, 0, 1306, 1786, 1428, 3535, 5039],
[3996, 3059, 3060, 5090, 4962, 5758, 7730, 8662, 8039, 9298, 9152, 6794, 7066, 9506, 1353, 0, 625, 1554, 4158, 5439],
[4501, 3564, 863, 4372, 4244, 5040, 7012, 7944, 7321, 8581, 8434, 7298, 7571, 10011, 1858, 613, 0, 2059, 4662, 5943],
[2811, 1466, 3867, 5898, 5769, 6565, 8537, 9470, 6121, 7625, 7234, 6552, 6825, 8944, 1112, 1332, 1812, 0, 3916, 4739],
[6367, 4694, 3871, 3870, 4310, 5276, 5898, 5948, 2187, 3691, 3301, 3401, 4310, 6318, 4668, 4929, 4012, 6120, 0, 4959],
[6398, 4725, 12655, 6994, 7434, 8400, 9022, 9072, 5311, 6124, 4943, 3006, 2549, 1571, 9211, 10119, 10599, 10241, 4496, 0]
]

data['pickups_deliveries'] = [
[4, 3],
[5, 9],
[7, 8],
[15, 11],
[13, 12],
[6, 14],
[17, 19],
]
data['num_vehicles'] = 4

data['starts'] = [1, 2, 10, 16]
data['ends'] = [0, 0, 0, 0]

It returns this solution:

Route for vehicle 0:

 1 ->  17 ->  19 ->  13 ->  12 -> 0

Distance of the route: 19382m

Route for vehicle 1:

 2 ->  4 ->  6 ->  3 ->  14 -> 0

Distance of the route: 20454m

Route for vehicle 2:

 10 ->  7 ->  8 ->  18 -> 0

Distance of the route: 19997m

Route for vehicle 3:

 16 ->  15 ->  5 ->  9 ->  11 -> 0

Distance of the route: 22333m

Total Distance of all routes: 82166m

Why is jumping to 18 , from 8 it should jump to 0. Did I setup something wrong ?

[Kejvi Doko]

for visualisation on the map 

[Priidik Vilumaa]

Well, node 18 exists and by default it must be visited by some vehicle. My guess is that node 8 was closest to 18, that's why it's 8 - > 18 -> 0.

[Rawan Gaafar]

Hello Kejvi, I was wondering if you were able to solve this?
I am trying to do something similar but I am having illogical routes.