Arxiv/Capacitated Vehicle Routing with Target Geometric Constraints 2021 2107.10382
Мы исследуем проблему маршрутизации емкостных транспортных средств (CVRP) под в контексте робототехники, где должна быть завершена доставка автомобиля с ограниченной полезной нагрузкой (или самовывоз) задач для обслуживания группы географически распределенных клиентов с различные требования.
В классической CVRP местоположение клиента моделируется как точка. Однако во многих приложениях робототехники более целесообразно моделировать такие «местоположения клиентов» как 2D-регионы.
Например, при воздушной доставке дрон может уронить посылку в любом месте на стоянке клиента. Это приводит к проблеме CVRG (Маршрутизация емкостного транспортного средства с целевыми геометрическими ограничениями). С вычислительной точки зрения CVRP уже сильно NP-труден; CVRG поэтому больше испытывающий. Тем не менее, мы разрабатываем быстрые алгоритмы для CVRG, способные Вычислительные решения высокого качества для сотен регионов.
Наши алгоритмические решение гарантированно будет оптимальным, когда клиентские регионы выпуклые. Численные оценки показывают, что предложенные нами методы значительно превосходят по эффективности. жадные подходы по принципу «лучший первым». Всесторонние исследования моделирования подтверждают эффективность наших методов.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.