Задачи маршрутизации транспортных средств для доставки дронами

Беспилотные летательные аппараты (дроны) обладают потенциалом значительного сокращения затрат и времени при доставке на «последней миле» и в реагировании на чрезвычайные ситуации. Несмотря на это, мало работ посвящено разработке задач маршрутизации транспортных средств (VRP) конкретно для сценариев доставки дронами. Существующие VRP недостаточны для планирования доставки дронами: либо не допускаются многократные рейсы к депо, что приводит к решениям с избыточным числом дронов, либо не учитывается влияние веса батареи и полезной нагрузки на энергопотребление, что приводит к дорогим или невыполнимым маршрутам. Мы предлагаем две многорейсовые VRP для доставки дронами, которые решают обе эти проблемы. Одна формулировка минимизирует затраты при заданном ограничении по времени доставки, другая минимизирует общее время доставки при заданном бюджете. Мы математически выводим и экспериментально валидируем модель энергопотребления для мультикоптеров, показывая, что энергопотребление приблизительно линейно зависит от веса полезной нагрузки и батареи. Мы используем это приближение для вывода целочисленных линейных программ для наших VRP. Мы предлагаем функцию затрат, учитывающую нашу модель энергопотребления и повторное использование дронов, и применяем её в эвристике имитации отжига (simulated annealing, SA) для поиска субоптимальных решений в практических сценариях. Чтобы помочь практикам доставки дронами балансировать затраты и время доставки, эвристика SA демонстрирует, что минимальные затраты имеют обратную экспоненциальную зависимость от предела времени доставки, а минимальное общее время доставки имеет обратную экспоненциальную зависимость от бюджета. Численные результаты подтверждают важность повторного использования дронов и оптимизации размера батареи в VRP для доставки дронами.