|
|
Семинар отдела управляемых систем
18 декабря 2014 г., г. Екатеринбург, ул. С. Ковалевской, 16, комн. 322
|
|
|
|
|
|
Модель «неаддитивной» задачи маршрутизации с функциями стоимости,
зависящими от списка заданий
А. Г. Ченцов, Я. В. Салий |
Количество просмотров: |
Эта страница: | 276 |
|
Аннотация:
Рассматривается следующий (усложненный) вариант маршрутной задачи “на узкие места”: исследуется задача последовательного обхода мегаполисов, осложненная условиями предшествования и тем, что функции стоимости (перемещений и внутренних работ) могут явным образом зависеть от списка заданий, которые не выполнены на данный момент. Процесс перемещений рассматривается в виде совокупности этапов, включающих внешнее перемещение к соответствующему мегаполису и последующее выполнение (внутренних по смыслу) работ, связанных с данным мегаполисом. Качество совокупного процесса оценивается максимумом стоимостей составляющих его этапов; рассматривается задача на минимум упомянутого критерия (получается задача на минимакс, обычно именуемая задачей “на узкие места”). Для построения оптимального решения в виде пары маршрут-трасса (трасса, или траектория, соответствует конкретному варианту прохождения мегаполисов, нумеруемых в соответствии с маршрутом, определяемым в виде перестановки индексов) построен “нестандартный” вариант метода динамического программирования, при реализации которого не используется, в случае ограничений в виде условий предшествования, построение всего массива значений функции Беллмана.
|
|