Алгоритм определения рациональных маршрутов движения грузовых автомобилей
Во многих автотранспортных предприятиях значительную долю общего объема перевозок составляет доставка грузов небольшими партиями, не обеспечивающими полной загрузки автомобилей. Для более полного использования грузоподъемности подвижного состава перевозки таких грузов организуются по развозочным (или сборочным) маршрутам. В реальных условиях возможны различные варианты решения этой задачи, поэтому возникает проблема выбора таких маршрутов движения автомобилей, которые позволяют выполнить заданные перевозки с минимальным пробегом транспортных средств.
В науке данная задача известна как \"задача коммивояжера\", которому требуется в определенных целях посетить несколько пунктов на транспортной сети и при этом минимизировать суммарное пройденное расстояние. Имеется метод точного решения этой задачи, получивший название метод \"ветвей и границ\" [1]. Однако, он не может прямо применяться для решения задач развоза (или сбора) груза, имеющих некоторые ограничения. Основными такими ограничениями является необходимость, во-первых, завозить грузы каждому потребителю в определенном и не одинаковом количестве и, во-вторых, учитывать требования Трудового Кодекса об обеденном перерыве и продолжительности рабочей смены водителя. Наличие хотя бы одного из этих ограничений вынуждает организовать завоз груза по нескольким маршрутам.
К настоящему времени имеются опробованные на практике методы решения задач развозки [2], основаные на интуиции и здравом смысле авторов, которые не гарантируют получение точного результата. Получить его можно, например, простым перебором всех вариантов, однако это возможно только при относительно небольшом количестве пунктов завоза. Кроме того, неясно как организовать саму систему перебора этих вариантов маршрутов. С этой целью была разработана методика оптимизации развозочно-сборочных маршрутов движения грузового автомобиля, которая позволяет найти решение путем перебора пунктов транспортной сети при помощи процедуры рекурсии [3]. В соответствии с данной методикой разработана компьютерная программа по определению рациональных маршрутов, написанная на языке программирования \"Visual Delphi 5.0\" под операционную систему Windows 98/Me/2000.
В основу методики оптимизации развозочно-сборочных маршрутов движения грузового автомобиля заложен алгоритм перебора пунктов с возвратами. Алгоритм перебора с возвратами представляет собой итерационный алгоритм прохождения пути, т.е. это способ поиска (по дереву решений), когда при возврате после рассмотрения «пробного» варианта решения на один шаг назад все переменные программы восстанавливают свои значения. Задается определенная процедура, где используется простой перебор целых значений от минимального до максимального. Для каждого значения проводится проверка сложного условия, после чего значение счетчика увеличивается на единицу, если это условие выполнено.
При запуске процедуры поиска вызывается процедура, которая выполняет первичное разбиение: исходя из грузоподъемности автомобиля и необходимого объема перевозок грузов мелкими партиями; определяется необходимое число циклов для выполнения задания на поставки. Т.е. осуществляется разбиение общего количества пунктов - получателей на несколько натуральных чисел всеми возможными способами (числа будут обозначать количество пунктов в одном маршруте). При этом необходимо учитывать, что если сумма груза по любым k пунктам больше грузоподъемности автомобиля, то разбиения, включающие в себя число, большее или равное k, можно не перебирать. Кроме того, если известно, что сумма груза по k+l пунктам всегда меньше грузоподъемности, то разбиения, включающие одновременно числа k и l, также можно отбросить.
Далее для каждого разбиения числа N-1 на несколько натуральных чисел N1, ...,Nk нужно перебрать все способы, которыми можно выбрать N1, ...,Nk пунктов из общего числа, т.е. проводится рекурсивный перебор всех возможных вариантов длин циклов с учетом количества пунктов перевозок. При этом учитывается, что два варианта не имеют принципиальных отличий, т.к. порядок, в котором совершаются маршруты, не существенен. Затем для каждого из вариантов запускается следующая процедура, которая на основании сформированных циклов рекурсивно перебирает все возможные комбинации пунктов перевозок по циклам (т.е. какие пункты входят в конкретный маршрут). Эта процедура разбивает пункты на подмножества с числом элементов N1, ...,Nk, но если среди N1, ...,Nk есть равные числа, то соответствующие подмножества не разделяются. Чтобы разбить множество на подмножества заданной мощности, первая процедура перебора отбирает первое из подмножеств, а затем вызывает себя. В свою очередь вторая процедура перебора выполняет разделение нескольких равных по мощности подмножеств. Отличие от первой процедуры в том, что 1-ый элемент из оставшихся выбирается всегда, для того чтобы исключить перестановки. После этого для каждой из этих комбинаций проверяется наличие превышения максимального объема перевозимого груза, т.е. находится суммарный объем требуемых грузов по каждому из циклов и сравнивается с грузоподъемностью автомобиля. Если полученная сумма не превосходит грузоподъемности автомобиля, то запускается процедура перебора всех возможных комбинаций маршрутов между заданными пунктами перевозок.
Основная трудность заключается в реализации данного алгоритма, т.е. обеспечении неповторяемости перебираемых вариантов, а также написании процедуры отсеивания заранее неподходящих вариантов (с превышением грузоподъемности).
В основу оптимизации последовательности объезда пунктов всех возможных комбинаций маршрутов движения грузового автомобиля заложен метод «ветвей и границ». Суть метода заключается в упорядоченном переборе возможных вариантов транспортной сети и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Для этого множество решений (планов) разбивается последовательно на подмножества, которые представляют между собой три категории. Подмножества первой категории удается отбросить заранее (не анализируя, каждый входящий в него план), как не содержащие оптимальных либо допустимых решений. Для подмножеств второй категории находят наилучшее (для рассмотренных подмножеств) допустимое решение. Подмножества третьей категории, не входящие ни в одну из вышеуказанных, делятся на более мелкие подмножества для того, чтобы свети их к подмножеству одной из двух первых категорий. Процесс последовательного дробления и отбрасывания подмножеств продолжается до тех пор, пока множество подмножеств третьей категории не окажется пустым. Сравнивая, полученные для подмножеств второй категории наилучшие решения, получают оптимальное решение.
Заключение об отсутствии в некотором подмножестве оптимального решения основывается на использовании оценок снизу минимального значения функции цели на данном подмножестве. Пусть имеется некоторое допустимое решение x, и для некоторого подмножества X1 решений можно указать такое число L, что . Если L > (x), то X1 не содержит оптимальное решение и может быть отброшено. Вывод об отсутствии допустимых решений в некотором подмножестве делается в том случае, если хотя бы для одного из условий нельзя найти в этом подмножестве допустимое решение. Такая проверка используется в ряде известных математических алгоритмов. Формализованно это выглядит следующим образом. Определяют подмножество X2 как совокупность таких планов, у которых некоторые компоненты зафиксированы, остальные произвольны (0 или 1). Для всех K, для которых, проверяется выполнение условия:
где R - множество индексов нефиксированных компонент планов подмножества X2.
Если хотя бы для одного K условие не выполняется, в подмножестве X2 нет ни одного допустимого плана.
Каждому подмножеству ставят в соответствие вершину дерева решений, а дуги будут отображать деление подмножества на составляющие части. При такой интерпретации процесс поиска оптимального решения представляют как перемещение по вершинам дерева. В настоящем алгоритме используется односторонний обход дерева, то есть после спуска по некоторой ветви происходит возвращение по этой ветви до тех пор, пока не встретится вершина, имеющая хотя бы одну необследованную ветвь, и вновь осуществляется спуск. Такой способ обхода дерева позволяет организовать компактное хранение информации, используемой при решении задачи маршрутизации мелкопартионных перевозок грузов. Основную часть памяти ПК занимают сведения о просмотренных (или не просмотренных) участках дерева. В данном случае достаточно хранить вершины одной главной ветви, на которой не может содержаться больше n + 1 вершин. Кроме того, для каждой вершины главной ветви необходимо хранить сведения о наличии неисследованных ветвей, исходящих из этой вершины.
Существенным моментом является правило выбора исследуемой ветви в случае, когда из вершины исходит более одной неисследованной ветви. В данном алгоритме выбор направления проводится на основании специально разработанного критерия, на вычисления которого затрачивается более 50% машинного времени решения задачи. Тем не менее, количество итераций не всегда оказывается минимальным. В данном алгоритме выбирается первая неисследованная ветвь.
Когда процедура оптимизации последовательности объезда пунктов завершена, для каждого из вариантов рассчитывается суммарная длина маршрутов по всем циклам, из числа которых выбирается маршрут, имеющий минимальную протяженность.
Эффективность предложенной методики оптимизации развозочно-сборочных маршрутов оценивалась экспериментально по результатам решения практических задач, выполненных студентами кафедры \"Менеджмент на АТ\" ИрГТУ. У данной методики оказались наименьшие: суммарная длина маршрутов по всем практическим работам (характеристика точности метода) и сумма процентов отклонений от оптимального решения (характеристика стабильности метода).
Еще один дополнительный критерий эффективности методики заключался в минимальных затратах машинного времени, которые используются на просмотр всех возможных комбинаций маршрутов движения автомобиля (рис.1).
Рис.1. Зависимость затрат машинного времени на просмотр всех возможных комбинаций маршрутов
Рис.2. Зависимость суммарной длины маршрута от грузоподъемности автомобиля
С использованием предложенной методики представилось возможным проследить, как будет изменяться суммарная длина маршрутов от изменения таких показателей как увеличение грузоподъемности автомобиля (рис.2) и увеличения числа пунктов завоза груза (грузополучателей) - рис.3.
Основные характеристики, полученные при использовании расчетов на ЭВМ, приведены в таблице. При увеличении грузоподъемности автомобиля и количества пунктов завоза груза (грузополучателей) суммарная длина маршрутов соответственно уменьшается и увеличивается согласно полиномиальным кривым шестого порядка.
Рис.3. Зависимость суммарной длины маршрутов от количества пунктов завоза груза (грузополучатели)
Табл. 1. Основные характеристики теоретических зависимостей
Литература
1. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы// 1965/ Т.1. Вып. 1. С. 94-107
2. Житков В.А., Ким К.В. Методы оперативного планирования грузовых перевозок.- М.: Транспорт, 1984. - 218 с.
3. Роджер Х.Н. Теория рекурсивных функций и эффективная вычислимость. - М.: Кибернетика, 1972. - 589 с.
/И.М. Головных, О.С. Прокофьева ©/