Theoretical question for CVRP

[glazaridis]

I'm wondering if there's is an actual difference between the following solutions in a vehicle routing problem: Given that we have a one-to-one pickup and delivery problem (each vehicle can pickup and deliver only one order and then return to depot), what is the difference between:

a) We specify for each vehicle to go to one node (pickup) and deliver to another node (delivery) and then force return to depot

b) We remove the pickup-delivery and incorporate the pickup-delivery time into the distance matrix of the pickup node. We use a counter to constraint the max number of nodes visited equal to 1.

[Mizux]

I would say, in the first case you'll have a distance matrix of NxN while in the second part you'll have only (N/2)^2 cells which should reduce the memory footprint, improve locality and cache usage.

note: You can also:

• forbid arcs by simply returning max_capacity for forbidden arc which should stop the solver earlier than checking the counter constraint etc and pick an other node.
• Modify the routing.nextVar(any_delivery_point) to only allow end nodes thus solver should not even try to compute/test all possible nodes.

[glazaridis]

@Mizux So basically the latter approach (b) would be preferable, and for improved computational efficiency the suggested bullet points could be adopted, right?

[Mizux]

yup

[paultrow]

If a vehicle has to pick up an item at a location, deliver it to another location, and then return to the depot, how is that part of the optimization problem? There are no choices to be made for the vehicle. So why even include that pickup/delivery in the problem?

…

On Fri, Jan 8, 2021 at 7:29 AM Mizux ***@***.***> wrote: yup — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2327 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEC63UKHVXVT46Z3AA2IYV3SY33CXANCNFSM4V2IQCLA> .