Справка по алгоритму проблем с доставкой и доставкой

Question

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

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

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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