Содержание к диссертации
Введение
Глава 1. Методы и задачи оптимального планирования завоза и вывоза грузов в транспортно-логистических системах 12
1.1. Организация и технология завоза и вывоза грузов на грузовые терминалы аэропортов при доставке грузов по схемам «от двери до двери» 12
1.2. Планирование перевозок авиакомпании с вертолетным парком 23
1.3. Организация завоза и вывоза грузов на терминал железнодорожной станции 27
1.4. Организация поставок в логистических системах основанных на дистрибуционных центрах 36
1.5. Постановка задачи оперативного планирования завоза/вывоза грузов, ее математическая формулировка 43
1.6. Аналитический обзор задач оптимизации и методов их решения 47
Выводы 64
Глава 2. Разработка методов, алгоритмов и компьютерных программ оптимального планирования задачи завоза/вывоза грузов 66
2.1. Алгоритм планирования перевозок основанный на методе динамического программирования 66
2.2. Метод оптимального планирования с использованием L— кратчайших маршрутов 76
2.3. Разработка программы в объектно ориентированной среде Delphi 85
2.4. Исследование характеристик работы алгоритма методом численного моделирования 91
Выводы 111
Глава 3. Разработка алгоритмических и программных средств повышения эффективности планирования перевозок 114
3.1. Влияние параметров близости маршрутов на поиск оптимального решения. 114
3.2. Возможность коррекции найденного плана перевозок. Ручная коррекция плана перевозок 124
3.3. Разработка алгоритма полуавтоматической коррекции найденного плана перевозок 130
3.4. Разработка алгоритма автоматической коррекции найденного плана перевозок 139
3.5. Оптимальное планирование доставки грузов как многоэтапный процесс. Программный комплекс планирования перевозок 147
Выводы 154
Глава 4. Применение разработанных методов и алгоритмов к решению задач оптимального планирования доставки грузов в транспортно-логистических системах 157
4.1. Планирование завоза и вывоза груза в аэропорт 157
4.2. Планирование перевозок для авиакомпании с вертолетным парком 161
4.3. Планирование городских перевозок автотранспортной и экспедиторской компании 165
4.4. Реализация программного комплекса для обучения решению задач планирования перевозок, примеры его применения 170
4.5. Особенности использования программы планирования перевозок в совместной работе с коммерческими пакетами прикладных программ 177
Выводы 188
Заключение 190
Литература 194
Условные обозначения 202
Приложения 203
- Планирование перевозок авиакомпании с вертолетным парком
- Метод оптимального планирования с использованием L— кратчайших маршрутов
- Возможность коррекции найденного плана перевозок. Ручная коррекция плана перевозок
- Планирование городских перевозок автотранспортной и экспедиторской компании
Введение к работе
Актуальность темы. В последнее время на рынке перевозок в Российской Федерации сложилась следующая ситуация. В результате экономического кризиса в августе 1998 года объемы перевозок упали на тех видах транспорта, которые считаются основными для внутренних перевозок (воздушный, автомобильный и железнодорожный) и для международных перевозок (воздушный, автомобильный, железнодорожный и морской). В условиях неопределенности и напряжения, особенно в первые дни кризиса большинство российских предприятий отменили заказы и разорвали торговые сделки, а зарубежные компании остановили свои грузы, транспортируемые в Россию. Это привело к ощутимым финансовым потерям не только у российских транспортных предприятий, но и у тесно связанных с ними финских, прибалтийских и прочих зарубежных фирмах работавших на российском направлении.
Из-за отсутствия загрузки на рынке транспортных услуг возникла жесточайшая конкуренция. Значительно смягчились критерии принятия перевозчиком заявки на перевозку (особенности маршрута, параметры груза и т.п.). Подавляющее большинство компаний на время отложили мероприятия по обновлению собственного транспортного парка, стремясь решать поставленные задачи имеющимися в наличии средствами. Остро сказывался избыток транспортных средств (нерациональный объем транспортного парка). Наиболее острыми проблемами являлись снижение себестоимости перевозок, рациональное использование транспортных средств (в целях их окупаемости).
В течение 1999 года обстановка в сфере перевозок постепенно нормализовалась, тем не менее стало возможным обозначить несколько особенностей. Произошло разделение клиентов по видам транспорта, что привело к более четкому выделению грузопотоков. Небольшой экономический рост соответственно привел к росту перевозок. Тем не менее, большинство компаний заинтересованы в укрупнении грузопотоков, перевозимых конкретными видами транспорта при посреднической деятельности этих компаний. В целях упрочнения своего положения фирмы, работающие на различных видах транспорта, комбинируются (кооперируются)друг с другом для выполнения интермодальных перевозок. В этих условиях аналогами зарубежных логистических центров становятся места сосредоточения грузов: терминалы аэропортов, морских и речных портов, грузовые дворы и склады железнодорожных станций. В данных пунктах имеется возможности не просто пропускать большие партии грузов, но и комбинировать их, оптимизируя, таким образом, грузопоток. Появилась потребность в новых методах обработки грузов и планирования перевозок. Перспективы развития экономики непосредственно связаны с повышением эффективности управления транспортными процессами в частности перевозками грузов.
Субъектами рынка транспортных услуг, обеспечивающими формирование грузовой базы воздушного транспорта являются авиакомпании их агенты и экспедиторские компании, специализирующиеся на воздушных перевозках. Эти компании часто владеют собственными терминалами или арендуют терминалы аэропорта и обеспечивают на них накапливание и консолидацию отправок. Агенты и экспедиторы обеспечивают не только передачу грузов в грузовые службы аэропортов, но и организуют прием грузов со склада отправителей с доставкой в аэропорт, планирование и организацию вывоза грузов с терминалов аэропортов «до двери» получателей.
В развитие этих функций некоторые экспедиторы становятся договорными перевозчиками, выдавая от своего имени сквозной транспортный документ на перевозку от отправителя до аэропорта назначения или «от двери до двери».
Авиакомпании, традиционно занимающиеся воздушными перевозками между аэропортами, в условиях обострившейся конкуренции расширяют свои функции и переходят на организацию доставки «от двери до двери». Эти компании через свои филиалы организуют завоза и ввоз грузов на терминалы аэропортов.
Активную позицию в этих вопросах занимают грузовые службы аэропортов (СОПГП) не только поощряющие развитие таких перевозок, но и самостоятельно организующие завоз и вывоз грузов по договорам для всех субъектов рынка воздушных перевозок. Ключевое положение грузовых служб аэропортов в обработке грузов на терминале и при перемещении их между терминалом и бортом ВС, а также совместная работа СОПГП с авиакомпаниями при организации воздушных перевозок, позволяют организовывать перевозки по принципу «точно в срок», включая доставку грузов в аэропорт и саму воздушную перевозку в состав логистической системы поставок, в качестве технологического звена.
Перевозки подобного рода являются наиболее перспективными в настоящий момент, поскольку позволяют гибко связать процесс производства с процессом
6 реализации товара с минимальными транспортными затратами на всех этапах логистической цепи. В развитии этого направления заинтересованы крупные торгово-промышленные компании, стремящиеся встроить транспортные процессы в сферу своей деятельности, в качестве равнозначной составляющей.
Важную роль в организации перевозок играет процесс планирования, учитывающий расположение грузовой клиентуры, размеры грузовых партий, характеристики парка транспортных средств. Для транспортно-логистических систем при поставках «от двери до двери» вопросы организации централизованного завоза и вывоза грузов на терминалы являются важными на любом виде транспорта, а также при смешанных перевозках. Оптимальное планирование облегчает управление перевозками, и сводит к минимуму возможные корректировки в ходе выполнения плана. Наличие и величина положительного результата определяется эффективностью использования парка ТС с учетом условий перевозки. Возможность использования ТС различных по техническим и экономическим характеристикам предполагает большое количество планов перевозки для одного набора заявок и даже приблизительная оценка диспетчером перевозок каждого из них с целью выбора оптимального является трудоемким процессом. С ростом грузопотока увеличивается время планирования и понижаются качественные характеристики плана перевозок.
Повысить качество планирования можно, используя современные ЭВМ программное обеспечение, использующее аппарат математического моделирования систем и процессов. Условия оперативной деятельности транспортных и логистических компаний требуют программного продукта позволяющего, используя стандартный набор исходных данных, составить оптимальный план перевозок с учетом особенностей комплекта заявок и имеющегося в наличии или предполагаемого парка ТС. Результаты работы программы должны представлять диспетчеру транспортной компании четкую картину планируемой оперативной обстановки, позволять принимать управляющие решения (заказ ТС, распределение заданий водителям, определение порядка загрузки ТС, выделение ресурсов ГСМ), обеспечивать производственный процесс необходимыми документами (путевые листы, план погрузо-разгрузочных работ). Таким образом, необходимо автоматизировать процесс принятия решений при организации перевозок, сведя роль диспетчера к минимуму. Алгоритмы, реализующие процесс поиска оптимального плана перевозок должны разрабатываться на базе математической модели описывающей характерные особенности реальных транспортных систем содержащих в себе подобные процессы.
Спрос на новые методы оптимального планирования и специальное программное обеспечение сформирован большим количеством самостоятельно действующих на рынке транспортно-логистических компаний и экспедиторских фирм. С учетом стремления Российской Федерации интегрироваться в мировую транспортную систему, разработка и внедрение этих методов должны строиться на базе новейших информационных технологий. Это обуславливает стремление предприятий, работающих в сфере транспорта, к автоматизации и компьютеризации процессов управления и планирования. Более того, можно сделать вывод, что даже при стабилизации экономических процессов в стране, актуальность этих задач снизится не намного, поскольку в условиях нарастающего развития производства объем перевозок будет также расти, а достаточно стремительный рост перевозок вызывает те же проблемы, что и стремительное падение. Поэтому постоянное обновление методов оптимизации и разработка новых алгоритмических и программных средств является одной из основных задач.
Методы оптимизации процессов, предназначенные и для решения транспортно-ориентированных задач, разрабатывались в математике с середины 20-го века. Математическим моделям транспортных систем, постановкам таких задач и методам их решения посвящены работы А.С.Беленького, А.Э.Горева, П.А.Кравченко, Г.А.Крыжановского, Е.А.Куклева, И.И.Меламеда, Ю.И.Палагина, Б.Н.Пшеничного, С.М.Резера, М.И.Рубинштейна, С.И.Сергеева, И.Х.Сигала, А.С.Шалыгина, В.В.Шашкина, Y.Dumas, M.M.Solomon, L.D.Bodin и других. К настоящему времени исследованы основные задачи транспортной оптимизации, отражающие способы организации перевозок при концентрации или разделении грузопотоков. Разработано множество алгоритмов, основанных на методах математического программирования и позволяющих получать оптимальные или близкие к ним решения для отдельных постановок. Очень часто весьма перспективные методы, позволяющие решать задачи с высокой степенью сложности и большим количеством ограничений, не могли быть реализованы на практике из-за сложности практической реализации. Первоначальное распространение получили лишь наиболее простые методы или частные случаи решения конкретных задач. С появлением и развитием электронно-вычислительной техники возможности использования различных методик расширились, хотя и в известных пределах, ограниченных уровнем технического развития.
Анализ работ по данным направлениям показал, что, несмотря на большое количество существующих работ близких по тематике, вопросы централизованного завоза и вывоза грузов с использованием парка из нескольких типов ТС, исследованы недостаточно. Описанные постановки задач, в большинстве не учитывают такого важного фактора как многотипность парка ТС или учитывают его не в полной мере. Известные методы поиска оптимальных решений, имеют определенные трудности при программной реализации. На рынке транспортных услуг отсутствуют программные пакеты, позволяющие осуществлять планирование завоза и вывоза грузов на терминалы, качественно и оперативно.
В настоящий момент, когда уровень техники весьма высок, а возможности компьютеров настолько велики, что позволяют всерьез говорить о создании информационного общества, стало возможным реализация новых технологий транспортной работы на базе математических методов оптимизации, позволяющих создавать компьютерные программы, гибко реагирующие на условия внешней среды. Разработка алгоритма поиска оптимального решения для задачи завоза вывоза груза с использованием парка из нескольких типов ТС, позволяющего находить оптимальные или близкие к ним решения, легко программируемого и адаптируемого к планированию перевозок на различных видах транспорта является весьма актуальной.
Цель работы. Целью работы является разработка методов, алгоритмов и программных средств поиска оптимальных решений для задач завоза вывоза грузов на терминалы аэропортов, ж/д станций морских и речных портов с использованием парка из нескольких типов ТС, практическое применение которых позволит повысить качество планирования и управления перевозками в деятельности транспортно-экспедиторских фирм и логистических торгово-промышленных компаний.
Объект исследования. Объектом исследования является транспортно-логистическая система, включающая терминал аэропорта, осуществляющий концентрацию и распределение грузов в пределах определенного региона, диспетчера перевозок, ответственного за планирование и организацию перевозок, автоматизированное рабочее место диспетчера перевозок, грузовую клиентуру, расположенную в пределах региона, парк, включающий один или несколько типов ТС.
Методы исследования. Методической основой для исследования послужили работы отечественных из зарубежных ученых в области математического моделирования транспортных задач и методов математического программирования, а также работы в области управления транспортом нормативные документы, регламентирующие работу воздушного и автомобильного транспорта, а также личный опыт работы автора в автотранспортной компании. При экспериментальных исследованиях и разработке компьютерной программы использовались интегрированная среда программирования Turbo Pascal 7.0 и объектно-ориентированная среда программирования Delphi 5.0, операционные системы WINDOWS 95/98.
Для достижения цели был поставлен и решен ряд задач. Выполнен анализ задач оптимального планирования концентрации и распределения грузопотоков на современном рынке транспортных услуг и выделены характерные особенности таких задач, дана математическая формулировка задачи оптимизации отражающей эти особенности.
Проведен анализ задач математической оптимизации их сходства и различия с поставленной задачей. Дан обзор и анализ методов решения задач оптимизации, исследована возможность их применения к поставленной задаче, обоснована необходимость разработки программно-алгоритмических.средств.
Предложен новый метод и алгоритмы поиска оптимального решения - плана перевозок, представляющего собой схему объезда клиентов с назначением на рейсы ТС определенного типа с целью минимизации транспортных расходов.
На базе разработанных методов и алгоритмов автором создана компьютерная программа, определены характеристики работы программы для случаев с различным количеством клиентов и типов ТС, определены предельные значения исходных данных для эффективной работы программы при существующих технических характеристиках современных ЭВМ.
Разработаны методы и алгоритмы повышения эффективности работы программы на ЭВМ с ограничениями по техническим параметрам.
Выполнены исследования возможности применения программы для решения задач планирования завоза/вывоза грузов на терминалы на различных видах транспорта.
Практическая значимость. Практическая значимость работы заключается в разработке комплекса алгоритмических и программных средств позволяющих диспетчеру перевозок транспортно- логистической или экспедиторской компании, занимающейся организацией перевозок на воздушном и других видах транспорта: проанализировать с учетом текущей оперативной ситуации по распределению грузопотоков и располагаемому парку ТС различные варианты доставки грузов и принять наилучший к исполнению, с сохранением альтернативных планов на случай возможного изменения оперативной обстановки; автоматизировать процессы планирования, принятия управляющих решений, и необходимого документооборота при организации завоза и вывоза грузов на терминалы. определить приоритет использования ТС с различными характеристиками для выполнения определенного комплекта заявок;
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях:
Международной научно-технической конференции - «Современные научно-технические проблемы гражданской авиации» (Москва, 20-21 апреля 1999 года, МГТУГА);
Научно-технической конференции студентов, аспирантов и молодых ученых -«Неделя науки - 99» (Санкт-Петербург, 10-17 мая, 1999 года, АГА); The International Seminar - "Vatry - Pulkovo airports, Logistics and Air Cargo Transportation of FoodStuffs" (Санкт-Петербург, апрель 2000 года, АГА);
Научной конференции и Чтений, посвященных памяти И.И. Сикорского - «Дни науки в Академии Гражданской Авиации» (Санкт-Петербург, 29-30 мая 2000 года, АГА);
Научно-технической конференции студентов, аспирантов и молодых ученых, посвященной памяти И.И. Сикорского - «Неделя науки - 2001» (Санкт-Петербург, 14-19 мая 2001 года, АГА).
Результаты исследований и основные положения диссертационной работы опубликованы в восьми печатных работах [29,53,52,54,55,75,76,77]. На защиту выносится: - метод решения задачи оптимального планирования завоза/вывоза грузов, основанный на предложенной новой модели оптимизации с использованием при построении плана перевозок многошагового процесса выбора направления движения исходя из заданных (и перебираемых в процессе) типов ТС, и выбора типа ТС из начального состояния и формированием по ходу решения L кратчайших маршрутов; - разработанные алгоритмы вычисления оптимального плана, включающие процедуры поиска шаговых целевых функций и семейства, упорядоченных L -кратчайших маршрутов на каждом шаге оптимизации, алгоритмы отбраковки «фрагментов» формируемых маршрутов, проверки на допустимость плана, поиска и сохранения улучшенных маршрутов; результаты исследования и разработанные алгоритмы улучшения сходимости предложенного метода оптимизации (введение параметров близости запоминаемых кратчайших маршрутов, а также режимы ручной, полуавтоматической, и автоматической коррекции) представляющие собой совокупность методов и приемов, обеспечивающих нахождение и принятие эффективного плана доставки грузов; алгоритмы автоматической и полуавтоматической коррекции найденного плана перевозок и результаты численного моделирования, обосновывающие эффективность их применения для повышения качества найденного плана перевозок; программный комплекс, реализующий предложенные методы и алгоритмы, позволяющий на ЭВМ малой и средней мощности применять его на практике в оперативной деятельности транспортно-логистических компаний и экспедиторских фирм при организации доставки грузов на воздушном и других видах транспорта.
Полученные результаты позволяют говорить о возможности широкого практического применения результатов исследования.
Планирование перевозок авиакомпании с вертолетным парком
Характер применения вертолетов в качестве транспортных средств определяется следующими отличительными свойствами: 1) возможность вертикального взлета посадки; 2) необязательность наличия комплекса аэродромных сооружений (взлетно-посадочных полос, рулежных дорожек, стоянок).
Если принять во внимание еще и ограниченную, по сравнению с самолетами дальность полета, то можно сделать вывод, что вертолеты являются региональным видом транспорта, следовательно, могут применяться в сочетании с магистральным на конечных звеньях транспортной цепи (аналогичной автомобильному транспорту) или выполнять перевозки в пределах региона. В обоих случаях возникают задачи планирования перевозок, сходные с представленной выше (п. 1.1).
Деятельность авиакомпании в высокогорных районах или в системе островов осуществляется по следующей схеме. Вертолетная авиакомпания со своим парком и техническими службами базируется на аэродроме, как правило, в крупном областном центре, имеющим выход на магистральные авиалинии. В дальнейшем будем называть его обслуживаемым аэропортом (ОА). ОА имеет комплекс летно-технических сооружений и способен принимать и обслуживать крупные грузовые и пассажирские самолеты. Грузы, прибывающие в населенные пункты, расположенные в труднодоступной местности или отправляемые из этих пунктов в другие точки страны обязательно проходят через ОА. Хранение грузов и перераспределение их осуществляется на терминале аэропорта.
Такая схема работы укладывается во все схемы перевозок, указанные в п. 1.1, поскольку может предполагать, а может и не предполагать следующего звена после перевозки вертолетом. В процессе транспортировки вертолетом груз остается на воздушном транспорте.
Задача вывоза из ОА возникает при таких схемах как доставка «от двери до двери», «терминал отправления до двери» получателя и при организации централизованного вывоза грузов с терминала ОА. Соответственно заказчиком перевозки грузов вертолетом может выступать экспедитор авиаперевозок или авиакомпания обслуживающая магистральные рейсы. Во всех случаях перевозка вертолетом считается отдельной перевозкой и оформляется отдельной авианакладной. Отношения между заказчиком перевозки и вертолетной авиакомпанией регулируются договором об оказании транспортных услуг.
Обычная технологическая схема основана на перегрузке через терминал аэропорта (перегрузка по прямому варианту оговаривается специально). Комплекты документов на грузы с доставкой до получателя через ОА вертолетом, поступают в службу организации перевозок вертолетной авиакомпании (рис. 1.2.1) после разгрузки прибывшего магистрального рейса. В зависимости от договорных отношений документы могут представляться или получателем (представителем получателя) заинтересованным в вывозе груза, или диспетчером группы доставки развозки или дежурным начальником склада ОА. Применительно к данному примеру возможно наличие в составе группы операторов занимающихся магистральными авиарейсами и оператора региональных авиарейсов организующего вертолетные перевозки. Для планирования передаются документы на грузы, по которым уже оплачены все необходимые сборы, то есть необходимо организовать только вывоз груза из ОА в пункт доставки расположенный в трудно доступном месте.
Аналогично описанным в п. 1.1 схемам документы на вывоз комплектуются по датам и планирование рейсов осуществляется вечером предыдущего дня. Планирование осуществляется диспетчером службы перевозок вертолетной компании. При прокладке маршрута используются эвристические методы, описанные в предыдущем параграфе. Следует отметить, что при организации вертолетных перевозок, наиболее часто используется назначение ВС по «географическому признаку» (разбиение района на зоны обслуживания с закреплением за каждой определенных ВС).
На рис. 1.2.1 представлена общая схема организации региональных авиаперевозок, сплошными стрелками показаны информационные, а штриховыми материальные потоки. Планирование рейсов осуществляется также исходя из характеристик имеющегося парка транспортных средств, действующих ограничений ресурсов грузоподъемности и требованиям к центровке ВС.
Пункты доставки в пределах региона лежат в труднодоступной местности часто не имеют специальных летно-технических сооружений и могут представлять собой всего лишь небольшую ровную площадку пригодную для посадки вертолета. В этом случае наиболее вероятной будет схема, по которой принимать груз с вертолета будет сам получатель. Поэтому диспетчер вертолетной компании оповещает клиентов о времени выполнения рейсов транспортирующих грузы в их адрес. Аналогично при отправке грузов клиенты заказывают у диспетчера вертолеты для транспортировки груза в ОА и дальнейшей его отправки магистральным рейсом. В этом случае перевозочная документация заполняется в ОА в представительстве авиакомпании на основании информации полученной по телефону или факсу и с пилотом вертолета доставляется в пункт отправления, где отправитель дополняет необходимую информацию и заверяет все экземпляры авианакладных (на перевозку вертолетом и на перевозку самолетом), оставляя у себя по одному экземпляру.
Возможны две схемы организации региональных авиаперевозок: 1) Количество и расположение пунктов доставки известно (все получатели так или иначе привязаны к ним). Составляется постоянное расписание, по которому производятся рейсы в данные пункты. При этом один рейс ВС может включать один или несколько пунктов. Вертолет завозит прибывшие грузы и забирает приготовленные для отправки. Общая загрузка ВС одна и та же, и равномерно (или в соответствующих долях) распределена между пунктами включенными в рейс. При комплектации отправки для конкретного пункта доставки решается задача о ранце (и при завозе и при вывозе). Расписание рейсов вертолетов увязано с расписанием магистральных авиалиний.
Метод оптимального планирования с использованием L— кратчайших маршрутов
Оптимизационная модель, основные соотношения. В предыдущем параграфе был рассмотрен алгоритм оптимального планирования, основанный на методе динамического программирования. На основе анализа работы алгоритма и приведенных примеров были сделаны выводы о том, что для решения транспортной задачи с большим количеством узлов метод динамического программирования в чистом виде не совсем подходит, поскольку механизм построения оптимального маршрута не учитывает возможностей развития цепочки на последующих шагах [29,53,54,76].
Развитие цепочек учитывает метод, основанный на использовании L -кратчайших маршрутов [52,55]. Введем в алгоритм новый параметр, который бы учитывал выше приведенный фактор. Пусть на каждом шаге регистрируются и запоминаются L - кратчайших маршрутов, причем в определенном порядке. На первом месте стоит самый кратчайший маршрут, соответствующий пошаговому оптимальному для метода динамического программирования, а остальные (L-\) записываются в порядке увеличения разницы между ними и оптимальным маршрутом. Порядок расположения кратчайших запоминаемых маршрутов обозначим номером и в дальнейшем будем называть рангом маршрута. Схема механизма принятия решения представлена на рис.2.2.1. При вычислениях на каждом шаге рассчитываются и запоминаются не один, как это было в алгоритме описанном в п.2.1, a L кратчайших маршрутов Мк , Мк2,..., Mkv,..., MkL, v=l,2,...,L и соответствующие значения целевой функции q vk(S).
При формировании начальных значений все v-ые целевые функции равны бесконечности, кроме тех, которые соответствуют формуле Приведенное выражение представляет собой преобразованную формулу (2.1.3) из предыдущего параграфа. где тіпД...} - v-oe наименьшее значение заключенной в фигурных скобках последовательности, зависящей от дискретной переменной Х=(/", v, /), Члены последовательности в первой строчке формируются путем перебора стоимости по двум переменным f и I. Для каждого варьируемого узла / просматривается L исходящих из него маршрутов, переменная оптимизации X включает дополнительно к выражению (2.1.7) параметр v- ранг запоминаемого кратчайшего маршрута. Ограничения на переменную X аналогичны приведенным в предыдущем параграфе. Оптимальный маршрут записывается следующим образом Учет условий (2.2.6) гарантирует допустимость маршрутов, исключая возможность заезда в данный пункт дважды. Если при некоторых v м S множество значений переменной X оказывается пустым, то значение целевой функции полагается равным бесконечности. Кратчайшие маршруты записываются следующим образом Условия остановки процесса оптимизации аналогичны алгоритму основанному на динамическом программировании. Вычисления прекращаются при к=2п, что обеспечивает включение в число анализируемых планов п - рейсовый маршрут. Алгоритм остановки процесса аналогичен представленному в п.2.1.
Алгоритм «L-кратчайших маршрутов». При введении нового параметра в алгоритм, в процесс построения оптимального маршрута добавились новые операции. Рассмотрим изменения, которые принесет введение нового параметра в алгоритм. Блок-схема алгоритма изображена на рис.2.2.2.
Основные корректировки коснулись той части алгоритма и программы, где производится построение оптимального маршрута. Однако некоторые корректировки произошли в программной части в целом. Поскольку кроме прежних параметров необходимо сохранять еще и ранг оптимального маршрута, то массивы сохраняющие эти данные (параграф 2.1, (2.1.9)), увеличат свою размерность
Аналогично используемые для записи параметров состояния So (п. 2.1, (2.1.10)) переменные превратятся в одномерные массивы, а массивы увеличат свою При использовании метода динамического программирования первые четыре массива были переменными, предназначенными для сохранения параметров найденного оптимального решения на к-ом шаге, а именно значения целевой функции на данном шаге, номера узла в который осуществляется шаг, типа транспортного средства которым осуществляется рейс и свободного ресурса грузовместимости ТС. При запоминании на каждом шаге нескольких кратчайших маршрутов, требуется запоминать v наборов этих параметров. Массив /kr[v] предназначен для хранения рангов маршрутов и осуществления процедуры ранжировки, то есть запоминания кратчайших маршрутов в порядке увеличения их целевых функций.
Для процедур нахождения, сохранения и ранжировки, осуществляемых в цикле, в программе используются несколько переменных г\, г2, /0, /ш, 12, все они соответствуют параметру v и имеют одинаковую с ним область значений. Рассмотрим общую схему алгоритма представленную на рис. 2.2.2, в основе своей она аналогична представленной в предыдущем параграфе. Первый раздел алгоритма реализуется в блоках 1 и 2 и осуществляет ввод исходных данных и формирование начальных значений.
В начале каждого шага для всего множества состояний S (нулевых и ненулевых) массивам, указанным в выражении (2.2.10) в блоке 1 присваиваются нулевые значения. После чего следуют циклы поиска решений сопровождаемые ограничениями типа (2.2.3) или (2.2.6) в зависимости от раздела алгоритма. Ограничения расположены в общей схеме в том же порядке, что и для метода динамического программирования. Однако сразу же после нахождения очередного допустимого решения начинается перебор v вариантов (для начальных значений
Возможность коррекции найденного плана перевозок. Ручная коррекция плана перевозок
В предыдущих разделах уже упоминалось, что при тестировании в ряде случаев программа выдавала план перевозок, имеющий возможность дальнейшего улучшения и приводились методы повышения эффективности алгоритма, такие как увеличение параметра L и введение изменяющихся параметров близости. Эти меры существенно улучшили качество находимых программой планов доставки, но не устранили полностью необходимости внесения изменений в план перевозок, созданный в результате работы программы. Воздействие предложенных методов ограничено характеристиками ЭВМ, кроме этого иногда диспетчер может посчитать, что имеется возможность дальнейшего улучшения плана, даже если ее нет на самом деле. Это возможно при большом количестве клиентов, типов транспортных средств, что затрудняет восприятие диспетчером целостной картины с учетом всех условий. Необходимость коррекции может возникнуть, исходя из изменения каких либо факторов, не учитываемых программой (изменении состава парка транспортных средств, внешней политики фирмы и т.п.). Такая ситуация наряду с планом предложенным программой допускает наличие других планов и требуется возможность их проверки, сравнительного анализа с целью дальнейшего улучшения окончательного плана доставки.
Необходима процедура коррекции позволяющая диспетчеру, после выдачи программой плана перевозок, внести в него необходимые изменения и сравнить показатели откорректированного плана с планом перевозок найденным программой.
Все методы коррекции имеют несколько общих отличительных черт, а именно: 1) метод применяется после выдачи программой начального плана перевозок для заданных условий; 2) улучшение, как правило, касается не всего плана, а некоторой его части (одноузловых или многоузловых рейсов, которые можно объединить или изменить структурный состав с явным выигрышем по расстоянию и загрузке); 3) все методы коррекции могут и должны быть оформлены в виде рабочих режимов программы в составе пользовательского интерфейса. Методы различаются между собой степенью участия в процессе коррекции пользователя и компьютера и в данном аспекте определены как ? ручная коррекция; ? полуавтоматическая коррекция; ? автоматическая коррекция.
1) Ручная коррекция. После выдачи на экран графика маршрута, диспетчер видит несколько рейсов, которые кажутся ему нерациональными, может предложить конкурирующие варианты. В режиме ручной коррекции диспетчер помечает узлы нерациональных рейсов и вводит для них и только для них новый маршрут. Новый план перевозок представляет собой комбинацию оптимальных рейсов программы и рейсов составленных диспетчером. Метод требует отдельной экранной формы (для выделения узлов для коррекции и составления нового маршрута), возможности для сравнительной оценки результатов машинного и комбинированного вариантов, возможности возврата предыдущего варианта. Изменения касаются в основном интерфейса и минимальны в программной части, реализующей непосредственно алгоритм. Метод годится для исправления простых несоответствий (с двумя или тремя одноузловыми маршрутами и т.п.) в примерах с небольшим количеством клиентов и проверки вариантов перспективных сточки зрения диспетчера.
2) Полуавтоматическая коррекция. После выдачи результата в графической форме на дисплей диспетчер видит несколько нерациональных или подозрительных рейсов, но поиск очевидного решения визуально затруднен (значительное количество несоответствий, трудная для визуального восприятия схема расположения клиентов и т.п.). В режиме полуавтоматической коррекции диспетчер помечает узлы подозрительных рейсов и запускает режим коррекции. По команде запуска, программа повторяет процесс оптимизации только для выделенных узлов. План также представляет собой комбинацию оптимальных рейсов основного варианта и вновь найденных. Метод не требует отдельной экранной формы, желательна лишь возможность сравнительной оценки предыдущего и вновь найденного результатов, но только с целью оценки улучшения. Характерны незначительные изменения в интерфейсе и более масштабные в тексте программы. Метод годится для проверки возможности улучшения плана и исправления нерациональных рейсов.
3) Автоматическая коррекция. Метод не требует выдачи на экран плана перевозки. Вводится одна процедура для оценки оптимальности каждого рейса найденного маршрута (например, по степени использования грузоподъемности транспортного средства) и если находятся рейсы, не удовлетворяющие ей, маршрут на экран не выводиться. Все рейсы, прошедшие процедуру запоминаются, а для узлов, не вошедших в эти рейсы, процесс оптимизации повторяется еще раз. Метод очень схож с предыдущим, но определение нерациональных рейсов выполняет не оператор, а машина. Метод не требует изменений в интерфейсе, а только в программной части и повышает качество плана выдаваемого диспетчеру.
Планирование городских перевозок автотранспортной и экспедиторской компании
ООО "Невско-Балтийская транспортная компания" осуществляет централизованный завоз и вывоз малотоннажных контейнеров грузобагажа со станции "Московская-товарная", а так же городские перевозки. Состав парка транспортных средств используемых при организации завозы и вывоза грузов представлен в табл. 4.3.1. Выделены следующие основные задачи: 1. Завоз и вывоз груженных трех- и пятитонных контейнеров. 2. Завоз и вывоз грузобагажа (тарно-штучные грузы в разном количестве). 3. Доставка материалов со склада на объекты с целью обеспечения производственного процесса. Регион обслуживания компании представляет собой прямоугольник размером [-100,100]х[-100,100] км с началом координат на терминале ж/д станции или терминале крупной промышленной или строительной компании, обозначенными на рисунках нулем. Вариант 1. Требовалось осуществить завоз трех и пятитонных контейнеров у п=20 отправителей. Характеристики парка представлены в табл. 4.3.1 (позиции№1,2). Отметим, что грузоподъемность и размеры кузова позволяют ЗИЛ-431510 перевозить два 3-х тонных контейнера одновременно. Первоначально составлен план с использованием только бортового автомобиля ЗИЛ-431510. План состоит из четырнадцати рейсов. Все клиенты, имеющие трех тонные контейнеры, объединены в рейсы по два узла в каждом (0-1-8-0, 0-2-12-0, 0-4-18-0, 0-7-14-0, 0-10-11-0, 0-17-19-0).
Эти рейсы обеспечивают полную загрузку транспортного средства. Клиенты, имеющие пятитонные контейнеры, объезжаются поочередно, поскольку, каждый пятитонный контейнер занимает 90% ресурса грузоподъемности ТС. Суммарный расход топлива =640,78 л (рис.4.3.1). При контейнерных перевозках может также использоваться тягач ГАЗ-4310 совместно с прицепом. Он более экономичен по сравнению с ЗИЛ-431510 и способен перевозить пяти тонные контейнеры и также трехтонные (только по одному за рейс). План перевозок с использованием обоих типов ТС представлен на рис.4.3.2. Данный план включает в себя четырнадцать рейсов. Все пятитонные контейнеры перевозятся ГАЗ-4301. Это рейсы 0-3-0, 0-5-0, 0-6-0, 0-9-0, 0-13-0, 0-15-0, 0-16-0 и 0-20-0, имеющие стопроцентную загрузку. Все остальные рейсы являются двух узловыми аналогичными представленным на рис.4.3.1. и выполняются ЗИЛ-431510. Общий расход топлива составил =616,40 л. Таким образом, введение более экономичного транспортного средства позволило сэкономить 24,38 литра за один день. Выполнения всего плана перевозок автомобилями ГАЗ-4301 не дает улучшения плана, поскольку ресурс грузоподъемности ГАЗ-4301 не позволяет перевозить два трехтонных контейнера одновременно, и план перевозок будет состоять из двадцати рейсов (Приложение 10, рис.П.10.1). Разница в расходе топлива между ГАЗ-4301 и ЗИЛ-431510 невелика и не только не покрывает увеличения суммарных затрат топлива на выполнение нового плана. Из-за значительного увеличения количества рейсов общий расход топлива составил 755,63 л, что на 139,23 л больше, чем в плане перевозок с использованием ТС обоих типов.
При завозе и вывозе малотоннажных контейнеров с ж/д станции а также при перевозке контейнеров по городу можно использовать тягачи КАМАЗ-5320 с прицепами ОДАЗ-93571, характеристики представлены в табл. 4.3.1 в строке 4. ООО «Невско-Балтийская транспортная компания» имеет ограниченное количество таких машин, поэтому их используют только при высоком объеме перевозок малотоннажных контейнеров для высвобождения автомобилей ЗИЛ-431510 на перевозки грузобагажа. Использование КАМАЗа-5320 дает также значительную экономию топлива за снижения количества рейсов, при одинаковом расходе топлива сЗИЛом-431510. С использованием автомобилей КАМАЗ-5320 и ГАЗ-4301 количество рейсов сократилось с четырнадцати до семи (Приложение 10, рис.П.10.2). ГАЗ-4301 выполняет только два рейса 0-20-0 и 0-9-0, оба со стопроцентной загрузкой. КАМАЗ-5320 выполняет три четырех узловых рейса с полной загрузкой (0-10-11-4-15-0, 0-17-19-6-1-0 и 0-13-12-2-18-0), трех узловый рейс 0-16-8-5-0 загруженный на 92,85% и трех узловый рейс 0-7-14-3-0 с загрузкой 78,57%. В среднем, использование ресурса грузоподъемности составляет 95,91%, в то время как для варианта 1 с использованием ГАЗ-4301 и ЗИЛ-4315120 - 94,66%. Общий расход топлива составляет =358,78 л, что на 257,62 меньше, чем требуется для плана с использованием ЗИЛа-431510 и ГАЗа-4301. Таким образом, программа позволяет практически реализовать преимущества заложенные в использовании комбинированного транспортного парка. Вторым важным направлением работы автотранспортной компании является организация завоза и вывоза грузобагажа. Грузобагаж составляют тарно-штучные грузы. Грузы, упакованные в транспортную тару, могут приниматься к перевозке как пакетированном так и не в пакетированном виде. Размеры грузовых партий колеблются 0,1 до 11,0 т. Основной состав отправок представляют собой партии от 1 до 5,5 т. Большинство грузов являются промышленной продукцией или полуфабрикатами и нормально сочетаются при совместной перевозке. В случае перевозки активных веществ или опасных грузов для их перевозки выделяются отдельные автомобили и составляется отдельный план таких перевозок. Вариант 2 (Приложение 10, рис.П.10.3). Необходимо осуществить вывоз груза со станции для п=20 получателей. Для завоза вывоза грузобагажа используются автомобили ЗИЛ-431510. Первоначальный план перевозок составлен с учетом использования ЗИЛ-431510. План состоит из тринадцати рейсов. Пять рейсов имеют полную загрузку (0-13-17-0, 0-19-16-0, 0-10-5-0, 0-1-11-0 и 0-14-9-0). Все они представляют двух узловые комбинации партий по одной и пять тонн или двух партий по три тонны. В узлы 6 и 20 необходимо доставить по пять тонн, а в узлы 15, 7, 3 и 8 по четыре тонны, что делает невозможным комбинирование их с другими узлами из-за ограничения грузоподъемности, поскольку трех узловый рейс 0-18-2-4-0 также имеет загрузку четыре тонны, а узел 12 содержит три тонны груза.
