Содержание к диссертации
Введение
Глава 1. Анализ известных методов и задач планирования завоза/вывоза грузов с учетом фактора времени 14
1.1.Анализ организационных схем завоза/вывоза грузов на грузовые терминалы 14
1.2.Анализ организационных схем завоза/вывоза грузов вертолетной авиацией... 29
1.3 Анализ организационных схем экспресс-доставки грузов и поставок в транспортно-логистических системах 35
Выводы 44
Глава 2. Синтез моделей функционирования систем завоза/вывоза грузов 47
2.1.Синтез модели организации завоза/вывоза грузов по топологическому принципу 47
2.2.Синтез модели организации завоза/вывоза с учетом фактора времени 52
2.3. Анализ возможности применения известных методов для решения задач обоснования оптимальных планов завоза/вывоза 57
Выводы 76
Глава 3. Алгоритм оптимального планирования завоза/вывоза с временным сервисом 78
3.1.Модель процесса оперативного планирования завоза/вывоза с использованием L-кратчайших маршрутов 78
3.2. Алгоритм определения L-кратчайших маршрутов в процессе оперативного планирования завоза/вывоза 84
3.3.Модификация алгоритма для обеспечения возможности учета фактора времени 90
3.4. Вариант реализации алгоритма определения L-кратчайшего пути для решения задачи оперативного планирования завоза/вывоза 99
Выводы 106
Глава 4. Рекомендации по внедрению предлагаемых моделей и алгоритмов в практику оперативного планирования завоза/вывоза грузов 109
4.1.Адаптация программного комплекса для оперативного планирования завоза/вывоза вручную с учетом фактора времени 109
4.2. Рекомендации по использованию алгоритма оперативного планирования завоза/вывоза в режиме совместной работы с коммерческими пакетами прикладных программ 118
4.3.Рекомендации по практическому внедрению формализованных задач завоза/вывоза с временным сервисом на основе эвристических алгоритмов оценки маршрутов 126
Выводы 136
Заключение 139
Литература 142
Условные обозначения 152
- Анализ организационных схем экспресс-доставки грузов и поставок в транспортно-логистических системах
- Анализ возможности применения известных методов для решения задач обоснования оптимальных планов завоза/вывоза
- Алгоритм определения L-кратчайших маршрутов в процессе оперативного планирования завоза/вывоза
- Рекомендации по использованию алгоритма оперативного планирования завоза/вывоза в режиме совместной работы с коммерческими пакетами прикладных программ
Введение к работе
Актуальность темы. Тенденции развития рынка транспортных услуг в Российской Федерации однозначно свидетельствуют о все большем внимании транспортных и экспедиторских компаний к методам повышения эффективности управления как одного из наиболее перспективных направлений повышения своей конкурентоспособности. Начиная с 1990г. при вхождении в мировой рынок началось активное внедрение в наших транспортных предприятиях западных систем управления. При этом, как правило, не уделялось должного внимания анализу применимости этих методов в сложившихся рыночных условиях. В результате, сохраняя общую для страны тенденцию, российские транспортные компании попали в жесточайшие условия конкуренции, оказавшись не в полной мере подготовленными к работе в таких условиях. Еще одним отрицательным фактором явилась общая нестабильность процессов реформирования экономической системы страны. Тем не менее, в таких тяжелейших условиях достаточно большое количество российских компаний, работающих на рынке перевозок и экспедирования на всех видах транспорта, сумели наладить производственный процесс. Причем самой доходной частью, вполне естественно, стали международные перевозки, что было обусловлено ростом товарооборота между Россией и западными странами. В основном за счет международного сектора более или менее поддерживалась транспортировка грузов и внутри России.
Со временем, однако, различие в этих двух сферах отрасли, внутренней и внешней, стало расти. Неравенство еще более усугубилось тем, что и на государственном, и на корпоративном уровне высшие приоритеты отдавались международным транспортным каналам. Между тем на Западе в рамках глобализации и создания единого мирового экономического пространства наблюдалось сближение и сращивание систем международных и внутренних перевозок. Это вполне отвечало доминированию весьма популярных принципов логистического подхода - «от двери до двери» и «точно в срок», позволявших получать значительные экономические выгоды в конкурентной борьбе клиентов.
Начиная с 1999 года обстановка в сфере перевозок в России стала постепенно нормализоваться, и на практике отчетливо обозначились ряд характерных особенностей рынка транспортных услуг в РФ. Произошло разделение клиентов по видам транспорта, что привело к более четкому выделению грузопотоков. Наметившийся экономический рост соответственно привел к росту перевозок.
Тем не менее, большинство компаний заинтересованы в укрупнении грузопотоков, перевозимых отдельными видами транспорта при посреднической деятельности этих компаний. В целях упрочнения своего положения фирмы, работающие на различных видах транспорта, комбинируются (кооперируются) друг с другом для выполнения интермодальных перевозок. В этих условиях аналогами зарубежных логистических центров становятся места сосредоточения грузов: терминалы аэропортов, морских и речных портов, грузовые дворы, и склады железнодорожных станций. В данных пунктах имеется возможность не просто пропускать большие партии грузов, но и комбинировать их, оптимизируя таким образом грузопоток. Появилась потребность в новых методах обработки грузов и планирования перевозок. Перспективы развития экономики непосредственно связаны с повышением эффективности управления транспортными процессами, в частности, перевозками грузов.
Субъектами рынка транспортных услуг, обеспечивающими формирование грузовой базы воздушного транспорта, являются авиакомпании, их агенты и экспедиторские компании, специализирующиеся на воздушных перевозках. Эти компании часто владеют собственными терминалами или арендуют терминалы аэропорта и обеспечивают на них накопление и консолидацию отправок. Агенты и экспедиторы обеспечивают не только передачу грузов в грузовые службы аэропортов, но и организуют прием грузов со склада отправителей с доставкой в аэропорт, планирование и организацию вывоза грузов с терминалов аэропортов «до двери» получателей.
В развитие этих функций некоторые экспедиторы становятся договорными перевозчиками, выдавая от своего имени сквозной транспортный документ на перевозку от отправителя до аэропорта назначения или «от двери до двери».
Авиакомпании, традиционно занимающиеся воздушными перевозками между аэропортами, в условиях обострившейся конкуренции расширяют свои функции и переходят на организацию доставки «от двери до двери». Эти компании через свои филиалы организуют завоз и вывоз грузов на терминалы аэропортов.
Активную позицию в этих вопросах, занимают грузовые службы аэропортов, не только поощряющие развитие таких перевозок, но и самостоятельно организующие завоз и вывоз грузов по договорам для всех субъектов рынка перевозок. Ключевое положение грузовых служб аэропортов в обработке грузов на терминале и при перемещении их между терминалом и бортом ВС, а также совместная работа с авиакомпаниями при организации воздушных перевозок, позволяют организовывать перевозки по принципу «от двери до двери», включая доставку грузов в аэропорт и саму воздушную перевозку в составе логистической системы поставок в качестве технологического звена.
Перевозки подобного рода являются наиболее перспективными в настоящий момент, поскольку позволяют гибко связать процесс производства с процессом реализации товара с минимальными транспортными затратами на всех этапах логистической цепи. В развитии этого направления заинтересованы крупные торгово-промышленные компании, стремящиеся встроить транспортные процессы в сферу своей деятельности в качестве равнозначной составляющей. Однако, для обеспечения наиболее полного и гибкого взаимодействия необходимо выполнение и второго принципа «точно в срок».
Это обстоятельство подчеркивает сложившийся разрыв между международной и внутренней составляющими рынка услуг доставки. Для повышения конкурентоспособности российских транспортных компаний и их эффективной деятельности в области логистики необходимо повысить уровень организации перевозок внутри Российской Федерации до мирового уровня.
Важную роль в организации перевозок играет процесс планирования, учитывающий расположение грузовой клиентуры, размеры грузовых партий, характеристики парка транспортных средств. Для транспортно-логистических систем при поставках «от двери до двери» вопросы организации централизованного завоза и вывоза грузов на терминалы являются важными на любом виде транспорта, а также при смешанных перевозках. Оптимальное планирование облегчает управление перевозками и сводит к минимуму возможные корректировки в ходе выполнения плана. Наличие и величина положительного результата определяется эффективностью использования парка транспортных средств (ТС) с учетом условий перевозки. Возможность использования ТС, различных по техническим и экономическим характеристикам, предполагает возможность использования большого количества допустимых планов перевозки для одного набора заявок, и даже приблизительная оценка диспетчером перевозок каждого из них с целью выбора оптимального является трудоемким процессом. С ростом грузопотока увеличивается время планирования и понижаются качественные характеристики плана перевозок.
Повысить качество планирования можно, используя современные ЭВМ, программное обеспечение, использующее аппарат математического моделирования систем и процессов. Условия оперативной деятельности транспортных и логистических компаний требуют программного продукта, позволяющего, используя стандартный набор исходных данных, составить оптимальный план перевозок с учетом особенностей комплекта заявок и имеющегося в наличии или предполагаемого парка ТС. Результаты работы программы должны представлять диспетчеру транспортной компании четкую картину планируемой оперативной обстановки, позволять принимать управляющие решения (заказ ТС, распределение заданий водителям, определение порядка загрузки ТС, выделение ресурсов ГСМ), обеспечивать производственный процесс необходимыми документами (путевые листы, план погрузо-разгрузочных работ). Таким образом, возникает объективная потребность в повышении степени автоматизации процесса принятия решений при организации перевозок, резкого снижения субъективной роли диспетчера. Алгоритмы, реализующие процесс поиска оптимального плана перевозок, должны разрабатываться на базе математических моделей, адекватно описывающих характерные особенности реальных транспортных систем, содержащих в себе подобные процессы.
К настоящему времени явно наблюдается на практике спрос на новые методы оптимального планирования и специальное программное обеспечение. Он сформирован большим количеством самостоятельно действующих на рынке транспортно-логистических компаний и экспедиторских фирм и их стремлением к повышению уровня своей конкурентоспособности. Кроме этого, на российском рынке транспортных услуг набирает силу и новая система экспресс-доставки грузов, построенная на принципах транспортной логистики. При этом фактор времени «точно в срок» является показателем качества доставки груза «от двери до двери», своеобразным товарным брендом. На российском рынке уже в настоящий момент действуют все мировые лидеры в области экспресс-доставки грузов. Российские компании также проявляют повышенный интерес к данной сфере транспортных услуг. Поэтому постоянное обновление методов оптимизации и разработка новых алгоритмических и программных средств в данной области является одной из основных задач. Указанные обстоятельства обуславливают высокую практическую актуальность темы настоящего исследования.
Методы оптимизации процессов, предназначенные и для решения транспортно-ориентированных задач, разрабатывались в математике с середины 20-го века. Математическим моделям транспортных систем, постановкам таких задач и методам их решения посвящены работы А.С.Беленького, А.Э.Горева, П.А.Кравченко, Г.А.Крыжановского, Е.А.Куклева, ИЛМеламеда, С.М.Резера, М.И.Рубинштейна, СИСергеева, И.Х.Сигала, Y.Dumas, M.M.Solomon, L.D.Bodin и других. К настоящему времени исследованы основные задачи транспортной оптимизации, отражающие способы организации перевозок при концентрации или разделении грузопотоков. Разработано множество алгоритмов, основанных на методах математического программирования и позволяющих получать оптимальные или близкие к ним решения для отдельных постановок. Очень часто весьма перспективные методы, позволяющие решать задачи с высокой степенью сложности и большим количеством ограничений, не могли быть реализованы на практике из-за сложности формализованного описания и объективных трудностей при формировании адекватных исходных данных. Первоначальное распространение получили лишь наиболее простые методы или частные случаи решения конкретных задач. С появлением и развитием электронно-вычислительной техники возможности использования различных методик расширились, хотя и в известных пределах, ограниченных уровнем технического развития.
Анализ работ по данным направлениям показал, что, несмотря на большое количество существующих работ, близких по тематике, вопросы завоза и вывоза грузов с использованием парка из нескольких типов ТС с учетом фактора времени нельзя считать исследованными исчерпывающим образом. В большинстве постановок задач приоритет отдается или минимизации затрат, или минимизации времени. Известные методы поиска оптимальных решений имеют определенные трудности при программной реализации.
В настоящий момент, когда уровень техники весьма высок, а возможности компьютеров настолько велики, что позволяют всерьез говорить о создании информационного общества, стала возможной реализация новых технологий транспортной работы на базе математических методов оптимизации, позволяющих создавать компьютерные программы, гибко реагирующие на условия внешней среды. Поэтому разработка алгоритма поиска оптимального решения для задачи завоза/вывоза груза с учетом фактора времени, позволяющего находить оптимальные или близкие к ним решения, легко программируемого и адаптируемого к планированию перевозок на различных видах транспорта, является весьма актуальной и с научной точки зрения.
Научная задача - синтез обобщённой модели функционирования системы завоза/вывоза по топологическому принципу с учётом фактора времени и разработка алгоритма оптимального планирования с временным сервисом.
Цель работы: автоматизация и оптимизация деятельности должностных лиц транспортно-экспедиторских фирм и логистических торгово-промышленных компаний в ходе решения задачи оперативного планирования, завоза/вывоза с временным сервисом.
Объект исследования. Объектом исследования является транспортно логистическая система, включающая терминал нового поколения, осуществляющий концентрацию и распределение грузов в пределах определенного региона, диспетчера перевозок, ответственного за планирование и организацию перевозок, автоматизированное рабочее место диспетчера перевозок, грузовую клиентуру, расположенную в пределах региона, парк включающий один или несколько типов ТС. Методы исследования. Методической основой для исследования послужили работы отечественных и зарубежных ученых в области математического моделирования транспортных задач и методов программирования, а также работы в области управления транспортом, нормативные документы, регламентирующие работу воздушного и автомобильного транспорта.
Для достижения цели на первом этапе исследований был выполнен анализ задачи оптимального планирования концентрации и распределения грузопотоков на современном рынке транспортных услуг с учетом фактора времени и выделены характерные особенности таких задач, дана математическая формулировка задачи оптимизации, отражающей эти особенности.
Проведен анализ известных задач математической оптимизации, выявлены их сходства и различия с поставленной задачей. Дан обзор и анализ методов решения задач оптимизации, исследована возможность их применения к поставленной задаче, обоснован выбор базового метода разработки программно-алгоритмических средств.
На третьем этапе была разработана модель процесса оперативного планирования завоза/вывоза на основе использования метода L-кратчайших маршрутов и предложена процедура модернизации базового метода и алгоритмы поиска оптимального решения - плана перевозок, представляющего собой схему объезда клиентов с назначением на рейсы ТС определенного типа с целью минимизации транспортных расходов при выполнении сервиса по времени доставки груза для каждого клиента.
Для проверки работоспособности предложенных моделей, алгоритмов и процедур на четвертом этапе были проведены экспериментальные работы по внедрению их в практику, и на этой основе сформулированы рекомендации по внедрению полученных результатов в процесс оперативного планирования завоза/вывоза грузов. Научная новизна заключается в синтезе модели процесса завоза/вывоза, учитывающей новые ограничения и временные показатели качества функционирования современного транспортного предприятия, а также в разработке модифицированного алгоритма решения задачи оптимизации, процесса завоза/вывоза с временным сервисом.
Практическая значимость. Практическая значимость работы заключается в обеспечении возможности:
использовать предложенный комплекс алгоритмических и программных средств должностными лицами транспортно- логистических компаний, занимающихся завозом/вывозом и организацией экспресс-доставки грузов:
-проанализировать с учетом текущей оперативной ситуации по распределению грузопотоков, характеру сервиса времени доставки и располагаемому парку ТС различные варианты доставки грузов и принять наиболее рациональный к исполнению, с сохранением альтернативных планов на случай возможного изменения оперативной обстановки;
-автоматизировать процессы планирования, принятия управляющих решений и необходимого документооборота при организации завоза и вывоза грузов на терминалы;
-определить приоритет использования ТС с различными характеристиками для выполнения определенного комплекта заявок.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на: конференциях и межвузовских тематических семинарах.
Результаты исследований и основные положения диссертационной работы опубликованы в 6 печатных работах.( 18,19,26,27,28,29)
«Методический подход к оценке эффективности функционирования транспортно логистической системы интермодальных перевозок компании с использованием перспективных телекоммуникационных систем», «Общие принципы формирование защищенных информационных каналов обслуживания интермодальных транспортных коридоров», «Методический подход для моделирования и анализа функционирования логистических систем», «Обеспечение безопасности информационных каналов интермодальных транспортных коридоров», «Имитационное моделирование функционирования логистической системы доставки грузов автомобильным транспортом», « Обоснование топологии информационных каналов контроля пропускной способности и эффективности функционирования интермодальных транспортных коридоров».
Положения, выносимые на защиту:
1.Синтезированная обобщённая модель функционирования системы завоза/вывоза более адекватно отражает такие организационные особенности и экономические реалии транспортного производства, как доставка «точно в срок», чем ранее известные.
2 Алгоритм оптимального планирования завоза/вывоза с временным сервисом позволяет получить оптимальный план завоза/вывоза, учитывающий, в отличие от ранее разработанных, требования клиента по времени доставки. З.Программные приложения, реализующие алгоритм оптимального планирования завоза/вывоза с временным сервисом, и рекомендации по их интеграции в пакеты прикладных программ транспортного предприятия позволяют реализовать полученные результаты при автоматизации и оптимизации деятельности должностных лиц транспортно-экспедиторских фирм и логистических компаний в ходе решения задач оперативного планирования.
Работа изложена на 152 страницах, включает 30 рисунков и 1 таблицу.
Анализ организационных схем экспресс-доставки грузов и поставок в транспортно-логистических системах
В настоящее время под крупными промышленными логистическими системами (ЛС) понимают, как правило, взаимосвязанную совокупность пространственно распределенных производственных и транспортных подсистем, обеспечивающих, наряду с производством, поставку товаров в пределах крупных регионов и государств. Логистические системы относят к классу компьютерно-интегрированных систем. Появление и развитие локальных, региональных и глобальных компьютерных сетей существенно повысило координацию, возможность взаимодействия и использования гибких систем управления участниками ЛС [29,60,67,82].
Основной причиной возникновения на практике естественных процессов формирования интегрированных транспортно-производственных логистических систем, является объективная потребность повышения эффективности организации производства и поставок товаров конечному потребителю, поэтому в логистических системах все большую роль играет не только технические и потребительские свойства самого товара, но и такие параметры каналов доставки готового продукта и комплектующих узлов, как надежность, стоимость и время доставки [42]. Минимизация собственно логистических издержек на хранение и доставку товаров становится фактором, определяющим выживание фирмы в условиях современного насыщенного рынка и растущей конкуренции.
Собственные логистические системы создают торговые компании, самостоятельно в условиях рынка формирующие свои каналы поставок и распределения товаров. В настоящее время компании-производители товаров широкого спроса уделяют большое внимание вопросам организации сбыта своей продукции. Проводятся крупные маркетинговые мероприятия информационного характера. Организованы крупные сети специализированных и универсальных торговых центров такие как «Офис Клаб», «Лента», «Метро» в Петербурге. Анализ показывает, что отличительной особенностью таких сетей является наличие в их структуре дистрибуционных (распределительных) центров (ДЦ). Дистрибуционные (распределительные) центры становятся обязательным элементом в структуре торгово-транспортных предприятий. Типовая схема организации поставок через дистрибуционный центр представлена на рис. 1.4..
Магазины (М}, М?,..., М„) работают с дистрибуционным центрами напрямую или через регионального торгового представителя (РТП1,..., РТПк) ДЦ, за каждым из которых закрепляется своя клиентская сеть. Магазины заказывают товары торговому представителю, который передает их далее в ДЦ для исполнения. Исходные товары закупаются распределительным центром у оптовых поставщиков (ПІ, П2,..., Щ), число которых может достигать 1000 и более. За каждым поставщиком стоит вполне определенный производитель товаров (Пр1, Пр2,..., Прк). поставок через дистрибуционный центр Распределительные центры собирают мелкие заявки, группируют их по каждому наименованию, закупают крупные партии у оптовых продавцов, организуют доставку товаров на сортирующую линию, сортируют поступившие товары по заказам, группам товаров и осуществляют доставку клиентам в кратчайшие сроки.
Доставка грузов по линии Поставщик - ДЦ осуществляется либо собственным транспортом, либо внешней транспортно-экспедиторской фирмой (ТЭК) (или несколькими фирмами). На рис. 1.4. фирма, осуществляющая перевозку от поставщиков, обозначена ТЭК1. Развозка заказов клиентам осуществляется ТЭК2 или же собственным транспортом ДЦ (часто ДЦ пользуется услугами одной ТЭК для решения всех транспортных вопросов).
Целью формирования интегрированной логистической системы, элементом которой является ДЦ, является создание объективных предпосылок для повышения эффективности организации поставок товаров в широкую пространственно-распределенную (в пределах крупного региона) сеть розничных продавцов. При этом в качестве показателя эффективности используют, как правило, векторный показатель, элементами которого являются частные показатели: степень удовлетворения спроса по широкому классу номенклатур товара, сроки доставки товара потребителю, транспортные и складские издержки и.т.п.
С точки зрения клиентов дистрибуционные центры являются универсальными мелкооптовыми продавцами - поставщиками.
Планирование всех работ по исполнению заказов и управлению грузопотоком осуществляется информационно-вычислительным центром (ИВЦ). Информационно-вычислительный центр связан локальной сетью со всеми точками управления грузопотоками внутри ДЦ - терминалами зоны приемки, загрузчиков, комплектовщиков, площадок отгрузки, а также каналами связи со всеми внешними участниками логистической системы - складами поставщиков, экспедиторами, торговыми представителями, клиентами. Организуя поставки, ИВЦ ДЦ планирует транспортно-логистические процессы в последовательности, обратной физическому движению товаров. При этом решаются следующие задачи; - по линии «ДЦ - клиент» -составление расписаний отгрузки и плана-графика подачи транспортных средств, оптимального распределения заказов клиентов по транспортным средствам, оптимальной загрузки и комплектации рейсов, составление оптимальных планов вывоза грузов с ДЦ и маршрутов завоза товаров клиентам, нахождения кратчайших маршрутов на сети между ДЦ и его клиентами, между двумя последовательными получателями товаров; - по линии «Поставщики товаров-» ДЦ» решаются аналогичные задачи оптимизации процесса завоза грузов на сортирующую линию или склад распределительного центра.
Как показывает анализ организации работы существующих ДЦ, эти задачи дистрибуционным центрам приходится решать ежедневно, при новых исходных данных, как правило, в процессе оперативного управления в соответствии с текущей складывающейся ситуацией.
В компаниях-производителях товаров массового потребления часто функции дистрибуционного центра выполняют отделы поставок этих компаний. Но в условиях современного рынка такие компании-производители систематически меняют номенклатуру выпускаемых товаров и расширяют ее. Поскольку часто они располагаются в корпусах старых предприятий-гигантов, то в одном корпусе могут располагаться поточные линии нескольких предприятий, и выпуск нового вида продукции требует лишь установки дополнительной поточной линии.
Анализ возможности применения известных методов для решения задач обоснования оптимальных планов завоза/вывоза
Задачи оптимального планирования на транспорте охватывают сферу оперативного и стратегического управления транспортным предприятием [1,2,3,4,71,72]. Постановка зависит от вида транспорта и сферы принятия решения (маршрутизация, загрузка, экономическое планирование, управление запасами, распределение потоков). Как правило, задача формулируется для отдельных видов транспорта, мультимодальных перевозок, транспортных узлов, складских комплексов, предприятий транспортной инфраструктуры.
Поэтому решение задачи оптимального планирования, сформулированное в п.2.2, может производится, сведением её к одной из «классических» задач оптимизации, для которой существуют эффективные численные методы, или разработкой специальных методов и алгоритмов, учитывающих специфику задачи [1]. В этом аспекте в интересах достижения целей настоящей работы был проведен анализ известных методов.
На стадии планирования перевозок грузов, когда возможен более чем один маршрут перевозки, возникает задача выбора наиболее рациональной схемы движения транспортных средств. Задача выбора рациональных или оптимальных схем перемещения грузов между конечным числом пунктов называют задачами маршрутизации транспортных средств.
Исходными данными являются объемы перевозок, типы транспортных средств и их характеристики, затраты на эксплуатацию ТС, схема размещения пунктов с указанием связующих их магистралей и их протяженности.
Рациональность и оптимальность маршрутов определяется размерами затрат на перевозку, длинами маршрутов, числом ТС, достаточных для обеспечения перевозок по этим маршрутам. Рациональными считаются те маршруты, которые обеспечивают выполнение ограничений на требуемые значения перечисленных показателей, а оптимальными - маршруты, которые обеспечивают их наилучшие, с точки зрения пользования, значения.
К задачам маршрутизации относятся как задача маршрутизации грузов, так и задача маршрутизации транспортных средств при заданных схемах перемещения грузов. Задача завоза/вывоза грузов, сформулированная в п.2.2, может быть отнесена к последнему классу задач, хотя она имеет сходные элементы и с задачами других групп, которые будут рассмотрены ниже. В качестве типовых примеров, следует указать следующее формулировки задач маршрутизации.
Маршрутизация движения судов [5]. При организации фидерного обслуживания морских портов для базового порта, в который заходит линейное судно, завоз и вывоз контейнеров осуществляется определенным количеством фидерных судов, связывающий базовый и тяготеющие к нему порты линии. В зависимости от числа судов, используемых для фидерного обслуживания, задача составления маршрутов движения судов формируется как задача одного или нескольких коммивояжеров с временными окнами.
Задачей планирования является определение минимального по общей стоимости маршрута завоза и вывоза контейнеров совместимого с расписанием движения линейных судов. Параметры, подлежащие определению: количество портов, обслуживаемое одним судном, и порядок захода судна в порты. Судно должно быть способно взять груз из всех портов рейса. Необходимо определить количество рейсов для каждого судна так, чтобы время выполнения всего плана фидерных перевозок не превышало интервала захода линейного судна в центральный порт.
Как и в задаче, сформулированной в п.2.2, здесь имеется центральный пункт и несколько пунктов завоза грузов, расположенных в пределах региона. Однако, наиболее важным ограничением является фактор времени, обеспечивающий согласование фидерных и линейных перевозок.
Планирование перевозок овощей [11]. Требуется имеющимися автомобилями с одного базового пункта доставить сельскохозяйственную продукцию п потребителям. Известна матрица расстояний между всеми пунктами. Маршруты движения автомобилей должны удовлетворять ограничениям по грузоподъемности, и их совокупность должна иметь наименьшую протяженность.
Аналогичную постановку имеет задача планирования завоза хлебобулочной продукции из пекарни в магазины [4].
Обе задачи формулируются как задачи развозки. В отличие от задачи планирования доставки грузов, количество транспортных средств в обеих задачах известно изначально, и не подвергается варьированию, что во многом определяет процесс планирования.
Планирование транспортного обслуживания предприятия [32]. При планировании работы внутризаводского транспорта, в частности, при планировании доставки груза с центрального склада в подразделения предприятия, возникает задача развозки. Требуется составить маршруты развозки груза, в соответствии с которыми суммарная потребность всех грузополучателей одного маршрута не превышала бы грузоподъемности транспортного средства, используемого на данном маршруте, потребности всех получателей были бы удовлетворены, и суммарный путь всех транспортных средств был бы минимальным. В случае, когда возможно обеспечить всех получателей одним ТС, данная задача сводится к задаче коммивояжера.
Основным отличием от задачи, сформулированной в п.2.2, является возможность доставки груза в один пункт по частям. Это условие допускает включение одного пункта доставки в состав нескольких рейсов.
Планирование завоза-вывоза грузов на железнодорожную станцию [65]. Имеется п — пунктов завоза и вывоза грузов. Завоз и вывоз осуществляются помашинными отправками, и после осуществления вывоза груза ТС может прибыть в пункт завоза и забрать оттуда груз на станцию. Перевозки осуществляются по определенным коммуникациям с известной длиной каждого отрезка, и расстояние между двумя узлами, не связанными непосредственно, является суммой расстояний кратчайшего маршрута между ними, но пролегающего через промежуточные узлы. В качестве промежуточных выступают узлы завоза-вывоза, между которыми есть транспортные коммуникации. Груз завозится или вывозится за одни рейс. Необходимо составить план завоза-вывоза грузов, так, чтобы суммарный пробег автомобилей был минимальным.
Алгоритм определения L-кратчайших маршрутов в процессе оперативного планирования завоза/вывоза
При использовании метода динамического программирования первые четыре массива были переменными, предназначенными для сохранения параметров найденного оптимального решения на fc-ом шаге, а именно, значения целевой функции на данном шаге, номера узла, в который осуществляется шаг, типа транспортного средства, которым осуществляется рейс, и свободного ресурса грузовместимости ТС. При запоминании на каждом шаге нескольких кратчайших маршрутов требуется запоминать v наборов этих параметров. Массив /kr[v] предназначен для хранения рангов маршрутов и осуществления процедуры ранжировки, то есть запоминания кратчайших маршрутов в порядке увеличения их целевых функций.
Для процедур нахождения, сохранения и ранжировки, осуществляемых в цикле, в программе используются несколько переменных: г\, г2, /О, /ш, 12. Все они соответствуют параметру v и имеют одинаковую с ним область значений.
Рассмотрим общую схему алгоритма представленную на рис. 3.2. В основе своей она аналогична представленной в предыдущем параграфе. Первый раздел алгоритма реализуется в блоках 1 и 2 и осуществляет ввод исходных данных и формирование начальных значений.
В начале каждого шага для всего множества состояний S (нулевых и ненулевых) массивам, указанным в выражении (3.13), в блоке 1 присваиваются нулевые значения, после чего следуют циклы поиска решений, сопровождаемые проверкой выполнения ограничений типа (3.6) или (3.9). Ограничения расположены в общей схеме в том же порядке, в каком принято использовать их для метода динамического программирования. Однако, сразу же после нахождения очередного допустимого решения начинается перебор у вариантов (для начальных значений они имеются только для v=l, поскольку в самом начале процесса много вариантность просто отсутствует).
Поиск оптимальных решений для состояний S=So (соотношения 3.5 -3.7) осуществляется в блоке 3, а для состояний S So (формулы 3.8 -3.10) в блоке 5. Блок 4, взаимодействуя последовательно с блоками 3 и 5, осуществляет смену состояний в цикле по переменной к.
После калькуляции и проверки на ограничения (3.6) или (3.9) каждый кратчайший маршрут проходит следующую процедуру (блок 6): 1) Проверяется, построен ли уже хотя бы один маршрут, приводящий к рассматриваемому шагу из данного состояния. 2) Существует ли возможность сохранения, в качестве кратчайших, маршрутов, практически дублирующих друг друга? Лишним маршрутом, например, для 0-»1-»2-»0, является обратный ему маршрут 0- 2-»1- 0. Для исключения подобной ситуации каждый найденный маршрут подвергается проверке. Если его длина (стоимость перевозки) отличается от уже найденных и хранящихся в памяти маршрутов на малую величину , то маршрут отбрасывается. Проверка производится и для состояний S4Sb, и для состояний & Sb, причем в последнем случае дважды: первая проверка варианта продолжения маршрута, вторая проверка возможности возвращения в центральный пункт с контрольной малой величиной 1. 3) Затем рассматриваемый вариант сравнивается с маршрутом из уже записанных и имеющих худшее значение целевой функции. Если значение ЦФ варианта оказывается еще хуже, то далее его рассматривать нет смысла, и алгоритм отбрасывает непригодный маршрут и возвращается для следующего расчета нового варианта. Если же вариант оказывается лучше, чем худший из сохраненных маршрутов, то определяется ранг этого маршрута, то есть то место, на которое он должен быть записан в порядке возрастания ранга. Рангом маршрута является выходное значение переменной г2. Если г2 меньше L, то происходит смещение уже записанных маршрутов на одну позицию вверх. Процедура осуществляется обратным циклом и маршрут, имеющий самый большой ранг, просто отбрасывается, как бесперспективный. Затем осуществляется запись параметров найденного кратчайшего маршрута на соответствующие места в массивах из выражения (3.13). После того, как будут перебраны все варианты, процедура заканчивается (блок 8) и переходит во внешние циклы, чтобы затем повториться для новых значений/и /. Вся процедура реализуется для состояний S=So один раз, а для состояний & So Два раза (для варианта продолжения маршрута и для варианта возврата в центр). Причем для состояний S 50 присвоение массивам, указанным в выражении (3.13), нулевых значений реализуется только один раз, и параметры кратчайших маршрутов для возврата в центр сравниваются и между собой, и со всеми кратчайшими вариантами продолжения маршрута. На каждом шаге происходит не только нахождение L кратчайших маршрутов, но и сравнение их с уже найденными, ранжировка и отбрасывание бесперспективных маршрутов. Это делает механизм построения оптимального маршрута более гибким в нахождении оптимальных вариантов. Для первых шагов возможно нахождение числа кратчайших маршрутов, меньшего чем L, однако с каждым новым шагом количество всех возможных решений будет возрастать, а вместе с ним будет расти и число кратчайших маршрутов, близких к оптимальному, и в некоторый момент оно сравняется с L, а затем превысит его. Следует отметить, что процедура проверки нахождения оптимального маршрута (блок 7) работает только для маршрута с рангом v=l, то есть с самым кратчайшим из запомненных.
Рекомендации по использованию алгоритма оперативного планирования завоза/вывоза в режиме совместной работы с коммерческими пакетами прикладных программ
Значительные изменения должны быть сделаны в режиме б, который позволяет оператору после ввода исходных данных вручную составить план перевозок. Для этого на главной форме отображается расположение клиентов и размеры их грузовых партий (рис. 3.6а), здесь также необходимо добавить информацию о сервисе времени доставки.
Процесс составления плана перевозок по-прежнему может осуществляться с помощью двух входных форм. В начале для рейса избирается тип ТС (рис. 3.3.46), после чего начинается комплектация рейса (рис. З.бв). Однако возможен вывод информации о характеристиках парка транспортных средств уже в виде не- редактируемой отдельной формы. Это облегчит оператору составление плана доставки.
В случае введения узла, уже включенного в состав маршрута, или узла с грузовой партией, превышающей свободный ресурс грузоподъемности, выдаются сообщения об ошибках. В первоначальном варианте их два, но в соответствии с условиями проверки исполнения сервиса времени и выполнения рейсов в пределах рабочего дня, должны быть добавлены еще два.
Алгоритм нахождения оптимального маршрута реализован в программном коде главной формы. Он представляет собой три отдельных процедуры, имеющих прямое отношение к процессу оптимизации: процедура режима 4 и процедуры Razl и Razll, назначение которых описано в п. 3.2. Программный код процесса оптимизации представляет собой систему вложенных циклов. Количество шагов внешнего цикла равно 2 и. Ограничения реализованы условными операторами или границами внутренних циклов, зависящими от динамических переменных. Операции ранжирования и смещения маршрутов и их параметров в основных массивах реализованы с помощью прямых и обратных циклов и циклов типа repeat until (выполняется, пока справедливо условие).
Несомненно, что при создании программы с целью более эффективного использования машинных ресурсов для хранения и обработки в ходе использования оперативных данных необходимо применять динамические массивы данных. Особенностью их применения является объявление массивов и типов данных, с которыми в них будут работать, без объявления размеров массивов. Размеры массивов определяются уже в ходе работы программы стандартной процедурой SetLength из арсенала Delphi. В программе это происходит после ввода исходных данных, которые и определяют размеры массивов. Для освобождения памяти, занимаемой массивами, применяется также стандартная процедура Finalize, после чего массивы можно открыть вновь, но уже другого размера. Такой режим работы увеличит производительность программы и позволит улучшить пользовательский интерфейс.
Кроме того, в коде обработки главной формы должна быть по новому реализована процедура отображения найденного оптимального маршрута в графическом виде. Прочие процедуры ввода данных и вывода результатов, связанные с другими формами, реализованы в программном коде соответствующих форм, в соответствии с вышеуказанными дополнениями.
Особенностями программирования в среде Delphi является работа с ее стандартными объектами (графическими формами, полями, таблицами), операции их открытия, закрытия, активирования. Чрезвычайно важными являются также способы объявления переменных (как локальных внутри конкретной процедуры, так и обще программных). Следует отметить, что инструментарий Delphi достаточно широк и позволяет создать рабочий интерфейс высокого уровня. Программный код для обработки каждой формы целесообразно создавать на языке Object Pascal, также в виде отдельных файлов. Вместе с графическими файлами они должны образовать программный проект. Изложенные результаты подтверждают возможность практической реализации предложенных моделей и разработанных на их основе алгоритмов.
Следует отметить, что разработка конкретного программного обеспечения АРМ является объектом специальных инженерных проработок и выходит в силу имеющихся резервных ограничений, за рамки настоящего исследования.
Предложены модель процесса оперативного планирования с использованием «,-кратчайших маршрутов» и модернизированный алгоритм решения сформулированной в п.2.2 задачи завоза/вывоза грузов с временным сервисом. На их основе: 1. Проведен анализ алгоритма, основанного на представлении задачи оптимизации в виде многошаговой модели принятия решения из начального состояния, определяемого как номер узла. На каждом из шагов принимается решение о выборе типа ТС, движении в следующий узел или возврате на базу. Выполненный анализ показал, что структура алгоритма предполагает циклическое повторение процедур, моделирующих последовательность переходов между узлами доставки и базой. Каждый шаг предполагает ряд процедур проверки на допустимость в соответствии с условиями, указанными в постановке задачи. Если шаг удовлетворяет всем условиям, то для него вычисляется и сохраняется значение целевой функции и направление шага. Такая структура алгоритма позволяет сравнительно легко вводить дополнительные ограничения в задачу без изменения обпщх принципов функционирования алгоритма.
