softUpperbound/ Penalty on Cumulative value of the dimension throughout the route.

[dhiraj shanbhag]

Let's assume my vehicle drops and pickups items during the route.

So, I have a dimension that keeps track of the current load in the vehicle.

The cumulVar goes up and down.

So, If the vehicle's max capacity is 1000kg, I can assign that value while creating the dimension. But this makes the solution infeasible in some cases.

So, I want to put 2000 kg as the max load but assign a soft upper bound with a high penalty. like : 

dimension_name.SetCumulVarSoftUpperBound(index, 1000, 10000000000)

so, beyond 1000 kg load at any point during the route a penalty will be assigned.

I have used this at the start and end node using routing.End(veh)/ routing.Start(veh), how can I implement this over all the nodes of the route.

for veh in range(0, num_vehicles):

        index_end = routing.End(veh)

        dimension_name.SetCumulVarSoftLowerBound(index_end, 10, 10000000000)

--

Regards,

dhiraj d shanbhag

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

maybe:

for veh in range(0, num_vehicles):

for node in range(num_nodes):
index = routing.NodeToIndex(node)
dimension_name.SetCumulVarSoftupperBound(index, 10000, 100)

Note the penalty is multiplied by the miss. So if the value is 10001,
the miss is 1 and the penalty is 100. If the value is 11000, the miss
is 1000 and the penalty is 100000. So don't set the penalty too crazy
high or the solver might end up treating this as a hard constraint.
Or worse, hit an overflow error.

Regards,
James

On Fri, Aug 06, 2021 at 09:47:35PM +0530, dhiraj shanbhag wrote:
> Let's assume my vehicle drops and pickups items during the route.
> So, I have a dimension that keeps track of the current load in the vehicle.
> The cumulVar goes up and down.
>
> So, If the vehicle's max capacity is 1000kg, I can assign that value while
> creating the dimension. But this makes the solution infeasible in some
> cases.
> So, I want to put 2000 kg as the max load but assign a soft upper bound
> with a high penalty. like :

> *dimension_name.SetCumulVarSoftUpperBound(index, 1000, 10000000000)*

> so, beyond 1000 kg load at any point during the route a penalty will be
> assigned.
>

> *I have used this at the start and end node using routing.End(veh)/

> routing.Start(veh), how can I implement this over all the nodes of the

> route.*

>
> for veh in range(0, num_vehicles):
> index_end = routing.End(veh)
> dimension_name.SetCumulVarSoftLowerBound(index_end, 10, 10000000000)
>
> --
> Regards,
> dhiraj d shanbhag
>

> --
> 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/CA%2BMtg5isageQf7oKnAtAoZGULDr0NHT-O1VSJnSb2%2BgJ2ABhZg%40mail.gmail.com.

--

James E. Marca
Activimetrics LLC

[dhiraj shanbhag]

Hi,

I will give another example of the scenario:

Let's assume we have 2 vehicles:

Vehicle 1, vehicle 2: Vehicle 1 with max capacity 1000kg and vehicle 2 with max capacity 2000kg.

I need to implement a constraint such that any time during the route The weight inside the vehicles doesn't cross their respective max capacity.

I want to implement this as a soft constraint.

@James, What you mentioned in the answer, will work if all vehicles have the same capacity.

should I use some form of solver.constraint()

Is there any better way to do it.

Thanks,

Dhiraj

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/20210806171404.GD1%40d0a76a895d96.

[dhiraj shanbhag]

@mizux any suggestions on this?

Thanks, 

On Mon, Aug 9, 2021, 3:53 AM blind.line <blind.lin...@gmail.com> wrote:

Sounds like a fun problem you’ve got there.  I’m sure you can figure something out. 

James

On Aug 8, 2021, at 09:58, dhiraj shanbhag <shanbha...@gmail.com> wrote:



[Mizux Seiha]

DISCLAIMER: NOT TESTED

I would try the same old trick: create in a dummy dimension's SlackVar any overload then on each 1000kg vehicle end nodes of this dimension add a CumulVarSoftUpperBound...

Something like this (not tested):
```python

routing.AddConstantDimensionWithSlack(

  0, # value

  MAX_TIME, # capacity

  LARGE_ENOUGH, # slack (ed yes after the capacity in this method -_-)

  True, #fix_start_cumul_to_zero

  "shanbhag")

dim = routing.GetDimensionOrDie("shanbhag")

load_dim = routing.GetDimensionOrDie("Load") # your load dimension used to compute the vehicle current load (in kg ?)

# Compute potential overweight (aka value above 1000) for each node
for node in all_location:
  if node == depot:

    continue

  index = manager.NodeToIndex(node)

  tmp = load_dim.CumulVar(index) > 1000 # if node has a CumulVar above 1000

  routing.solver().Add( (load_dim.CumulVar(index) - 1000) * tmp == dim.SlackVar(index)) # then set SlackVar to the overweight

# Compute upper bound soft penalty ONLY for 1000kg vehicles

for vehicle in vehicle_with_one_thousand_capacity:
  end = routing.End(vehicle)

  dim.SetCumulVarSoftUpperBound(end, 0, PENALTY_PER_UNIT) # penalty is per unit i.e. per kg per location here...

```

note: tmp is use in case load if < 1000 instead of having a negative slack, slack will be zero since tmp will be false aka 0.

note: upper bound limit is 0 since I already offset by 1000 when computing the SlackVar, so the CumulVar at end node is the cumulative sum of the overweight along the route i.e. you want the "shanbhag" dimension to be zero for each 1000kg vehicle at end node.
note: Vehicle with 2000kg may have a CumulVar positive at the end but I don't care since the vehicle loop filter out them -> no soft upper bound for them, +by default all dimension have a span cost coefficient to zero i.e. won't participate/influence the objective IMHO.

ref: RoutingModel::AddConstantDimensionWithSlack() https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L457-L467