автореферат диссертации по транспорту, 05.22.10, диссертация на тему:Совершенствование сменно-суточного планирования перевозок тарно-штучных грузов с применением персональных ЭВМ

МОСКОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ АВТОМОБИЛЬ Ю- ДОРОЖНЫЙ ИНСТИТУТ

РГ6 од

2 6 ДПР 1993 правах рукописи

ЗАГРАЕБСКИЯ СЕРГЕИ ВОЛЬФГАНГОВИЧ

СОВЕРШЕНСТВОВАНИЕ СМЕННО-СУТОЧНОГО ПЛАНИРОВАНИЯ ПЕРЕВОЗОК ТАРНО-ШГУЧНЫХ ГРУЗОВ С ПРИМЕНЕНИЕМ ПЕРСОНАЛЬНЫХ ЭВМ

05.22.10 - Эксплуатация автомобильного транспорта

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Мэсква 1993

Работа выполнена в Московском ордена Трудового Красного знамени автомобильно-дорожном институте на кафедрах "Автомобильные перевозки" и "Прикладная математика".

Научный руководитель - кандидат технических наук, профессор ЕФРЕМОВ А. а

Официальные оппонента- доктор технических наук,

профессор КЛЕЙНЕР ЕС.

кандидат экономических наук, профессор КОЖИН А. П.

Ведудая организация - Научно-производственное объединение Ыосавтотранса.

Защита состоится " "а? " _199_^г.

в /9 часов на заседании специализированного совета К 053.30.09 ВАК в Московском ордена Трудового Красного Знамени автомобильно-дорожном институте по адресу:

125828, ГСП, Москва А-319, Ленинградский просп., 64, ауд. 42.

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

Автореферат разослан " " 199 ^г.

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

Доцент К М. ВЛАСОВ

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

АКТУАЛЫЮСТЬ ТЕШ. Рыночные экономические отношения требуют по-новому решать вопросы планирования и управления грузовыми автомобильными перевозками. В настоящее время деление автотранспорта на ведомственный и транспорт "обп^го пользования" отживает свой век, и внимание.разработчиков программ планирования и управления автотранспортной инфраструктурой доллно быть уделено всему автотранспортному комплексу. Кроме того, важно обеспечить стабильную работу автотранспортных предприятий в условиях конкурентной борьбы, оценить перспективы развития рынка автотранспортных услуг.

Совершенствование планирования и управления автотранспортным комплексом позволит повысить эффективность и прибыльность автомобильного транспорта, улучшить экологическую обстановку в регионе.

Широкое внедрение на автотранспортных предприятиях персональных ЭШ (ПЭВМ) накладывает на разрабатываемые алгоритмы повышенные требования в области быстродействия и размерности, которые в существующих методиках часто не выполнялись.

В настоящее время централизованная диспетчеризация перевозок осуп^ствляется преимущественно при перевозках мелкопартионных, в частности, тарно-штучных грузов. Вследствие этого имеется возможность на примере перевозок тарно-штучных грузов (ШГ) апробировать перспективные методики планирования и управления грузовыми автомобильными перевозками.

ОСНОВНОЙ ЦЕЛЬЮ работы является разработка методики построения алгоритмов и программ, отвечающих следующим современным требованиям:

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

- научно обоснованная предельная эффективность использования автотранспорта;

- учет требований эффективного экономического функционирования автотранспортного предприятия в конкурентной борьбе;

- создание инструмента планирования, могущего служить

инструментом оперативного управления перевозками, исследования и прогнозирования объекта управления.

ОБЩЕЙ МЕТОДОЛОГИЕЙ ИССЛЕДОВАНИЯ является подход с точки зрения таких фундаментальных положений общей математической теории управления, как управляемость, наблццаемость и идентифицируемость объекта управления - грузовых автомобильных

перевозок.

НАУЧНАЯ ЮВИЗНА работы заключается в:

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

- постановке задачи планирования ПГГ как задачи исследования операций;

- подходе к задаче планирования ПГГ как к задаче многокритериальной оптимизации;

- разработке двухступенчатого модельно-звристического метода планирования ПТГ;

- разработке на ГБВМ задачи определения кратчайших расстояний по г. 1Ъскве и области, соответствующей существующим нормативам;

- исследовании применимости систем управления базами данных для решения на ПЭВЫ оптимизационных задач большой размерности.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ работы заключается в:

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

- разработке перспективных требований к алгоритмам управления перевозками и путей их.реализации;

- рассмотрении ГГГГ как объекта для апробации перспективных методик планирования и управления автотранспортным комплексов на региональном и государственном уровнях;

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

- исследовании применимости ШВЫ для решения задач планиро-2

вания и управления грузовыми автомобильными перевозками.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. На базе 1ВШ были реализованы следующие программные комплексы:

- сменно-суточное планирование перевозок грузов с заводов Промстройматериалов - на Автокомбинате N 1 в 1989г.;

- сменно-суточное планирование автотранспорта на перевозках мебельных гарнитуров населению - в Ыострансагентстве

в 1991г.;

- сменно-суточное планирование работы передвижных мастерских по ремонту дорожно-строительной техники - в тресте "Центроспецстрой" в 1989г.;

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

- в ГПИ "Согидорпроект" в 1991г.;

- сменно-суточное планирование централизованного завоза грузов предприятий и организаций на железнодорожные станции Московского транспортного узла - в Ыострансэкспедиции (М1ТЭС) в 1988г. (на ЭЕМ СЫ-1300);

-'определение кратчайших расстояний по г. МзскЕе и области

- на автокомбинатах NN 1 (1991г.) и 36 (1992г.), в Мзстранс-агентетве (1992г.), Мэсавтобирже (1991г.);

- определение кратчайших расстояний с блоком оптимизации маршрутов - на автокомбинате N 34 (1992г.), на Московском экспериментальном заводе безалкогольных налитков (1991г.).

АПРОБАЦИЯ РАБОТЫ. Промежуточные результаты работы докладывались автором на 48-й, 49-й и 50-й научно-практических конференциях МАДИ, в двух отчетах о НИР кафедры Прикладной математики в 1988 и 1989 гг.

ПУБЛИКАЦИИ. Промежуточные' результаты работы были опубликованы автором в пяти научных трудах (сборники трудов МАДИ, обзорная информация ЕИШГГИ серии "Транспорт").

НА ЗАЩИТУ ЕЫНОСИТСЯ:

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

- постановка задачи планирования и управления ПГГ;

- -двухступенчатый модельно-эвристический метод планирования ГГГГ;

- рекомендации по применении ШВЫ для решения задач управления грузовыми автомобильными перевоаками.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, четырех глав, основных выводов, списка литературы из 71 наименования и приложения. Диссертация изложена на 117 страницах машинописного текста, в ней содержится 9 рисунков и 2 таблицы.

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

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

В ПЕРВОЙ ГЛАВЕ проведен анализ современного состояния объекта управления - грузовых автомобильных перевозок. Отмечено, что совершенствование планирования и управления автотранспортным комплексом позволит повысить эффективность и прибыльность автомобильного транспорта, улучшить .экологи-ческуп обстановку в регионе. Ситуация, сложившаяся в настоящее время, когда вместе со снижением общего объема перевозок грузов автомобильным транспортом значительно снизилась и потребность АТП в автоматизированном планировании и диспетчерском управлении перевозками, со стабилизацией экономики должна коренным образом измениться.

Рассмотрен зарубежный и отечественный опыт создания централизованных служб управления автомобильными перевозками, внедрения в технологический процесс управления перевоаками персональных ЭВЫ (ШВЫ). Отмечено, что при внедрении ГОШ повышаются требования к программному обеспечению алгоритмов планирования и управления в области быстродействия и экономного использования оперативной памяти.

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

грузов С ГГТГ) апробировать перспективные методики планирования и управления грузовьам автомобильными перевозками, рута для каждого автомобиля.

Наибольший интерес для разработки и апробации перспективных методик управления автотранспортным комплексом представляет перевозки тарно-пггучных грузов (ПГГ), осуществляемые в г. Иоскве такими организациями, как ИГТЭС "Мэст-ранезкепедиция", Мэстрансагентство, рядом коммерческих предприятий. Эти организации арендует автотранспорт у АТП и используют его для перевозок грузов своей клиентуры.

Эти перевозки, в основном, характеризуются большим числом заездов в день, а также неравномерными габаритами и весом перевозимого груза (бочки, мебель, обрешетки, ящики, поддоны, связки и т.п.). Если при перевозке сыпучих грузов или молока коэффициент использования грузоподъемности автомобиля должен быть близок к единице, то для тарно-штучных грузов хорошим считается его значение 0.7-0.9 (в начале раз-возочного и в конце сборного маршрутов).

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

Отмечено, что алгоритмы приближенного расчета расстояний на реальной транспортной сети, приведенные в работах А. А. Аникеича, А. Б. Грибова, С. С. Сурина, Д. А. Белова, В. А. Бо-барыкина, А. Л Воркута, В. А. Житкова и С. К Просова при их высокой эффективности для промышленной эксплуатации задач планирования ПГГ не всегда применимы, т. к. рассчитанные на ГОШ расстояния используются не только для составления расписания движения, но и для расчета с водителями и клиентурой. Расхождение с нормативными (табличными) расстояниями, рассчитанными Вычислительным Центром Мэсавтотранса, даже на 1-2 км может вызвать арбитражные и трудовые споры.

Сформулирована математическая' постановка задачи плани-

Роеэния ГГГГ как задачи исследования операций класса многокритериальной оптимизации, что является наиболее обп»й постановкой, позволявшей применять к ее исследовании классические методы прикладной математики.

Такие организации, как ЫГА и ШТЭС, заказывает автомобили у АТП, и для них при расчете с АТП за "машино-дни" выгодна минимизация количества заказанных автомобилей при условии гарантированной доставки грузов клиентуре. Такой подход является наиболее перспективным, т. к. штрафные санкции за сорванные ездки уже сейчас значительны, и намечается устойчивая тенденция к их росту.

3 главе показано, что внедрение оптимизационной модели управления перевозками дает возможность повышения.производительности каждого автомобиля за счет: 1) уменьшения длины ездки с грузом, что для ПГГ аналогично уменьшению общей длины сборного (развозочного) маршрута; 2} увеличения коэффициента использования грузоподъемности; 3) увеличения коэффициента использования пробега.

Рассмотрены виды критериальных функций в работах А. А. Ани-кеича, А. Б. Грибова, С. С. Сурина, К А. Житкова, С. Н. Цросова. Отмечено, что подходы к вопросу формирования критериальных функций в указанных работах эффективны для многих видов мелкопартионных перевозок, но не для ПГГ.

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

Во ВТОРОЙ ГЛАВЕ приведен перспективный подход к построению алгоритмов планирования и управления работой грузового автомобильного транспорта.

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

е

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

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

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

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

Из вышеизложенного следует, что на стадии планирования алгоритм должен предусматривать ввод в сменно-суточные планы (ССП) автомобилей резерва рабочего времени.

Кроме этого, требуется, чтобы другие ресурсы управления (заявки на перевозки, резервные автомобили) на стадии планирования также использовались предельно эффективно по любому критерию.

Следовательно:

- алгоритм должен охватывать оптимальным планированием не отдельные автомобили, а всю их совокупность при взаимодействии друг с"другом;

- алгоритм должен формировать непротиворечивое расписание работ (ССП) для каждого автомобиля;

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

Специфика управления в стохастических системах состоит в том, что управление (ресурс) вводится не непрерывно, а порциями, в те случайные моменты времени, когда отклонение выходных величин превышает некоторый порог. В этом случае управление имеет форму перепланирования з заранее неизвестные моменты времени.

Следовательно, алгоритм должен:

- иметь возможность работать от ненулевых начальных условий;

- иметь достаточное быстродействие.

Кроме того, АСУ должна иметь возможность прогнозирования состояния объекта на некоторый период в течение рабочего дня и готовить (при участии диспетчера) резерв для реакции на возможные отклонения.

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

Проведен анализ экономических и маркетинговых требований к алгоритмам. Рассмотрены вопросы:

- оперативного обслуживания заявок на перевозки;

- использования "человеческого" ресурса управления;

- экономико-статистического использования имитационной модели объекта управления.

Статистическое моделирование хода выполнения плана в условиях заданных возмущений позволяет решить следующие маркетинговые задачи:

- определение уровня надежности выполнения заявок по критерии минимума потерь и сравнение его с уровнем, достигнутым на рынке транспортных уедут;

- определение договорного тарифа для экономического оправдания перевозок при требуемом уровне надежности;

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

В диссертационной работе отмечено, что применение такой экономико-статистической имитационной модели реализует фундаментальное требование идентифицируемости объекта управления.

В

В ТРЕТЬЕЙ ГЛАВЕ рассмотрен двухступенчатый модельно-эври-стический метод (ДкВЫ) решения задач планирования и управления ПГГ. ' '

Рассматривается необходимость внедрения в практику планирования ПГГ метода, обеспечивающего быстрое и эффективное решение задач планирования и оперативного управления ПГГ на ПЭВМ и удовлетворяющего требованиям, сформулированным в гл. 2. Такую возможность нам дает модельно-динамический (модельно-эвристический) метод решения задач теории расписаний, разработанный на каф. Прикладной математики МАДИ, при использовании специальной подготовки транспортной сети и решении задачи в два этапа.

Диссертантом разработана и находится в промышленной эксплуатации на ряде АТП г. Москвы справочная программа определения кратчайших расстояний (ОКР) между любыми двумя адресами или транспортными вершинами г. Москвы и области. Наличие такой программы решает проблемы справочного характера, но не проблемы построения математических моделей.

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

Для каждого автомобиля необходимо определить район объезда, исходя из распределения заявок по "карте" города и области. Но транспортная сеть "в чистом виде" в ЭВМ такую карту не создаст: Для этого необходимо районирование сети.

Решение задачи маршрутизации ПГГ при помощи разбиения транспортн<5й сети на районы тяготения-'к поставщикам, предложенное А- А. Землянским, требует значительной дополнительной работы при изменении номенклатуры поставщиков. Разработан принцип районирования сети, применимый для решения задач маршрутизации с любым набором поставщиков и потребителей.

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

9 '

ментом планирования являются районы.

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

ластк

Раиокн

Специальная подготовка транспортной сети г. Москвы и области.

Первой ступенью разработанного двухступенчатого мо-дельно-эвристического метода (ДкВМ) является набор заявок на каждый автомобиль.

Для решения задачи набора заявок на автомобиль предлагается модифицированный модельно-эвристический метод.

При нахождешга автомобиля в данный (модельный) момент времени у клиента 2 проблема выбора следуга^го клиента л в указанном методе решается при помощи ряда локальных критери-10

ев, сводимых в обобщенный показатель. В модификации метода, используемой в качестве первого этапа ДМЭМ, в качестве локального критерия с наибольшим весом предлагается использовать расстояние между заявками 1 и } при условии расположения заявки j в районе заявки 1 или разрешенным для совместного с ним планирования. Местонахождение заявки 1 на одной улице с заявкой ] или, например, местонахождение заявки у в области также являются локальными критериями.

В качестве одного из локальных критериев предлагается использовать расстояние следупдей заявки до АТП, что позволяет увеличить коэффициент использования пробега.

Блок-схема алгоритма ДЮМ приведена в гл. 4.

фи таком подходе достигается значение итогового показателя качества плана (минимум количества задействованных автомобилей), близкое к оптимальному.

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

Конкретно для специфической "радиально-кольцевой" планировки г. Москвы и Московской области планирование в секторе должно начинаться не от центра, не от произвольной точки в секторе, а от Московской Кольцевой автомобильной дороги (МКАД). Объяснить это можно следующим образом.

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

Начиная планирование в секторе от МКАД, мы имеем большой выбор заявок в окраинной, широкой части сектора. Остатки же, не "поместившиеся" в автомобили, планируемые на сектор, будут располагаться преимущественно в центральной части, и мы их присоединим к соседним секторам.

Заявки по Московской области присоединяются к соответствующим секторам г. Москвы и условно относятся к районам, ближайшим к МКАД, с которых и начинается планирование. Таким образом, область планируется в первую очередь, что оправдано сложностью включения в маршрут удаленных областных точек.

После того, как на каждый автомобиль определен набор

Н

заявок, мы можем считать первый этап ДЮМ проведенным.

Вторая ступень ДМЭМ - оптимизация объезда набранных заявок. Фактически необходима решить столько задач определения порядка объезда маршрута по критерии минимума суммарного пробега по маршруту, сколько автомобилей оказалось необходимым для перевозок на данный день.

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

При наличии программы определения кратчайших расстояний (ОКР) мы имеем и расстояния между любыми парами вершин (заездов) на маршруте.

Наиболее распространенный метод решения таких задач -метод ветвей и границ (МВТ). Опишем применение МВТ к данной задаче.

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

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

\г

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

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

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

Основной сложностью при реализации МВТ на ПЭВМ является объем информации по ветвям, которую необходимо хранить на протяжении всего процесса оптимизации. Размерность кесси-ва для хранения данных по ветвям должна быть достаточно велика. Обработка такого массива на каждом шаге также займет много времени.

Шход из этой ситуации был найден при использовании для решения задачи СУБД Foxbase или Clipper. При этом не требовалось даже формирования исходной матрицы расстояний между вершинами на маршруте, т.к. время обращения к общей матрице транспортной сети составляет доли секунды.

Основной идеей реализации МВТ на IEBM является хранение данных по ветвям в файле типа "DBF". При таком подходе, на базе реальной транспортной сети, время расчета каждого маршрута для РС-АТ составляет 10-20 секунд при десяти заездах, и около 2 минут при двадцати. Большее количество заездов в день обычно не планируется даже при ПГГ.

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

13

рения поиска имеет смысл иметь одно дополнительное поле, в котором можно хранить значение итогового показателя и (или) номер шага, на котором ветвь была прервана.

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

ПЬсле выполнения второго этапа ДЪШ возможен расчет расписания работы автомобилей на сформированных маршрутах.

В главе приведены рекомендации по применению ДЮЫ на разнообразных видах задач планирования ПГГ.

Возможно введение в алгоритм учета временных ограничений и резерва рабочего времени, что позволяет использовать ДОЗМ для решения задач развозки (сбора) обп^го типа.

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

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

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

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

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

Таким образом, при использовании ДЮМ основной проблемой является специальная подготовка транспортной сети региона. В принципе, конкретный вид секторов будет всегда зависеть от наличия в регионе рек, лесных массивов, железных дорог и т. п. Эта проблема может быть решена параллельно с созданием справочной программы по определению расстояний между любыми двумя точками региона.

Выбор типа и конфигурации ПЭВЫ для решения задач планирования и управления перевозками также потребовали отдельного рассмотрения в диссертационной работе.

При решении задач управления автомобильным транспортом на базе ПЭВМ наиболее предпочтительным видится применение вычислительной сети, где в качестве центральной ЭВМ используется PC-AT, AT-386 или PS/2, а в качестве рабочих станций - ЕС-1840 или РС-ХГ (беэ жестких дисков), стоимость которых сравнительно невысока. Такая конфигурация позволяет, во-первых, вести ввод информации с нескольких терминалов, а, во-вторых, при надлежащем системном обеспечении проводить мультиобработку данных. Внедрение многотерминальных систем на базе PS/2 также может бить рекомендовано для решения задач планирования и управления вследствие большой производительности центральной ЭВМ (тактовая частота процессора типа 80386 - от 25 до 50 МГц), что позволяет сократить время решения задач на 20-407.. ■

В главе также рассмотрено решение задачи определения кратчайших расстояний (ОКР) на ПЭВМ. Отмечено, что задача определения кратчайших расстояний (ОКР) решается практически на всех ДТП, а также в транспортно-экспедиционных организациях, на предприятиях, пользующихся автомобильным транспортом, в различных коммерческих организациях и т. п. ОКР используется в задачах расчета с клиентурой, таксировки накладных, учета топлива и ГСМ, начисления сдельной заработ-

15

ной платы водителей, многих других задачах финансово-хозяйственного характера, а также для задач планирования и управления перевозками.

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

Проведен сравнительный анализ "табличной" технологии решения задачи ОКР (на больших ЭВМ) и технологии ОКР на IDEM.

Инструкцией Главмосавтотранса "О порядке пользования таблицами кратчайших расстояний, рассчитанными Шчислитель-ным Центром Главмосавтотранса" от 1 сентября 1976г. данные, указанные в таблицах, были объявлены нормативными для всех расчетов ДТП с госбюджетом, клиентурой и водителями. В связи с этим основной целью при разработке программы ОКР на ПЭВМ являлось полное соответствие рассчитываемых расстояний "табличным" при максимально быстром ответе на запрос.

В 1991 г. автором на ПЭВМ типа РС-АТ'была реализована задача ОКР на базе алгоритма Дейкстра-Ыинти.

Программный комплекс, внедряемый в промышленную эксплуатацию, реализован на базе СУБД Clipper. Вьйор для решения задачи ОКР именно СУБД, а не какого-либо из алгоритмических языков высокого уровня (Си, Паскаль) обусловлен тем, что задача ОКР требует большого количества нормативно-справочной информации (справочники адресов г.Москвы, населенных пунктов области), которые на ГОШ не могут для обработки быть считаны в оперативную память вследствие недостаточного объема адресуемого ОЗУ на ПЭВМ. Обращение к таким файлам может производиться только на жестком диске. В этом случае нам обычно необходим прямой доступ к информации, что наилучшим образом обеспечивается средствами СУБД.

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

Несмотря на значительный размер такого файла (около 5,5 Мбайт), время ответа на запрос измеряется сотыми долями

ie

секунды вследствие, как уже говорилось, эффективной работы СУБД Clipper с базами данных на диске.

Большой объем программного комплекса (около 6,5 И5айт) оказался незначительной проблемой при решении задачи ОКР на PC-AT с объемом жесткого диска не менее 40 Мбайт. Несомненным преимуществом является полное соответствие расстояний "табличным", что исключает возможность арбитражных и трудовых споров по этому поводу.

В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание блок-схемы алгоритма, реализующего ДМЭМ при планировании перевозок мебельных гарнитуров в рамках Мострансагентства. Описана программная реализация ДМЭМ на языке СУБД FoxProLn 2. 0: Это наиболее современная из DBase-совместимых СУБД, отличающаяся высоким быстродействием, эффективной работой с файлами, удобством разработки входных и выходных макетов и экономным использованием оперативной памяти.

Проведен сравнительный анализ различных методов планирования ПТГ по критерию минимального количества автомобилей, задействованного для выполнения заданного объема перевозок мебельных гарнитуров на день. Результаты анализа приведены в табл.1.

Таблица 1

Наименование метода

Время решения Число авто-на PC-AT,мин. мобилей

1. Метод ветвей и границ

2. Стандартный модельно-эври-стический метод

3. Мэдельно-эвристическнй метод со специальной подготовкой транспортной сети

4. ДЮМ'

около 600

24

4

30

4

5

27 25

5. Ручное планирование

около 240

27

Проведена оценка годового экономического эффекта от внедрения программного комплекса, реализующего Д1Ш при сменно-суточном планировании перевозок ИГА.

Если при ручном планировании для выполнения заданного объема перевозок ежедневно требуется в среднем 27 автомобилей типа ЗЮЫЗО, перенос планирования на ШВЫ позволяет сократить это число до 25, т.е. в среднем на два автомобиля и, соответственно, машино-дня. Таким образом, в течение года эксплуатация программного комплекса, реализующего Д&£ЭМ, позволит сэкономить около 600 машино-дней, или 4800 машино-часов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ПО ДИССЕРТАЦИИ

Проведенные исследования позволили получить следующие основные результаты и сделать ряд выводов. ■

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

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

и др., и показана невозможность выполнения требований к времени и качеству решения при планировании ПТГ указанными методами.

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

4. Разработаны и исследованы требования к указанным алгоритмам с позиции перспективного подхода к функционированию автомобильного транспорта в условиях действия рыночных отношений. Исследован способ объединения имитационной мо-

13

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

5. На основании проведенного исследования показано, что единственно приемлемым из существующих методов решения задачи планирования ГГТГ в классе задач теории расписаний является метод, базирующийся на эвристических подходах и формализующий опыт диспетчеров-планировщиков. Разработан двухступенчатый модельно-эвристический метод (ДИЭМ), сочетающий в себе преимущэства модельно-эвристического метода и метода ветвей и границ при специальной подготовке транспортной сети региона.

6. Практическое решение задач планирования ПГГ потребовало исследования методов решения задачи определения кратчайших расстояний на реальной транспортой сети, а также применения их в рамках алгоритмов решения задач планирования перевозок на персональных ЭВМ. Разработан программный комплекс, позволяпций свести к нулю расхождения между расстояниями, рассчитываемыми на ПЭВМ, и нормативными (табличными). Время ответа на запрос о расстоянии между двумя любыми транспортными вершинами г. Москвы и области на ПЗЕМ не превышает 0.1 секунды, что позволяет использовать указанный программный комплекс для решения оптимизационных задач.

7. Разработанный на основе проведенных исследований двухступенчатый модельно-эвристический метод решения задач планирования ПГГ реализован в виде пакета программ для ПЭВМ в системе управления базами данных Foxproln 2. 0. Такой подход позволяет сократить время планирования перевозок мебельных гарнитуров автомобилями Мэстраксагентства на 50* относительно ручной технологии планирования (включая ввод информации в ПЭВМ и генерацию выходных форм). Время работы самого алгоритма планирования при 200-300 ежедневных заявок на перевозки и 24-26 автомобилях не превышает 6 минут.

8. Исследована'возможность применения для решения на ПЭВМ оптимизационных задач большой размерности систем управления базами данных типа Foxpro, Clipper и др., что позволяет экономно использовать ресурсы адресуемой оперативной памяти ГОШ, обычно не превышающие 640 Кбайт, и при помощи соэда-

19

ваемых индексных файлов эффективно работать со значительными объемами информации на жестком диске.

9. фактическое применение двухступенчатого модельно-эвристического метода при планировании перевозок мебельных гарнитуров автомобилями УЬстрансагентства позволило сократить количество автомобилей, ежедневно заказываемых у автотранспортных предприятий, на 2 единицы, или на 10-15%. Таким образом, годовой экономический эффект внедрения задачи планирования указанных перевозок ориентировочно равен стоимости бООмашино-дней. Срок окупаемости капиталовложений на решение задачи планирования оценивается в один квартах

ПУБЛИКАЦИИ ГО ТЕМЕ ДИССЕРТАЦИИ

1. Заграевский С. Е Вопросы совершенствования планирования перевозок пакетированных грузов в рамках Мостранс-экспедиции. /Сб. науч. трудов "^тематические методы оптимального управления в задачах автомобильного транспорта/. -к»: МАДИ, 1988. - С.61-65.

2. Заграевский С. Е Некоторые вопросы применения персональных ЭВМ в управлении автомобильными перевозками. /Сб. научных трудов "Оптимизационные методы в задачах автомобильного транспорта"/. - Ы. : НАДИ, 1990. - с. 23-27.

3. Заграевский С. Е Двухступенчатый эвристический метод планирования перевозок мелкопартионных.грузов. /Обзорн. информация "Транспорт: наука, техника, управление"/. - и.: ВИНИТИ, 1992, N 3. - С. 27-30.

4. Заграевский С. Е Решение задачи определения кратчайших расстояний в городе Мэскве и Московской области на базе персональных ЭВМ. /Обзорн. информация "Транспорт: наука, техника, управление"/. - Ц.: ВИНИТИ, 1992, N 7. - с. 28-31.

5. Заграевский С. Е Перспективные методы управления работой грузового автомобильного транспорта /Обзорн. информация "Транспорт: наука, техника, управление"/. - М.: ВИНИТИ, 1992, N 9. - с. 5-10.

МАЛИ э.69 1.100 10.02.93г.