Просмотр исходного текста страницы Arxiv/Online Food Delivery to Minimize Maximum Flow Time 2021 2110.15772

{{checked|}}
{{arxivlink|arxiv/Online Food Delivery to Minimize Maximum Flow Time 2021 2110.15772|2=
Мы изучаем распространенную проблему доставки, с которой сегодня сталкиваются в Интернете. платформы заказа еды: клиенты заказывают блюда онлайн, а в ресторане доставляет еду после получения заказа.

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

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

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

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

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

Дополняем результаты некоторыми отрицательными.
}}
{{enddiv}}

[[Категория:ArxivArticles]]