Optimize based on most distant/costly point

[GB]

Hello,

I need to handle a case in which each vehicle's route cost is determined solely by the cost assigned to the most most distant point that it reaches during its route;  visits to all other point in each vehicle's route are 'free'.

Naturally, we do not know a priori which is that most costly point, as this is also part of planning ...

Any ideas how to handle such case?

Thx,

Guy

[Paulius Grigelis]

Sounds like you should use VRP, create distance dimension and set SetCumulVarSoftUpperBound on each vehicle end node (depot, end index of the vehicle), with penalty for each unit of distance.

[Paulius Grigelis]

I might have misunderstood, maybe what you want is:
Keep nodes values locally, create transit callback for cost, if node junction is any to end of route, then return that cost of "any" node, otherwise -> 0.

[blind.line]

I would try a matrix zero cost everywhere, only non zero for trips to depot node. 

But that result might be nonsensical unless you have done other dimension with same bounds. 

James

On Apr 4, 2021, at 10:00, Paulius Grigelis <p.gri...@gmail.com> wrote:

I might have misunderstood, maybe what you want is:

--
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/6a09029a-5971-4fcc-ac62-70e351a228d4n%40googlegroups.com.

[GB]

Thx p.gri

Does not seem to apply a cost only for visiting the most distant or costly Node, and 0 for visiting any other.

[blind.line]

I mean, define most distant. From what?

Consider. 

A — depot — B

     

A to B is more distant than A to depot, B to depot 

But if more distant us from depot, then a valid trip is depot to A, A to B, B to depot

And my idea will fail if depot to A is longer than B to depot. 

Might not be possible without a lot of trickery

James

On Apr 4, 2021, at 10:54, GB <guy.be...@gmail.com> wrote:

Thx p.gri

--

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/fd52d5e1-bab5-49b3-836b-83a8b129959an%40googlegroups.com.

[Laurent Perron]

Tsp or vrp ?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/D0123ACC-8E17-489C-AD47-20C6327C703D%40gmail.com.

[GB]

VRP

[GB]

Single depot, where each field-Node has an assigned cost for visiting it, regardless which Node preceded it.

In many cases this visit-cost is proportional to the Node's distance from the depot.

[GB]

I'm looking for a 'peak-detector', that reflects only the cost of the highest cost Node. 

Tricky without memory.

[Laurent Perron]

1 or mor vehicle?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/75f1da0c-1a2a-4c4a-8964-efc3367fb236n%40googlegroups.com.

[GB]

VRP with multiple-vehicles.

If there is a way to handle this for a single vehicle at a time, it could be used iteratively.

[GB]

Single vehicle is trivial, as you know in advance what is the most costly point it would visit ...

I can't see how to iterate this and solve for VRP.

[GB]

Laurent, @Mizux - any tips for a way  to achieve this?

Thx

[Laurent Perron]

I do not think you can do it with the routing library.

I could be done with CP-SAT, but modeling VRPs is a bit tricky, and I am not sure it will scale that well.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/480eca66-9927-486a-b0b6-78b25355e1f1n%40googlegroups.com.

[GB]

Could there be a trick around span-cost, that somehow captures the highest cost?

[Laurent Perron]

span is total trip with the initial waiting time.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/55102978-ab1f-4b53-afd8-4c9952ee188bn%40googlegroups.com.

[Vincent Furnon]

Span costs can be on any dimension, not only time or distance. However they are based on the cumul values of the start and end nodes of a route, so it won't catch the max.

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

[GB]

Indeed. Trivial usage of span would not work.

Thx.

[Mizux Seiha]

My 0.5 cent
DISCLAIMER: THIS IS NOT TESTED AT ALL (any feedback welcome)

Technically you can have a "value memory" per node using a SlackVar:

1) Use the IntExpr `NextVar(I) == J` to check (i.e. having a BooleanVar) if "node J is the next node of node I".

2) use a SlackVar from a dummy dimension (let's call it DIM_ONE) as node memory to store the max(the current node, the previous slack)

2.1) DIM_ONE dimension has a 0 constant transit callback, a very big capacity and slack range that must be at least PEAK cost

3) You should have the "peak" value in the last node's SlackVar before the end node (and an ugly CumulVar)
4) Create an other dummy dimension (let's call it TWO) whose is zero everywhere only slackVar of last node before end node == slackVar of dimension ONE
5) Use dimTWO.SetCumulVarSoftUpperBound(routing.End(0), 0, penalty_per_unit) to have a peak cost added to the objective.

6) Profit ?

e.g. route S(0) -> 13 -> 42 -> 31 -> E(0),
 with: cost(13) = 5, cost(42) = 10 (our peak), cost(31) = 8
```md

|  Dim/Field   | S | 13 | 42 | 31  | E |

| --                 | -- | --  | --   | -- | --  |
| Point cost    | 0 |  5  |  10 | 8  | 0 |
|ONE/Slack  | 0 |  5  |  10 | 10  | NA | < max (cost(N), slack(N-1))
|ONE/Cumul| 0 |  0  |   5  |  15 |  25 |  < pill of xxxxx
|TWO/Slack  | 0 |  0  |  0 | 10  | NA |  < should have all slack to 0 except the "last one"
|RWO/Cumul| 0 |  0  |   0  |  0 |  10 | <= What we are looking for ! (we can use CumulVarSoftUpperBound to create an "objective's cost" from it)

```

pseudo code:

# Initialisation
cost = [......] # your point cost array

routing.AddConstantDimensionWithSlack(
 0, # transit 0
 BIG_ENOUGH, # capacity: don't care jsut need to be able to store at least PEAK*ROUTE_LENGTH in worst case
 PEAK, # slack_max: to be able to store peak in slack
 True, #  Fix StartCumulToZero not really matter here

 "ONE"
)

dim_one = routing.GetDimensionOrDie("ONE")

routing.AddConstantDimensionWithSlack(
 0, # transit 0
 PEAK, # capacity: we only want to be able to have PEAK value in CumulVar(End)
 PEAK, # slack_max: to be able to store peak in slack
 True, #  Fix StartCumulToZero YES here

 "TWO"
)

dim_two = routing.GetDimensionOrDie("TWO")

# force depot Slack to be cost since we don't have any predecessor... 

for v in range(manager.GetNumberOfVehicles()):
  dim.SlackVar(routing.Start(v)).SetValue(cost[0])

# Step by step relation

for I in all_node:
   if I is in end_nodes_list:
     continue # again end node don't have any successor + end node don't have any slack...

   for J in all_node:

     # todo(mizux) test what happen when using NextVar(EndNode) for fun ;)
     cond = routing.NextVar(I) == J

     expr = dim_one.SlackVar(J) == solver.Max(dim_one.SlackVar(I), cost[j])

     solver.ConditionalExpression(cond, expr, 0)  # not tested should do the implication

# relation between dimensions, copy last node Slack from dim ONE to dim TWO
for I in all_node:

  cond = routing.NextVar(I) == solver.IntVar([end_nodes_list]) # The node after I is an End node

  expr = dim_one.SlackVar(I) == dim_two.SlackVar(I)
  solver.ConditionalExpression(cond, expr, 0) 

# Should force all others dim_two slack var to zero...

for v in range(manager.GetNumberOfVehicles()):

    # routing.AddVariableMinimizedByFinalizer(dim_two.CumulVar(routing.End(v))); # not sure is needed

    dim_two.SetCumulVarSoftUpperBound(routing.End(0), 0, penalty_per_unit) # step 5)

```

note: I'll try to create a gist and/or a github discussion (Find Max costly node in a route ? (any suggestion welcome)) to have syntax highlight etc...
mailing list don't support markdown and message edit...

PS:

  std::pair<int, bool> AddConstantDimensionWithSlack(

      int64_t value, int64_t capacity, int64_t slack_max,

      bool fix_start_cumul_to_zero, const std::string& name);

ref: https://github.com/google/or-tools/blob/fa84bc05e72641dddfbb98164d81b8bc9bef6ea5/ortools/constraint_solver/routing.h#L462-L472

YUP slack_max is AFTER [vehicle] capacity argument ONLY in this method ! Google consistency for the win ;) 
-> maybe we should fix it for v9.0 (and break the code of everyone using it #ConsistencyMatter #YouCanBlameMe (ed don't know if this #tag exists))

[Mizux Seiha]

After few trials, starting from the vrp_global_span.py sample:
node cost used:
* depot: 0
* node 1,2,15,16: 42
* others: 8

dim_two.CumulVar(End) contains the Max node cost along the road...

./vrp_max.py 

Objective: 316840

Route for vehicle 0:

 N:0 one:(0,0) two:(0,0) -> N:0 one:0 two:0

Distance of the route: 0m

Route for vehicle 1:

 N:0 one:(0,0) two:(0,0) ->  N:5 one:(0,8) two:(0,0) ->  N:13 one:(8,8) two:(0,8) -> N:0 one:16 two:8

Distance of the route: 1256m

Route for vehicle 2:

 N:0 one:(0,0) two:(0,0) ->  N:7 one:(0,8) two:(0,0) ->  N:1 one:(8,42) two:(0,0) ->  N:4 one:(50,42) two:(0,0) ->  N:3 one:(92,42) two:(0,0) ->  N:15 one:(134,42) two:(0,0) ->  N:11 one:(176,42) two:(0,0) ->  N:12 one:(218,42) two:(0,42) -> N:0 one:260 two:42

Distance of the route: 2192m

Route for vehicle 3:

 N:0 one:(0,0) two:(0,0) ->  N:8 one:(0,8) two:(0,0) ->  N:6 one:(8,8) two:(0,0) ->  N:2 one:(16,42) two:(0,0) ->  N:10 one:(58,42) two:(0,0) ->  N:16 one:(100,42) two:(0,0) ->  N:14 one:(142,42) two:(0,0) ->  N:9 one:(184,42) two:(0,42) -> N:0 one:226 two:42

Distance of the route: 2192m

Maximum of the route distances: 2192m

[Guy Benhaim]

Thanks for the effort and creativity @Mizux !

Assuming I manage to understand this ... I will check to see if it can be applied to the real use-case and its scale.

I am investigating another option which also requires a super-tricky model. Still not sure that it works.

Guy

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/tQjKhNupnWY/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/426b41dc-0085-4eba-b872-754a2cef6cc7n%40googlegroups.com.

[GB]

Hello,

I believe the creative concept is valid, but I got lost in the implementation. 

Follow the two main functions with clarification questions.

 # Step by step relation

    # Slack(N) = max( Slack(N-1) , cost(N) )

    solver = routing.solver()

    for node in range(1,17):

       index = manager.NodeToIndex(node)

       routing.AddToAssignment(dim_one.SlackVar(index))

       routing.AddToAssignment(dim_two.SlackVar(index))

       test = []   

# GB: What type of variable does "test" array/list hold - IntVar?, IntExpr?

       for v in range(manager.GetNumberOfVehicles()):

         previous_index = routing.Start(v)

# GB: Is this s 3-level nexted-loop or is the "v" for-loop just used for getting the first Node?

         cond = routing.NextVar(previous_index) == index

# GB: then we progress via NextVar and check that Node vs. all Nodes, using the "node" for-loop?

# GB: what variable type is "cond" - IntExpr?, IntVar?

         value = solver.Max(dim_one.SlackVar(previous_index), data['cost'][node])

#GB: Getting an error using Max, should we use "MakeMax"?

         test.append(cond * value)

       for previous in range(1,17):

#GB: Can you explain this for loop?

         previous_index = manager.NodeToIndex(previous)

         cond = routing.NextVar(previous_index) == index

# GB: what variable is "cond" - IntExpr?, IntVar?

         value = solver.Max(dim_one.SlackVar(previous_index), data['cost'][node])

         test.append(cond * value)

       solver.Add(solver.Sum(test) == dim_one.SlackVar(index))

# GB: Getting an error using "Sum" when test[] holds IntExpr. Should we use MakeSum?

 # relation between dimensions, copy last node Slack from dim ONE to dim TWO

    for node in range(1,17):

       index = manager.NodeToIndex(node)

       values = []

# GB: What type of variable does "values" array/list hold - IntVar?, IntExpr?

       for v in range(manager.GetNumberOfVehicles()):

         next_index = routing.End(v)

         cond = routing.NextVar(index) == next_index

# GB: what variable is "cond" - IntExpr?, IntVar?

         value = dim_one.SlackVar(index)

         values.append(cond * value)

         expr = dim_one.SlackVar(index) == dim_two.SlackVar(index)

# GB: "expr" is defined, but is not used. Should it be used?

       solver.Add(solver.Sum(values) == dim_two.SlackVar(index))

# GB: Getting an error using "Sum". Should we use MakeSum?

[Mizux Seiha]

ps: don't hesitate to join us on discord (chat badge in the readme on github) if you have question

Le lundi 19 avril 2021 à 05:36:10 UTC+2, GB a écrit :

Hello,

I believe the creative concept is valid, but I got lost in the implementation. 

Follow the two main functions with clarification questions.

 # Step by step relation

    # Slack(N) = max( Slack(N-1) , cost(N) )

    solver = routing.solver()

    for node in range(1,17): # First Loop Level

       index = manager.NodeToIndex(node)

       routing.AddToAssignment(dim_one.SlackVar(index))

       routing.AddToAssignment(dim_two.SlackVar(index))

       test = []   

# GB: What type of variable does "test" array/list hold - IntVar?, IntExpr?

test will be an array of IntExpr see below...

 

this loop A is basically the same than the loop B below but since I loop on node and convert them to index I've to use manager.NodeToIndex()...

which is undefined for start/end node so I use two loops, an improvment would be to loop on index directly
i.e. using `for index in range(routing.size()):`

       for v in range(manager.GetNumberOfVehicles()):   # LOOP A, Second Loop Level (just to deal with previous_index being a start node)

         previous_index = routing.Start(v)

# GB: Is this s 3-level nexted-loop or is the "v" for-loop just used for getting the first Node?

 v for-loop for getting the first nodes i.e. for previous_index in all start nodes (internally each vehicle has an unique id for its start node which can be retrieve by using routing.Start(vehicle_index)) 

         cond = routing.NextVar(previous_index) == index

# GB: then we progress via NextVar and check that Node vs. all Nodes, using the "node" for-loop?

# GB: what variable type is "cond" - IntExpr?, IntVar?

here cond is a Constraint, true if we have the route `previous_index -> index` false otherwise.

long story:
routing.NextVar(previous_index) is an IntVar,

IntExpr is the base class of IntVar (see https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/constraint_solver.h#L4001)

and you have an overload for operator == in IntExpr (see https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/python/constraint_solver.i#L406-L408)

for any index (not being a start node) there is an unique predecessor so this cond is always false except for one value of previous_index 

You can see it as a Boolean or bit flag "is index nextVar of previous index ?" 

 

         value = solver.Max(dim_one.SlackVar(previous_index), data['cost'][node])

#GB: Getting an error using Max, should we use "MakeMax"?

if using max() it will be interpreted by Python and its builtin max function, here we want the max operator provided by the routing solver

ref: https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/constraint_solver.h#L1175-L1177

in python binded as max: https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/python/constraint_solver.i#L763

 

         test.append(cond * value)

here "cond * value"  is an IntExpr, (we overload the operator Constraint::__mul__(int64) -> IntExpr)

see: https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/python/constraint_solver.i#L513-L515

 

       for previous in range(1,17):  # LOOP B, Second Loop Level (to deal with previous_index being NOT a start node)

#GB: Can you explain this for loop?

same as above but this time previous index is range 1,17 aka this is NOT a start or end node so we can use manager.NodeToIndex() method to retrieve the solver internal "index" value

again is just a convertion between user "node" ordering and solver "index" ordering

 

         previous_index = manager.NodeToIndex(previous) # This call is undefined for start node thus Loop A

         cond = routing.NextVar(previous_index) == index

# GB: what variable is "cond" - IntExpr?, IntVar?

As above a Constraint  `routing.NextVar(previous_index) == index` in literal "is index the following node of previous_index in the route ?"

         value = solver.Max(dim_one.SlackVar(previous_index), data['cost'][node])

         test.append(cond * value)

again "cond * value" will be an IntExpr

       solver.Add(solver.Sum(test) == dim_one.SlackVar(index))

# GB: Getting an error using "Sum" when test[] holds IntExpr. Should we use MakeSum?

here again we are using the contraint solver MakeSum() method which take an array of IntVar
https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/constraint_solver.h#L1088

note: Sum is a python rename of MakeSum (i.e. all "Make" have been removed in the python api)

see: https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/python/constraint_solver.i#L761 

Yes test is an array of IntExpr BUT we since have `class IntVar : public IntExpr` so I guess here we have a broken downcasting and luckily for us, code only use IntExpr virtual methods

see: https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/expr_array.cc#L3252-L3299

note: we can also see the overload method MakeSum(IntExpr*, IntExpr*) ...

todo(mizux): add a DCHECK(dynamic_cast<IntVar*>(var) != nullptr_t) just for fun :D

 # relation between dimensions, copy last node Slack from dim ONE to dim TWO

    for node in range(1,17):

       index = manager.NodeToIndex(node)

       values = []

# GB: What type of variable does "values" array/list hold - IntVar?, IntExpr?

see below but you should already know now ;)

       for v in range(manager.GetNumberOfVehicles()):

         next_index = routing.End(v)

         cond = routing.NextVar(index) == next_index

# GB: what variable is "cond" - IntExpr?, IntVar?

as usual cond is a Contraint object (print(f"cond {type(cond)}"))  -> cond: <class 'ortools.constraint_solver.pywrapcp.Constraint'>

         value = dim_one.SlackVar(index)

         values.append(cond * value)

and "cond * value" is an ............... IntExpr ! (one point if you found it)

 

         expr = dim_one.SlackVar(index) == dim_two.SlackVar(index)

# GB: "expr" is defined, but is not used. Should it be used?

dead code, should be removed, i guess it was a previous attempt before using Sum of "boolean_flag(i) * slackVar(i)" approach...

EDIT: seems to have been cleanup https://github.com/google/or-tools/blob/c62fd93d2787ae785fdf8661f47d27195fcdf3b5/ortools/constraint_solver/samples/vrp_node_max.py#L258-L267

       solver.Add(solver.Sum(values) == dim_two.SlackVar(index))

# GB: Getting an error using "Sum". Should we use MakeSum?

yup, again don't use python sum which will be evaluated during the model creation but use the MakeSum/Sum of the solver which will be "dynamically" evaluated during the search... 

[GB]

Now I can take-a-shot at testing this.

Thx.

[GB]

Hello

For C# : when value is IntExpr and values is IntExpr[] then MakeSum fails, as it can only handle IntVarVector 

IntExpr[] values = new IntExpr[manager.GetNumberOfVehicles()];  

 for (int v = 0; v < manager.GetNumberOfVehicles(); v++)   {       

long next_index = routing.End(v); 

Constraint cond = routing.NextVar(index) == next_index;    

IntExpr value = dim_one.SlackVar(index);       

values[v] = cond * value;       

solver.Add(solver.MakeSum(values) == dim_two.SlackVar(index));
}

If value is IntVar and values is IntVarVector, then MakeSum is ok, but cond * value fails ...

Any recommendation?

[Laurent Perron]

use IntVar[], IntVar and write values[v] = (cond * value).Var();

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e8f0bf56-7aee-4f38-acce-a1b86e60a780n%40googlegroups.com.

[GB]

Indeed, cleans the errors.

Thx

[GB]

The current scheme's rules seems to apply, but I still have doubts whether the result is optimal or close to optimal. Testing.

I want to set  dim_two.SlackVar to be equal to its previous node's dim_one.SlackVar  (of the same vehicle, of course).

I tried the following, which has an error that does not accept  solver.MakeMax(indices) as index value. 

Any tips?  Is there a simpler way ?

for (int n = 1; n < nodes; n++)     

{     

 IntVar[] indices = new IntVar[nodes];      

long index = manager.NodeToIndex(n);      

     for (int p = 1; p < nodes; p++)      CHECK WHICH NODE IS THE PREVIOUS

     {          

     long previous_index = manager.NodeToIndex(p);  

     Constraint cond = routing.NextVar(previous_index) == index;   

      indices[p]= (cond * p).Var();      STORE ITS NODE-INDEX IN THE ARRAY

      }      

solver.Add(dim_two.SlackVar(index) == dim_one.SlackVar(solver.MakeMax(indices));   ERROR WHEN SETTING THE CONSTARINT

}

[hannes]

I'd like to limit the cumulative value of a dimension for each tour. I have tried two approaches. Example code at end of mail.

1. settings the capacity in the dimension constructor
2. using dimension.SetSpanUpperBoundForVehicle

The docstring of SetSpanUpperBoundForVehicle states that this is the preferred way of limiting the "length" of a route along a dimension.

First question: (just to be sure) constraint 2 is a hard constraint, right?
Second question: if I want to limit the length of all routes, what's wrong with the capacity parameter?


=== Python example ===
   
    capacity = 200
    span = 200
    n_stops = 3
    n_vehicles = 2
    start_locations = n_vehicles * [0]
    end_locations = n_vehicles * [0]
    index_manager = RoutingIndexManager(n_stops, n_vehicles, start_locations, end_locations)
    routing_model = RoutingModel(index_manager)

    callback_index = routing_model.RegisterTransitCallback(callback=lambda x, y: 100)
    routing_model.SetArcCostEvaluatorOfAllVehicles(callback_index)

    routing_model.AddDimension(
        evaluator_index=callback_index,
        slack_max=0,
        capacity=capacity,
        fix_start_cumul_to_zero=True,
        name="transit")

    transit_dimension = routing_model.GetDimensionOrDie("transit")

    if span:
        for vehicle_ix in range(n_vehicles):
            transit_dimension.SetSpanUpperBoundForVehicle(span, vehicle_ix)
            transit_dimension.SetS(span, vehicle_ix)

    assignment = routing_model.Solve()
    assert assignment is not None

[Guy Benhaim]

I believe you also need to consider whether the dimension starts at 0 or a higher value.

--

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/tQjKhNupnWY/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/c860cdbf-13ab-1695-016c-9873c47a5d7e%40yahoo.de.

[hannes]

Although I don't know how to test it yet it could well be that the span puts a constraint on the difference between end and start value (i.e. "the span") while the capacity limits the cumulative value at each intermediate stop of a route. In that case the two constraints would not be comparable in the sense that I could not replace one with the other.

So, if I want to put a constraint on the difference between start and end value I use SetSpanUpperBoundForVehicle.

If on the other hand I want to limit the cumulative value at each stop I use the capacity parameter of the dimension.

To my understanding, the fix_start_cumul_to_zero is in both cases another optional constraint that may be relevant to my model or not.

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/CAPeLag%2B4UUGwZhqrKbQ7d7N%2B3swQBijKGmoWXzDwg5oJFOCGeg%40mail.gmail.com.

[GB]

The structure @MIZUX suggested runs and gives reasonable results. (a demo case, small scale > 16 Nodes)

However, very often the result could be easily improved by a human, for example:

With 4 Nodes with low-cost to visit plus 4 Nodes with high-cost to visit, the solver mixes Nodes in each vehicle and the result is not optimal:

V0 > high, high, high, low

V1> low, low, low, high

I expected the solver to replace low <-> high and yield a better total result, but this does not occur even after 120 Sec of GLS.

Is it due to cost-ing using SoftUpperBound, which prevents the solver the re-evaluate the cost after every insertion?

Any way to guide the search process, to make such exchanges?

Thx

On Tuesday, April 20, 2021 at 11:43:43 AM UTC+3 mizu...@gmail.com wrote:

[J. E. Marca]

Guy, sorry for resurrecting an older thread, but I was looking at this and I wondered if you had a simple data set that exhibits the issues you outlined above...4 nodes high cost, 4 nodes low cost.  I was looking at the sample program vrp_node_max.py, and wanted to try a few things, and maybe compare versus a CP-SAT based solution.

Thanks,

James

[J. E. Marca]

I was able to reproduce the issue @GB was seeing, and came up with a different approach to this problem that seems to work correctly.  I wrote it up in a blog post here: https://activimetrics.com/blog/ortools/vrp_node_max_take2/

I think the issue with using slack to ferret out information is that the solver does not have consistent inputs.  For example, if a route has two cheap nodes and two expensive nodes, then swapping either one cheap or one expensive node has no effect.  But if the (cheap or expensive) node being swapped out is the last of its kind on a route, then all of the values of all of the nodes will change.  I suspect the solver is not designed to expect this kind of situation. 

Therefore, my approach was to create dummy nodes for the real nodes, one for each possible "promotion" in value.  So if the most expensive node is in a route, it can only be reached by other, equal value nodes, which can be actually that value, or else cheaper nodes that have been duplicated up into the expensive value group.  In this case, the solver has some consistency.  It knows from the disjunction call all of the alternative duplicate nodes for a single real node, and can properly evaluate the cost of rotating the various alternatives in and out.  Differently valued nodes cannot reach each other, and so the solver can come up with a "correct" solution.

If the weight of the soft lower bound is small, then the solver will prefer shorter routes over minimizing the value of a route.  If the soft lower bound weight is larger, then the solver prefers grouping together low value nodes into a single route, at the expense of longer routes.

As I said, I wrote it up in more detail in my post.  Plus my final program.

James