RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2012, выпуск 1, страницы 96–119 (Mi vuu313)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

МАТЕМАТИКА

Об одной задаче маршрутизации с внутренними работами

И. Б. Чеблоковa, А. Г. Ченцовb

a Кафедра вычислительных методов и уравнений математической физики, Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, Россия, г. Екатеринбург
b Отдел управляемых систем, Институт математики и механики УрО РАН, Россия, г. Екатеринбург

Аннотация: Рассматривается маршрутная задача о посещении сечений мультифункций с ограничениями в виде условий предшествования. Кроме того, по постановке предусматривается выполнение некоторых “работ” на упомянутых сечениях. Каждое решение определяется в виде упорядоченной пары, компоненты которой имеют смысл маршрута (перестановки индексов) и трассы (траектории) перемещений по сечениям мультифункций. Согласование трассы и маршрута реализуется на основе процедур последовательного выбора упорядоченных пар (пунктов прибытия и отправления) из декартовых “квадратов” сечений мультифункций, занумерованных в соответствии с маршрутом. Агрегирование стоимостей предполагается аддитивным; совокупный критерий включает стоимости (внешних) перемещений между сечениями мультифункций, внутренних “работ” и финального состояния. При построении расширения основной задачи, порождающего используемую далее функцию Беллмана, применяется эквивалентное преобразование ограничений: допустимость маршрутов по предшествованию заменяется допустимостью по вычеркиванию (заданий из списка), что соответствует варианту ограничений на текущие перемещения с одного множества на другое. Получен аналог уравнения Беллмана в виде процедуры преобразования слоёв функции Беллмана. Операция, определяющая данное преобразование, используется далее для построения эвристических алгоритмов, реализованных на ПЭВМ.

Ключевые слова: маршрут, перестановка, трасса, функция Беллмана.

Полный текст: PDF файл (300 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 517.977
MSC: 76D55, 90C27
Поступила в редакцию: 09.02.2011

Образец цитирования: И. Б. Чеблоков, А. Г. Ченцов, “Об одной задаче маршрутизации с внутренними работами”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2012, № 1, 96–119

Цитирование в формате AMSBIB
\RBibitem{CheChe12}
\by И.~Б.~Чеблоков, А.~Г.~Ченцов
\paper Об одной задаче маршрутизации с~внутренними работами
\jour Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки
\yr 2012
\issue 1
\pages 96--119
\mathnet{http://mi.mathnet.ru/vuu313}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vuu313
  • http://mi.mathnet.ru/rus/vuu/y2012/i1/p96

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Цикл статей

    Эта публикация цитируется в следующих статьяx:
    1. A. G. Chentsov, Ya. V. Salii, “A model of “nonadditive” routing problem where the costs depend on the set of pending tasks”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 8:1 (2015), 24–45  mathnet  crossref  elib
    2. М. С. Кошелева, А. А. Ченцов, А. Г. Ченцов, “О задаче маршрутизации с ограничениями, включающими зависимость от списка заданий”, Тр. ИММ УрО РАН, 21, № 4, 2015, 178–195  mathnet  mathscinet  elib
    3. А. Г. Ченцов, А. А. Ченцов, “Маршрутизация перемещений при динамических ограничениях: задача “на узкие места””, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 26:1 (2016), 121–140  mathnet  crossref  mathscinet  elib
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Просмотров:
    Эта страница:193
    Полный текст:70
    Литература:26
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020