Wydajne ładowanie magistrali

To właśnie zrobiłem dawno temu dla biura podróży autobusowych i nigdy nie byłem zadowolony z rezultatów. Ostatnio myślałem o tym starym projekcie i pomyślałem, że wrócę do tego problemu.

Problem:

Firma zajmująca się podróżami autobusowymi ma kilka autobusów o różnych pojemnościach pasażerskich (np. 15 autobusów 50-osobowych, 25 autobusów 30-osobowych ... itd.). Specjalizowali się w oferowaniu transportu do bardzo dużych grup (ponad 300 pasażerów na grupę). Ponieważ każda grupa musi podróżować razem, musiała skutecznie zarządzać swoją flotą, aby zmniejszyć ilość odpadów.

Na przykład 88 pasażerów lepiej obsługuje trzy autobusy 30-osobowe (2 puste miejsca) niż dwa autobusy 50-osobowe (12 pustych miejsc). Kolejny przykład: 75 pasażerów byłoby lepiej obsługiwanych przez jeden autobus 50-osobowy i jeden autobus 30-osobowy, połączenie różnych rodzajów.

Jaki jest dobry algorytm, aby to zrobić?

Jest to (poniekąd) przykład problemu pakowania pojemnika, który często jest mylony z problemem plecaka. W przypadku pakowania pojemników masz pojemniki o określonej pojemności i próbujesz rozdzielić przedmioty o różnych rozmiarach do pojemników. Chodzi o to, aby użyć możliwie najmniejszej liczby pojemników.

Jednak nie próbujesz dokładnie zminimalizować liczby pojemników, próbujesz zminimalizować liczbę pustych miejsc. Możliwe, że próbujesz zminimalizować liczbę pustych miejsc we flocie, to znaczy, że masz cztery grupy wycieczek o różnych rozmiarach i chcesz pomieścić wszystkie z najmniejszą liczbą pustych miejsc. Nie mogę sobie wyobrazić instancji od razu, ale wyobrażam sobie, że może być możliwe zbudowanie floty i zestawu grup wycieczkowych, tak aby lepiej byłoby, gdybyś miał jakieś niestandardowe rozwiązanie dla niektórych grup, ponieważ pozwoliło to uniknąć stosując jeszcze gorsze rozwiązanie dla innej grupy.

Pogarsza się. Co jeśli masz 20,30 i 50 autobusów pasażerskich. Każdy z nich zużywa inną ilość paliwa, ale bardziej wydajne jest uruchomienie jednego 50, niż 20 i 30. Ale z naszego pojedynczego pomiaru (najmniejszej liczby pustych miejsc), sensownie jest uruchomić albo dla 50 wycieczka pasażerska.

Również autobusy o dziwnych liczbach, takie jak 28 lub 39, wypaczyłyby wiele naszych skrótów.

Tak więc, w zależności od złożoności sytuacji, możesz zrobić jedną z dwóch rzeczy:

Po pierwsze i wyczerpujące drzewo wyszukiwania: użyj każdej możliwej kombinacji autobusów. Jeśli masz tylko 3 lub 4 rozmiary autobusów, jest to prawdopodobnie rozsądne rozwiązanie. W przeciwnym razie obniżenie najlepszego dopasowania przyniosłoby rozsądne, ale nie optymalne wyniki.

Oto szybkie i brudne rozwiązanie w Pythonie:

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, [])

Po uruchomieniu otrzymuję:

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

Kod dokonuje dogłębnego przeszukiwania możliwych scenariuszy. Ponieważ kolejność nie ma znaczenia ( [30, 50]jest taka sama jak [50, 30]), możemy zmniejszyć przestrzeń wyszukiwania, dodając tylko autobusy tego samego rozmiaru lub większe. Dlatego add30()może dzwonić add50(), ale nie na odwrót.

Odpowiem na to z perspektywy klienta. Nie chciałbym mieć sztywnego algorytmu dla tej aplikacji. Istnieje zbyt wiele zmiennych, które można zmieniać w czasie. Chociaż nic w twoich autobusach nie może zmienić ciężaru czynników, może się zmienić lub odkryć nowe czynniki, o których nigdy nie myślałem (np. Nadgodziny, przepisy i inne koszty kierowcy).

Z tego powodu chciałbym móc stworzyć własną tabelę przeglądów na podstawie zakresu żądanej liczby pasażerów i stworzyć własne ustawienia dla najlepszych kombinacji autobusów. Przykład: 31–50 = 1 x 50, 51–60 = 2 x 30. Czy to naprawdę musi być obliczone? Łatwiejsza zmiana ustawień niż kilka formuł uwzględniających miejsca, paliwo i kierowców. Wymyśl najlepszą kombinację i zrób to, a użytkownik ma dużo miejsca na zmianę tych ustawień według własnego uznania.

Można odkryć nowe czynniki. Czy większe autobusy płacą wykładniczo wyższą stawkę za przejazd? Czy mogę dostać tańszych kierowców do małych autobusów, gdy nowe przepisy dotyczące dodatkowej certyfikacji i licencji będą obowiązywać kierowców autobusów powyżej 30 pasażerów?

Zatrudniają nowego konsultanta o innej logice niż ich formuła, a Twoja aplikacja może wymagać przepisania. Masz na myśli koszt parkingu?