автореферат диссертации по транспорту, 05.22.10, диссертация на тему:Оптимизация автомобильных перевозок мелких партий грузов по разовым заявкам

РГВ од

9 ГС 'Г|Р •Т'-1-'.!

московский ордена трудового красного знакени Автаягничънс - дороясй институт

На ггрэрзг р-стси

лтрохов николай анл70и£ве'1

шгеггзаэдя авташяыж перевозок ьешх партий ГРУВОЗ по рабозй,; 3.'<2КАм

05.22.10 - акяиуатгхза автоксбкльвсго тр депорта

АВТОРЕФЕРАТ ¿иссзрсзц^и дс ссг-'гкзвг" у-ёгсЗ сззлени

ЬЭСКВА 10&3

Работа выполнена за кафедре "Автомобильные перевозки" Московского ордена Трудового [фасного Знамени аБтоиоС;щ>но-дсрохЕЗГо института

- доктор технических наук, профессор Миротяк Л. Б.

- заслуаонныи деятель науки и техники FC2CP, доктор технических нзу:;, профессор Рыбаков К.В.

- кандадат технических тук, профессор Якобашвили A.M.

- АО "btaccoдст тогранс''

Защита состоитсп " M&ft 1953 годь в "j.0 ■■ часов на заседании специализированного совета К 053.30.СЭ ВАК Рй при Московском ордена Трудового Красного Внеиени авгомобилъно-дорсянои институте по адресу: 125829, ГСП-47, Шсхез, А-319, Ленинградски проспект, 64, ауд. 42.

С диссертацией цдано ознакомиться в библиотеке института.

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

Автореферат разослан " >0 1993г.'

Телефон для справок 155-03-28.

Научный руководитель

Официальные оппонент

Ведув^я организация

Ученый секретарь специализированного совета кандидат технических наук,

доцент Власов В.М.

- 1 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ. Развитие в стране рыночных условий хозяйствования существенным образом изменяет содержание коммерческой работы автотранспортных предприятий. Под воздействием расшир.тощейся сети малых производств и частного предпришз'-а-телъстза объем перевозок мелких партии грузов увеличивается.

В таких условиях существующие метода организации перевозок грузов мзлозщфективны, так как они ориентированы н^ применение з достаточно крупных по количеству единиц яодеютого состава автотранспортных предприятиях с системой централизованного планирования перевозок.

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

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

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

ЦЕЛЬ К ЗАДАЧИ ИССЛЕДОВАНИЯ. Исходя из перечисленных проблем целью диссертационной работы является снижение транспорт-

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

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

разработка моделей и алгоритмов оптимизации иарирутов перевозок мелки партий гругов;

разработка программ для практической реализацта предлагаемых методик к алгоритмов на ПЕ2М;

проведение экспериментальных вычислений на ПЭВМ. Оценка эффективности предлагаемых методик и алгоритмов.

ОБЪЕКТОМ КССЯЕДШАНйЯ является процесс организации автомобильных перевозок мелких партий груаоз.

НАУЧНАЯ НЗВЙЗНА результатов исследования содержится в: предлаяегаоу критерии оценки эффективности тшзгов перевозок целккх партий грузов и соответствующем алгоритмическом расчете этой величина по набору заявок без их предварительной мзршрутизации;

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

модификагш: метода Кларка к Райта в части очередности включения пунктов в раавегочные маршруты при равных "выгодах";

расширений возможностей методов маршрутизации мелкспар-тиоеных перевозок за счет учета взаимного расположения начального я конечного пунктов! разЕозошщх маршрутов;

разработке эффективных развозочных маршрутов методом моделирования ограниченного числа их вариантов к перераспределения степени использования грузсподъеь^ости автотранспортных средств по раазозочнкм маршрутам;

исследовании ЕозшнЕостай погшения производительности подвижного состава и енняениз затрат автотранспортных предприятий за счет разработки оптимальных технологических схем доставки мелка партий грузов;

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

числительньк итераций;

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ. Применение разработанных методик оптимизации планов перевозок мелких партяй грузов позволяет повысить конкурентоспособность автотранспортных предприятий за счет эконшии ссботаешп^с ресурсов посредством повышения производительности подвижного состава, учета при маршрутизации месторасполояения автотранспортного предприятия, использования рациональных схем перевозок мелких картин груэоЕ, снижения общего пробега и транспортной работы при выполнении перевозок, ыинтаизации откгенепил фактической траектории движения подвижного состаза от кратчайшего путл следования по маршруту. Ери этой, снижается неб^агоприягяое воздействие на окружающую среду за счет высвобождения подвязного состава при выполнении фиксированного с&аэна перевозок, сокращения расхода топлива и уменьшения выбросов отработавших газоз.

Результаты выполненного иосдедсзашз ьюгут попользоваться автотранспортными предприятие.«:;, научно-иссгедоЕгто.ЕЬския! ор-ганизгцияют, разрабатнэасщиги проекты перепозск нелкспзртион-ных грузов, в учебное процессе для студентов специальности "Организация перевозок и управление на транспорте".

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные результаты теоретических и экспериментальных исследовании прияты к практическому кспольаоваЕйю в учебном процессе па кафэдгу? "Автомобильные перевозки" МДДИ, ШМАТ, АО 'ЪЬхивгопрогресс" и в Одинцовском грурозом трзнспортно- экспедиционно;' ЕредаркятЕи (0Г-ТЭП). Огсндгешй экономический эффект от знедренгя рззработаз-ных в лисоертгции методик при организации перевозок мелких партий грузов грузополучателям г.Москвы и Московской области автотранспортом ОГТЗИ с грузового тгрглшзш, рзстазоткЕпого в г.Одкяцово и являги^егося типовым в единой транспортной системе, состаыт: не кенеэ 1.2 млн. руб. в гсд.

АПРОБАЦИЯ РАБОТЫ. Основные положении диссертации обсуждены и одобрены на 46-й и 47-й нау^о-иетодичэсигс и научно-

исследовательских конференциях МАДИ в 1988-1989 гг. и на заседаниях кафедры "Автомобильные перевозки" МАДИ в 1991-1992 гг.

ПУБЛИКАЦИИ. По материалам исследований опубликовано 3 статьи обЬзм объемом 1.7 печатных листа.

НА ЗАЩГГУ ВЫНОСЯТСЯ:

методика экспертной оценки эффективности аланов перевозок мелких партий грузов по разовым заявкам;

коадиедс алгоритмов расчета кратчайших путей проезда ыеяду пунктам! маршрутов перевозок;

модификация метода Кларка и Раита для расчета развозочных маршрутов ;

комплекс.алгоритмов разработки и оптимизации маршрутов перевозок калкшс иартий грузов;

методика оценки эффективности сравниваемых алгоритмов маршрутизаци перевозок мелких партий грузов.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ. Диссертационная работа состоит из введения, пяти глав, выводов и прилаяений. Диссертация содержит 205 стр. машинописного текста, в том числе 1В1 стр. основного текста, 7 сгр. прнлешэчкй, 8 таблиц, 49 рисунков. Библиография на 13 стр. вкличает 150 наименовании.

СОДЕРЖАНИЕ РАБОТЫ

ВО ВВЕДЕНИИ обосновывается актуальность теш, сформулированы цель и задачи, изложены научная новизна и практическая ценность исследования.

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

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

Так, на производительность подвижного состава при работе на развозочных маршрутах значительное влияние оказ^паит среднее расстояние достэв:и ыелхих партий грусов халдаиу получателю и среднее расстояние пробега автожб:иш иекду смежными пунктами развозочного маршрута ¡а^.х^ . Качественная и ¡количественная связь этих величин с интенсивностью поступления

заявок на разовую доставку мелких партии грузов, плотностью их располскения на транспортной сети, предельными сроками наполнения, принимаемой продолжительностью накопления заявок и соответственно устанавливаемой периодичностью разработки оперативных планов перевозок не установлена. Кроне того, к настоящему времени не существует методики экспертного определения внаяений Ьх^ и для конкретных исходных данных по пе-

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

Оптимальность таков перевозок мелких партай грузов зависит также от избранного метода и критерия маршрутизации, наложенных ограничений в соотнетствии с практическими условиями перевозок и достоверности икформагаи о транспортной сети. В соответствии с такой постановкой Есзроса достаточно полно Еро-веден анализ существующее критериев и методов ¡¿аршрутизации йелкопарткршак грузов, сконцентрировано внзиззке на причинах, сдергиЕаэщих их прг^ененнз. Установлено, что достаточно практичным и аффективным критерием нащрутизации пзгкстся критерий ыинииЕзахжй общего пробега автотранспорта при выполнении фиксированного количества заявок.

ЗВирокпй спектр сур.еструщих методов решшш развозочных задач не шэдсреплеп банком условий, при которых целесообразнее применять тот ши иной метод в силу их ецдепидуаль ессти . Классификация этих методов приведена в диссертэдишЕОЙ работе. Ряд авторов и результаты решения практичзскп:; задан свидетельствуют, что наиболее иерспектианым является иэтсд Кларка и Райта. Однако этот метод неполностью учзпызаэт реальные условия перевозок.

Азалис результатов проведенного анкетного опроса и натурных наблюдений за работай автотранспорта б системе транспорт-Ео-экспедиционного обслушвания нгсгления г.1взскэн показал, что недостаточное пниигЕне отводится информации о состоянии транспортном сети и кргитайиих путях проезда мэяду пунктам изршрутоз перевозок, что приводит к увеличен® пробега по соаглгхя с расчетаьм. Су^ествупщкэ способы определения кратчайших путей проезда не даст нечерпываотего репевля названной прсблеш.

Такил сбразо^, выявленные недостатки в организации перевозок ¡¿едких партий х-рузов и особенности их доставки по разовым заявкам определили необходимость комплексного исследования

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

ВТОРАЯ ГЛАВА диссертации посвящрна разработке концепции управления процессом оптимизации планов перевозок на этапе па-бора заявок.

Известно, что накопление заявок на перевозки мелких партий грузов есть функция времени (n=f(t)). С увеличением плотности заявок на транспортной сети района перевозок средняя длина ездки _медду двуш пооледоЕЗтельшами пунктами маршрута уменьшается (Ler = f(n)). Это в конечном итоге позволяет сократить пробег при выполнении фиксированного количества заявок на переволки. Однако ориентация игаоточитгльно на сокрэлуэнае пробега ведет к увеличению времени накопления заявок, а следовательно, и к росту затрат на складское хранение грузов, затрат, связанных с "заморазипзаниеы" материальных ресурсов и ожиданием заказчиками доставки грузов. Таким образом, необходим затратный компромисс, заключащийся з определении оптимальной периодичности автотранспортного обслуживания района перевозок мелких партий грузов. Графическая интерпретация решения задачи приведена на рио.1.

Рис.1. Зависимость затрат от среднего пробега ыезвду смежными пунктами развозочных маршрутов

Соответствупцая оптимкзируэдзя функция имеет вид:

Зпр = f (-СРатМРзак)-) —> min, (1)

где Snp - приведенные затраты, связанные с перевоз-

кой мелких партий грузов, руб;

•СРат},{Рз2к} - множество факторов, характеризует™ затраты, соответственно, автомобильного транспорта и заказчиков.

В работе предлагаете« простой способ skdhspsok оценки эффективности планов перевозок, згклпчящкйся к сравнении средяеи_длины ездки мелду сьгеяными пунктам развогокЕья маршрутов Ler с "эталонными" параметрами тргяспортксп сети Lera и Ler „о. _

Еерхняя оценка Ler3 соответствует средней длине дуги транспортной сети. Нканяя оценка LerH0 - средней удаленности вершин транспортной сета друг ст друга. Среднее значение Ler для фактического забора заявок определяется средни значением шшкизльиых элементов, расположенных в разноименных строках и стодбцрх матрицы кратчайших расстояний, образованной вершинами, к которым прикреплены поступившие затаки.

Наиболее предпочтительным пакетом зарок будет тот, для которого Ler по значения будет ближе к Ler, . Тас-е с учетом этого критерия ыатет вестись подбор заявок дгк вклячеЕия л планы перевозок.

В ТРЕТЬЕЙ ГЛАВЕ диссертационной работы расагатриваатся алгоритмы расчета [фатчаиших путей прегзда изяду пунктами маршрутов. Комплекс предлагаемых алгоритмов ориентирован на разнообразие исходных даннгж.

Алгоритм последовательного поиска кратчайших путей проезда используется в том случаз, когда пути определится по матрице кратчайших расстояний (ЫКР) |io(Xi,Xj)||. Пошагово из МКР выбираются вершины Xi, удовлетворшопре уошзггп:

о( h,Xi) + c(Xi,k) = c(h,k) (i=j~h) (2)

и _

c(h,Xi) = min c(hsXj) , Xj <s R? 0=1,n), (3)

где h, k - пункты, мелду которыми определяются кратчайшие пути проезда.

На каздом шаге h принимает значения Xi. Итерационные расчеты выполняются до тех пор, пока Xi не примет анакезке к.

В алгоритме дискретного поиска дополнительно используется матрица непосредственных связей (ШС) мезду вершинами ||b(s,Xj)||, позволяющая значительно сократить количество вычислений и соответственно продолжительность расчетов за счет

- 8 -

направленного перебора дуг транспортной сети:

c(h,b(s,XJ})+o(b(s,XJ)tk) = c(h,k) (s=i~«r(Xj)), (4)

где w(Xj) - массив количества непосредственных связей каждой

воряошы транспортной сети (j=l,n). На первом шаге Xj=h. На последующ?« иагах h и Xj принимают значение b(SjXj).

Алгорятм поиска кратчайших путей по продаклтеэльности проезда используется в тем случае, когда необходимо определить кратчайший путь с минимальным количеством промежуточных вершин, полагая, что в каждой из них происходит задержка по времени движения в среднем на величину Т (чао):

o(h.k) _

T(R') = min i -=- + t? > (7=i,f), (5)

R'<£ R? Vt

где Vt - средняя техническая скорость автотранспортного средства, км/ч;

{ R7> - множество кратчайших путей проезда мепду h и к; ty - количество промежуточных вершин кратчайшего пути

с номером ip ; ju - количество кратчайших путей мезду h и к. Первоначально о псыоцьи выиеназзядтах алгоритмов рассчитываются все альтернативные кратчайшие пути. Затем каждой дутэ полученного подграфа присваивается условная досша. равиач 1. На получеиной -/агаш образом транспортной сети рассчитывается ¡сратчайшее расстояние между вершина1« h и к и одновременно определяется кратчайший путь проезда, который и будет являться искомым. В случае необходимости определения кратчайшего пути с максимальным количеством промежуточных вериин кагздей дуге подграфа присваивается условная длина, равная -1.

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

Так, при расположении h и к соответственно в подрайонах d и У, перзоЕачально формируются Еектор-столбец j ¡cfli(h,Xi'/rp) |!,

Еврн вершин альтернативных кратчайших путей: 1-5 1-2 2-4 4-6 5-6 5-4 6-10 10-11 11-16 11-23 16-19 19-41 23-28 23-34 28-29 29-22 32-34 34-66 34-37 37-73 41-44 44-47 47-51 51-50 52-53 53-50 66-69 63-70 69-58 70-52 71-70 7Й-71 73-72

Один из кратчайших путей : путь |1 - 5 - 3 - 10 - 11 - 16 - 19 - 41 - '44 - 47 - Б1 - 50

длкна|0 3 6 7 9 13 20 22 28 34 40 42

Рис. 2. Результаты иэделирования кратчайших путей проезда ьгнду верлинаю! 1 и 50 на транспортной сети размерности 100x100

у у

вектор-строка !|с (Xj r',k)|| и МКР граничных вершин подрайонов d и X I Ic'Cti^Xj*?) 11 (i=l,nf- ; 3=í,níP) и производится суммирование аначс-ний соответствующих элементов по вырадешао: h к

с ' (xi4x/rf) = (h,Xi^")+crf(Xi¿r',XpXp)+сУ(ХоЧк) (6)

(i=i,n^, ; 3=1,П*Г, ).

h,k Л

Значение аавдого элемента полученной иатрицы ¡ | с (Xi rf , Xj Уг' ) 11 есть длина пути между h и к, который проходит через граничное вершины, представленные этими элемента}ги.

Затем из всех значений, рассчитанных по (б), выбираем минимальное, которое определит пару граничных вершин, в соответствии с которой запишем ;фатчайппй путь:

R. -С hI...,Xi4...,XJIfr',...,k >. (7)

I_1 I_I I_!

Недостающие фрагменты пути (7) определяются с использованием вышеописанных алгоритмов последовательного и дискретного поисков.

В качестве примера на рис. 2 приведен результат машинного эксперимента по определению альтернативных кратчайших путей проезда ыезду вершинами 1 и 50 на транспортной сети размерностью 1С0 х 100, разделенной 5-ю подрайонами. Кратчайший путь с минимзльим количеством промежуточных вершин выделен утолщенной лин29й.

ЧЕТВЕРТАЯ ГЛАВА посвящена исследовании алгоритмов разработки и огашизации маршрутов перевовок мелких партий грузов.

Математическая постановка задачи в обцэм виде заключается в следующем.

Задан район перевозок мелких партий грузов, представленный трано1шрпшк_сегью. Известны грузоотправитель Хо, грузополучатели Xi (i=l,n) к их потребности в грузах Qxi. Для выполнения перевозок могут быть использованы автомобили грузоподъемностью ч1,(г2,... ,qk,... ,ql. Задача замотается в пострсешш таких разведочных маршрутов дсставга грузов получателям, суммарная лретяденность которых является минимальной:

J*

L(ÍR„» = min (S)

R _-?=l

Протяженность маршрутов Rp(j=l,jn) в (8) определяется как:

L(R?) = с(Хо,Х1) +2ZI c(Xl,Xi+l) * с(Хп^,Хо). Í9) i=i

- 11 -

Исследование метода Кларка и Райта для решения таких задач выявило следующие его недостатки.

1. Не формализована процедура ЕЫбсра пар пунктов в матрице "функций выгод" при нескольких максимальных значениях "выгод".

2. Не учитывается при ¡.¡аршрутизации месторасположение автотранспортного предприятия (АТП), а таже условие выполнения автомобилем развозочных 1-гаршрутов от нес'-сайгак грузоотправителей.

3. При разработке маршрутов не принимается в расчет величина транспортной работы, зависящая от очередности объезда грузополучателей.

На основе анализа результатов моделирования и решения развозочных задач методом Кларка.и Райта установлена возможность локального сокращении протяженности развозочных маршрутов при проведении пошаговой оптимизации. В диссертации предложено при равных "выгодах" выбирать пару, которой соответствует минимальное значение в матрице кратчайших расстояний. Соответствую!?!« образом модифицирован алгоритм Кларка и Райта и выражение расчета "функций выгод":

Л (Хз., >у) =с (XI, Хо) +с (Хо, Хз) - с (XI ,ХЯ+1/с(Х1,)у). (10)

В результате проведенного исследования выдвинута такая очевидная аксиома: если па задзпной транспортной сети определен порядок объезда п пунктов, начиная с исходного Хо, то ыарлрут передвижения пе изиенится и з том случае, когда исходным является лпбой пункт из мзояестга, зкпочеяных а маршрут. Это означает, что лучший разгозочный маршрут ыожет быть Еыбрая из некоторого янсжества полученных мэтодсу моделирования, когда в качестве относительной поочередно назначается кагздая из зераиз, зхтачасмых в разЕозс-шый маршрут. ГТолучаеша маршруты могут иметь над Х1.Х2,...,Х1,Хо,Х1+1....,Хп,Х1 >, которые щишепительго к условия решаемой развозочной задачи интерпре-тпрустся как гг7=< Хо,Х1+1,... ,Хп,Х1,Х2.....УЛ,Ха У.

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

г>

с(ХГ.Хо) (12); »пах =_шах5х^ (13) £=0,п,

(11); Бх

йпах

где í - порядковый номер вершины, относительно которой предполагается производить расчет патрицы "выгод"; Бх^- оумма элементов строки Х^ МКР.

Очередность перебора верши в качестве относительных определяется по убывающей последовательности значении коэффициентов

В результате проведенного анализа било установлено, что при маршрутизации наряду о функционалом (8) реализуется татае процедура максимальной загрузки подвижного состава: Ч

ок

где цк - фактическое количество груза, перевозимого к-ым ч автомобилем на ¡р -ом маршруте; дк - грузоподъемность (грузовместимость) к-го автомобиля, используемого на ^-ом маршруте.

Исследования показали, что ке всегда целесообразным является разбиение множества получателей грузов N на подшодестЕа Н9 (.ч=1,/л) таким образом, чтобы грузоподъемность автомобилей использовалась полно. Ври этом увеличение общего пробега связано с тем, что на конечном этапе построения кэкдого маршрута при поиокэ очередного пункта о цельа включения в маршрут опре-делягзщкп является не критерий "макогггум выитршд", а объем груза, доставляемого в этот пункт, который может находиться на значительном расстоянии от предыдущего, включенного а маршрут, пункта. В связи с этим дня построения лучшего по общему пробегу плана маршрутизации ыедкопартионвых перевозок грузов следует ке '^рпруты формировать под подвютой состав, а наоборот, на сфодафозадные оптимальный образом развззочшэ нарагруты в соответствии с грузоподъемностью Еспа?ьэуемых автотранспортных средств назначать подвижной состав. Улучшение планов харшрути-зацик достигается за счет перераспределения степени использования грузоподъемности подвижного состава по разБОзочным маршрутам.

ч

-> 1.0

(14)

- 13 -

Такой подход при решении задач может быть реализован методом моделирования вариантов раэвозочных маршрутов. На каждой итерации моделирования задается определенная величина недогруза автотранспортных средств. За исходнул величину недогруза

принимается при моделировании минимальный размер доставляемой партии груза. Максимальная величина недогруза wtm<>* , как показали исследования, ограничена Уст= 0.7 т 0.8. Смежные щхллеку точные значения могут отличаться на величину постоянного шага. Чек мегаие шаг, тем больше требуется итераций моделирования, тем 'точнее результаты и наоборот.

При использовании метода Кларка и Райта пришибается допущение, заключавшееся в том, что груз доставляется от одного отправителя многим поручателям по маршрутам, для которых отправитель является начальным и конечным пунктом. В действительности автогранспсртныэ средства начипаат и заканчивав? работу в автотранспортных предприятиях.

В диссертации разработан алгоритм, позеоляпецш учитывать ьгестораспалояеяяе АШ. Конфигурация маршрута в этом случае имеет гид:

Ry = -(Хр,Хо,Х1,... ,Xi.....Xn,Xp>, (15)

где Xp - вершина расположения АТП.

Постановке задачи учета месторасположения АТП при маршрутизации соответствует оптимизационный функционал:

L(Rn)=fflinLc(Xp,Xo)-!-c(Xo,Xl)+^Zlc(Xi,Xi+i)+c(XnIXp)]. (16) * L=i

В основу стратегии решения сформулзфованной задачи положена рабочая гипотеза: какой бы метсд не предлагался для решения указанной вадачи фрагмент i... ,Хр,Хо,.. .> б',дет присутствовать во всех допустимых рззвегочтк маршрутах. Поэтому целесообразно зггфэпить это свойство в кетоде Кларка и Райта алгоритмическим путем. Л именно, после того, нак будет рассчитана матрица "функций выгод" ? = 11 A(Xi,Xj) 11, з первую очередь необходимо выбирать пару (Xi.Xj) такую, что i=p и j=o. Соответственно, исходный фрагмент ¡¿ашрута запишется х£к R?= i... .Хр.Хо,.. .>. Алгоритм последущего подключения пунктов к фрагыедту маршрута Rp тажк ле, как и в методе Клзркз - Райта.

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

- 14 -

Предложенная методика решения развозочкых садач с учетом месторасположения А.ТП может успептао применяться при разработке плзное маршрутизации перевозок мелких партии грузов автотранспортными средствам из двух и более грузообрззувщих пунктов. В этом случае первоначально должка быть проведена декомпозиция задачи в соответствии с установленной очередностью обслуживания грузсобразуищах пунктов (рио.З).

Рис.3. Скорректированной по условиям перевозок план маршрутизации

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

Проведенные исследования локзэгли, что оптимальное по общему пробегу месторасположение передаточного пункта Хо' на транспортной сети монет быть определено изводом моделирования. Оптимизационная функция м&ет вид:

Ь ({&)>)гш1пС^ЦЬ(1?^) +с(Хо,Хо')+о(Хо*,Хо)3х0> . (17)

{Хо'=ХЩ=1,п>

Анзлкз множества результатов моделираванил назначения Хо' в произвольно выбранные на сети пункты, выполненного по рлду задач, позволил установить, что пункт Хо'=Х1 (1<г1,п) является либо "центральным", либо близким к "центральному" по отношению к другим пунктам этой хе транспортной сети. "Степень центральности" каждого пункта на сети предлагается оценивать коэффициентом Кх£:

БХ;

Кх^г-

(18); Б::

Бтах

1с(Ха,Хо) (19); 5ках=рах Бх^ (20)

(1=1,п),

где Эх— сумма элементов строки XI НКЯ за исключением элемента (XI,Хо).

К "центральному" на транспортной сети по отношекко к другим пунктам относится тот пункт XI, для которого значение Кх-и яеляэтся минимальном. Очередность перебора пунктов в качестве относительных для расчета матриц "функцкй выгод" при оптимизационном ¡¿оделировешга определится Есгрзстасщзй последовательностью значений козйкциэптов Кх;. (1=1,п).

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

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

Ир (Йп)=т1п [>~~Охл*д(Хо. Х1)+^^:СН1.0хз*с(Х1,Х1+1)) ] (21)

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

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

Эффективность рззеозочннх маршрутов оценивается комплексным показателем - величиной расхода топлива.' Сравниваемый развозочкыи маршрут (с индексом 2) лучше исходного (с индексом 1) по расходу тошшвз в том случае, если выполняется условие:

За5ачц

Риа.4. Часгоаги ловдчзажл развозочаюс маршрутов минимальной дооЕягёнвопги ео: 1-нзгод5 Кларка ж Райга; г-ыодзфикгции мз г ода Кларка я Райга

Рис.5, Оп'.лонзнпе средней прпгянснносги развозоч-

кого маршоуга ог минимальной, полученного по: Т-мегода Кларка и Райга; 2-моди»д1кащт метода Кларка и Райга

- 17 -Нкн

д р <--* Д L

Нткы

где К]см - норма расхода топлива на 100 км пробега,л; Нгкм - норма расхода топлива на 100 тхм , л; ДL - разность в общем пробеге по маршрутам, км; ДР - разность в транспортной работе по маршрутам, ткм.

ПЯТАЯ ГЛАВА посвящена экспериментальным исследованиям, целью которых является проверка достоверности научных гипотез и положений диссертации.

, Для проведения малинных экспериментов разработаны блок-схеш управления моделированием транспортных сетей и ог-тимйзацйокным моделированием развозочных маршрутов. По полученным результатам с использованием предложенной методики произведена сценка эффективности разработзяЕЫХ алгоритмов марлру-таэацип перевозок в сравнении с методом Кларка и Райта. Наглядно результаты сравнительных расчетов представлены графиками, изображенными на р?-;с. 4-5.

Все расчеты в работе проводились на ПЭВМ по программам, написанным на алгоритмическом языке "Бзйсик".

0Н™£ ВЫВОДЫ И ПРЕДШШШВ

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

2. Установлено, что по ряду разовых перевозок мелких партий грузов развозочлке изрзгсута могут быть улучшены путем управления дредЕЕйк^.пуе^^ периодом накопления заявок. В связи с зчт о цэльэ искляченпя затрат автотранспортных предприятий на разработку заведомо нграцчоЕаяьпых планов перезоэок предложено экспертную оценку их эффективности производить путем стзнения средней джяы еад;<и меч-ду смгязгзли пунктами развозочных маршрутов с аналогичной "эталонной'1 для данной транспортной сети.

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

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

Б. По результатам исследования предложена качественно иная схема доставки мелких партии грузов и оказания услуг заказчикам, расположении на значительном расстоянии от грузоотправителей, позволявшая существенно сократив общгй пробег автотранспортных средств. В соответствии с этой схемой методом моделирования оптимального слана перевозок производится закрепление заказчиков за одним из некоторого множества пунктов -передаточный пунктом. Доставта. грузов ьа участке грузоотправитель - передаточной пункт производится большегрузными автомобилями по иаягниковыы «арпрутаы. При этом погашается производительность автотранспортных средств за счет внедрения прогрессивных форн организации перевозок к сокращения времени простоя под погрузкой-разгрузкой. Исследованием выпилено, что снижение пробега зависит от протяячнпекзти маятниковых маршрутов перевозок мелких партии грузов. Так, при длине такого маршрута в 37 км и средпак удаленности згкггчикез друг от друга ез 7.3 км сокращение общего пробега составило В2.5Х.

- 19 -

6. Исследование оптимальности планов перевозок в зависимости от степени использования грузоподъемности автотранспортных средств показало, что их разработка по схеме "разбиение мяо.'чества получателе»! на подмнсяества з соответствии с грузоподъемностью используемых автотранспортных средств и последующее определение очередности объезда грузополучателей в полученных подмножестЕак" способствует получению менее эффективны;: планов пергзогок, чем в результате первоначального фор^и-

■ рования рациональных развозочных маршрутов о ориентацией на грузоподъемность используемых азтотранспортннх-средств. Б ходе малинных экспериментов сокращение общего пробега за счет перераспределения степели использовали.? грузоподъемности автотранспортных средств по разЕОзочным маршрутам достигало 22.5 л, а в среднем составило 7.1 7..

7. В соответствии о проведенным обзором литературы и анализом практики перевозок установлено, что недостаточно исследованным является путь снижения затрат автотранспортных предприятий за счет ¡сомплэксного сокращения общего пробега и транспортной работы при доставке ыэдких партий грузов по раз-возочны?! маршрутам. В диссертации задача минимизации общего пробега и транспортной работы сведена к задаче минимизации расхода топлива. Разработало аналитическое соотношение приращения транспортной работы и общего пробега, позволяющее из двух сравниваемых развозочных маршрутов выбрать более эффективный по критерию минимум расхода топлива. Вычислительные эксперлмэнты показали, что предлагаемая методика позволяет б среднем на 2-3 7, сократить расход топлива за счет рациональной последовательности объезда пунктов по развозочным маршрутам. Максимальная величина снитания расхода топлива составила 9.5Х.

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

кость расчетов.

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

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

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

Основные положения диссертации опуйликовзны в следующих работах:

1. Атрохов H.A. Ьгазтруткзсция мелкопарткочных перевозок грузов с учетом ограничения на возврат азто&обнаей (на примере развозки грузов). Дел. в ЦБНТИ МикаЕтотрзаос. РОйСР. - М. :1SS8. - Но.

2. Атрохов H.A. Мзрпрутизация ис-лкопарташшж перевозок грузов с учетом ориентации на работу подвижного состава по системе тяговых плеч (па гримере развозки грузов). Деп. в ЦБНТИ Мкнавтотраноа РСЯСР. - И.: 1933. -14с.

3. Атрохсв H.A. 0 задаче комиивояяера / Повышение эффективности и качества автотранспортного обслуживания. Сб. науч. Тр. МАДИ. - U.: 1939. - С.22-24.