Файл: Оптимизация процессов грузовой работы..pdf

Минимизируемый функционал F представляет собой чаще всего линейную форму

F — ^ L H QH ,

н

где Ьн — расстояние ездки на маршруте;

QH — количество погруженного и выгруженного груза.

Основная трудность поставленной таким образом задачи состоит в том, что число возможных маршрутов чрезвычайно велико и матрицу ограниче­ ний невозможно выразить в явном виде (безусловное требование для исполь­ зования алгоритмов составления развозочно-сборочных маршрутов в такой постановке в оперативном планировании — применение Э ВМ ), а так ж е, что задача комбинаторная и привести ее к задаче линейного программиро­ вания довольно трудно. Следовательно, составление маршрутов для завоза и вывоза мелких отправок со станции в форме задачи линейного програм­ мирования — решение неудовлетворительное.

Более перспективно планировать развозочно-сборочные маршруты, используя теорию графов, так как модель транспортной сети обслуж ивае­ мой области (в рассматриваемом случае — города и прилегающих областей) представляет собой конечный смешанный связный граф, вершины которо­ го — пункты завоза, вывоза и проследования груза, а ребра — дороги (ули­ цы), по которым можно попасть из одного пункта в другой; каждому ребру приписана мера р, — расстояние между его концами. Задачу составления развозочно-сборочных маршрутов можно сформулировать следующим об­ разом.

Известны пункты x t{i = 1, 2, ..., п), в которые должен быть доставлен (или вывезен) груз соответственно в количествах qx, q2, ..., qn из начально­ го пункта А (станции) г транспортными средствами грузоподъемностью Q, причем г достаточно для освоения перевозок. Требуется составить коль­ цевые развозочно-сборочные маршруты, общая протяженность которых минимальна. В такой постановке задача близка к известной задаче комми­ вояж ера, которая относится к классу задач о розыске гамильтоновых це­ пей1 и состоит в том, чтобы найти цикл Р , для которого сумма

П

где аи с т — конечные вершины ребра.

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

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

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

груза. П ривязка адреса отправки к вершине графической модели транспорт­ ной сети осуществлена для определения кратчайших расстояний между пунктами маршрута. Планирование произведено в двух вариантах: в пер­ вом маршруты составлены раздельно для шоферов-почасовиков и шоферовсделыциков только по весу отправки; во втором маршруты не разделя­ лись. В обоих вариантах в качестве критерия оптимальности принято рас­ стояние L M.

Методику определения порядка объезда пунктов рассмотрим на приме­ ре. Граф на рис. 7 а отображает размещение пунктов А и x t, количество гру­ за, перевозимого в х и и расстояния между ними. Цифры: в числителе — номер вершины транспортной сети, к которой привязан объект x t на основа­

графе G каждому ребру Е = (а,в) приписывается мера р(а,е). Задача состоит

втом, чтобы построить связную часть Т, содержащую все вершины графа,

ичтобы ее полная мера была минимальной:

Ц (Г ) = 2 [X (£ ) -> -m in.

Е С Т

46

47

парой пунктов начального маршрута. При этом для каждой пары пунктов находим приращения расстояния:

где С — мера ребра — расстояние, км\ і — индекс включаемого пункта;

k,p — индекс первого, второго пункта из пары.

Последовательно получаем равноценные маршруты: А — Д — В— Г— Б—

— А, А —Д — Г—В—Б—А, А— В—Г—Д — Б—А, А —Г— В - Д — Б —А; І м=

=14,4 км, ß « 0,7, tM - 2,69 ч.

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

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

г

Г )

Е

) Г

’ 0 ,6

Рис. 8. Этапы определения оптимального варианта развоза груза

49