|
|
Семинар отдела математического программирования
12 апреля 2019 г. 11:00–12:00, г. Екатеринбург, Институт математики и механики им. Н. Н. Красовского УрО РАН, ул. Софьи Ковалевской 16,
актовый зал
|
|
|
|
|
|
Аппроксимационная схема для задачи маршрутизации транспорта с ограничениями на грузоподъёмность и временные промежутки обслуживания и неединичным спросом
Ю. Ю. Огородников Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
|
Количество просмотров: |
Эта страница: | 104 |
|
Аннотация:
Задача маршрутизации транспорта с временными окнами (CVRPTW) является широко извстной задачей комбинаторной оптимизации имеющей огромное число приложений в исследовании операций. В отличие от классической постановки задачи CVRP, которая не учитывает временные промежутки обслуживания, аппроксимационные алгоритмы с гарантированными оценками точности для задачи CVRPTW до сих пор мало изучены, даже для случая евклидовой плоскости. В данной работе мы предлагаем, возможно, первую аппроксимационную схему для постановки задачи CVRPTWна плоскости с неединичным делимым спросом, сочетая хорошо известную схему декомпозиции задачи, разработанную A.Adamaszeketel., и квазиполиномиальную приближённую аппроксимационную схему (QPTAS), предложенную L.Songetal. Предложенная нами схема для любогоε∈(0,1)находит (1+ε)-приближённое решение задачи за полиномиальное время при условии, что трудоёмкость qи число временных промежутков обслуживания pне превосходит 2^(〖log〗^δ n)для некоторого δ=O(ε). Также, данная схема является эффективной полиномиальной (EPTAS) для любых фиксированных значений параметров pи qс субквадратичной трудоёмкостью.
|
|