Fairness - balance number of locations serviced per vehicle
- Dominant language
- C++
- Stars
- 155
- Forks
- 47
- PR merge metrics
- No merged PRs in 30d
Description
We want to be able to balance the number of locations serviced by each vehicle to be as even as possible. The use-case is for example drivers who are getting paid (at least partially) by number of deliveries.
This constraint should be behind a flag and optional.
---
Implementation: use the underlying solver to
- Establish a vehicle vars <-> vehicle counts relationship via the `Distribute` constraint
- Add a `Deviation` constraint for vehicle counts targeting the `deviation` var
- Minimizing the `deviation` var
Roughly as follows:
```c++
std::vector vehicleCounts;
for (auto vehicle = 0; vehicle < numVehicles; ++vehicle)
vehicleCounts.push_back(solver->MakeIntVar(0, numNodes));
solver->AddConstraint(solver->MakeDistribute(vehicleVars, vehicleCounts));
auto* deviationVar = solver->MakeIntVar(0, numNodes * numNodes);
solver->AddConstraint(solver->MakeDeviation(vehicleCounts, deviationVar, numNodes));
model.AddVariableMinimizedByFinalizer(deviationVar);
```
Contributor guide
Research direction
No file or test is named. Start by locating the vehicle-routing model and its optional-constraint configuration, then inspect how the underlying solver exposes Distribute, Deviation, and finalizer minimization. Done means an optional flag enables balanced per-vehicle location counts and the solver minimizes their deviation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 28/100