CODEWITHSUNDEEP
constraintsor-toolsvehicle-routing
heman33
heman33

Reputation: 45

in VRPTW, how to make the constraints soft instead of being strictly hard when doing the routing?

as the title indicates, when incorporating time window, vehicle constraints for nodes, in some scenarios the constraints are too strict and I am unable to produce an output.
How can I make the constraints optional or soft but reflect that in a cost (utility) function, so I can rank my solutions?

Used combinations of constraints to solve the VRPTW but it turned out to be unsolvable, how to make it solvable but reflect the degree to which I am violating the constraints?

Upvotes: 3

Views: 350

Answers (1)

Mizux
Mizux

Reputation: 9291

Please try to use

void RoutingDimension::SetCumulVarSoftUpperBound(
  int64_t index,
  int64_t upper_bound,
  int64_t coefficient);

ref: https://github.com/google/or-tools/blob/f460e9b0fcd444c37878ec64be9822d40fb375f4/ortools/constraint_solver/routing.h#L2905-L2914

and/or

void RoutingDimension::SetCumulVarSoftLowerBound(
  int64_t index,
  int64_t upper_bound,
  int64_t coefficient);

ref: https://github.com/google/or-tools/blob/f460e9b0fcd444c37878ec64be9822d40fb375f4/ortools/constraint_solver/routing.h#L2927-L2937

note: Supposing you have

0 ---- [min_hard -- [min_soft --- max_soft] -- max_hard] --- vehicle_capacity

You could use (in Python)

index = manager.NodeToIndex(42)
time_dimension = routing.GetDimensionOrDie('Time')
time_dimension.CumulVar(index).SetRange(min_hard, max_hard)
penalty = 100
time_dimension.SetCumulVarSoftLowerBound(index, min_soft, penalty)
time_dimension.SetCumulVarSoftUpperBound(index, max_soft, penalty)

if vehicle visit index at max_soft + k then the objective will have k * penalty extra cost.

Upvotes: 3

Related Questions