Or-tools: VRP with backhaul

[davide-malagoli]

Hi,

I didn't find something similar so I opened this issue.

I'm trying to solve a problem that is similar to pickup and delivery, but it has some differences.
In the literature I think it is referenced through the acronym of VRPB .

The main difference from Pickup and Delivery is that deliveries must be made on each route before any pickups can be made.
A real business case could be an hospital laundry, that need to deliver clean clothes before collecting the dirty (and possible infected) ones, never mixing clean with dirty.

I really don't know how to model this with OR Tools, any ideas?

I thought to use a variable to "change the map" for the vehicle when it has finished delivery, but it is not working well.
Another thought would be running two simulations, one for delivery and then the second for pickup, but it seems to be sub-optimal in some cases.

Thank you

[jmarca]

I think all you have to do is prevent transitioning from a drop off to a pickup unless the truck is empty.

So set up two dimensions. Hacking here:

[routing.AddDimensionWithVehicleCapacity(
        demand_cb,  # demand callback
        null_capacity_slack,
        supply_arr,  # capacity array
        True,
        dimname) for demand_cb,supply_arr,dimname in zip(
                                                 [clean_demands,dirty_demands],
                                                 [clean_cap,dirty_cap],
                                                 ['clean','dirty'])]
clean_dim = routing.GetDimensionOrDie('clean')
dirty_dim =  routing.GetDimensionOrDie('clean')

for node in dirty_laundry_nodes:
    idx = manager.NodeToIndex(node)
    # cannot visit dirty unless clean is empty
    solver.AddConstraint(clean_dim.CumulVar(idx) == 0)

The clean laundry loads picked up at the depot fill up the "clean" dimension in the vehicle. They all need to be delivered to nodes (demand of negative values). When the vehicle is empty, then it can visit dirty laundry nodes.

PS I like to think of all problems as pickup and delivery with time windows, as it is most general. The various hierarchies in the literature are great and all, but I suspect they are mostly just noise to get a paper published.

[davide-malagoli]

Hi jmarca,

thanks a lot for your solution, but I'm not sure about this contraint.

For example, let's consider a vehicle with a capacity of 15, that starts on the map visiting 3 nodes with some clean demand, for example 3, 5 and 5.
Now it's clean dimension is 2, if I am correct.
If a node with clean demand 2 does not exists he cannot visit the dirty nodes, and it returns to depot.

I know it sounds like a contradiction, but I'm trying to maximize both the "clean" and "dirty" quantity.
A vehicle can start or end "underloaded", if necessary.

As I see now this contraint enforces me to create some "variants" of the vehicle, with different start clean capacity, just to find a feasible route.

There isn't another way to change a "status" for the vehicle?

I don't know I explained myself, so let me argument it further: after the vehicle visited the 3 nodes in the example, is there a way to save in a "variable" (bound to that specific vehicle) that there's no other "clean" node to be satisfied and now he can visit only "dirty" nodes?

Thanks

[jmarca]

Well, you said you were doing pickup and delivery, so I assumed you were actually doing pickup and delivery problem. You also said:

need to deliver clean clothes before collecting the dirty (and possible infected) ones, never mixing clean with dirty.

So, in keeping with pickup and delivery conventions, you need to pickup each clean parcel and deliver it.

So at start, vehicle is loaded with some parcels from dummy nodes (co-located with depot), for delivery at nodes in the city, then when empty, it picks up dirty for delivery to another set of dummy nodes also colocated with the depot.

To be explicit and using your example:

Vehicle starts with load of zero, picks up 3 from A', then 5 from B', then 5 from C' (with travel time of zero, and order is arbitrary). Assuming there is no load of 2 to pickup and deliver, it sets off on its route.

Vehicle then delivers each parcel, in some order determined by solver, to A, B, C, thereby zeroing out its load.

With each delivery, the possibility exists to pickup a dirty load, but the constraint that it have empty clean dimension prevents it.

When the last clean load is delivered, the clean dimension is empty, and pickups of dirty are possible. Vehicle picks up dirty items from D, E, F, G, etc, for delivery to dummy nodes adjacent to depot (D', E', F', G', etc).

Seems clear to me. Have you bothered to try this yet?

[davide-malagoli]

I hadn't thought of using dummy nodes for the initial load, thanks a lot. ;)
I think I missed that point in the previous examplanation.

But now I don't get the role of the dirty fake nodes.
Let me explain: I have a list of nodes with both clean an dirty demands, so for every destination I will have 2 coincident nodes, one for the clean and one for the dirty load (the clean nodes will have negative demands).

To overcome the initial load problem, I have to "copy" the clean nodes and put them coincident with the depot, and with demands positive.

If I ask the solver to maximize the dirty load, I don't think I have to create copies (co-located with the depot) of the dirty nodes too.

I am correct?

Thank in advance

[jmarca]

In general, it is safest to have a unique pickup node paired with a unique dropoff node.

In some cases you can condense, but here I don't see how you can, because you don't want to mix clean and dirty.

So, yes, if a node A "demands" a dropoff of x clean items and "supplies" y dirty ones, then you'd end up making (by my count) 4 dummy nodes:

1. Dummy A1 (at depot, clean source):

   • clean demand callback function returns +x in clean dimension
   • dirty demand callback function returns 0 in dirty dimension

2. Dummy A2 (at depot, dirty destination)

   • clean demand callback function returns 0 in clean dimension
   • dirty demand callback function returns -y in dirty dimension

3. Dummy A3 (at customer site, clean destination):

   • clean demand callback function returns -x in clean dimension
   • dirty demand callback function returns 0 in dirty dimension

4. Dummy A4 (at customer site, dirty source)

   • clean demand callback function returns 0 in clean dimension
   • dirty demand callback function returns +y in dirty dimension

In your loop, you'd pair pickup_and_delivery(A1,A3), and pickup_and_delivery(A4,A2), etc etc.

When truck leaves depot it has clean 0, dirty 0.

Truck leaves A1 it has clean +x, dirty 0

Truck arrives A3, has clean +x, dirty 0
Truck leaves A3, has clean 0, dirty 0

Truck arrives A4 has clean 0, dirty 0
Truck leaves A4, has clean 0, dirty +y

Truck arrives A2, has clean 0, dirty +y
Truck leaves A2, has clean 0, dirty 0

Truck returns to depot empty in both dimensions.

[davide-malagoli]

It works, but it seems to be unable to find a solution with more than 4-5 nodes.

I was wandering if it will be sufficient to impose that every "clean" node is visited BEFORE any "dirty" node, something like that:

for clean in clean_nodes:
    clean_index = manager.NodeToIndex(clean)
    for dirty in dirty_nodes:
        dirty_index = manager.NodeToIndex(dirty)
        routing.solver().Add(
            time_dimension.CumulVar(clean_index) <=
            time_dimension.CumulVar(dirty_index))

[jmarca]

On Mon, Aug 26, 2019 at 07:41:12AM -0700, davide-malagoli wrote:

It works, but it seems to be unable to find a solution with more than 4-5 nodes.

You mean it hits a time limit, or comes back with no solution? It
seems like a tiny problem, and I've done more complicated things up to
about 500 customers. But even then I just didn't want to wait that
long for the solution, so I started partitioning the problem.

What is the time limit you are using?

I was wandering if it will be sufficient to impose that every "clean" node is visited BEFORE any "dirty" node, something like that:

for clean in clean_nodes: clean_index = manager.NodeToIndex(clean) for dirty in dirty_nodes: dirty_index = manager.NodeToIndex(dirty) routing.solver().Add( time_dimension.CumulVar(clean_index) <= time_dimension.CumulVar(dirty_index))

The time dimension cumul var trick could work too. On the other hand,
it might get strange if you have multiple vehicles. It might end up
forcing all clean to be served before all dirty, regardless of
vehicle. What you want is for a vehicle to visit cleans then dirties,
but to allow vehicle 1 to visit dirties when it can, not when all
vehicles have finished visiting clean nodes. You might need to throw
a conditional in there...if same vehicle, then constraint.

But try it and see. I'm not sure why you are asking the internet when
you can just write a program and test it out yourself!

--
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
https://github.com/google/or-tools/issues/1481#issuecomment-524887645

--

James E. Marca

[davide-malagoli]

It comes back with no solution.
I tried to change first solution startegy and metaheuristic.
Normally I use a time limit of 30 sec, but also raising it to 1 hour does not held any result.

I tried also to drop other costraints , but nothing changed, when I add more than 5 nodes it fails (also with no time window).

Is there a way to increase to time limit for the first solution strategy (or the search space)?
I saw that it immediately returns with no feasible solution.

Thanks

[lperron]

If it says no solution, then increasing the time limit will not help.

Le mer. 28 août 2019 à 08:51, davide-malagoli [e-mail] a
écrit :

It comes back with no solution.
I tried to change first solution startegy and metaheuristic.
Normally I use a time limit of 30 sec, but also raising it to 1 hour does
not held any result.

I tried also to drop other costraints , but nothing changed, when I add
more than 5 nodes it fails (also with no time window).

Is there a way to increase to time limit for the first solution strategy
(or the search space)?
I saw that it immediately returns with no feasible solution.

Thanks

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1481?email_source=notifications&email_token=ACUPL3PO4BURIBHMLIRRB5TQGYN6DA5CNFSM4IKREF7KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD5KCN3I#issuecomment-525608685,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3OIOYGPCXRYL2QAF2TQGYN6DANCNFSM4IKREF7A
.

[JacobenVosloo]

solver.AddConstraint(

@jmarca
I tried your suggestion in my model and everything seems to work right up to the point where I need to set the condition for pickup nodes of dirty items to solver.AddConstraint(clean_dim.CumulVar(idx) == 0)

I resorted to using the Delivery and Pickup example from the docs and simply adding in some additional code and see if I can get it working there. But the results is an infeasible solution to something that appears to be trivial.

I added the following to the example (In Java)

• Added demand and vehicle capacity
  long[] demands = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; long[] vehicleCapacities = {15, 15, 15, 15};
• Created separate lists for the pickup and delivery nodes

ArrayList<Integer> pickupsList = new ArrayList<Integer>(); pickupsList.add(1); pickupsList.add(2); pickupsList.add(4); pickupsList.add(5); pickupsList.add(7); pickupsList.add(15); pickupsList.add(13); pickupsList.add(16);

ArrayList<Integer> deliveries = new ArrayList<Integer>(); deliveries.add(6); deliveries.add(10); deliveries.add(3); deliveries.add(9); deliveries.add(8); deliveries.add(11); deliveries.add(12); deliveries.add(14);

• Added a capacity call back and dimension
  final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> { int fromNode = manager.indexToNode(fromIndex); if (fromNode == 0) return 0; if (pickupsList.contains(fromNode)) return data.demands[fromNode]; return -data.demands[fromNode]; });

routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, data.vehicleCapacities, true, "Capacity");

Everything up to this point works fine, I can view the output of the algorithm - but it does seem to only record the change in capacity once the vehicle has left the node. Is this expected?

As a simplification of what you suggested above now I only need to ensure the capacity dimension is 0 before doing a new pickup so I added this constraint to the solver

for (Integer i:pickupsList) { int node = manager.indexToNode(i); solver.addConstraint(solver.makeLessOrEqual(capacityDimension.cumulVar(node), 0)); }
And the result is not feasible anymore
Which does not make sense.... Please assist.

Thank you for the great input, not only here but everywhere!

[jmarca]

Okay, forgive me if I'm not answering the question properly, but...here is what I was thinking of in pseudo-python.

Basic idea is to actually set up a conditional constraint. The idea is that the vehicles must drop off all clean clothes before picking up any dirty clothes, right? So the crux is to prevent any transitions from a dropoff node to a pickup node unless the vehicle is empty when it arrives at the pickup node. So that's what this code does...it loops over all of the nodes, and if the "from node" is a dropoff, then it loops over all the possible pickup nodes, and sets a conditional constraint that the next value of dropoff(i) can only be pickup(j) if the clothes dimension is zero at pickup(j).

# assume you have some nodes
# assume each  is some sort of object like
# [{id: 0, Event: "Dropoff Clean", ... quantity: -4, location: [x0,y0], ...etc},
#  {id: 1, Event: "Pickup Dirty", ... quantity: 2, location: [x1,y1], ... etc},
# ...]
#  id is your local index, and event type is what is happening
# assume you have a single dimension for clothes, called clothes_dimension, and 
# it must be zero before accumulating more in the field (or you can have two dimensions, 
# but I don't see the need)
# 
# I'm assuming dropoff is a negative demand of some size, pickup is a positive demand
# and that the vehicles "load up" somehow at the depot with clean, make deliveries, 
# and then pickup dirties, and I'm ignoring the need to make sure the depot load up will divide
# equally over the delivery demands...

for current_event in nodes:
    current_event_idx = manager.NodeToIndex(current_event.id)
    if current_event.Event == "Dropoff Clean":
        # currently dropping off clean clothes, cannot pickup dirty unless empty
        for next_event in nodes:
            # move along if considering the same node
            if current_event.id == next_event.id:
                continue
            # move along if another dropoff
            if next_event.Event == "Dropoff Clean":
                continue
            # etc for other non-constraint cases
            #
            # now, worry about picking up dirty only if empty of all clean
            if next_event.Event == "Pickup Dirty":
                possible_next_idx = manager.NodeToIndex(next_event.id)
                if routing.NextVar(current_event_idx).Contains(possible_next_idx):
                    # model *might* transition from current event to next event

                    # when the vehicle arrives at pickup, it needs to be empty if coming from this event (which is a dropoff)
                    empty_load_condition = clothes_dimension.CumulVar(possible_next_idx) == 0
                    next_node_condition = routing.NextVar(current_event_idx) == possible_next_idx
                    # maybe add a vehicle condition?  but I don't think you need it as it is redundant with routing
                    # vehicle_condition = routing.VehicleVar(e_idx) == routing.VehicleVar(n_idx)

                    expression = solver.ConditionalExpression(next_node_condition,
                                                              empty_load_condition,
                                                              1)
                    solver.AddConstraint(
                        expression >= 1
                    )

Okay, there are two big caveats here. First it has been a year or three since I've used conditional expressions in anger, and it might be the case that the underlying C++ has changed. But I just grepped through the current master and didn't see any red flags.

Second, I never can quite wrap my head around the terminology and usage of conditional expressions, but...here is how I see it and here's the caveat---I could be wrong. The ConditionalExpression API (or makeConditionalExpression in Java) takes three arguments. The first is a decision variable that is not a constraint. So in this case, the decision is whether or not the solver is going to assign the pickup node j to be the "next node" for the drop off node i. Next comes the constraint. If the decision is true, then the constraint is added to the solution, which might mean that the whole thing is impossible. But if the decision variable is false, then the constraint never applies, but instead the value of 1 is applied (always true).

This means that if a node j is not the next node from some dropoff node i, then the constraint that the cumul value is zero is not applied. Which is good, because you don't want to require an empty vehicle before all pickups, or you'd never find a solution.

I've also used this sort of trick to "force" the solver to visit far away nodes after close by ones.

Consider you have two passengers on board to deliver, one to A and one to B. The solver doesn't care if the order is B then A, or A then B, but people tend to feel it is more "fair" if the closer passenger is dropped off first.

Depot ------   A  --------    B

But of course, you only want this sort of constraint to apply if the passengers are on the same vehicle. So the expression is

expression = solver.ConditionalExpression(
         # same_vehicle_condition
        routing.VehicleVar(A_idx) == routing.VehicleVar(B_idx),
        # time at B is after time at A
        time_dimension.CumulVar(A_idx) < time_dimension.CumulVar(B_idx),
        1)

[JacobenVosloo]

@jmarca Thank you very much.

Can you or @Mizux help me convert this into Java?

It is similar to my question on StackOverflow https://stackoverflow.com/questions/62514537/how-to-create-intexpr-from-multiple-intexpr-in-java-using-or-tools-same-as-in

as well as on this git issue
https://github.com/google/or-tools/issues/685#issuecomment-647494699

I can't figure out how to convert the Python code to Java

[JacobenVosloo]

After some trial and error, I managed to create the constraints in Java!

IntExpr empty_load_condition = solver.makeEquality(deliveryDimension.cumulVar(nextIndex), 0).var();
IntVar next_node_condition = solver.makeEquality(routing.nextVar(currentIndex), nextIndex).var();
IntExpr expression = solver.makeConditionalExpression(next_node_condition, empty_load_condition, 1);
solver.addConstraint(solver.makeGreaterOrEqual(expression, 1));

[lperron]

This can be simplified by removing intermediate objects and constraints

IntVar empty_load_condition =
solver.makeIsEqualCstVar(deliveryDimension.cumulVar(nextIndex), 0);

IntVar next_node_condition =
solver.makeIsEqualCstVar(routing.nextVar(currentIndex), nextIndex);

solver.addConstraint(solver.makeGreaterOrEqual(empty_load_condition,
next_node_condition));

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53 00

Le lun. 22 juin 2020 à 18:11, Jaco-Ben Vosloo [e-mail] a
écrit :

After some trial and error, I managed to create the constraints in Java!

IntExpr empty_load_condition = solver.makeEquality(deliveryDimension.cumulVar(nextIndex), 0).var();
IntVar next_node_condition = solver.makeEquality(routing.nextVar(currentIndex), nextIndex).var();
IntExpr expression = solver.makeConditionalExpression(next_node_condition, empty_load_condition, 1);
solver.addConstraint(solver.makeGreaterOrEqual(expression, 1));

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1481#issuecomment-647621509,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/ACUPL3JLFXOTL5UEOIRFUVLRX57ETANCNFSM4IKREF7A
.