И построения маршрута движения автотранспорта
Объект исследования: логистические задачи и автоматизация управления грузоперевозками.
Результаты, полученные лично автором: проанализирована предметная область, определен объект автоматизации, сформулирована алгоритмическая задача. Проведено исследование математических методов решения транспортной задачи и задачи коммивояжера. Сформулированы их достоинства и недостатки, сделаны выводы.
В наше время деятельность многих предприятий не обходится без очень тесного сотрудничества с транспортными компаниями. Качественная, быстрая, своевременная доставка груза является одним из важнейших факторов, которые влияют на развитие и стабильность организации. Кроме того, благодаря грузоперевозкам любой человек имеет возможность осуществлять транспортировку грузов любого объема и габаритов буквально в любую точку земного шара.
При организации грузоперевозок транспортным компаниям важно минимизировать сроки доставки груза и затраты на нее. Для этого нужно решить две основные проблемы:
1. Выбор оптимального маршрута.
2. Учет заявок и их оптимальное распределение по маршрутам и транспортным единицам.
В некоторых компаниях данные задачи все еще решаются вручную. С ростом количества заказов и объёмов грузоперевозок такой подход требует неоправданно много сил и затрат. Поэтому необходимо автоматизировать механизмы распределения заявок клиентов и составления маршрутных адресов для грузоперевозок.
При построении оптимального маршрута необходимо решить задачу коммивояжера и транспортную задачу.
Задача коммивояжера – задача математического программирования по определению оптимального маршрута движения коммивояжера, цель которого состоит в том, чтобы посетить все объекты, записанные в задании, за кратчайший срок и с наименьшими затратами. Для решения задачи коммивояжера были исследованы следующие методы: полный перебор, метод ветвей и границ, метод ближайшего соседа, муравьиный метод.
Метод полного перебора заключается в переборе всех возможных комбинаций точек (пунктов назначения). Метод гарантированно находит наилучший маршрут, но имеет слишком высокую временную сложность, поэтому может применяться только для задач малой размерности.
В методе ветвей и границ отсеиваются подмножества, заведомо не содержащие оптимальных решений. В процессе работы некоторые решения не рассматриваются, поэтому нахождение точного решения задачи не гарантируется.
Метод ближайшего соседа относится к так называемым жадным алгоритмам. Выбирается ближайший из еще не посещенных пунктов. Метод является очень быстрым ввиду чрезвычайно малого числа операций, требуемых для осуществления его работы, но не всегда дает оптимальное решение.
Муравьиный метод – один из эффективных полиномиальных методов для нахождения приближенных решений задачи коммивояжера. Идея заключается в моделировании поведения муравьев, которые быстро находят кратчайший путь к источнику пищи и адаптируются к изменяющимся условиям.
Транспортная задача – это задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку между пунктами отправления и назначения.
Самый простой и известный метод решения задачи – это итерационное улучшение плана перевозок. Вычисляется первоначальный опорный план и на каждом шаге улучшается, пока не будет соответствовать заданному условию оптимальности (он должен стремиться к минимуму).
Есть разные методы нахождения опорного плана, но наиболее распространенные это методы «северо-западного угла», минимальной стоимости, Фогеля.
В методе «северо-западного угла» ячейки транспортной таблицы последовательно заполняются максимально возможными объемами перевозок сверху вниз и слева направо. Метод прост и понятен, но малоэффективен и в большинстве случаев не даёт оптимальный план.
Метод минимальной стоимости также прост, но эффективнее предыдущего. Сначала заполняются ячейки с наименьшими тарифами, а затем ячейки с большими тарифами. Данный метод не всегда приводит к оптимальному плану.
Основа метода Фогеля заключается в нахождении разности между парой минимальных тарифов в каждой строке и столбце. Затем в строке или столбце с наибольшей разностью заполняется клетка с наименьшим тарифом. Метод простой и позволяет получить приближенный к оптимальному опорный план.
Расвывод, что точные методы просты в реализации, почти всегда дают точное решение, но малопригодны для задач больших размерностей, т.к. неэффективны по времени. Поэтому для реализации программной системы предполагается использовать эвристические методы, имеющие высокую скорость выполнения в задачах большой размерности, а результатом является достаточно точное приближенное решение.
Материал поступил в редколлегию 05.04.2017
УДК 004.8
И.В. Бондарева
Научный руководитель: доцент кафедры «Информатика и программное обеспечение», к.т.н., Д.Г. Лагерев