4
$\begingroup$

I have a problem that can be reduced to the following:

There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points" (eg. there are five places where you can pick up object A, and five places where you must deliver it). What is the optimal route?

It is similar to the "vehicle routing problem with pickups and deliveries", except that rather than delivering one item from one point to another there are multiple choices for pickup and delivery points.

Is there literature, or perhaps software, that treats this specific problem? Alternatively, can this problem be reduced to a more common variant?

Improve this question
$\endgroup$
3
  • $\begingroup$ Are there any constraints around the carrying capacity of the vehicle? $\endgroup$ – Dylan Black Mar 12 '17 at 9:49
  • 1
    $\begingroup$ I'd want to know: Is there a given start and end point (unrelated to the pickup and delivery points)? How many items can be picked up at each pickup point, how many need to be delivered at each delivery point, and how many items can we carry? $\endgroup$ – gnasher729 Apr 5 '18 at 15:22
  • $\begingroup$ Is there a cost $C(d|s)$ associated with picking up an object at a given pickup point $s$ and delivering it to a destination $d$ ? $\endgroup$ – droptop Apr 20 at 14:29
0
$\begingroup$

It can be reduced to a TSP with an incomplete graph (i.e. with some missing edges). Each delivery "slot" is simply represented as a node in the graph, connected appropriately to the other nodes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If the carrying capacity of the vehicle is greater than 1 item but finite the solution to the TSP reduction is no longer guaranteed to be the optimal path. $\endgroup$ – Jeremy List May 1 '19 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.