set costs for orders in or-tools

user_5448552 0
Viewed 349

We minimize the fuel consumed by the vehicles in terms of cost. Some customers may sometimes need an extra staff member while purchasing their products. These extra staffs have a fixed daily cost. This cost + fuel consumption should be minimized.

In the products you see in the figure, those with a code of 1 need extra staff in the car.

enter image description here

If those with 1 code go more in the same car and if there is no 1 code in other cars, they do not need staff and no extra money is paid for that person. This is not a necessity of course, but the aim is to minimize the total cost spent.

Note: If there is 1 product that needs even one extra person in the car, an extra fee will be paid. (extra $50 cost will be if there's an extra person in the car)

Here is how I calculate vehicle costs.

data['costs'] = [0.2314,0.158,0.132,0.201]
number_of_vehicles = 4
for vehicle_id in range(number_of_vehicles):
    routing.SetFixedCostOfVehicle(data['costs'][vehicle_id], vehicle_id)
vehicle-routing or-tools python
1 Answers

So basically if a vehicle visit a node which require a staff member you want to add a cost of 50 to the objective ?

Proposal in 3 steps:

  • Count number of staff needed locations which have been visited;
  • Transform this value in range [0, 1] at each end node.
  • Add a penalty cost to the objective if this value is 1.
  1. first I would add a dimension "staff_count" which is increased by 1 each time you visit a location which need a staff. (see capacity example: https://developers.google.com/optimization/routing/cvrp#python_1)
staff_cost = [...., 1, 0, 1, 0, 1, 0, 0, 0, 1, 1] # from 0..., 101 to 110

def staff_counter_callback(from_index):
  """Returns if staff is needed for this node."""
  # Convert from routing variable Index to demands NodeIndex.
  node = manager.NodeToIndex(from_index)
  return staff_cost[node]

staff_counter_callback_id = routing.RegisterUnaryTransitCallback(
staff_counter_callback)

dimension_name = "staff_counter"
routing.AddDimension(
 staff_counter_callback_id,
 0, # no slack
 N, # don't care just big enough so we won't reach it
 True, # force it to zero at start
 dimension_name
)
staff_counter_dimension = routing.GetDimensionOrDie(dimension_name)
  1. Second I'll create a second dimension "staff_used" (between 0,1) whose end node is 1 iif end node of the "staff" dimension is > zero.
    note: you can see it as a boolean set to 1 if we need a staff along the route, 0 otherwise
dimension_name = "staff_used"
routing.AddConstantDimensionWithSlack(
 0, # transit is 0 everywhere
 1, # capacity will be 0 everywhere and maybe 1 on end node
 1, # need slack to allow transition to 1 in end node
 True, # force it to zero at start
 dimension_name
)
staff_dimension = routing.GetDimensionOrDie(dimension_name)

solver = routing.solver()
for vehicle_id in range(manager.GetNumberOfVehicles()):
  index = routing.End(vehicle_id)
  # the following expr will resolve to 1 iff staff has been required along the route 
  expr = staff_counter_dimension.CumulVar(index) > 0
  solver.Add(expr == staff_dimension.CumulVar(index))

note: please notice that AddConstantDimensionWithSlack() has slack and capacity parameter swapped, I'm sorry for this API consistent issue...
ref: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L457-L467

  1. Third, use RoutingDimension::SetCumulVarSoftUpperBound, with upper bound 0 and penalty 50 on each end node of this second dimension.
    note: Idea pay 50 if staff_used_dimension.CumulVar(end_node) == 1
for vehicle_id in range(manager.GetNumberOfVehicles()):
  index = routing.End(vehicle_id)
  staff_dimension.SetCumulVarSoftUpperBound(index, 0, 50)

ref: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L2514-L2523

Annexe

If you want to limit the total number of vehicles having an extra worker to N you can use:

solver = routing.solver()
staff_at_end = []
for vehicle_id in range(manager.GetNumberOfVehicles()):
  index = routing.End(vehicle_id)
  staff_at_end.append(staff_dimension.CumulVar(index))

solver.Add(solver.Sum(staff_at_end) <= N)
user_57102330
Related