Effizientes Laden von Bussen

Dies ist etwas, was ich vor langer Zeit für ein Busreiseunternehmen getan habe, und ich war nie zufrieden mit den Ergebnissen. Ich habe kürzlich über dieses alte Projekt nachgedacht und dachte, ich würde dieses Problem noch einmal aufgreifen.

Problem:

Das Busreiseunternehmen verfügt über mehrere Busse mit unterschiedlichen Passagierkapazitäten (z. B. 15 Busse mit 50 Passagieren, 25 Busse mit 30 Passagieren usw.). Sie haben sich darauf spezialisiert, Transporte für sehr große Gruppen anzubieten (mehr als 300 Passagiere pro Gruppe). Da jede Gruppe zusammen reisen muss, muss sie ihre Flotte effizient verwalten, um Abfall zu reduzieren.

Zum Beispiel werden 88 Passagiere besser von drei Bussen mit 30 Passagieren (2 leere Sitze) bedient als von zwei Bussen mit 50 Passagieren (12 leere Sitze). Ein weiteres Beispiel: 75 Passagiere würden besser von einem Bus mit 50 Passagieren und einem Bus mit 30 Passagieren bedient, eine Mischung aus verschiedenen Typen.

Was ist ein guter Algorithmus, um dies zu tun?

Dies ist (eine Art) Beispiel für das Problem der Behälterverpackung, das häufig mit dem Problem des Rucksacks verwechselt wird. Beim Verpacken von Behältern haben Sie Behälter mit einer bestimmten Kapazität, und Sie versuchen, Objekte unterschiedlicher Größe in den Behältern zu verteilen. Die Idee ist, die geringstmögliche Anzahl von Behältern zu verwenden.

Sie versuchen jedoch nicht genau, die Anzahl der Fächer zu minimieren, sondern die Anzahl der freien Plätze. Und es ist möglich, dass Sie versuchen, die Anzahl der freien Plätze in der gesamten Flotte zu minimieren, dh Sie haben vier Reisegruppen unterschiedlicher Größe und möchten alle mit der geringsten Anzahl leerer Plätze aufnehmen. Ich kann mir keine Instanz auf Anhieb vorstellen, aber ich stelle mir vor, dass es möglich sein könnte, eine Flotte und eine Reihe von Reisegruppen so aufzubauen, dass Sie mit einer minderwertigen Lösung für eine Gruppe besser dran sind, weil Sie dies vermeiden konnten mit einer noch schlechteren Lösung für eine andere Gruppe.

Es wird schlimmer. Was ist, wenn Sie 20,30 und 50 Passagierbusse haben? Jeder verbraucht unterschiedliche Kraftstoffmengen, aber es ist effizienter, eine 50 zu fahren als eine 20 und eine 30. Aus unserer Einzelmaßnahme (geringste Anzahl leerer Sitze) ist es jedoch sinnvoll, entweder eine 50 zu fahren Passagiertour.

Auch Busse mit seltsamen Zahlen wie 28 oder 39 würden viele unserer Abkürzungen verzerren.

Abhängig von der Komplexität der Situation können Sie also eines von zwei Dingen tun:

Erster und umfassender Suchbaum: Verwenden Sie jede mögliche Kombination von Bussen. Wenn Sie nur 3 oder 4 Busgrößen haben, ist dies wahrscheinlich eine vernünftige Lösung. Andernfalls würde eine Verringerung der besten Anpassung zu angemessenen, aber nicht optimalen Ergebnissen führen.

Hier ist eine schnelle und schmutzige Lösung in Python:

def add50(passengers, buses):
    proposed = buses + [50]
    if sum(proposed) < passengers:
        return add50(passengers, proposed)
    return proposed

def add30(passengers, buses):
    proposed = buses + [30]
    if sum(proposed) < passengers:
        proposed30 = add30(passengers, proposed)
        proposed50 = add50(passengers, proposed)
        return proposed30 if sum(proposed30) < sum(proposed50) else proposed50
    return proposed

print add30(88, [])
print add30(75, [])
print add30(105, [])

Wenn ich es starte, bekomme ich:

[30, 30, 30]
[30, 50]
[30, 30, 50]

Der Code führt eine Tiefensuche durch die möglichen Szenarien durch. Da die Reihenfolge keine Rolle spielt ( [30, 50]ist die gleiche wie [50, 30]), können wir den Suchraum viel kleiner machen, indem wir nur Busse gleicher oder größerer Größe hinzufügen. Deshalb add30()kann man anrufen add50(), aber nicht umgekehrt.

Ich werde dies aus Kundensicht beantworten. Ich würde keinen fest codierten Algorithmus für diese Anwendung wollen. Es gibt zu viele Variablen, die sich im Laufe der Zeit ändern können. Obwohl sich an Ihren Bussen nichts ändern kann, kann sich das Gewicht der Faktoren ändern oder es können neue Faktoren entdeckt werden, an die ich nie gedacht habe (z. B. Überstunden, Gesetze und andere Fahrerkosten).

Aus diesem Grund möchte ich in der Lage sein, eine eigene Nachschlagetabelle basierend auf einem Bereich der Anzahl der angeforderten Passagiere zu erstellen, und ich würde meine eigenen Einstellungen für die besten Buskombinationen erstellen. Beispiel: 31-50 = 1 x 50, 51-60 = 2 x 30. Muss dies wirklich berechnet werden? Das Ändern von Einstellungen ist einfacher als bei einer Reihe von Formeln, bei denen Sitze, Benzin und Fahrer berücksichtigt werden. Finden Sie die beste Kombination heraus und machen Sie damit fertig. Der Benutzer hat ausreichend Platz, um diese Einstellungen nach eigenem Ermessen zu ändern.

Neue Faktoren konnten entdeckt werden. Zahlen größere Busse einen exponentiell höheren Mautsatz? Kann ich günstigere Fahrer für kleine Busse bekommen, wenn ein neues Gesetz für zusätzliche Zertifizierung und Lizenzierung für Fahrer von Bussen mit mehr als 30 Fahrgästen erlassen wird?

Sie stellen einen neuen Berater mit einer anderen Logik als ihre Formel ein, und Ihre App muss möglicherweise neu geschrieben werden. Sie meinen, Sie müssen die Parkkosten berücksichtigen?