mapbox / mapbox/node-or-tools

Fairness - balance number of locations serviced per vehicle

Offen
#1 3 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Dieses Issue hat noch niemand übernommen.

Vorherrschende Sprache
C++
Sterne
155
Forks
47
PR-Merge-Kennzahlen
Keine gemergten PRs in 30 T.

Beschreibung

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);
```

Beitragsleitfaden

Beitragsleitfaden öffnen

Erste Schritte

  1. Lies das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreib ins Issue, dass du es übernimmst — das erspart doppelte Arbeit.
  3. Forke das Repository und arbeite in einem Branch.
  4. Öffne einen Pull Request, der die Issue-Nummer nennt.

Rechercherichtung

Es wird keine Datei und kein Test genannt. Beginne damit, das Fahrzeugroutenmodell und seine Konfiguration für optionale Constraints zu finden, und untersuche anschließend, wie der zugrunde liegende Solver Distribute, Deviation und die Finalizer-Minimierung bereitstellt. Fertig ist es, wenn ein optionales Flag ausgeglichene Standortanzahlen pro Fahrzeug aktiviert und der Solver deren Abweichung minimiert.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Bewertung

Tech-Stack
cpp
Bereich
backend
Issue-Typ
Feature
Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Aktivitätsstatus
Veraltet
Klarheit
Größtenteils klar
Anfängerfreundlichkeit
28/100

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.