Route sequence constraint with optional nodes

[angelo manzatto]

Hi, I am having difficult to model a route sequence constraint with optional nodes called "events" in the middle. So my data dict has a 'route' key with a list of routes that must be followed in sequence like [1,2,3] in that the vehicle MUST visit 1 -> 2 -> 3 and a 'event' key with optional nodes that can be inserted anywhere in the middle or even outside of the route but with the condition that the you cannot move to another route before completing the route you are already in.

Example: 

data['starts'] = 1 # vehicle starting node

data['ends'] = 0 # vehicle ending node

data['routes'] = [[6,7,8], [9,10,11]] # routes

data['events'] = [2,3,4,5] # events

You could go for [1,6,7,2,3,8,4,9,10,5,11,0] 

You can't go for [1,6,7,2,3,9,10,5,11,8,4,0] since you didn't finish route [6,7,8] before moving to route [9,10,11]

My strategy on modeling this constraint are:

* same vehicle for all nodes

* removing all non next nodes from nodes inside same route

* removing all non start nodes from other routes when in end node inside route

* using count dimension 

Here is a toy sample for testing but it is falling to achieve the "finish entire route" before moving to another because I don't know how to guarantee that after going to an event node you MUST return to the route you already started. If you run the example the result would be:  (1 ->  4 ->  11 ->  12 ->  13 ->  14 ->  5 ->  8 ->  9 ->  10 ->  2 ->  6 ->  7 ->  3 ->  15 ->  16 -> 0) but it is incorrect since you didn't finish the route [11,12,13,14,15,16] before moving to other routes.

Also I will have to add an additional drop disjunction in favor of 'event's over 'routes' in the future meaning maybe more one challenge.

[Mizux Seiha]

My 2 cents

1. Since you can insert event inside a "node chain"  e.g. `6 -> 7 -> 2 -> 8`
I won't try to use  IntVar* ApplyLocks(const std::vector<int64>& locks);

ref: https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/constraint_solver/routing.h#L1031-L1039

2. So for a chain I would use a counter and some constraint

```python

six = manager.NodeToIndex(6)

seven = manager.NodeToIndex(7)

routing.solver().Add(counter_dim.CumulVar(six) < counter_dim.CumulVar(seven))

```

3. between chain [6,7,8] and [9,10,11] basically you just want `8 < 9` OR `11 < 6` depending on whether the vehicle will visits the first chain or the second one

[Mizux Seiha]

something like this to replace all your constraints:

```python

    # Sequence constraint

    for route in data['routes']:

        for i in range(len(route) - 1):

            current_index = manager.NodeToIndex(route[i])

            next_index = manager.NodeToIndex(route[i+1])

            solver.Add(

                count_dimension.CumulVar(current_index) <

                count_dimension.CumulVar(next_index))

    # Enforce same vehicle on route sequence

    # note(mizux): note needed for a single vehicle problem...

    for route in data['routes']:

        for i in range(len(route) - 1):

            current_index = manager.NodeToIndex(route[i])

            next_index = manager.NodeToIndex(route[i + 1])

            # same vehicle condition

            solver.Add(

                routing.VehicleVar(current_index) == routing.VehicleVar(next_index))

    # Forbid interleaved route chains

   # i.e. we have for any pair of chain X, Y "end_X < start_Y OR end_Y < start_X"

    for i in range(len(data['routes'])):

        for j in range(i+1, len(data['routes'])):

          #print(f'indices {i},{j}')

          start_i = manager.NodeToIndex(data['routes'][i][0])

          end_i = manager.NodeToIndex(data['routes'][i][-1])

          start_j = manager.NodeToIndex(data['routes'][j][0])

          end_j = manager.NodeToIndex(data['routes'][j][-1])

          #print(f'{end_i} < {start_j}')

          #print(f'{end_j} < {start_i}')

          first = count_dimension.CumulVar(end_i) < count_dimension.CumulVar(start_j)

          second = count_dimension.CumulVar(end_j) < count_dimension.CumulVar(start_i)

          solver.Add(solver.Sum([first, second]) == 1)

    # Setting first solution heuristic.

    # [START parameters]

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    search_parameters.first_solution_strategy = (

        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    search_parameters.local_search_metaheuristic = (

        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

    search_parameters.log_search = True

    search_parameters.time_limit.FromSeconds(5)

    # [END parameters]

    # Solve problem

    solution = routing.SolveWithParameters(search_parameters)

    if solution:

        print_solution(manager, routing, solution)

    else:

        print("NO SOLUTION FOUND!")

```

side note: Your bunch constraint would reduce much more the research space since you barely remove all next nodes but here i would like to keep it simple and rely on solver heuristic

possible output:

```sh

./chain.py

...

, memory used = 14.71 MB, limit = 99%)

I0727 15:23:45.283691  9085 search.cc:260] Solution #1119 (5374, objective maximum = 7986, time = 4995 ms, branches = 25463, failures = 140128, depth = 33, TwoOpt, neighbors = 344217, filtered neighbors = 128207, accepted neighbors = 1119, memory used = 14.71 MB, limit = 99%)

I0727 15:23:50.335205  9085 search.cc:260] Finished search tree (time = 5000 ms, branches = 25466, failures = 140305, neighbors = 344421, filtered neighbors = 128353, accepted neigbors = 1119, memory used = 14.71 MB)

I0727 15:23:50.362792  9085 search.cc:260] End search (time = 5000 ms, branches = 25466, failures = 140305, memory used = 14.71 MB, speed = 5093 branches/s)

Objective: 5374

Route for vehicle 0:

 1 ->  4 ->  3 ->  11 ->  12 ->  13 ->  14 ->  15 ->  16 ->  8 ->  9 ->  10 ->  2 ->  6 ->  5 ->  7 -> 0

Distance of the route: 5374m

Maximum of the route distances: 5374m

```

[Mizux Seiha]

gist: https://gist.github.com/Mizux/f200bd2b0fc6ad622922b0ca9e868823

[angelo manzatto]

Excellent! It worked, but now I am dealing with the first big challenge that was conciliate the route constraint with drop penalty to infeasible nodes.

Event nodes have higher priority over route nodes so the penalty applied on them is 1000 time more but the solver prefers paying the cost for some unknown reason.

Attached again I put a toy sample adding the constraint code above and time windows with the following parameters:

data['starts'] = 1 # vehicle starting node

data['ends'] = 0 # vehicle ending node

data['events'] = [2] # events

data['routes'] = [[3,4,5]] # routes

route node penalty = 1000

event node penalty = 1000000

Time windows are made in such a way that or you do the route or the event, but even with event having a higher drop penalty the solver is doing the route way:

Expected solution: [2] (Objective Cost: 30684 , dropped nodes: [3,4,5]) 

Solver solution: [3,4,5] (Objective Cost: 1000000958, dropped nodes: [2])

Can you bring some light again @mizu?

Best Regards,

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

So I've been hacking at this and I had a small bit of success but then
ran into more failure.

Working from Mizux's gist version, I modified the code to replicate
the issue surfaced by Angelo.

My modified gist is here:
https://gist.github.com/jmarca/c78b0b5d785e36cf89f15692d68165b0

I've been hacking on this and have forgotten what works, what doesn't,
but definitely it isn't working.

run with python chain_modified_with_disjunctions.py -h

The "time windows" are actually distance windows

data['distance_windows'] = {
2: [0, 1000],
5: [0, 1200],
6: [600, 1200],
# 8: [600, 1200],
13: [600, 1200], # try 11, 12, etc, solver breaks
# 16: [600, 1200], # if uncommented, solver cannot use 11 to
# 16, so does the right thing (keeps 6, drops 11 to 15)
}

Unhelpful as far as solving the problem goes, but perhaps it is a
solver bug.

James

On Thu, Mar 04, 2021 at 05:44:25AM -0800, angelo manzatto wrote:
> Excellent! It worked, but now I am dealing with the first big challenge
> that was conciliate the route constraint with drop penalty to infeasible
> nodes.
>

> *Event *nodes have higher priority over *route *nodes so the penalty

> applied on them is 1000 time more but the solver prefers paying the cost
> for some unknown reason.
> Attached again I put a toy sample adding the constraint code above and time
> windows with the following parameters:
>
> data['starts'] = 1 # vehicle starting node
> data['ends'] = 0 # vehicle ending node
> data['events'] = [2] # events
> data['routes'] = [[3,4,5]] # routes
>
> route node penalty = 1000
> event node penalty = 1000000
>
> Time windows are made in such a way that or you do the route or the event,
> but even with event having a higher drop penalty the solver is doing the
> route way:

> *Expected solution*: [2] (Objective Cost: *30684 , *dropped nodes: [3,4,5])
> *Solver solution: *[3,4,5] (Objective Cost: *1000000958, *dropped nodes:

> >> 1 -> *4 -> 3* -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 8 -> 9
> >> -> 10 -> *2* -> 6 -> *5* -> 7 -> 0

> >> Distance of the route: 5374m
> >>
> >> Maximum of the route distances: 5374m
> >> ```
> >> Le jeudi 4 mars 2021 à 08:57:45 UTC+1, Mizux Seiha a écrit :
> >>
> >>> My 2 cents
> >>>
> >>> 1. Since you can insert event inside a "node chain" e.g. `6 -> 7 -> 2
> >>> -> 8`
> >>> I won't try to use IntVar* ApplyLocks(const std::vector<int64>& locks);
> >>> ref:
> >>> https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/constraint_solver/routing.h#L1031-L1039
> >>>
> >>> 2. So for a chain I would use a counter and some constraint
> >>> ```python
> >>> six = manager.NodeToIndex(6)
> >>> seven = manager.NodeToIndex(7)
> >>> routing.solver().Add(counter_dim.CumulVar(six)
> >>> < counter_dim.CumulVar(seven))
> >>> ```
> >>>
> >>> 3. between chain [6,7,8] and [9,10,11] basically you just want `8 < 9`

> >>> *OR* `11 < 6` depending on whether the vehicle will visits the first

> >>> chain or the second one
> >>>
> >>> Le mercredi 3 mars 2021 à 20:42:37 UTC+1, angelo....@gmail.com a écrit :
> >>>
> >>>> Hi, I am having difficult to model a route sequence constraint with
> >>>> optional nodes called "events" in the middle. So my data dict has a 'route'
> >>>> key with a list of routes that must be followed in sequence like [1,2,3] in
> >>>> that the vehicle MUST visit 1 -> 2 -> 3 and a 'event' key with optional
> >>>> nodes that can be inserted anywhere in the middle or even outside of the
> >>>> route but with the condition that the you cannot move to another route
> >>>> before completing the route you are already in.
> >>>>
> >>>> Example:
> >>>> data['starts'] = 1 # vehicle starting node
> >>>> data['ends'] = 0 # vehicle ending node
> >>>> data['routes'] = [[6,7,8], [9,10,11]] # routes
> >>>> data['events'] = [2,3,4,5] # events
> >>>>
> >>>> You could go for [1,6,7,2,3,8,4,9,10,5,11,0]

> >>>> You can't go for [1,*6*,*7*,2,3,9,10,5,11,*8*,4,0] since you didn't

> >>>> finish route [6,7,8] before moving to route [9,10,11]
> >>>>
> >>>> My strategy on modeling this constraint are:
> >>>> * same vehicle for all nodes
> >>>> * removing all non next nodes from nodes inside same route
> >>>> * removing all non start nodes from other routes when in end node
> >>>> inside route
> >>>> * using count dimension
> >>>>
> >>>> Here is a toy sample for testing but it is falling to achieve the
> >>>> "finish entire route" before moving to another because I don't know how to
> >>>> guarantee that after going to an event node you MUST return to the route
> >>>> you already started. If you run the example the result would be: (1 -> 4
> >>>> -> 11 -> 12 -> 13 -> 14 -> 5 -> 8 -> 9 -> 10 -> 2 -> 6 -> 7
> >>>> -> 3 -> 15 -> 16 -> 0) but it is incorrect since you didn't finish
> >>>> the route [11,12,13,14,15,16] before moving to other routes.
> >>>>
> >>>> Also I will have to add an additional drop disjunction in favor of
> >>>> 'event's over 'routes' in the future meaning maybe more one challenge.
> >>>>
> >>>>
>

> --
> 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/a5855372-d264-4878-9f57-d2c807d6bc7an%40googlegroups.com.

> # -*- coding: utf-8 -*-
> """
> Created on Wed Mar 3 14:06:28 2021
>
> @author: sirga
> """
>
> ##################################################################################################
> # Libraries
> ##################################################################################################
>
> from ortools.constraint_solver import routing_enums_pb2
> from ortools.constraint_solver import pywrapcp
>
> ##################################################################################################
> # Print Function
> ##################################################################################################
> def print_solution(data, manager, routing, solution):
> """Prints solution on console."""
> max_route_distance = 0
> for vehicle_id in range(data['num_vehicles']):
> index = routing.Start(vehicle_id)
> plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
> route_distance = 0
> while not routing.IsEnd(index):
> plan_output += ' {} -> '.format(manager.IndexToNode(index))
>
> previous_index = index
> index = solution.Value(routing.NextVar(index))
> route_distance += routing.GetArcCostForVehicle(
> previous_index, index, vehicle_id)
> plan_output += '{}\n'.format(manager.IndexToNode(index))
> plan_output += 'Distance of the route: {}m\n'.format(route_distance)
> print(plan_output)
> max_route_distance = max(route_distance, max_route_distance)
> print('Maximum of the route distances: {}m'.format(max_route_distance))
>
> ##################################################################################################
> # Parameters
> ##################################################################################################
>
> data = {}
> data['distance_matrix'] = [
> [ 0, 0, 0, 0, 0, 0],
> [ 0, 0, 684, 308, 194, 502 ],
> [ 0, 684, 0, 992, 878, 502 ],
> [ 0, 308, 992, 0, 114, 650 ],
> [ 0, 194, 878, 114, 0, 536 ],
> [ 0, 502, 502, 650, 536, 0 ],
> ]
>
> data['time_matrix'] = [
> [0, 6, 9, 8, 7, 3],
> [6, 0, 8, 3, 2, 6],
> [9, 8, 0, 11, 10, 6],
> [8, 3, 11, 0, 1, 7],
> [7, 2, 10, 1, 0, 6],
> [3, 6, 6, 7, 6, 0]
> ]
>
> data['time_windows'] = [
> (0, 999), # depot
> (0, 999), # 1
> (10, 10), # 2
> (16, 16), # 3
> (32, 32), # 4
> (55, 55) # 5
> ]#5
>
> data['num_vehicles'] = 1
> data['starts'] = [1]
> data['ends'] = [0]
>
> data['events'] = [2]
> data['routes'] = [[3, 4, 5]]
>
> ##################################################################################################
> # Model
> ##################################################################################################
>
> # Create the routing index manager.
> manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
> data['num_vehicles'],
> data['starts'],
> data['ends'])
>
> # Create Routing Model.
> routing = pywrapcp.RoutingModel(manager)
>
> ##################################################################################################
> # Dimensions
> ##################################################################################################
> # Create and register a transit callback.
> def distance_callback(from_index, to_index):
> """Returns the distance between the two nodes."""
> # Convert from routing variable Index to distance matrix NodeIndex.
> from_node = manager.IndexToNode(from_index)
> to_node = manager.IndexToNode(to_index)
> return data['distance_matrix'][from_node][to_node]
>
> transit_callback_index = routing.RegisterTransitCallback(distance_callback)
>
> # Define cost of each arc.
> routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
>
> # Add Distance constraint.
> dimension_name = 'Distance'
> routing.AddDimension(
> transit_callback_index,
> 0, # no slack
> 99999999999, # vehicle maximum travel distance
> True, # start cumul to zero
> dimension_name)
> distance_dimension = routing.GetDimensionOrDie(dimension_name)
> distance_dimension.SetGlobalSpanCostCoefficient(0)
>
> #####################
> # Count dimensions
> #####################
> routing.AddConstantDimension(
> 1,
> 1000000,
> True,
> "Count")
> count_dimension = routing.GetDimensionOrDie("Count")
>
> #####################
> # Add Time dimension
> #####################
> def time_callback(from_index, to_index):
> """Returns the travel time between the two nodes."""
> # Convert from routing variable Index to time matrix NodeIndex.
> from_node = manager.IndexToNode(from_index)
> to_node = manager.IndexToNode(to_index)
> return data['time_matrix'][from_node][to_node]
>
> transit_callback_index = routing.RegisterTransitCallback(time_callback)
>
> time = 'Time'
> routing.AddDimension(
> transit_callback_index,
> 1000000000000, # allow waiting time
> 1000000000000, # maximum time per vehicle
> False, # Don't force start cumul to zero.
> time)
> time_dimension = routing.GetDimensionOrDie(time)
> # Add time window constraints for each location except depot.
> for location_idx, time_window in enumerate(data['time_windows']):
> if location_idx == 0:
> continue
> index = manager.NodeToIndex(location_idx)
> time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
>
> for i in range(data['num_vehicles']):
> routing.AddVariableMinimizedByFinalizer(
> time_dimension.CumulVar(routing.Start(i)))
> routing.AddVariableMinimizedByFinalizer(
> time_dimension.CumulVar(routing.End(i)))
>
> ##################################################################################################
> # Parameters
> ##################################################################################################

> # Setting first solution heuristic.

> search_parameters = pywrapcp.DefaultRoutingSearchParameters()
>
> search_parameters.first_solution_strategy = (
> routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
>
> search_parameters.local_search_metaheuristic = (

> routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC)
> search_parameters.log_search = True
>
> # Search time limit to find a solution
> search_parameters.time_limit.seconds = 60
>
> ##################################################################################################
> # Sequence constraint
> ##################################################################################################

> for route in data['routes']:
> for i in range(len(route) - 1):
> current_index = manager.NodeToIndex(route[i])
> next_index = manager.NodeToIndex(route[i + 1])

> routing.solver().Add(

> count_dimension.CumulVar(current_index) <
> count_dimension.CumulVar(next_index))
>
> # Enforce same vehicle on route sequence
> # note(mizux): note needed for a single vehicle problem...
> for route in data['routes']:
> for i in range(len(route) - 1):
> current_index = manager.NodeToIndex(route[i])
> next_index = manager.NodeToIndex(route[i + 1])
> # same vehicle condition

> routing.solver().Add(

> routing.VehicleVar(current_index) == routing.VehicleVar(next_index))
>
> # Forbid interleaved route chains
> # i.e. we have for any pair of chain X, Y "end_X < start_Y OR end_Y < start_X"
> for i in range(len(data['routes'])):
> for j in range(i+1, len(data['routes'])):
> #print(f'indices {i},{j}')
> start_i = manager.NodeToIndex(data['routes'][i][0])
> end_i = manager.NodeToIndex(data['routes'][i][-1])
> start_j = manager.NodeToIndex(data['routes'][j][0])
> end_j = manager.NodeToIndex(data['routes'][j][-1])
> #print(f'{end_i} < {start_j}')
> #print(f'{end_j} < {start_i}')
> first = count_dimension.CumulVar(end_i) < count_dimension.CumulVar(start_j)
> second = count_dimension.CumulVar(end_j) < count_dimension.CumulVar(start_i)

> routing.solver().Add(routing.solver().Sum([first, second]) == 1)
>
> #################################################################
> # Add disjunction
> #################################################################
>
> # Add penalty to route nodes

> for route in data['routes']:

> for i in range(len(route)):
> node_index = manager.NodeToIndex(route[i])
> routing.AddDisjunction([node_index], 10000)
>
> # Add penalty for event. Event penalty should be higher than route penalty to avoid drop it
> for event_node in data['events']:
> event_index = manager.NodeToIndex(event_node)
> routing.AddDisjunction([event_index], 1000000000)
>
> ##################################################################################################
> # Solve problem
> ##################################################################################################

> solution = routing.SolveWithParameters(search_parameters)
>
> if solution:

> print_solution(data, manager, routing, solution)
> print(f"Objective Cost: {solution.ObjectiveValue()}")

> else:
> print("NO SOLUTION FOUND!")

--

James E. Marca
Activimetrics LLC

[Mizux Seiha]

Blind hypothesis,

All constraints imply all nodes in  chain node are node dropped

I mean

```python

 solver.Add(routing.VehicleVar(current_index) == routing.VehicleVar(next_index))

solver.Add(dim.CumulVar(current_index) < dim.CumulVar(next_index))
```

imply both nodes to be in the solution otherwise constraint would be violate IMHO...

So I suggest to use the same tricks than in same vehicle, aka you must use  active_a_b = routing.ActiveVar(a) * routing.ActiveVar(b) and or "1 - active_a_b"

ref: https://gist.github.com/Mizux/9e37c370a459bd472a6ac13c304f0b54#file-same_vehicle-py-L45

as well for this

```python

first = count_dimension.CumulVar(end_i) < count_dimension.CumulVar(start_j)

second = count_dimension.CumulVar(end_j) < count_dimension.CumulVar(start_i)

routing.solver().Add(routing.solver().Sum([first, second]) == 1)

```

if few nodes are dropped...

note for myself...

Things to test e.g. group a [5,6,7] and group b [8,9,10]

pseudo code:

```

start_a = solver.min([dim.CumulVar(5), dim.CumulVar(6), dim.CumulVar(7)])

end_a = solver.max([dim.CumulVar(5), dim.CumulVar(6), dim.CumulVar(7)])

active_a = solver.max([routing.ActiveVar(5), routing.ActiveVar(6), routing.ActiveVar(7), ])

start_b = solver.min([dim.CumulVar(8), dim.CumulVar(9), dim.CumulVar(10)])

end_b = solver.max([dim.CumulVar(8), dim.CumulVar(9), dim.CumulVar(10)])

active_b = solver.max([routing.ActiveVar(8), routing.ActiveVar(9), routing.ActiveVar(10)])

active_a_b = active_a * active_b # 0 if one chain if at least one chain is empty

first = active_a_b * (end_a < start_b)

second = active_a_b * (end_b < start_a)

disable = 1 - active_a_b # only true when first and second are false 

solver.Add(solver.Sum([first, second, disable]) == 1)

```

ref: solver::MakeMin()

https://github.com/google/or-tools/blob/fa84bc05e72641dddfbb98164d81b8bc9bef6ea5/ortools/constraint_solver/constraint_solver.h#L1168

Min in Python: https://github.com/google/or-tools/blob/fa84bc05e72641dddfbb98164d81b8bc9bef6ea5/ortools/constraint_solver/python/constraint_solver.i#L763-L766

[angelo manzatto]

If you remove the drop penalty from the event node meaning that  it should be on the solution or put an infeasible time window inside the chain it is dropped without any problem. I tried the other approaches but without success. Maybe I am commissioning it doing something wrong ?. Either way as I stated above paying the event penalty in favor of the chain seems strange to me. 

[angelo manzatto]

Hi, I really need to return on this problem because it is a major feature on our application. The problem is on this constraint here like @mizu pointed out:

# same vehicle condition

 routing.solver().Add(

        routing.VehicleVar(current_index) == routing.VehicleVar(next_index))

As I understood this implies that besides both indices must be visited by the same vehicle they also MUST be part of the solution right ?

I tried to add a condition where both indices must be active on the solution for this constraint to work but didn't work either since any node node from route now can be dropped invalidating the rule where the same vehicle must visit ALL nodes from a route in sequence : 

active_nodes_condition = routing.ActiveVar(current_index) * routing.ActiveVar(next_index)

        

# same vehicle condition

 routing.solver().Add(

        routing.VehicleVar(current_index) * active_nodes_condition == routing.VehicleVar(next_index) * active_nodes_condition)

Result:

Route for vehicle 0:

 1 ->  2 ->  4 ->  5 -> 0 (missing node 3 here)

Distance of the route: 2098m

Another interesting part is that if I force all route nodes to be dropped with a zero penalty without using the "active_nodes_condition" trick the solver drops the event node without an explanation.

# Add penalty to route nodes

for route in data['routes']:

    for i in range(len(route)):

        node_index = manager.NodeToIndex(route[i])

        routing.AddDisjunction([node_index], 0)

        

# Add penalty for event. Event penalty should be higher than route penalty to avoid drop it

for event_node in data['events']:

    event_index = manager.NodeToIndex(event_node)

    routing.AddDisjunction([event_index], 1000000000)

Result:

Route for vehicle 0:

 1 -> 0

Distance of the route: 0m

Maximum of the route distances: 0m

Objective Cost: 1000000000 (paid the drop penalty even when doing it would be less expensive)

Could some one suggest another approach ?

[blind.line]

If a node is not active, I am 90% sure that the assigned vehicle at that node is guaranteed to be -1. Note this is not true for dimension cumulvars. 

Adding your active node Boolean is not needed. 

(I haven’t worked through the rest of your code)

James

On Mar 16, 2021, at 13:38, angelo manzatto <angelo....@gmail.com> wrote:

Hi, I really need to return on this problem because it is a major feature on our application. The problem is on this constraint here like @mizu pointed out:

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a5c8388b-7d3e-415c-988c-cab92bd39337n%40googlegroups.com.

[angelo manzatto]

I think you are correct @blind. Adding the active vars didn't make any difference in the end for this problem, but the drop on the event node is still unexplainable. The same vehicle constraint will be true only if a vehicle is used on the [3,4,5] route but otherwise I don't see why the event node is being dropped in favor of paying the large penalty cost. As I understood from @mizu post, adding this constraint is like forcing the solver to give a solution using these nodes, but that defeats the purpose of adding disjunction.

I believe that this is a very feasible problem to solve using or-tools but the problem lies on AddDisjunction() + routing.VehicleVar(current_index)  == routing.VehicleVar(next_index) constraint combo. If I remove this constraint, the solver finds a feasible solution despite it being incorrect according to problem formulation.

[angelo manzatto]

Some detail I forgot to mention that can help on solving the problem. All events belongs to a single and just a single vehicle.

For a given premise of event node 2 belongs to vehicle id 0 if I add the following constraint the solver seems (have to test more!!!) to work as expected in conjunction with AddDisjunction:

# same vehicle condition

routing.solver().Add(

        routing.VehicleVar(routing.Start(0))  == routing.VehicleVar(manager.NodeToIndex(2))) 

[angelo manzatto]

Now the issue is that when you have more events and they conflict with each other the solver return the worst solution: NO SOLUTION FOUND!

[Mizux Seiha]

If your problem is heavily constrained, sometime it's better to "disable" the first strategy by using ALL_UNPERFORMED and only rely on the local search.
warning: need all your nodes to be optionals i.e. in at least one Disjunction each. 

[angelo manzatto]

The ALL_UNPERFORMED didn't work either. Maybe trying to think in a different way. 

The event nodes are mandatory like some maintenance, rest or any other activity that the driver MUST perform BUT I added a drop penalty on them to avoid one impossible route to break the entire solution. 

Maybe there is a way to remove the drop penalty from the events at the same time I add a conditional constraint that "or those events that belongs to a single driver are possible to make, or are removed from the solution" without using drops.

Best Regards

[dhiraj shanbhag]

Can we put a constraint like 

range_start is a constant value for each node.

routing.solver().Add((time_dimension.CumulVar(dummy_node_index) - range_start )> 0)

This is part of the bigger constraint,

routing.solver().Add(((abs(time_dimension.CumulVar(dummy_next_node_index)      - time_dimension.CumulVar(dummy_node_index))< 30000) - ((time_dimension.CumulVar(dummy_node_index     ) - range_start )> 0)) >=0)

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/3f2dd771-c3c1-43c7-beef-4c0685d563ecn%40googlegroups.com.

--

Regards,

dhiraj d shanbhag

[angelo manzatto]

Yes you can, but what exactly are you trying to achieve? 

The routing.solver().Add((time_dimension.CumulVar(dummy_node_index) - range_start )> 0) could be replaced by:  time_dimension.CumulVar(dummy_node_index).SetMin(range_start) ?

The routing.solver().Add(((abs(time_dimension.CumulVar(dummy_next_node_index)  - time_dimension.CumulVar(dummy_node_index))< 30000) could be replaced by time_dimension.CumulVar(dummy_node_index).SetMax(30000) ?

Or  time_dimension.CumulVar(dummy_node_index).SetRange(range_start, 30000) ?

Won't this condition >=0 always evaluate as true ?

Is this the right thread ?

[dhiraj shanbhag]

routing.solver().Add(((abs(time_dimension.CumulVar(dummy_next_node_index)      - time_dimension.CumulVar(dummy_node_index))< 30000) - ((time_dimension.CumulVar(dummy_node_index     ) - range_start )> 0)) >=0)

actually the requirement is when the dummy_node_index is delivered after a constant time indicated by range_start.

I want the nodes dummy_next_node_index and dummy_node_index to be delivered within 30k seconds interval between each other.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1f17d107-cd71-4d02-b74c-0df37c762274n%40googlegroups.com.

[dhiraj shanbhag]

The doubt is can i add a constant value for comparison in the solver.Add()

[angelo manzatto]

routing.solver().Add(time_dimension.CumulVar(current_index) + 30000 <   time_dimension.CumulVar(next_index))

[Mizux Seiha]

basically you have all this operators available in python with an IntExpr ;)
https://github.com/google/or-tools/blob/fa84bc05e72641dddfbb98164d81b8bc9bef6ea5/ortools/constraint_solver/python/constraint_solver.i#L348-L481

[dhiraj shanbhag]

So what happens when we add the constraint,

routing.solver().Add((time_dimension.CumulVar(dummy_next_node_index)      - time_dimension.CumulVar(dummy_node_index))< 30000)

What does this enforce.

I have seen places where the cumulvars min value is used.

plan.Min(time_dimension.CumulVar(order))

plan.Max(time_dimension.CumulVar(order))

so what is the condition added in the solver enforcing?

Iam assuming that time_dimension.CumulVar(dummy_next_node_index)    is a single value...is that correct?

I want the delivery time suggested by google or for these 2 nodes to be within 30k seconds.

please correct me.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c98c0849-68da-47ad-835d-b58782d303b6n%40googlegroups.com.

[angelo manzatto]

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CA%2BMtg5iU5V2cqVryTFjAVqo%3DoLLHuaCDFWv6TLDCoNQGjqK12Q%40mail.gmail.com.

[dhiraj shanbhag]

routing.solver().Add((time_dimension.CumulVar(dummy_next_node_index)      - time_dimension.CumulVar(dummy_node_index))< 30000)

in reference to the above diagram,

In first case, does this mean 29999 -10000= 19999 < 30000

second case , 30k -10k=20k < 30k

I want that transit time (indicated by 19999, 20000) to be below 30k. 

How can I enforce this?

Thanks,

Dhiraj

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CACKMtOji7%2Bn0YZBBcw2ZihcUZH0QmgQthqr%2B%3DrpYi6d7svdzKA%40mail.gmail.com.