Copies of nodes not visited consecutively

[Jean Paul Nery]

Briefly:
I used OR-Tools to implement control nodes (with copies) that the vehicles have to visit before visiting the destination nodes. The issue is that vehicles don't visit control copies consecutively (bad solutions). Putting constraints to avoid this, solutions are actually worse. Can I speed up good solutions using constraints?

In more detail:
I used OR-Tools to allow for control nodes: nodes that have to be visited (to inspect the merchandise) before visiting each destination node. Several vehicles will go through the same control node. Since in OR-Tools each node can be visited only once, I created copies of the control nodes and used Pickups and Deliveries to set the precedences.

The code works, but an issue is that there are routes where a vehicle goes to the control node (i.e. control node or one of the copies), to a nearby node, and back to the control node, as in this post: https://groups.google.com/g/or-tools-discuss/c/3dfHtiLgxRA
This is inefficient, since it could just visit the copies one after the other and not waste time coming back.

If the solver is given more time, then actually these bad routes go away. But it's taking too long for my purposes. I was wondering if it's possible to put restrictions that avoid these cases and speed up good solutions. I tried using the code below.

The code adds a dimension with vehicle capacity and the counter increases for each vehicle every time it visits a destination node (not when it visits a control node). Then it adds the constraint that the counter for the control copies of each group have to be the same. It seems to be correct since vehicles only visit more than one copy consecutively. However, solutions are worse given the same amount of solver time: more visits are dropped relative to not putting any constraint.

Can anyone suggest maybe a more efficient way of imposing these constraints? Or is it likely constraints will slow up the optimization and not result in any time gains?

####### Code #######
# Add a counter dimension with vehicle capacity for destinations
    def counter_callback(index):
        node = manager.IndexToNode(index)
        return 1 if node in data['destinations'] else 0
   
    counter_callback_index = routing.RegisterUnaryTransitCallback(counter_callback)
    routing.AddDimensionWithVehicleCapacity(counter_callback_index,  0, [big_number] * data['num_vehicles'],  # large enough capacity for each vehicle
        True,  'Counter'    )
    counter_dimension = routing.GetDimensionOrDie('Counter')

    # Enforce same counter for consecutive control node visits within each group
    for group_id, group in enumerate(data['control_center_groups']):
        control_indices = [manager.NodeToIndex(node) for node in group]
        for ctrl_index_i in control_indices:
            ctrl_counter_i = counter_dimension.CumulVar(ctrl_index_i)
            for ctrl_index_k in control_indices:
                ctrl_counter_k = counter_dimension.CumulVar(ctrl_index_k)
                routing.solver().Add(ctrl_counter_i == ctrl_counter_k )

# Note: the constraint I mentioned is not perfect, since the vehicle could go back and forth

# between control nodes, but this hasn't happened anyway so far because control nodes are far

# away. This is maybe good since it avoids constraints of solutions that are already not occuring.

[Jean Paul Nery]

In the code above I am double counting when enforcing the constraints. I forgot to update that. But it doesn't change the results.

Another option to get a good solution within a certain amount of time, would be to re-route the bad routes (the ones that go back and forth between control nodes and destination nodes) in a "post processing".

But this would complicate the code, and would take considerable more time to implement it and make sure everything works well together. So I wanted to first invest some time in trying something like what I mentioned above.

Or maybe there's some other strategy that doesn't consist of just repeating the control nodes in the same position?

Thanks in advance if you took the time to read this and if you have any suggestions.

[vuongdanghuy]

I also face the same problem and this is my current solution using NextVar() and IsMemberVar() constraint

https://github.com/google/or-tools/discussions/3161

This solution can ensure that if 2 (or more) nodes are on the same vehicle then they must be consecutive. But it's also heavy and not perfect. Because if I have n duplicates of a node, i will have to add n * (n - 1) /2 constraints to the model and sometime it also leads to the result where some nodes are dropped.

It'd be nice if there is a more efficient way of handling this problem :))

Vào lúc 01:36:33 UTC+7 ngày Chủ Nhật, 14 tháng 7, 2024, jeanp...@gmail.com đã viết:

[Jean Paul Nery]

For anyone interested, I ended up just re-routing all routes (it takes very little time, so no need to analyze if the route is bad or not).

I had to wait a long time for routes to improve (i.e. to get rid of the back and forth). At the same time, the number of nodes dropped didn't change for a long time (long for my purposes). I don't know if the nodes each vehicle was visiting was changing, or if  each vehicle was visiting the same nodes but changing order, but in any case, the number of dropped nodes was not reducing within the time scales I was interested.

So I set a short but sufficiently long solver time, that dropped not too many visits. And then I just call the solver again for each vehicle and the nodes it visits, which gives good routes (without the back and forth) very quickly.

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/_O46NsYiuPA/unsubscribe.
To unsubscribe from this group and all its topics, 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/d45cc8f4-5fb7-4dba-b93d-54b8a27f7397n%40googlegroups.com.