Гибридные алгоритмы локального поиска для задач маршрутизации транспортных средств с многократным посещением клиентов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Кулаченко Игорь Николаевич

• Кулаченко Игорь Николаевич
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Кулаченко Игорь Николаевич

1.2.3 Интенсификация поиска

1.2.4 Диверсификация поиска

1.2.5 Постоптимизация

1.3 Метод декомпозиции для примеров большой размерности

1.3.1 Описание метода

1.4 Численные эксперименты

1.4.1 Исходные данные

1.4.2 Примеры результатов

1.4.3 Особенности реализации алгоритма

1.4.4 Влияние ограничения на грузоподъемность

1.4.5 Сравнение с точным методом

1.4.6 Сравнение с альтернативной реализацией схемы

1.4.7 Сравнение с метаэвристическим решателем

1.4.8 Сравнение методов декомпозиции на примерах большой размерности

2 Матэвристика для решения задачи маршрутизации буровых установок

2.1 Постановка задачи и математическая модель

2.1.1 Математическая модель для распределительной задачи

2.2 Матэвристика на основе локального поиска

2.2.1 Окрестности

2.2.2 Построение начального решения

2.2.3 Общий поиск с чередующимися окрестностями

2.3 Численные эксперименты

2.3.1 Тестовые примеры

2.3.2 Настройка параметров

2.3.3 Сравнение с точным методом

2.3.4 Сравнение различных схем

3 Пороговая робастность для задачи маршрутизации буровых

установок

3.1 Постановка задачи и математическая модель

3.1.1 Модель смешанного целочисленного квадратичного программирования

3.1.2 Линеаризация

3.2 Оптимизационная схема

3.2.1 Представление решения

3.2.2 Вычисление целевой функции

3.2.3 Алгоритм адаптивного поиска по большим окрестностям

3.2.4 Операторы разрушения

3.2.5 Операторы восстановления

3.2.6 Критерий принятия решения

3.2.7 Адаптивный механизм

3.3 Численные эксперименты

3.3.1 Важность используемых операторов

3.3.2 Примеры малого размера

3.3.3 Анализ чувствительности

3.3.4 Примеры среднего размера

3.3.5 Примеры большого размера

Заключение

Список литературы

Приложение А Свидетельства о государственной регистрации

программ для ЭВМ

Введение диссертации (часть автореферата) на тему «Гибридные алгоритмы локального поиска для задач маршрутизации транспортных средств с многократным посещением клиентов»

Введение

Актуальность темы1. Транспортная логистика играет ключевую роль в экономике. Оптимизация маршрутов востребована не только в производстве и дистрибуции, где расходы на перевозки достигают 20-30 % от совокупных затрат, но и в других сферах, требующих планирования перемещений ресурсов, персонала или оборудования. В последние годы объёмы коммерческих автомобильных перевозок стабильно растут благодаря развитию торговли, усложнению логистических цепочек и усилению конкуренции. Это повышает требования к поставщикам транспортных услуг, делая оптимизацию перевозок важным инструментом сокращения затрат и повышения конкурентоспособности. Однако в задачах маршрутизации помимо минимизации издержек могут преследоваться и другие цели, например, повышение устойчивости решений к неопределённостям входных данных или построение допустимого расписания в условиях жёстких ограничений. Необходимость решать широкий спектр задач маршрутизации делает разработку для них эффективных алгоритмов актуальной для множества практических приложений.

Задачи маршрутизации транспортных средств являются важной частью исследований в области комбинаторной оптимизации. Их основная цель заключается в построении оптимального плана маршрутов для автопарка с учётом различных ограничений, таких как грузоподъёмность, временные окна и требования клиентов. Впервые классическая постановка задачи маршрутизации транспортных средств была сформулирована Данцигом и Рамсером в 1959 году и с тех пор эта задача остаётся предметом активных исследований. С развитием логистических процессов задачи маршрутизации приобрели всё большую сложность, что связано с увеличением масштабов перевозок и необходимостью учитывать дополнительные факторы, возникающие в реальных условиях. Совре-

1 Работа поддержана грантами РФФИ №19-47-540005 и РНФ №21-41-09017, программой ФНИ СО РАН №1.5.1 (проект №0314-2019-0014) и Математическим центром в Академгородке (соглашение №075-2019-1613).

менные исследования сосредоточены на расширении классической постановки задачи за счёт таких аспектов, как раздельные поставки, многоскладская логистика и динамическое изменение параметров задачи. Существенный вклад в развитие данной области внесли P. Toth, G. Laporte, M. Gendreau, D. Vigo, T. Vidal, Y. Nagata, C. Archetti, а также российские учёные — Э. Х. Гимади, Е. М. Бронштейн, М. В. Бацын, М. Ю. Хачай, А. Г. Ченцов, А. И. Ерзин.

В данной работе рассматриваются различные задачи маршрутизации транспортных средств, возникающие в прикладных логистических сценариях и предложенные индустриальными партнерами. Эти задачи учитывают практические ограничения, включая согласованность визитов клиентов в течение горизонта планирования, наличие нескольких депо, временные ограничения и возможность совместного обслуживания клиентов. Сложность рассматриваемых задач обусловлена их NP-трудностью, что ограничивает возможность применения точных методов для решения практических примеров. В таких условиях метаэвристические подходы, в частности методы локального поиска, являются эффективным инструментом для получения качественных приближённых решений за разумное время. Перспективным направлением остаётся разработка гибридных алгоритмов, комбинирующих локальный поиск с методами декомпозиции и математического программирования для повышения качества решений. Реальные сценарии осложняются неопределённостями входных данных, что делает актуальным применение подходов робастной оптимизации.

Цель данной работы заключается в разработке эффективных алгоритмов локального поиска, учитывающих практические ограничения реальных задач маршрутизации, включая периодичность и согласованность визитов клиентов, наличие нескольких депо, временные окна и совместное обслуживание. Особое внимание уделяется созданию методов, способных находить приближённые решения с малой погрешностью для задач высокой размерности, а также учитывать неопределённость входных данных.

Методика исследований. В диссертации применяются современные

методы комбинаторной оптимизации, включая использование математического программирования, анализ алгоритмов локального поиска и вычислительной сложности, а также проведение экспериментальных исследований. В рамках работы используются элементы робастной оптимизации для учета неопределённости исходных данных. Для оценки эффективности предложенных алгоритмов применяются вычислительные технологии и комплексы программ.

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем:

1. Для нового варианта периодической задачи маршрутизации транспортных средств с условиями согласованности визитов составлена модель смешанного целочисленного линейного программирования, учитывающая требования к равномерности интервалов между визитами и согласованности транспортных средств.

2. Сформулирована оригинальная постановка задачи маршрутизации мобильных буровых установок, в которой совместное обслуживание объектов обусловлено временными ограничениями, а не грузоподъемностью. Выделена и формализована подзадача в виде модели смешанного целочисленного линейного программирования. Доказано, что эта подзадача является КР-трудной. Для задачи предложен матэвристический алгоритм, интегрирующий точное решение подзадачи в схему локального поиска с чередующимися окрестностями.

3. Впервые в задачах маршрутизации транспортных средств применён подход пороговой робастности. Предложена модель смешанного целочисленного линейного программирования для робастной постановки задачи маршрутизации буровых установок. Введена комбинированная целевая функция, учитывающая различные показатели устойчивости, и предложен алгоритм для её вычисления. В рамках анализа чувствительности изучено влияние параметров задачи на оптимальные значения устойчивости.

4. Разработаны программные комплексы, реализующие предложенные методы и алгоритмы на языке С++, обеспечивающие решение задач с числом клиентов до 900, что подтверждено экспериментальными исследованиями на данных, основанных на реальных сценариях.

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Исследованы свойства различных задач маршрутизации, модифицированы известные и построены новые математические модели, разработаны численные методы решения. Разработанные методы реализованы в виде комплекса программ. Они показали свою эффективность и могут применяться при решении практических задач большой размерности. Основные положения, выносимые на защиту.

1. Для задачи маршрутизации транспортных средств с условиями согласованности визитов предложен гибридный алгоритм локального поиска с чередующимися окрестностями, сочетающий рандомизированный поиск с запретами, интенсификацию, диверсификацию, адаптивные штрафы и схему декомпозиции, что приводит к значительному сокращению погрешности по сравнению с базовой схемой.

2. Для задачи маршрутизации буровых установок предложен матэвристиче-ский алгоритм, интегрирующий точное решение выделенной КР-трудной подзадачи в схему локального поиска.

3. Впервые в задачах маршрутизации транспортных средств применён подход пороговой робастности, рассмотренный на примере маршрутизации буровых установок. Разработан алгоритм пересчёта комбинированной целевой функции с учётом различных показателей устойчивости. Представлен метод адаптивного поиска по большим окрестностям, обеспечивающий стабильное нахождение оптимальных решений для задач малой и средней размерности. Проведён анализ чувствительности, исследующий влияние

параметров задачи на оптимальные значения устойчивости и эффективность алгоритма.

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

1. Международная конференция «Проблемы оптимизации и их приложения», OPTA, Омск, Россия, июль 2018 г.;

2. Международная конференция «Manufacturing Modelling, Management and Control», MIM, Берлин, Германия, август 2019 г.;

3. Международная конференция «Mathematical Optimization Theory and Operations Research», MOTOR, Новосибирск, Россия, июль 2020 г.;

4. Международная конференция по локальному поиску с чередующимися окрестностями ICVNS, Абу-Даби, ОАЭ, октябрь 2020 г.;

5. Международная летняя школа-семинар MESS, Катания, Италия, июнь 2021 г.;

6. Международная конференция «Mathematical Optimization Theory and Operations Research», MOTOR, Иркутск, Россия, июль 2021 г.;

7. Международная конференция по вычислительной логистике ICCL, Энсхе-де, Нидерланды, сентябрь 2021 г.;

8. Международная конференция «Mathematical Optimization Theory and Operations Research», MOTOR, Петрозаводск, Россия, июль 2022 г.;

9. Международная конференция «Mathematical Optimization Theory and Operations Research», MOTOR, Екатеринбург, Россия, июль 2023 г.;

10. Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», OPCS, Новосибирск, Россия, август 2023 г.

Результаты неоднократно докладывались на научных семинарах Института математики им. С. Л. Соболева СО РАН, Омского филиала данного института и Института вычислительной математики и математической геофизики СО РАН.

Личный вклад. Вклад соискателя включает постановку и формализацию задач, доказательство теоретических результатов, разработку и реализацию алгоритмов, планирование, проведение и интерпретацию результатов вычислительных экспериментов. Все программные комплексы, исходный код и материалы вычислительных экспериментов созданы соискателем. Уточнение исходной постановки задачи из главы 1 выполнено при участии А. А. Курочкина. Формулировки математических моделей и направления совершенствования алгоритмов локального поиска обсуждались с Ю. А. Кочетовым. Научный руководитель П. А. Кононова обеспечивала научное сопровождение: формирование стратегии, рекомендации по моделям и алгоритмам, обсуждение результатов и редактура текста.

Публикации. По теме диссертации автором:

- Опубликовано 7 статей в реферируемых журналах из списка ВАК [101-107]. Все публикации индексируются в базе Scopus, а некоторые из них также входят в состав Web of Science. В частности, статья [106] опубликована в журнале первого квартиля (Q1) по версии Scopus и Web of Science.

- Получено 2 свидетельства о государственной регистрации программ для ЭВМ № 2021617091 и № 2022681063, выданные Федеральной службой по интеллектуальной собственности [108, 109].

Объём и структура диссертации. Диссертация состоит из введения, трёх глав, заключения, списка литературы (109 наименований) и приложения. Объём диссертации — 127 страниц. Благодарности.

Автор искренне благодарит своего научного руководителя, Кононову Полину Александровну, за поддержку, наставничество и ценные советы, которые

помогли в реализации данной работы. Особая признательность выражается Ко-четову Юрию Андреевичу за полезные обсуждения, конструктивные замечания и неоценимую помощь в научной деятельности. Автор также признателен коллективу лаборатории «Математические модели принятия решений» ИМ СО РАН за теплую и продуктивную атмосферу и содействие в реализации научных идей.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Глава 1 рассматривает новую постановку периодической задачи маршрутизации транспортных средств с условиями согласованности визитов, возникшую благодаря заинтересованности одной транспортной компании. В данной задаче каждый клиент обслуживается одним и тем же транспортным средством на протяжении всего планового периода, а дни посещений выбираются гибко при соблюдении равномерных интервалов между визитами. Разработана математическая модель смешанного целочисленного линейного программирования, учитывающая требования к периодичности обслуживания и закреплению клиентов за транспортными средствами. Для решения задачи предложен гибридный алгоритм локального поиска с чередующимися окрестностями, включающий рандомизированный поиск с запретами, механизмы интенсификации и диверсификации, а также метод адаптивного изменения штрафных коэффициентов. Алгоритм использует девять типов окрестностей, включая модификации Кернигана-Лина и специализированные перемещения, минимизирующие нарушения ограничений. В ходе тестирования исследованы стратегии изменения штрафов и влияние различных окрестностей, что позволило определить ключевые механизмы, обеспечивающие наилучшие результаты. Для эффективного решения примеров большой размерности адаптирована схема декомпозиции, основанная на методе РОРМи81С, с исследованием декомпозиции на основе маршрутов и на основе расположения клиентов. Проведено детальное сравнение с СигоЫ, Ьоеа18о1уег и базовой версией алгоритма. Эксперименты на данных с числом клиентов до 900 показали, что предложенный метод превосходит базовую схему в среднем на 2%,

а применение декомпозиции обеспечило дополнительное улучшение качества решений на 4 %.

Глава 2 посвящена оригинальной постановке задачи маршрутизации, возникающей при планировании буровых работ, необходимых для газо- и нефтедобывающей промышленности. В этой задаче присутствует необходимость в совместном обслуживании объектов, связанная с временными ограничениями. Для решения данной задачи разработан матэвристический подход, объединяющий метод поиска с чередующимися окрестностями и математическое программирование. В рамках локального поиска применяется набор специализированных окрестностей, позволяющих изменять распределения работ на объектах и эффективно оценивать нарушения временных окон в построенных маршрутах. Кроме того, выделена и формализована подзадача в виде модели смешанного целочисленного линейного программирования, для которой доказана КР-трудность. Проведена настройка гиперпараметров предложенной схемы. Экспериментальные результаты показали, что интеграция точного решения подзадачи в общий процесс локального поиска существенно улучшает итоговые результаты, а постоптимизация на основе математической модели позволяет улучшать качество построенных маршрутов при использовании эвристически найденных решений в качестве начальной точки.

Глава 3 посвящена исследованию методов робастной оптимизации в задаче маршрутизации мобильных буровых установок с учетом факторов неопределённостей, связанных с увеличением времени бурения (например, из-за неблагоприятных условий). В качестве подхода для решения рассматриваемой задачи выбрана концепция пороговой робастности, впервые применённая в задачах маршрутизации транспортных средств. В данном подходе максимизируется устойчивость решения при условии, что суммарное время перемещений не превышает заданного порогового значения. Отличительной чертой выбранного подхода также является использование множителя для увеличения всех времён

бурения, а не абсолютной разницы между ожидаемыми и фактическими значениями. Это важно, поскольку позволяет адаптировать запас устойчивости к масштабу неопределённости: при увеличении времён бурения возрастают и потенциальные отклонения, требующие дополнительного временного резерва. Для поставленной цели разработана модель смешанного целочисленного линейного программирования, в которой целевая функция декомпозируется на несколько компонентов, отражающих различные показатели устойчивости решения. На основе этой модели предложен алгоритм, обеспечивающий эффективный пересчёт комбинированной целевой функции, а также разработан метод решения задачи, основанный на адаптивном поиске по большим окрестностям. В работе подробно описаны операторы разрушения, работающие на уровне маршрутов, клиентов и отдельных посещений, и операторы восстановления, учитывающие возможность перераспределения работ между установками. Проведён анализ зависимости качества решений от числа используемых операторов, что позволило установить, что оптимальным является выбор пяти из двенадцати операторов, что, в свою очередь, значительно упрощает настройку алгоритма за счёт сокращения числа управляющих параметров. Также выполнен анализ чувствительности параметров задачи, демонстрирующий их влияние на итоговую устойчивость решений и результаты алгоритма. Показано, что алгоритм находит (суб)оптимальные решения в подавляющем большинстве случаев для примеров малой и средней размерности.

В заключении сформулированы основные выводы, обобщающие полученные научные результаты.

В приложении А приведены копии и описания свидетельств о государственной регистрации программ для ЭВМ.

1 Гибридный алгоритм локального поиска для периодической задачи маршрутизации транспортных средств с условиями согласованности визитов

Класс задач, занимающихся оптимизацией маршрутов, называют задачами маршрутизации транспортных средств (англ. Vehicle Routing Problem, VRP). В классическом варианте VRP имеется неограниченный парк идентичных транспортных средств (ТС) и конечное множество клиентов. Цель задачи — построить набор маршрутов для ТС так, чтобы все клиенты были обслужены, а суммарное время, затраченное на перемещение, было минимальным. При этом рабочий день ТС начинается и заканчивается в депо. Известно, что VRP является NP-трудной, поскольку задача коммивояжера является ее частным случаем. Предложено множество обобщений этой модели. Одним из естественных уточнений является ограниченная грузоподъемность ТС, так называемая Capacitated VRP или CVRP. Если ТС находятся не в одном депо, а в нескольких, то задачу называют Multiple Depot VRP или MDVRP [1].

Другое важное обобщение задачи появляется с введением конечного планового периода для обслуживания клиентов [2-4]. Задана частота обслуживания каждого клиента или даже дни его обслуживания. В постановке Periodic VRP или PVRP необходимо построить набор маршрутов транспортных средств для каждого дня планового периода. Дальнейшее развитие этой модели связано с желанием логистической компании получить дополнительные конкурентные преимущества. С этой целью вводятся два новых требования к маршрутам транспортных средств. Во-первых, клиент должен обслуживаться одним и тем же транспортным средством на протяжении всего планового периода, что упрощает общение поставщика и клиента. Во-вторых, обслуживание должно проводиться

примерно в одно и то же время, чтобы клиент мог к нему подготовиться заранее. Такую модель в англоязычной литературе принято называть Сопв1в1еп УИР или СопУИР [5, 6].

В настоящей работе рассматривается новая задача типа СопУИР, которая возникла в результате сотрудничества с одной из российских логистических компаний. Компания владеет набором ТС различной грузоподъемности. Каждое ТС базируется в своем депо. Известно множество клиентов. Каждый клиент имеет свою частоту посещения и обслуживается одним и тем же ТС. Частота посещения задается на весь плановый период, при этом интервалы между посещениями должны быть одинаковыми (раз в неделю по понедельникам, раз в две недели и т.п.). Время посещения может быть любым в рамках рабочей смены, т.е. порядок посещения клиентов внутри рабочего дня может быть произвольным. Требуется построить такое расписание обслуживания клиентов и набор маршрутов ТС для каждого дня планового периода, чтобы суммарное пройденное расстояние было минимальным и выполнялись условия на частоту посещения клиентов, грузоподъемность ТС и длину рабочей смены. В [5, 7-11] рассматривались близкие задачи. В [5, 7, 8] клиенты должны посещаться только одним ТС примерно в одно и то же время, но дни посещения фиксированы и условия на их согласованность могут не соблюдаться. Статья [9], опубликованная после проведения исследований, представленных в этой главе, содержит формулировку задачи, схожую с рассматриваемой, но дополненную возможностью для каждого клиента обслуживать продукты нескольких типов, для каждого из которых задаётся своя частота посещения. В работах [10, 11] для задачи, описанной в [5], предложена модификация, которая, в отличие от других подходов, учитывает неопределённости времени обслуживания, переезда и спроса клиентов.

Поскольку РУИР является КР-трудной [12], то и ее расширение, СопУИР, относится к классу КР-трудных. Так как точные методы часто оказываются непрактичными для таких задач из-за высокой вычислительной сложности, популярным подходом является использование метаэвристических алгоритмов,

способных эффективно находить качественные приближённые решения. Для алгоритма локального поиска с чередующимися окрестностями [4, 8, 13-15] разработаны 9 окрестностей, учитывающие частоту посещения клиентов и интервалы между их посещениями. Эти окрестности включают в себя четыре большие окрестности Кернигана-Лина [16, 17]. Ограничения на длительность рабочей смены и грузоподъемность ТС заносятся в целевую функцию со штрафом. Такой подход позволяет расширить область поиска и выходить за границы допустимой области [18]. Величина штрафа меняется в ходе поиска в зависимости от величины нарушений соответствующих ограничений. Процедуры интенсификации и диверсификации применяются для повышения эффективности алгоритма. Алгоритм тестировался на реальных исходных данных и показал высокую эффективность. В разработанном алгоритме также применяются стратегии интенсификации и диверсификации поиска. Для повышения эффективности алгоритма на примерах большой размерности предложен метод декомпозиции, который разбивает задачу на подзадачи, оптимизирует их и интегрирует в единое решение.

Структура главы следующая. В разделе 1.1 представлена математическая модель. Раздел 1.2 посвящён описанию гибридной схемы У^. Метод декомпозиции рассмотрен в разделе 1.3. В разделе 1.4 обсуждаются результаты вычислительных экспериментов на примерах, основанных на реальных данных.

1.1 Постановка задачи и математическая модель

Рассмотрим полный ориентированный граф С = (V., А) с множеством вершин V и множеством дуг А. Для каждой дуги (\) € А известна ее длина и время на передвижение . Множество V = М и I является объединением множеств депо М и мест расположения клиентов I. Число клиентов обозначим через п = \11. В каждом депо т € М имеется определенное количество транспортных средств различной грузоподъемности. Конечное множество К

задает все множество ТС. Для каждого к € К известна грузоподъемность Vк и депо т(к), в котором находится ТС. Ежедневно каждое ТС выезжает из депо в момент времени 0 и должно вернуться в него до времени Т. Предполагается, что в течение одного дня ТС не могут несколько раз возвращаться в депо. Для каждого клиента г € I заданы спрос ^ и частота посещения Клиент должен быть посещен ^ раз в течение планового периода И, каждый раз одним и тем же ТС. Временной интервал между последовательными посещениями клиента г должен быть одинаковым и равным = Через обозначим время

обслуживания, которое положительно для всех клиентов и равно нулю для депо. Введем переменные задачи:

%ijkd Уiкd Ща =

Вспомогательные переменные и^ы, ^ 0 будут использованы для исключения под-циклов. Математическая модель задачи смешанного целочисленного линейного программирования (СЦЛП) может быть представлена следующим образом:

т1п ^2 ^2 ^2 ^2 ^ хчы (1-1)

кеК ¡еУ з€У

при ограничениях:

^ Шы. < Vк, к € К,<1 € В, (1.2)

г€1

1, т = т(к),

Ушкл = < т € М,к € К, А € И, (1.3)

0, т = т(к),

1, если маршрут ТС к содержит дугу (г,]) в день ¿,

0, иначе;

1, если маршрут ТС к в день ё, содержит вершину % € V,

0, иначе;

1, если клиент г обслуживается в день (1, 0, иначе.

^Уъкё, = Ыы, г € 1,(1 € В, (1.4)

кеК

= уг, г € I, (1.5)

¿еБ

п-1

= 1, I € I, (1 €{0,..., - 1)тг}, (1.6)

¿=0

** + -2 < у>ка - уъе, (1.7)

г € 1,к € К,а,р € В, а = р,

^2 = ^2 хзгЫ = УзкЬ 3 € V, к € К,(1 € В, (1.8)

Щкв. - Щкв, + пхг]к<1 < П -1, г,] € 1,к € К, (1 € В, (1.9)

^ ^ хцм(и, + з,) ^ Т, к € € В, (1.10)

гз€У

Щы > 0, г € I, к € К, А € В, (1.11)

Ща, Хг3к<1, Угка € {0,1}, г,] € V, к € К, 6 € В. (1.12)

Целевая функция (1.1) задает суммарное пройденное расстояние для всех ТС на всем плановом периоде. Неравенства (1.2) контролируют грузоподъемность ТС. Равенства (1.3) устанавливают распределение ТС по депо. Условия (1.4) и (1.5) гарантируют требуемую частоту посещения клиентов. Неравенства (1.6) задают необходимые временные интервалы между последовательными посещениями. Требование посещать клиента одним и тем же ТС записано в (1.7). Равенства (1.8) гарантируют каждому клиенту предшественника и преемника в маршруте ТС, а так же выезд ТС и возвращение в депо. Неравенство (1.9) обеспечивает отсутствие подциклов. Длительность рабочей смены ограничена условием (1.10). Последние два неравенства задают область изменения переменных.

Заметим, что число переменных можно сократить заменой трехиндексной матрицы переменных Щка на двухиндексную матрицу ща.

Теорема 1. Замена переменных щ к а на новые переменные щ а и введение новых ограничений

пи)и1 ^ та ^ 0, г € I, (1 € В, вместо условий (1.11) не меняет множество допустимых маршрутов.

ДОКАЗАТЕЛЬСТВО. Вспомогательные переменные щ к а использовались в ограничениях (1.9) для запрета циклов, не проходящих через депо. Без ограничения общности, можно считать, что они задавали порядок обхода клиентов в каждом маршруте в каждый день планового периода. Индекс к задавал номер маршрута, и для каждого маршрута была своя нумерация. Удаление этого индекса означает единую нумерацию посещения клиентов в каждый день планового периода: сначала нумеруются клиенты первого маршрута, затем второго и т.д. Условие ^ удаляет клиентов из этой нумерации, если они не посещаются в день Таким образом множество маршрутов остается тем же самым. □

Список литературы диссертационного исследования кандидат наук Кулаченко Игорь Николаевич, 2026 год

Список литературы

[1] Salhi S., Imran A., Wassan N. A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation // Computers & Operations Research. 2014. Vol. 52. P. 315-325. Recent advances in Variable neighborhood search.

[2] Christofides N., Beasley J. E. The period routing problem // Networks. 1984. Vol. 14, no. 2. P. 237-256.

[3] Cordeau J.-F., Gendreau M., Laporte G. A Tabu Search heuristic for periodic and multi-depot vehicle routing problems // Networks. 1997. — Sep. Vol. 30, no. 2. P. 105-119.

[4] Hemmelmayr V. C., Doerner K. F., Hartl R. F. A variable neighborhood search heuristic for periodic routing problems // European Journal of Operational Research. 2009. Vol. 195, no. 3. P. 791-802.

[5] Groer C., Golden B., Wasil E. The Consistent Vehicle Routing Problem // Manufacturing & Service Operations Management. 2009.— Oct. Vol. 11, no. 4. P. 630-643.

[6] Kovacs A. A., Golden B. L., Hartl R. F., Parragh S. N. Vehicle routing problems in which consistency considerations are important: A survey // Networks. 2014. Vol. 64, no. 3. P. 192-213.

[7] Kovacs A. A., Parragh S. N., Hartl R. F. A Template-based Adaptive Large Neighborhood Search for the Consistent Vehicle Routing Problem // Networks. 2014. —Jan. Vol. 63, no. 1. P. 60-81.

[8] Xu Z., Cai Y. Variable neighborhood search for consistent vehicle routing problem // Expert Systems with Applications. 2018. Vol. 113. P. 66-76.

[9] Messaoudi B., Oulamara A., Salhi S. A decomposition approach for the periodic consistent vehicle routeing problem with an application in the cleaning sector // International Journal of Production Research. 2023. Vol. 61, no. 22. P. 77277748.

[10] Yang M., Ni Y., Yang X., Ralescu D. A. The consistent vehicle routing problem under uncertain environment // Journal of Intelligent & Fuzzy Systems. 2021. Vol. 41, no. 2. P. 2797-2812.

[11] Yang M., Ni Y., Song Q. Optimizing driver consistency in the vehicle routing problem under uncertain environment // Transportation Research Part E: Logistics and Transportation Review. 2022. Vol. 164. P. 102785.

[12] Coene S., Arnout A., Spieksma F. On a periodic vehicle routing problem // Journal of the Operational Research Society. 2010. —Dec. Vol. 61, no 12. P. 1719-1728.

[13] Mladenovic N., Hansen P. Variable Neighborhood Search // Computers and Operations Research. 1997. Vol. 24. P. 1097-1100.

[14] Mladenovic N., Hansen P. Developments of Variable Neighborhood Search // Essays and Surveys in Metaheuristics / Ed. by C. Ribeiro, P. Hansen. Boston, MA: Springer, 2002. Vol. 2. P. 415-439.

[15] Hansen P., Mladenovic N., Todosijevic R., Hanafi S. Variable neighborhood search: basics and variants // EURO J. Comput. Optim. 2017. Vol. 5, no. 3. P. 423-454.

[16] Kernighan B., Lin S. An Efficient Heuristic Procedure for Partitioning Graphs // Bell System Technical Journal. 1970. Vol. 49, no. 2. P. 291-307.

[17] Kononova P., Kochetov Y. The variable neighborhood search for the two

machine flow shop problem with a passive prefetch // Journal of Applied and Industrial Mathematics. 2013. Vol. 7, no. 1. P. 54-67.

[18] Glover F., Hao J.-K. The case for strategic oscillation // Annals of Operations Research. 2011. Vol. 183, no. 1. P. 163-173.

[19] Kochetov Y., Khmelev A. A hybrid algorithm of local search for the heterogeneous fixed fleet vehicle routing problem // Journal of Applied and Industrial Mathematics. 2015. Vol. 9, no. 4. P. 503-518.

[20] Khmelev A., Kochetov Y. A hybrid VND method for the split delivery vehicle routing problem // Electronic Notes in Discrete Mathematics. 2015. Vol. 47. P. 5-12.

[21] Davydov I., Kochetov Y., Carrizosa E. A local search heuristic for the (r|p)-centroid problem in the plane // Computers and Operations Research. 2014. Vol. 52. P. 334-340.

[22] Diakova Z., Kochetov Y. A double VNS heuristic for the facility location and pricing problem // Electronic Notes in Discrete Mathematics. 2012. Vol. 39. P. 29-34.

[23] Davydov I., Kochetov Y., Carrizosa E. VNS heuristic for the (r|p)-centroid problem on the plane // El. Notes in Discr. Math. 2012. Vol. 39. P. 5-12.

[24] Aarts E. H. L., Lenstra J. K. Local Search in Combinatorial Optimization. New York: John Wiley & Sons, 1997.

[25] Golden B. L., Raghavan E. A., S.and Wasil. The vehicle routing problem: latest advances and new challenges. Springer US, 2008.

[26] Grover L. K. Local Search and the Local Structure of NP-complete Problems // Oper. Res. Lett. 1992. Vol. 12, no. 4. P. 235-243.

[27] Alekseeva E., Kochetov Y., Plyasunov A. Complexity of local search for the p-median problem // European Journal of Operational Research. 2008. Vol. 191, no. 3. P. 736-752.

[28] Gutin G. Z., Yeo A. Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour // Computers & OR. 1999. Vol. 26, no. 4. P. 321-327.

[29] Ahuja R. K., Ergun O., Orlin J. B., Punnen A. P. A survey of very large-scale neighborhood search techniques // Discrete Applied Mathematics. 2002. Vol. 123, no. 1-3. P. 75-102.

[30] Kochetov Y. Computational bounds for local search in combinatorial optimization // Computational Mathematics and Mathematical Physics. 2008. Vol. 48, no. 5. P. 747-763.

[31] Irnich S. P., Toth, Vigo D. Vehicle routing: problems, methods, and applications / Ed. by P. Toth, D. Vigo. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2014. P. 1-33.

[32] Kochetov Y., Kononova P., Paschenko M. Formulation space search approach for the teacher/class timetabling problem // Yugoslav Journal of Operations Research. 2008. Vol. 18, no. 1. P. 1-11.

[33] Santini A., Schneider M., Vidal T., Vigo D. Decomposition Strategies for Vehicle Routing Heuristics // INFORMS Journal on Computing. 2023. Vol. 35, no. 3. P. 543-559.

[34] Taillard E. D. Decomposition Methods // Design of Heuristic Algorithms for Hard Optimization: With Python Codes for the Travelling Salesman Problem. Cham: Springer International Publishing, 2023. P. 131-152. ISBN: 978-3-03113714-3.

[35] Walshaw C. A Multilevel Approach to the Travelling Salesman Problem // Operations Research. 2002. Vol. 50, no. 5. P. 862-877.

[36] Chevalier C., Safro I. Comparison of Coarsening Schemes for Multilevel Graph Partitioning // Learning and Intelligent Optimization / Ed. by T. Stutzle. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. P. 191-205.

[37] Pisinger D., Ropke S. Large neighborhood search // Handbook of metaheuris-tics. 2019. P. 99-127.

[38] Sahling F., Buschkuhl L., Tempelmeier H., Helber S. Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic // Computers & Operations Research. 2009. Vol. 36, no. 9. P. 2546-2553.

[39] Ribeiro C. C., Hansen P., Taillard E. D., Voss S. POPMUSIC — Partial optimization metaheuristic under special intensification conditions // Essays and surveys in metaheuristics. 2002. P. 613-629.

[40] Queiroga E., Sadykov R., Uchoa E. A POPMUSIC matheuristic for the capacitated vehicle routing problem // Computers & Operations Research. 2021. Vol. 136.

[41] Taillard E. D., Helsgaun K. POPMUSIC for the travelling salesman problem // European Journal of Operational Research. 2019. Vol. 272, no. 2. P. 420-429.

[42] Braysy O., Gendreau M. Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms // Transp. Sci. 2005. Vol. 39, no. 1. P. 104-118.

[43] Nagata Y., Braysy O. A powerful route minimization heuristic for the vehicle routing problem with time windows // Operations Research Letters. 2009. Vol. 37, no. 5. P. 333-338.

[44] Gendreau M., Tarantilis C. D. Solving Large-Scale Vehicle Routing Problems with Time Windows: The State-of-the-Art // CIRRELT-2010-04. Montreal: 2010.

[45] Ho S. C., Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries // Comput. Oper. Res. 2004. Vol. 31, no. 12. P. 1947-1964.

[46] Vidal T., Crainic T. G., Gendreau M., Prins C. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows // Computers & Operations Research. 2013. Vol. 40, no. 1. P. 475-489.

[47] Archetti C., Speranza M. G. Vehicle routing problems with split deliveries // International Transactions in Operational Research. 2012. Vol. 19, no. 1-2. P. 3-22.

[48] Braekers K., Ramaekers K., Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review // Computers & Industrial Engineering. 2016. Vol. 99. P. 300-313.

[49] Lambert V., Laporte G., Louveaux F. Designing collection routes through bank branches // Computers & Operations Research. 1993. Vol. 20, no. 7. P. 783-791.

[50] Li F., Golden B., Wasil E. The open vehicle routing problem: Algorithms, large-scale test problems, and computational results // Comput. Oper. Res. 2007. Vol. 34, no. 10. P. 2918-2930.

[51] Yakici E., Karasakal O. A min-max vehicle routing problem with split delivery and heterogeneous demand // Optimization Letters. 2013. Vol. 7. P. 1611-1625.

[52] Aloise D. J., Aloise D., Rocha C. et al. Scheduling workover rigs for onshore oil

production // Discrete Applied Mathematics. 2006. Vol. 154, no. 5. P. 695-702. IV ALIO/EURO Workshop on Applied Combinatorial Optimization.

[53] Ribeiro G., Desaulniers G., Desrosiers J. et al. Efficient heuristics for the workover rig routing problem with a heterogeneous fleet and a finite horizon // Journal of Heuristics. 2014. Vol. 20. P. 677-708.

[54] Aronofsky J., Williams A. The use of linear programming and mathematical models in under-ground oil production // Management Science. 1962. Vol. 8, no. 4. P. 394-407.

[55] Santos I. M., Hamacher S., Oliveira F. A Systematic Literature review for the rig scheduling problem: Classification and state-of-the-art // Computers & Chemical Engineering. 2021. Vol. 153. P. 107443.

[56] Eagle K. Using simulated annealing to schedule oil field drilling rigs // Interfaces. 1996. Vol. 26, no. 6. P. 35-43.

[57] Flager F. A method to optimize onshore drilling rig fleet size and schedule considering both reservoir management and operational objectives // Journal of Project Production Management. 2014. Vol. 1, no. 2014.

[58] Santos I. M., Carrilho L. M., Oliveira F. L. C. et al. Offshore Oil Rig Scheduling Simulation: a multi-perspective approach. 2017.

[59] Santos I. M. Mathematical Programming Models and Local Search Algorithms for the Offshore Rig Scheduling Problem. Master's thesis, Programa de Pos-Graduacao em Engenharia de Producao, PUC-Rio, Rio de Janeiro, 2018. — March.

[60] Заозерская Л. А., Захарова Ю. В. Модели и алгоритмы локального поиска для маршрутизации транспортных средств с возвратами и временными

окнами // Известия Иркутского государственного университета. Серия Математика. 2024. Т. 48. С. 95-110.

[61] Borisovsky P., Eremeev A., Kovalenko Y., Zaozerskaya L. Rig Routing with Possible Returns and Stochastic Drilling Times // Mathematical Optimization Theory and Operations Research / Ed. by P. Pardalos, M. Khachay, A. Kazakov. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2021. P. 51-66.

[62] Borisovsky P. A parallel greedy approach enhanced by genetic algorithm for the stochastic rig routing problem // Optimization Letters. 2024. Vol. 18, no. 1. P. 235-255.

[63] Kibzun A. I., Naumov A. V., Norkin V. I. On reducing a quantile optimization problem with discrete distribution to a mixed integer programming problem // Automation and Remote Control. 2013. Vol. 74. P. 951-967.

[64] Pecin D., Contardo C., Desaulniers G., Uchoa E. New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows // INFORMS Journal on Computing. 2017. Vol. 29, no. 3. P. 489-502.

[65] Archetti C., Speranza M. G. A survey on matheuristics for routing problems // EURO Journal on Computational Optimization. 2014. Vol. 2. P. 223-246.

[66] Maniezzo V., Stützle T., Vofi S. Matheuristics: Hybridizing Metaheuristics and Mathematical Programming. Springer, 2009.

[67] Talbi E.-G. Hybrid Metaheuristics. Berlin, Germany: Springer, 2013.

[68] Hemmelmayr V. C., Doerner K. F., Hartl R. F., Vigo D. Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management // Transportation Science. 2014. Vol. 48. P. 103-120.

[69] Talbi E.-G. Metaheuristics: From Design to Implementation. Wiley, 2009.

[70] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982.

[71] Nagata Y., Braysy O., Dullaert W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows // Computers & Operations Research. 2010. Vol. 37, no. 4. P. 724-737.

[72] Toth P., Vigo D. The Granular Tabu Search and Its Application to the Vehicle-Routing Problem // INFORMS Journal on Computing. 2003. Vol. 15, no. 4. P. 333-346.

[73] Solomon M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints // Operations Research. 1985. Vol. 35. P. 254265.

[74] Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by Simulated Annealing // Science. 1983. Vol. 220, no. 4598. P. 671-680.

[75] Hutter F., Hoos H. H., Leyton-Brown K. Sequential Model-Based Optimization for General Algorithm Configuration // Learning and Intelligent Optimization / Ed. by C. A. C. Coello. Berlin, Heidelberg: Springer, 2011. P. 507-523.

[76] Gendreau M., Laporte G., Seguin R. Stochastic vehicle routing // European Journal of Operational Research. 1996. Vol. 88, no. 1. P. 3-12.

[77] Oyola J., Arntzen H., Woodruff D. L. The stochastic vehicle routing problem, a literature review, part I: models // EURO Journal on Transportation and Logistics. 2018. Vol. 7, no. 3. P. 193-221.

[78] Tillman F. A. The multiple terminal delivery problem with probabilistic demands // Transportation Science. 1969. Vol. 3, no. 3. P. 192-204.

[79] Gendreau M., Laporte G., Seguin R. A tabu search heuristic for the vehicle

routing problem with stochastic demands and customers // Operations research.

1996. Vol. 44, no. 3. P. 469-477.

[80] Stewart Jr W. R., Golden B. L. Stochastic vehicle routing: A comprehensive approach // European Journal of Operational Research. 1983. Vol. 14, no. 4. P. 371-385.

[81] Florio A. M., Feillet D., Poggi M., Vidal T. Vehicle Routing with Stochastic Demands and Partial Reoptimization // arXiv preprint arXiv:2201.08866. 2022.

[82] Miranda D. M., Conceicao S. V. The vehicle routing problem with hard time windows and stochastic travel and service time // Expert Systems with Applications. 2016. Vol. 64. P. 104-116.

[83] Ben-Tal A., El Ghaoui L., Nemirovski A. Robust optimization // Robust optimization. Princeton university press, 2009.

[84] Poort E. S. v. d. Aspects of Sensitivity Analysis for the Traveling Salesman Problem: Ph. D. thesis / University of Groningen. Groningen, The Netherlands,

1997.

[85] Borisovsky P., Battaia O. MIP-Based Heuristics for a Robust Transfer Lines Balancing Problem // International Conference on Optimization and Applications / Springer. 2021. P. 123-135.

[86] Gurevsky E., Rasamimanana A., Pirogov A. et al. Stability factor for robust balancing of simple assembly lines under uncertainty // Discrete Applied Mathematics. 2022. Vol. 318. P. 113-132.

[87] Carrizosa E., Ushakov A., Vasilyev I. Threshold robustness in discrete facility location problems: a bi-objective approach // Optimization Letters, 9 (7), 1297-1314. 2015.

[88] Carrizosa E., Nickel S. Robust facility location // Mathematical methods of operations research. 2003. Vol. 58, no. 2. P. 331-349.

[89] Ратушный А. В., Кочетов Ю. А. Матэвристика для минимизации времени ожидания трейлеров при неточных временах прибытия // Дискретн. анализ и исслед. опер. 2022. Т. 29, № 3. С. 85-101. Переведена на английский: «Matheuristics for Waiting Time Minimization for Trailers with Uncertain Arrival Times», J. Appl. Industr. Math. 16, 540-549 (2022).

[90] Huang M., Zhang H., Kuang H. et al. Flexible truckload pickup and delivery problem considering reserved orders and fuel consumption // Computers & Industrial Engineering. 2019. Vol. 138. P. 106-117.

[91] Zhang Q., Wang Z., Huang M. et al. Heterogeneous multi-depot collaborative vehicle routing problem // Transportation Research Part B: Methodological. 2022. Vol. 160. P. 1-20.

[92] Laporte G., Ropke S., Vidal T. Chapter 4: Heuristics for the vehicle routing problem // Vehicle Routing: Problems, Methods, and Applications, Second Edition. SIAM, 2014. P. 87-116.

[93] Qiu M., Fu Z., Eglese R., Tang Q. A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickups // Comput. Oper. Res. 2018. Vol. 100. P. 102-116.

[94] Gu W., Cattaruzza D., Ogier M., Semet F. Adaptive large neighborhood search for the commodity constrained split delivery VRP // Computers & Operations Research. 2019. Vol. 112. P. 104761.

[95] Pessoa A., Sadykov R., Uchoa E., Vanderbeck F. A generic exact solver for vehicle routing and related problems // Mathematical Programming. 2020. Vol. 183, no. 1. P. 483-523.

[96] Ropke S., Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows // Transportation science. 2006. Vol. 40, no. 4. P. 455-472.

[97] Hemmelmayr V. C., Cordeau J.-F., Crainic T. G. An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics // Computers & Operations Research. 2012. Vol. 39, no. 12. P. 3215-3228.

[98] Azi N., Gendreau M., Potvin J.-Y. An adaptive large neighborhood search for a vehicle routing problem with multiple routes // Comput. Oper. Res. 2014. Vol. 41. P. 167-173.

[99] Pelletier S., Jabali O., Laporte G. The electric vehicle routing problem with energy consumption uncertainty // Transportation Research Part B: Methodological. 2019. Vol. 126. P. 225-255.

[100] Mladenovic N., Drezner Z., Brimberg J., Urosevic D. Less Is More Approach in Heuristic Optimization // The Palgrave Handbook of Operations Research, Ed. by S. Salhi, J. Boylan. Cham: Springer International Publishing, 2022. P. 469-499. ISBN: 978-3-030-96935-6.

Публикации автора по теме диссертации

[101] Kulachenko I. N., Kononova P. A., Kochetov Y. A., Kurochkin A. A. The variable neighborhood search for a consistent vehicle routing problem under the shift length constraints // IFAC-PapersOnLine. 2019. Vol. 52, no. 13. P. 2314-2319.

[102] Kulachenko I. N., Kononova P. A. The VNS approach for a consistent capacitated vehicle routing problem under the shift length constraints // Commun. Comput. Inform. Sci. 2019. Vol. 1090. P. 51-67.

[103] Кулаченко И. Н., Кононова П. А. Гибридный алгоритм локального поиска для задачи маршрутизации транспортных средств с многократным посещением клиентов // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 2. С. 43-64. Переведена на английский: «A hybrid local search algorithm for consistent periodic vehicle routing problem», J. Appl. Industr. Math. 14(2), 339-351 (2020).

[104] Kulachenko I. N., Kononova P. A. A Matheuristic for the Drilling Rig Routing Problem // Lecture Notes in Computer Science. Vol. 12095 of Lecture Notes in Computer Science. 2020. P. 343-358.

[105] Кулаченко И. Н., Кононова П. А. Гибридный алгоритм решения задачи маршрутизации буровых установок // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 2. С. 35-59. Переведена на английский: «A hybrid algorithm for the drilling rig routing problem», J. Appl. Industr. Math. 15(2), 261-276 (2021).

[106] Kulachenko I. N., Kononova P. A. An adaptive large neighborhood search for the robust rig routing // Expert Systems with Applications. 2023. Vol. 231. P. 120626.

[107] Kulachenko I. Decomposition Strategies for Solving a Large-Scale Consistent Vehicle Routing Problem // Proceedings of the 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS). 2023. P. 48-52.

[108] Программа оптимизации маршрутов транспортных средств с многократным посещением клиентов // Свидетельство о государственной регистрации программы для ЭВМ № 2021617091. Кулаченко И. Н., Кононова П. А. Зарегистрировано: 06.05.2021.

[109] Программа оптимизации маршрутов мобильных буровых установок // Свидетельство о государственной регистрации программы для ЭВМ № 2022681063. Кулаченко И. Н., Кононова П. А. Зарегистрировано: 09.11.2022.

Приложение А Свидетельства о

государственной регистрации программ для ЭВМ

российская федерация

RU

2021617091

федеральная служба по интеллектуальной собственности

(12) ГОСУДАРСТВЕННАЯ РЕГИСТРАЦИЯ ПРОГРАММЫ ДЛЯ ЭВМ

Номер регистрации (свидетельства): 2021617091

Дата регистрации: 06.05.2021

Номер и дата поступления заявки: 2021616125 22.04.2021

Дата публикации и номер бюллетеня: 06.05.2021 Бюл. № 5

Контактные реквизиты: РоНпа Копопоуа <[e-mail]

Авторы:

Кулаченко Игорь Николаевич ^и), Кононова Полина Александровна ^и)

Правообладатель: федеральное государственное автономное образовательное учреждение высшего образования «Новосибирский национальный исследовательский государственный университет» (Новосибирский государственный университет, НГУ) ^и)

Название программы для ЭВМ:

Программа оптимизации маршрутов транспортных средств с многократным посещением клиентов

Реферат:

Программа предназначена для оптимизации маршрутов транспортных средств для обслуживания клиентов, требующих многократное посещение с равными интервалами, при ограниченной продолжительности рабочей смены. Программа основана на методе локального поиска с чередующимися окрестностями, усиленным методом поиска с запретами и включающим в себя процедуры интенсификации и диверсификации поиска. Программа может быть использована для автоматизации планирования маршрутов в компаниях, занимающихся регулярными поставками, или для составления расписания для торговых представителей. ОС: Windows 7/8/10.

Язык программирования: С++

Объем программы для ЭВМ: 92 КБ

Рис. А.1. Свидетельство о государственной регистрации программы для ЭВМ № 2023688138.

российская федерация

RU

2022681063

федеральная служба по интеллектуальной собственности

(12) ГОСУДАРСТВЕННАЯ РЕГИСТРАЦИЯ ПРОГРАММЫ ДЛЯ ЭВМ

Номер регистрации (свидетельства): 2022681063

Дата регистрации: 09.11.2022

Номер и дата поступления заявки: 2022680286 31.10.2022

Дата публикации и номер бюллетеня: 09.11.2022 Бюл. № 11

Контактные реквизиты: Демидов Михаил Борисович, [e-mail]

Авторы:

Кулаченко Игорь Николаевич ^и), Кононова Полина Александровна ^и)

Правообладатели: Федеральное государственное автономное образовательное учреждение высшего образования «Новосибирский национальный исследовательский государственный университет» (Новосибирский государственный университет, НГУ) ^и) Федеральное государственное бюджетное учреждение науки Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук ^и)

Название программы для ЭВМ:

Программа оптимизации маршрутов мобильных буровых установок Реферат:

Программа предназначена для оптимизации маршрутов буровых установок для обслуживания объектов, требующих проведение работ в течение заданного времени. Для обслуживания всех объектов в соответствии с временными окнами может потребоваться совместное обслуживание несколькими буровыми установками. Алгоритм сочетает в себе метод локального поиска с чередующимися окрестностями для поиска маршрутов и методы математического программирования для распределения работ по скважинам при заданных маршрутах. Программу можно использовать для автоматизации планирования работ буровых установок или для других областей, где требуется составление маршрутов для совместного обслуживания при ограничениях на временные окна. ОС: Windows 7/8/10.

Язык программирования: С++

Объем программы для ЭВМ: 272 КБ

Рис. А.2. Свидетельство о государственной регистрации программы для ЭВМ № 2023684795.