ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

В работе рассматривается задача нахождения маршрутов развоза товаров на объекты заданного регион при помощи услуг железнодорожного транспорта, возникающая у компаний, желающих сократить транспортные расходы на доставку продукции. При решении задачи необходимо учитывать реалии и ограничения, с которыми перевозчики сталкиваются на практике. Существующая региональная сеть железных дорог характеризуется, как правило, сильной разветвленностью разного качества, сотнями объектов развоза, большим разбросом расстояний между поставщиками и получателями (от единиц до сотен километров), возможностью использования промежуточных складов станций для хранения товаров, небольшими объемами складских помещений у получателей товара, ограниченными возможностями транспортного парка.[2]

1. Постановка проблемы

В связи с вышеперечисленными факторами, увеличению прибыли компании способствует комплексное решение таких задач как: обеспечение своевременности исполнения заявок, поступающих от получателей; сокращение расходов на транспортировку и хранение товаров; уменьшение количества транспортных средств, необходимых для обеспечения заказов каждого из объектов в нужное время; составление оптимальных графиков использования имеющихся транспортных средств; построение оптимальных по транспортным расходам и времени доставки маршрутов и расписаний развоза товаров по конечным станциям.[18]

Для обеспечения эффективного решения перечисленных задач с целью увеличения суммарной прибыли компании необходима разработка системы оптимизации доставки товаров железнодорожным транспортом. Необходимо отметить, что в термин оптимизация используется не в строгом математическом смысле (optimum – неулучшаемый), а как устоявшийся в биснес-приложениях термин, характеризующий эффективность и результативность процесса сокращения затрат.[1]

2. Анализ литературы

Необходимость такой системы обусловлена спадом объемов перевозок железнодорожным транспортом по причине увеличения доли автомобильного транспорта. Ранее разработанные алгоритмы Юсиповым Р.А. в диссертации «Прогнозирование показателей в оперативных планах поездной и грузовой работы», Шапкиным И.Н. «Организация железнодорожных перевозок на основе информационных технологий», Макаровым В.М. «Разработка и применение математической модели оперативного прогнозирования поездной работы» и другими являются не эффективными, т.к. в них не учитывается качество перевозочного процесса.[5]

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

3. Постановка задачи исследования

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

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

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

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

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

Для достижения указанных результатов необходимо решить такие задачи:[3]

  1. Получить формальную постановку задачи оптимального планирования маршрутов.
  2. Построить математическую модель процесса поиска оптимального маршрута с ограничениями на порядок обхода станций с помощью муравьиного алгоритма.
  3. Построить математическую модель процесса поиска оптимального маршрута с ограничениями на порядок обхода станций с помощью генетического алгоритма.
  4. Построить математическую модель гибридной муравьиной системы.
  5. Экспериментально исследовать построенные модели и выбрать наилучшую.
  6. Разработать структуру системы оптимального планирования маршрутов и мониторинга железнодорожных перевозок.
  7. Разработать информационное и программное обеспечение системы на основе выбранной математической модели.
  8. Проверить корректность работы создания системы на контрольном примере.[4]

4. Математическая постановка задачи оптимального планирования маршрутов железнодорожных перевозок

Почти в каждом городе Украины есть станция, которая использует некоторое количество поездов поставки с идентичной грузоподъемностью Q. На N станциях есть груз весом Р, i. Нужно составить маршруты доставки грузов с одних станций на другие, причем выгрузка и дозагрузки могут осуществляться на станциях по пути следования поезда.[8]


Рисунок 4.1 – Пример решения задачи оптимального планирования маршрутов грузовых перевозок
(анимация: объем – 133 КБ, размер – 600x368, количество кадров – 30, задержка между кадрами – 30 мс; задержка между последним и первым кадрами – 100 мс; количество циклов повторения – 7)

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

5. Применение задачи коммивояжера

Задача коммивояжера (ЗК) - довольно старая, она была сформулирована еще в 1759 году (под другим именем). Термин «Задача коммивояжера» был использован в 1932 г. в немецкой книге «The traveling salesman, how and what he should to get commissions and be successful in his business», написанной старым коммивояжером.[9]

ЗК формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Содержательно вершины графа являются городами, которые должен посетить коммивояжер, а веса ребер отражают расстояния (длины) или стоимости проезда. Эта задача является NP-сложной, и точный преодолим алгоритм ее решения имеет факториальная сложность [16].

ЗК является широко известной задачей оптимизации комбинаторного типа. Она формулируется следующим образом: даны полный взвешенный граф G (X, V) порядка n, где X = {x, ..., x} - множество вершин; V=X*X- множество ребер, в нем необходимо найти цикл Гамильтона, имеющий наименьший суммарный вес ребер, входящих в него [18].

Цикл в графе называется циклом Гамильтона, если он содержит все ребра, причем каждое ребро один и только один раз.[10]

Очевидно, решением задачи является перестановка n! вершин, количество возможных перестановок равно n!, однако количество различных решений задачи с учетом направления обхода и сдвига начальной вершины будет (n-1)!\2 .

Задача не имеет алгоритма, позволяющего найти решение за приемлемое время, и решается в основном эвристическими методами.[11]

6. Применение муравьиного алгоритма для поиска оптимального маршрута

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

Опишем локальные правила поведения муравьев при выборе пути [16].

1. Муравьи имеют собственную «память». Поскольку каждый город может быть посещен только один раз, то у каждого муравья есть список уже посещенных городов - список запретов. Обозначим через Jik список городов, которые необходимо посетить муравью k, что находится в городе i.[12]

2. Муравьи обладают «зрением» - видимость - эвристическое желание посетить город j, если муравей находится в городе i. Будем считать, что видимость обратно пропорциональна расстоянию между городами Nij=1\Dij

3. Муравьи обладают «нюхом» - они могут улавливать след феромона, подтверждающий желание посетить город j из города i на основании опыта других муравьев. Количество феромона на ребре (i, j) в момент времени t обозначим через Tij(t).[14]

Муравьи размещаются в случайно выбранные города без совпадений. Каждый муравей начинает движение со своего узла и проходит новые узлы до тех пор, пока все узлы графа НЕ будут посещены. Находясь в узле и, муравей вероятностно выбирает следующий узел j из набора допустимых узлов по правилу, что определяет вероятность перехода k-ого муравья из города i в город j [16][13]:

где a,b - параметры, определяющие веса следа феромона. При a = 0 алгоритм вырождается в жадный алгоритм (будет выбран ближайший город).

Пройдя ребро (i, j), муравей откладывает на нем некоторое количество феромона, которое должно быть связано с оптимумом сделанного выбора. Пусть Tij(t) есть маршрут, пройденный муравьем k к моменту времени t - длина этого маршрута, а Q - параметр, имеющий значение порядка длины оптимального пути. Тогда количество феромона, которое откладывается, может быть задано в виде [20]:

Правила внешней среды определяют, в первую очередь, испарения феромона. Пусть PЄ[0;1] коэффициент испарения, тогда правило испарения имеет вид [22]:

где m - количество муравьев в колонии.

В начале алгоритма количество феромона на ребрах принимается равным небольшому положительному числу. Общее количество муравьев остается постоянным и равным количеству городов, каждый муравей начинает маршрут из своего города.[15]

Дополнительная модификация алгоритма заключается в введении так называемых «элитных» муравьев, которые усиливают ребра наилучшего маршрута, найденного с начала работы алгоритма. Обозначим через T * лучший текущий маршрут, через L * - его длину. Тогда, если в колонии есть e элитных муравьев, то ребра маршрута получат дополнительное количество феромона [19]:

7. Использование генетического алгоритма для локального поиска

Генетические алгоритмы используют принципы и терминологию, заимствованные у биологической науки - генетики. В ГА каждая особь представляет потенциальное решение некоторой проблемы. Множество особей, потенциальных решений, составляет популяцию. Поиск (суб) оптимального решения проблемы выполняется в процессе эволюции популяции - последовательного преобразования одного конечного множества решений в другое с помощью генетических операторов репродукции, кроссинговера и мутации. Эволюционные вычисления используют такие механизмы естественной эволюции [17]:

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

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

После того, как генетический алгоритм «распределил» грузы по станциям, каждый из них решает оптимизационную задачу развоза грузов при минимизации собственного пути. Таким образом, система строится как гибридная, в которой присутствуют разнородные подсистемы — оптимизации маршрутов, генетический алгоритм, имитационная модель для определения пройденного пути.

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

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

1. Маршруты из выбранных особей объединяем в одно решение. Данное решение назовем объединенным решением;

2. Пока в объединенном решении есть маршруты, делаем следующее: выбираем маршрут и вставляем его в новое решение, для этого берем случайное число в пределах от 0 до количества маршрутов в объединенном решении, данное число и будет указывать номер маршрута в объединенном решении; удаляем выбранный маршрут в объединенном решении; удаляем в объединенном решении все маршруты, в которых есть клиенты из выбранного решения;

3. Вставляем не обслуженных клиентов в новое решение с использованием метода самого дешевого включения с учетом грузоподъемности. Если вставка не возможна – создается новый маршрут.

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

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

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

3. перемещение: выбирают подмаршрут и вставляют его в другое место. Этот оператор может выполнить внутреннее или внешнее перемещение;

4. вторичная вставка маршрутов: из решения удаляются маршруты целиком, затем клиенты с удаленных маршрутов заново вставляются в решение;

5. вторичная вставка клиентов: из решения удаляются отдельные клиенты, и затем заново вставляются в маршрут;

6. восстановление: удаляет клиентов, нарушающих временные ограничения из их маршрутов. Удаленные клиенты потом повторно вставляются, используя метод самого дешевого включения с учетом грузоподъемности;

7. переупорядочивание клиентов: процедура интенсификации, которая пытается уменьшить полное расстояние допустимых решений, переупорядочивая клиентов в пределах маршрута с помощью эвристического метода вставок.

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

Оператор редукции отбирает в новую популяцию 5% элитных хромосом, затем методом рулетки формируем недостающее количество особей.

В качестве критерия останова используется либо количество генераций либо отсутствие улучшения среднего значения фитнес-функции на протяжении нескольких итераций.

8. Достоинства и недостатки муравьиных алгоритмов

Достоинства

  1. Для TSP (Traveling Salesman Problem) сравнительно эффективны
  2. Для небольшого количества узлов TSP может быть решена полным перебором
  3. Для большого количества узлов TSP вычислительно сложна (NP-трудная) - экспоненциальное время сходимости
  4. Работают лучше, чем другие глобальные оптимизации для TSP (нейронные сети, генетические алгоритмы)
  5. Сравнение с GAs (Genetic Algorithms):опираются на память обо всей колонии вместо памяти только о предыдущем поколении
  6. Меньше подвержены неоптимальным начальным решениям (из-за случайного выбора пути и памяти колонии)
  7. Могут использоваться в динамических приложениях (адаптируются к изменениям, скажем, расстояний)
  8. Применялись к множеству различных задач

Недостатки

  1. Теоретический анализ затруднён: в результате последовательности случайных (не независимых) решений, распределение вероятностей меняется при итерациях
  2. Обычно необходимо применение дополнительных методов таких, как локальный поиск
  3. Сильно зависят от настроечных параметров, которые подбираются только исходя из экспериментов[13]

Заключение

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

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

При построении подсистемы надо учитывать, что подсистема АСУ – сложная человеко-машинная система и экономический эффект применения технических средств достигается в основном в производстве.

При построении подсистемы необходимо стремиться к выполнению основного принципа информационного обеспечения: одноразовости ввода информации в систему и многократности ее использования. Следует также учитывать специфику автоматизируемого производственного процесса и выполнение целей и задач управления.

Список источников

  1. Современные системы планирования и управления транспортом // Склад и Техника. – 2008.
  2. GPS GPRS Слежение. Определение местоположение через спутник.
  3. Васильева Наталья Курьерская почта UPS: быстро и надежно // Бизнес & Балтия. – 2004. – № 222.
  4. Транспортная логистика :: Оптимизация грузоперевозок.
  5. SystemGroup Логистика.
  6. Решение "IT-Box: Грузоперевозки, Логистика, Склад".
  7. Транспортная логистика.
  8. Метод ветвей и границ.
  9. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. — 476 c.
  10. Пушкарёва Г.В. Исследование и применение бионических методов и моделей для автоматизированного проектирования маршрутов обхода геометрических объектов. Компьютерная графика и представление GraphiCon 2005: науч.-техн. конф., 20-24 июня 2005г. : - 2005.
  11. Генетический алгоритм.
  12. Бейсенбек Б.М. Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки.
  13. Glover F. Tabu Search Journal of the Operational Research Society. – 1999. – Vol.50, № 1. – pp. 106–107.
  14. Сухарев А.Г. Курс методов оптимизации: Учебное пособие. - [2-е изд]. – М.: ФИЗМАТЛИТ, 2005. – 368 с.
  15. Муравьиный алгоритм.
  16. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. - 2003. – № 4. – С. 70-75
  17. Семенюта E.В., Привалов М.В. Применение муравьиных алгоритмов для поиска оптимальных маршрутов грузоперевозок. // Інформаційні управляючі системи та комп'ютерний моніторинг (ІУС та КМ - 2011) / Матеріали II науково-технічної конференції студентів, аспірантів та молодих вчених. — Донецьк, ДонНТУ — 2011. – с. 199-203
  18. Методичні вказівки до виконання лабораторних робіт за курсом “Еволюційні обчислення у технічних задачах” (для студентів спеціальності 7.091503 “Спеціалізовані комп’ютерні системи” (СКС)) / Укл. Ю.О. Скобцов, С.В. Хмільовий, Т. О. Васяєва – Донецьк, 2008. – 91 с.
  19. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Учебно-методический материал по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике». – Нижний Новгород, 2007. – 85 с.
  20. Семенюта Е.В., Привалов М. В. Применение муравьиных и генетических алгоритмов для решения задачи коммивояжера с ограничениями на направленность маршрута. // Інформатика та комп’ютерні технології / Збірка праць VII міжнародної науково-технічної конференції студентів, аспірантів та молодих науковців – 22-23 листопада 2011 р., Донецьк, ДонНТУ. – 2011. У 2-х томах, Т. 1 – с. 159-163
  21. Gambardella L.M., Dorigo M. HAS-SOP Hybrid Ant System for the Sequential Ordering Problem Technical Report IDSIA 11-97.
  22. Ascheuer N., Escudero L. F., Grotschel M. and Stoer M., 1993, A Cutting Plane Approach to the Sequential Ordering Problem SIAM Journal on Optimization 3, 25–42. – 355 pp.

Замечание

При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение работы – декабрь 2013 года. Полный текст работы и материалы могут быть получены у автора или научного руководителя после указанного времени.