Arxiv/Online Food Delivery to Minimize Maximum Flow Time 2021 2110.15772 — различия между версиями

«Online Food Delivery to Minimize Maximum Flow Time 2021 2110.15772»^{скачать}

«Мы изучаем распространенную проблему доставки, с которой сегодня сталкиваются в Интернете. платформы заказа еды: клиенты заказывают блюда онлайн, а в ресторане доставляет еду после получения заказа.

Конкретно изучаем проблему где k автомобили вместимостью c обслуживаем набор запросов на заказ еды из одного ресторана. После поступления заявки его может обслужить автомобиль. переезд из ресторана в место доставки. Мы заинтересованы в обслуживание всех запросов с минимизацией максимального времени потока, то есть максимального время, в течение которого покупатель ждет своей еды после подачи приказ.

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

Наш главный результат — это О(1) — конкурентный онлайн-алгоритм для некомпетентных (то есть c=∞) проблема доставки еды на древовидных метриках. Затем мы рассматриваем увеличение скорости модель.

Мы развиваем экспоненциальное время (1+ϵ) — скорость О(1/ϵ) — конкурентный алгоритм для любых ϵ>0.

Полиномиальное время алгоритм может быть получен с коэффициентом скорости α_{TSP}+ϵ или α_{CVRP}+ϵ, в зависимости от того, исправна ли проблема. Здесь α_{TSP}, а также α_{CVRP} являются коэффициентами наилучшего приближения для коммивояжер (TSP) и проблемы с маршрутизацией транспортного средства (CVRP) соответственно.

Дополняем результаты некоторыми отрицательными.…»