Arxiv/Online Food Delivery to Minimize Maximum Flow Time 2021 2110.15772
Конкретно изучаем проблему где k автомобили вместимостью c обслуживаем набор запросов на заказ еды из одного ресторана. После поступления заявки его может обслужить автомобиль. переезд из ресторана в место доставки. Мы заинтересованы в обслуживание всех запросов с минимизацией максимального времени потока, то есть максимального время, в течение которого покупатель ждет своей еды после подачи приказ.
Мы показываем, что проблема сложна как в офлайн, так и в онлайн-настройках: Там это жесткость приближения Ω(п) для автономной проблемы и нижняя граница Ω(п) о конкурентоспособности любого онлайн-алгоритма, где п количество точек в метрике.
Наш главный результат — это О(1) — конкурентный онлайн-алгоритм для некомпетентных (то есть c=∞) проблема доставки еды на древовидных метриках. Затем мы рассматриваем увеличение скорости модель.
Мы развиваем экспоненциальное время (1+ϵ) — скорость О(1/ϵ) — конкурентный алгоритм для любых ϵ>0.
Полиномиальное время алгоритм может быть получен с коэффициентом скорости α_{TSP}+ϵ или α_{CVRP}+ϵ, в зависимости от того, исправна ли проблема. Здесь α_{TSP}, а также α_{CVRP} являются коэффициентами наилучшего приближения для коммивояжер (TSP) и проблемы с маршрутизацией транспортного средства (CVRP) соответственно.
Дополняем результаты некоторыми отрицательными.…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.