Setting pickup and delivery nodes correctly

AI & Data Science NVIDIA cuOpt cuOpt
1

Hi there,

I am running into an issue that I think might be a easy thing for you all to spot :)

I have a distance matrix setup as follows:

           0          1          2          3
0        0.0       27.0  9999999.0  9999999.0
1       27.0        0.0       28.0  9999999.0
2  9999999.0       28.0        0.0       16.0
3  9999999.0  9999999.0       16.0        0.0

where the values set to 9999999 are invalid paths. I am trying to model a pickup/delivery task, where the optimal route would be:

0 -> 1 -> 2 -> 1 -> 0
where 0 is the start, 2 is the pickup node, and 0 is the dropoff node
In this case, index 3 is neither required nor optimal and I would prefer if it were dropped.

I was initially trying to setup the constraints as below, but always run into the same error of "Pickup/delivery indices size is not equal to number of pairs" no matter the size of my input. Can you shed some light onto what is expected here? I am not sure what is meant by the ‘pairs’ in this error

I’ve tried:

  my_data_model.set_pickup_delivery_pairs(
      cudf.Series([2]
      cudf.Series([0])
  )

as well as:

  my_data_model.set_pickup_delivery_pairs(
      cudf.Series([2, 0, 0, 0]),
      cudf.Series([0, 0, 0, 0])
  )

Secondary question: If I wished to visit a node more than once, am I required to duplicate it? (Like so:)

           0          1          2          3          4          5          6          7
0        0.0        0.0       27.0       27.0  9999999.0  9999999.0  9999999.0  9999999.0
1        0.0        0.0       27.0       27.0  9999999.0  9999999.0  9999999.0  9999999.0
2       27.0       27.0        0.0        0.0       28.0       28.0  9999999.0  9999999.0
3       27.0       27.0        0.0        0.0       28.0       28.0  9999999.0  9999999.0
4  9999999.0  9999999.0       28.0       28.0        0.0        0.0       16.0       16.0
5  9999999.0  9999999.0       28.0       28.0        0.0        0.0       16.0       16.0
6  9999999.0  9999999.0  9999999.0  9999999.0       16.0       16.0        0.0        0.0
7  9999999.0  9999999.0  9999999.0  9999999.0       16.0       16.0        0.0        0.0

based on what I can see in the set_order_locations() docs it seems like multiple visited are supported, but I would just like to be sure. Thanks for any help!

2

From what I can tell, it seems like the issue is that having less pickups/dropoffs than the number of orders is currently not supported with this version. By default it seems to input an order for every entry in the distance matrix, but I am not sure how to edit this. Would there be a way to decrease this to only have orders at specific nodes?

3

Hi,
Thank you for posting the question here. There are three things going on here.

  1. ReOpt expects the distance matrix to contain the shortest distances (or associated costs) between all pairs. For the above-mentioned problem, if the order needs to be picked up at location 2 and dropped off at 0, the generated route would be 0 -> 2 -> 0 if the run was successful. So for the input, the distance matrix should be:
            0          1          2                           3
0        0.0       27.0   55.0 (27.0+28.0)     71.0 (27.0 + 28.0 + 16.0)
1       27.0        0.0   28.0                         44.0 (28.0 + 16.0)
2       55.0      28.0     0.0                         16.0
3       71.0      44.0   16.0                         0.0
  1. By default, ReOpt assumes that there is exactly one location per order (order can be pickup or delivery). In this case, you have two orders. One pickup and one delivery. So the matrix dimension should be 3x3 and contain only locations 0, 2, and 0 (duplicated).
            0           1 (oringally 2)     2 (originally 0) 
0        0.0      55.0                          0.0
1       55.0       0.0                        55.0
2         0.0     55.0                          0.0 

my_data_model.set_pickup_delivery_pairs(cudf.Series([1]), cudf.Series([2]))
  1. You are right about set_order_locations(). It not only allows the ability to visit any location multiple times but also allows you to skip any locations specified in the distance matrix. It is a more flexible way to specify the pickup and delivery. With this approach, you do not have to modify the distance matrix. The above-mentioned problem can be setup as:
            0          1          2        3
0        0.0       27.0   55.0     71.0 
1       27.0        0.0   28.0     44.0
2       55.0      28.0     0.0     16.0
3       71.0      44.0   16.0       0.0

# always start with 0, pickup at 2 and deliver at 0
# This means order number 1 is pickup at location 2,  and order number 2 is delivery at location 0
my_data_model.set_order_locations(cudf.Series([0, 2, 0])) 

my_data_model.set_pickup_delivery_pairs(cudf.Series([1]), cudf.Series([2]))

Please let us know if you are able to set up this model and/or any questions you may have on this one. We will also add more examples related to the pickup delivery feature and setting order locations in the coming release.

4

Hey, thanks for the reply! Sorry if I am misunderstanding, but let me clarify a bit more.

The reason I had originally had values listed as 9999999 was to specify that this connection did not actually exist between the two nodes. So in the case of that problem, the route of 0 → 2 → 0 would not count as a valid solution. Is there a way that this can be modeled with that constraint in mind? A sketch of the graph:

toy_graph
toy_graph1265×285 16 KB

It seems that if I try the following matrix:

            0          1          2        3
0        0.0       27.0   55.0     71.0 
1       27.0        0.0   28.0     44.0
2       55.0      28.0     0.0     16.0
3       71.0      44.0   16.0       0.0

with the following orders:
my_data_model.set_order_locations(cudf.Series([0, 2, 0, 0]))

it is successful at setting the orders, but I actually end up being limited by the demo version of ReOpt

RuntimeError: Euler failure - Limited version: Order locations is not supported
Obtained 25 stack frames
#0 in /miniconda/conda/envs/reopt/lib/python3.7/site-packages/reopt-22.4.0a0+50.g37a4b982-py3.7-linux-x86_64.egg/reopt/vehicle_routing_wrapper.cpython-37m-x86_64-linux-gnu.so(_ZN4raft9exception18collect_call_stackEv+0x52) [0x7f7c48179132]
#1 in /miniconda/conda/envs/reopt/lib/libreopt.so(_ZN5reopt11logic_errorC1ERKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE+0xd1) [0x7f7c30d8a551]
#2 in /miniconda/conda/envs/reopt/lib/libreopt.so(_ZN5reopt7routing17data_model_view_tIifE19set_order_locationsEPKi+0xd1) [0x7f7c30dde341]
#3 in /miniconda/conda/envs/reopt/lib/python3.7/site-packages/reopt-22.4.0a0+50.g37a4b982-py3.7-linux-x86_64.egg/reopt/vehicle_routing_wrapper.cpython-37m-x86_64-linux-gnu.so(+0x44379) [0x7f7c4815e379]
#4 in python(_PyMethodDef_RawFastCallKeywords+0x143) [0x55de610fc033]
#5 in python(+0x13b1e8) [0x55de610fd1e8]
#6 in python(_PyEval_EvalFrameDefault+0x4f0a) [0x55de61173cba]
#7 in python(_PyEval_EvalCodeWithName+0x242) [0x55de610b3ea2]
#8 in python(_PyFunction_FastCallKeywords+0x320) [0x55de610fa370]
#9 in python(+0x13b0d8) [0x55de610fd0d8]
#10 in python(_PyEval_EvalFrameDefault+0xb41) [0x55de6116f8f1]
#11 in python(_PyEval_EvalCodeWithName+0x242) [0x55de610b3ea2]
#12 in python(_PyFunction_FastCallKeywords+0x320) [0x55de610fa370]
#13 in python(+0x13b0d8) [0x55de610fd0d8]
#14 in python(_PyEval_EvalFrameDefault+0x172a) [0x55de611704da]
#15 in python(_PyEval_EvalCodeWithName+0x242) [0x55de610b3ea2]
#16 in python(PyEval_EvalCodeEx+0x39) [0x55de610b50b9]
#17 in python(PyEval_EvalCode+0x1b) [0x55de6119415b]
#18 in python(+0x23dd53) [0x55de611ffd53]
#19 in python(PyRun_FileExFlags+0x97) [0x55de6120a307]
#20 in python(PyRun_SimpleFileExFlags+0x19c) [0x55de6120a4dc]
#21 in python(+0x248a39) [0x55de6120aa39]
#22 in python(_Py_UnixMain+0x3c) [0x55de6120ab8c]
#23 in /usr/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf3) [0x7f7d9a83d0b3]
#24 in python(+0x1be51d) [0x55de6118051d]

I am able to get a working solution with approach #2:

Final Cost         :  110.0
Number of Vehicles :  1
Vehicle-0 starts at: 0.0, completes at: 110.0, travel time: 110.0,  Route : 
0->1->2->0

However I feel that this approach loses the context of the problem. In terms of the image, this route equates to 0 → 2 → 0 → 0 which uses the invalid edges of 0 → 2. Thanks for any clarification on if this is possible!

5

Hi,
Glad that you are able to use at least one approach. The Order locations feature will be enabled with the coming release. Sorry for not verifying that before suggesting the usage.

With regards to the path, ReOpt does not concern with how a vehicle goes from location 0 to location 2 (i.e the path 0 -> 1 -> 2). The assumption is that the best (or shortest) distance (not path) between 0 and 2 is already precomputed and given as input to the solver. The route generated by the solver only corresponds to orders specified by the user. In this particular example, there is no pickup or delivery order location 1, so it does not play any role in the optimization.

Please let us know if this answers your question!

6

I see, that make sense and clears up my problems a bit. I think I will still be able to find a good way to be able to use ReOpt. Thanks for the input!

1 Like