Блог

Давайте предположим, что доставка еды осуществляется для нескольких ресторанов (скажем, 20). Доступно (скажем, 10) драйверов. Далее, допустим, мы получаем 100 заказов в течение 4-часового периода для доставки еды из этих ресторанов на дом.

Таким образом, водители должны быть скоординированы, чтобы забирать еду в определенном месте и доставлять клиентам на дом.

Основная цель — минимизировать время доставки, то есть время между заказом и прибытием на дом. Вторичная цель — максимизировать пропускную способность водителя (т. Е. за наименьшее количество времени доставить все заказы).

Имейте в виду, что заказы поступают в течение четырехчасового периода, так что давайте скажем равномерно, то есть всего за 3 минуты. Кроме того, давайте предположим, что заказы распределяются случайным образом по 20 ресторанам.

Предположим, что я могу рассчитать время на дорогу из любого места в пункт назначения с точностью до секунды.

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

Ограничения таковы: 1) Должен забрать заказ через определенное время (т. Е. время приготовления блюда в ресторане) 2) Должен доставить заказ менее чем за 45 минут (в противном случае выдается предупреждение) 3) Должен заполнить время «x» минутами, чтобы учесть время, потраченное на то, чтобы дойти до магазина, забрать заказ и т.д. 4) Необходимо дополнить время «y» минутами, чтобы учесть время, затраченное на доставку заказа клиенту и получение оплаты. 5) У водителей есть только определенный набор способов оплаты (например, наличные, Visa, Amex, MasterCard). Мы должны сопоставить запрос клиента (наличные, visa и т.д.) С возможностями водителя (наличные, visa, amex и т.д.).

Так, например, если я получаю два заказа с близкими местами назначения и получения, даже если есть другой «Бесплатный» драйвер (ничего не делающий), было бы эффективнее использовать один и тот же драйвер для получения обоих заказов и доставки обоих заказов.

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

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

Это зависит от того, сколько времени у вас ушло на разработку самого алгоритма (не включая графический интерфейс, оповещения и все такое).

• Если вы говорите о 1 или 2 днях, используйте детерминированный алгоритм: поместите заказы в стек FIFO, затем итеративно возьмите следующий заказ и назначьте его первому доступному драйверу. Примерно так это делают люди. Это также не очень эффективно (особенно с 3 или более ресторанами).
• Если у вас есть больше времени (потому что вы обсуждаете эту проблему для большой компании), тогда начинается самое интересное. Ознакомьтесь с метаэвристикой (поиск по табу, генетические алгоритмы, имитация отжига). Взгляните на существующие библиотеки, которые сделают большую часть работы за вас. Например, если вы работаете на Java, взгляните на Drools Planner.

Кстати: если вы думаете о грубом форсировании этого. Не беспокойтесь: он не будет масштабироваться.