VRP - Minimize the Pickup and Delivery time difference

[sebastia...@gmail.com]

Hi!

I'm currently working in a VRP with pickup and delivery considerations, using the python versión of OR-TOOLs.

I have been trying to minimize the pickup and delivery time difference, but still haven't found a way.

 

Something like a cost that applies over: 

time_dimension.CumulVar(delivery_index)) -  time_dimension.CumulVar(pickup_index)

The objective is to reduce the time that an item spend over the vehicle, without applying a hard constraint to achieve this.

Is possible to achieve this without a constraint?, can someone give me a hint?

Thanks in advance

[blind.lin...@gmail.com]

Just an idea...the solver will minimize whatever the callback is in

routing.SetArcCostEvaluatorOfAllVehicles(myFancyCallbackIndex);

So...if you want to avoid constraints (not sure why) maybe make a
dimension with a completely broken distance matrix. Something like
distances from any pickup location to any other pickup location is 2x
the normal distance (I want to avoid state-based dimensions, but you
can know for certain that if the origin is a pickup node, then the
vehicle has an item). Also any pickup node to any delivery node other
than its delivery node is also large, but not as large, say 1.1x. And
finally, the cost to travel from delivery node to any node is 1.0x (or
maybe 1.1 to pickup, 1.0 to delivery.

So obviously, the trick will be balancing the scale factors. The
difficult edge case I'm thinking of is pickup three items at a
single real location but three virtual locations. The travel cost for
the three pickups is zero (0*2 is still zero), but then the last item
travel time to its delivery point will be favored. But....

a0
b0
c0 a1 b1 c1

If the third item travels from c0 to c1, obviously it should instead
go to a1 first, then b1, then c1 to minimize the aggregate in-vehicle
time for all items. I think with my setup, the solver will be
incentivized to go directly to c1 first (longest trip is longer still
when multiplied by 2) but the shortest net cost for all three items in
vehicle is pickup-a1-b1-c1.

(I once did some fancy hackery to fix just such a case, so that's why
I'm thinking about it).

Anyway, theres an idea to try. Hope it isn't too crazy. But again,
you cannot use state-dependent dimensions, so you can't "know" the
items in the vehicle when computing the dimension.

James

> --
> 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/2a68f3a2-317b-4a36-8f5d-253be0e8e107n%40googlegroups.com.


--

James E. Marca
Activimetrics LLC