Автореферат (1137431)
Текст из файла
На правах рукописиЧернышев Сергей ВладленовичМодели, методы и алгоритмы эффективногорешения задачи маршрутизации транспортана графах больших размерностей05.13.18 — Математическое моделирование,численные методы и комплексыпрограммАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата физико-математических наукМосква — 2011Работа выполнена в Федеральном государственном автономном учреждениивысшего профессионального образования Национальный исследовательскийуниверситет «Высшая школа экономики».Научный руководитель:кандидат технических наук, доцентЧеповский Андрей МихайловичОфициальные оппоненты:доктор физико-математических наук,профессор Старков Сергей Олеговичкандидат технических наукГаврилов Александр ВикторовичВедущая организация:Московский физико-технический институт (Государственный университет)Защита состоитсядекабря 2011 года вчасовмин.
на заседаниидиссертационного совета Д 212.048.09 при Национальном исследовательскомуниверситете «Высшая школа экономики» по адресу: 105187, Москва, ул.Кирпичная, д. 33, ауд..С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики».Ученый секретарьдиссертационного советадоктор технических наукВ.А. ФомичевОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность работы.
Задачи маршрутизации являются ключевымив областях транспортных перевозок, перемещения и логистики и представляют огромный практический интерес. В решении подобных задач заинтересованы многие организации, например, службы скорой помощи, интернетмагазины, оптовые базы, автотранспортные предприятия, компании, занимающиеся грузоперевозками.В работе рассматриваются задачи оптимизации на графах больших размерностей, возникающие в транспортной логистике, не имеющие эффективных алгоритмов нахождения точного решения. Исследуемый класс задач является вариацией задач маршрутизации транспорта с временными окнами идополнительными ограничениями.Задача формулируется следующим образом. Есть множество клиентов имножество агентов.
Агенты обслуживают клиентов. Обслуживание заключается в доставке (сборе) товара (предоставлении услуг). Каждый товар имеетнабор характеристик (вес, объем, стоимость и др.). Для каждого агента заданы местоположение в начале и в конце рабочего дня, интервал работы, ограничения на суммарные доставляемые характеристики товара. Для каждогоклиента заданы интервал времени, в течение которого должен быть доставлентовар, характеристики товара, который он должен получить, и приоритет.Необходимо обслужить максимальное количество клиентов с учетом приоритетов так, чтобы были выполнены временны́е ограничения и ограничения насуммарные характеристики доставляемых товаров. При этом нужно минимизировать суммарные накладные расходы (время работы, время простоя,суммарные транспортные расходы, количество задействованных агентов ит.д.).Рассматриваемый класс задач представляет интерес с научной точки зрения.
В данном направлении на протяжении последних сорока лет ведутся интенсивные исследования. Огромное количество входных параметров, с однойстороны, делают задачу настолько сложной, что многие существующие алгоритмы либо не применимы, либо плохо адаптируемы к практике. С другойстороны, эта же особенность предоставляет простор для новых исследований.Первые приближенные алгоритмы были созданы в 1970-х годах (Clarke G.,Wright J.W.). В 1980-е годы были заложены основные подходы к приближенному решению задач маршрутизации транспорта (Cook T., Russel R.A.,Christofides N., Mingozzi A., Toth P.). С середины 1990-х годов исследованиясосредоточились на построении метаэвристик, в основе которых лежат такиеметоды как поиск с исключениями, метод отжига, генетические алгоритмы,метод муравьиных колоний, нейросети и другие (Gendreau M., Osman I.H.,Matsuyama Y.). В последние десять лет исследования cклонились в сторонуобработки сложных видов ограничений (Frazzoli E., Bullo F.).3Главной целью большинства исследователей является повышение качества результатов счета.
При этом скорость работы алгоритмов уходит навторой план. В то же время высокий темп роста IT-индустрии и интернеттехнологий приводит к необходимости создания программных продуктов, ориентированных на широкий круг пользователей. Для задач массового обслуживания количество клиентов может достигать нескольких тысяч, но приэтом время работы не должно превышать заданного временно́го порога. Таким образом, поиск алгоритмов, способных находить решения приемлемогокачества за заданное время, становится все более актуальной задачей.Целью работы является разработка моделей и алгоритмов для практического решения задач маршрутизации транспорта на графах больших размерностей, содержащих до 10 000 клиентов.Задачами исследования являются:1. Разработка моделей и на их основе приближенных алгоритмов для решения многокритериальной задачи о поиске кратчайших путей.2. Разработка новых и ускорение существующих алгоритмов для решениязадачи маршрутизации транспорта с временны́ми окнами и дополнительными ограничениями.Методы исследования.
В диссертации применяются методы дискретной оптимизации, математического моделирования, динамического программирования и теории сложности алгоритмов.Научная новизна. В диссертации получены следующие основные научные результаты, которые выносятся на защиту:1. Предложен и исследован приближенный алгоритм для построения Парето-минимальных путей в двумерном случае.2. Предложено обобщение многокритериальной задачи на случай графовс произвольно заданным частичным порядком и построен алгоритм дляее решения.3. Предложен метод фиктивных клиентов для снижения размерности задачи.4.
Создан и исследован алгоритм построения начального приближения,основанный на решении задачи о назначениях.5. Построена новая структура данных для выполнения операции обмена сегментов маршрутов и доказано, что применение этой структуры позволяет сократить время выполнения таких операций с O(n) доO(log2 n), где n — общее количество клиентов в маршрутах.6. С помощью введенного в диссертации понятия «разрез» сформулировано часто выполняющееся на практике условие фильтрации и доказано,что выполнение данного условия позволяет сократить количество разрезов с O(n2) до O(n).47.
Разработан многофазный эвристический алгоритм для приближенного решения задачи маршрутизации транспорта с временными окнами,позволяющий учитывать такие дополнительные ограничения, как множественность депо, приоритеты клиентов, зоны обслуживания, множественность характеристик товаров.Практическая ценность. Алгоритмы, опубликованные в данной работе, реализованы на языке C++ и протестированы в операционных системахWindows, Linux.
Для практического использования создана динамическаябиблиотека, которая в настоящее время внедрена в программном комплексеPlanVidia.Достоверность результатов подтверждена строгими доказательствамии результатами численных расчетов.Апробация результатов работы. По результатам, полученным в данной работе, были сделаны доклады на следующих российских и международных конференциях:1. Всероссийская научная конференция «Высокопроизводительные вычисления и их приложения», Черноголовка, 20002.
Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций»,Рязань, 20013. Научная конференция «Ломоносовские чтения», Москва, 20034. Всероссийская конференция студентов, аспирантов, молодых ученых«Технологии Microsoft в теории и практике», Москва, 20055. Международный семинар по компьютерной алгебре и информатике,Москва, 20056. Шестая международная конференция памяти академика А.П. Ершова«Перспективы систем информатики», Новосибирск, 20067. Всероссийская конференция студентов, аспирантов, молодых ученых«Технологии Microsoft в теории и практике», Москва, 2008Публикации.
Основные результаты работы изложены в 10 научных статьях, среди которых 6 — в тезисах докладов [3-5,7-9], 3 — в рецензируемыхроссийских периодических изданиях [1,2,6], из которых 2 статьи [1,2] опубликованы в журналах из списка ВАК и 1 статья в международном рецензируемом журнале [10].Личный вклад соискателя. Все исследования, результаты которых изложены в диссертационной работе, проведены лично соискателем в процессенаучной деятельности. Из совместных публикаций в диссертацию включенлишь тот материал, который непосредственно принадлежит соискателю.5Структура и объем диссертации.
Диссертация состоит из введения,четырех глав, заключения и списка литературы. Работа изложена на 115страницах, содержит 39 иллюстраций. Библиография включает 113 наименований.Автор выражает глубокую признательность к.ф.-м.н, в.н.с. ПанкратьевуЕвгению Васильевичу за научные консультации и поддержку.СОДЕРЖАНИЕ РАБОТЫВо введении обоснована актуальность темы, сформулированы цели изадачи исследования, научная новизна, теоретическая и практическая значимость полученных результатов, основные положения, выносимые на защиту,а также приведены данные о структуре и объеме диссертацииВ первой главе приведен подробный обзор задач маршрутизации транспорта (ЗМТ) и известных алгоритмов ее решения.В разделе 1.1 рассматриваются ЗМТ с дополнительными ограничениями,приводится их классификация.В разделе 1.2 описаны наиболее популярные методы оптимизации, такиекак метод ветвей и границ, методы линейной оптимизации, генетические алгоритмы, методы имитации отжига, поиск с запретами.В разделе 1.3 содержится обзор литературы для решения ЗМТ, приводится классификация по Фишеру.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
