Эффективная загрузка шины

Это то, что я сделал для автобусной туристической компании давным-давно, и я никогда не был доволен результатами. Недавно я думал об этом старом проекте и решил вернуться к этой проблеме.

Проблема:

Компания Bus Travel имеет несколько автобусов с различной вместимостью пассажиров (например, 15 автобусов на 50 пассажиров, 25 автобусов на 30 пассажиров и т. Д.). Они специализировались на предложении перевозки для очень больших групп (более 300 пассажиров на группу). Поскольку каждая группа должна путешествовать вместе, им необходимо эффективно управлять своим парком, чтобы сократить количество отходов.

Например, 88 пассажиров лучше обслуживают три автобуса с 30 пассажирами (2 свободных места), чем два автобуса с 50 пассажирами (12 свободных мест). Другой пример: 75 пассажиров лучше обслуживать одним автобусом на 50 пассажиров и одним автобусом на 30 пассажиров, что является смесью типов.

Какой хороший алгоритм для этого?

Это (своего рода) пример проблемы упаковки бункера, который часто путают с проблемой ранца. В упаковке бункеров у вас есть бункеры определенной емкости, и вы пытаетесь распределить объекты различных размеров в бункеры. Идея состоит в том, чтобы использовать минимально возможное количество ячеек.

Вы не пытаетесь свести к минимуму количество корзин, но вы пытаетесь минимизировать количество свободных мест. И возможно, что вы пытаетесь свести к минимуму количество свободных мест по всему флоту, то есть у вас есть четыре туристические группы разных размеров, и вы хотите разместить все из них с наименьшим количеством свободных мест. Я не могу вспомнить случай с самого начала, но я думаю, что можно было бы построить флот и набор туристических групп таким образом, чтобы вам было лучше с некачественным решением для какой-то группы, потому что это позволило вам избежать используя еще худшее решение для какой-то другой группы.

Становится хуже. Что делать, если у вас есть 20,30 и 50 пассажирских автобусов. Каждый из них использует разное количество топлива, но более эффективно пробежать один 50, чем 20 и 30. Но по нашему единственному показателю (наименьшее количество свободных мест) имеет смысл пробежать либо за 50 пассажирский тур.

Кроме того, автобусы со странными номерами, такими как 28 или 39, могут исказить многие из наших ярлыков.

Таким образом, в зависимости от сложности ситуации, вы можете сделать одну из двух вещей:

Первое и исчерпывающее дерево поиска: используйте всевозможные комбинации автобусов. Если у вас только 3 или 4 размера шины, это, вероятно, разумное решение. В противном случае что-то вроде уменьшения наилучшего соответствия дало бы разумные, но не оптимальные результаты.

Вот быстрое и грязное решение в 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, [])

Когда я запускаю его, я получаю:

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

Код выполняет поиск в глубину по возможным сценариям. Поскольку порядок не имеет значения (так [30, 50]же, как [50, 30]), мы можем сделать пространство поиска намного меньше, добавив только шины одинакового размера или большего размера. Вот почему add30()можно звонить add50(), а не наоборот.

Я собираюсь ответить на это с точки зрения клиента. Я не хотел бы жестко закодированный алгоритм для этого приложения. Слишком много переменных, которые могут меняться со временем. Хотя ничто в ваших автобусах не может изменить вес факторов, может измениться, или могут быть обнаружены новые факторы, о которых я никогда не задумывался (например, сверхурочные, законы и другие расходы водителя).

Из-за этого я хотел бы иметь возможность создавать свою собственную справочную таблицу на основе диапазона числа запрошенных пассажиров, и я бы создал свои собственные настройки для лучших автобусных комбинаций. Пример: 31-50 = 1 х 50, 51-60 = 2 х 30. Это действительно нужно рассчитать? Проще изменить настройки, чем кучу формул с учетом сидений, газа и водителей. Определите лучшую комбинацию и покончите с этим, и у пользователя будет достаточно места для изменения этих настроек по своему усмотрению.

Новые факторы могут быть обнаружены. Платят ли большие автобусы экспоненциально более высокую ставку за проезд? Могу ли я получить менее дорогие водители для небольших автобусов, когда новый закон о дополнительной сертификации и лицензировании вступит в силу для водителей автобусов старше 30 пассажиров?

Они нанимают нового консультанта с другой логикой, и ваше приложение, возможно, придется переписать. Вы имеете в виду, что вы должны учитывать стоимость парковки?