Математические модели, методы и проблемно-ориентированные системы дробно-линейной оптимизации : (На примере задач планирования автомобильных грузовых перевозок) Соломон, Дмитрий Ильич

Введение к работе

^^^ьност.ь_^сде5о6стгій_і В последние года сіфоксе развитие получили Еовые информационные технологія!, связанные со всесторонним внедрением персональных компьютеров, современных средств обработки данных и эффективных методоз выбора управленческих решений. Одновременно с этим появились различные формы хозяйствования и собственности, которые выдвигают ноекє требования к совершенствованию методологій и технологии моделирования и оптимизации технических и экономических процессов.

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

Дополнительные задачи в новых условия?, хозяйствования выдвигаются перед транспортной системой ь целом и автомобильным транспортом общего пользования (АТОП) з отдельности. Автомобильный транспорт (AT) является тем видом транспорта, которому присуди високая маневренность подвижного состава и возмої.'носїь оперативно реагировать на изменения объемов производства и новых направлений грузопотоков. Для этого необходимо совершенствовать структуру производственных и транспортных ресурсов, чтобы своевременно, качественно и полностью удовлетворить потребности экономики в грузовых перевозках. Повышение эффективности перевозочного процесса на AT невозможно без применения вычислительной техники я новых информационных технологий» Параллельно с задачами, выдвигаемыми экономикой перед AT, возникают новые транспортные и технологические процессы, которые требуется смоделировать и автоматизировать. Из сказанного следует актуальность и необходимость решения рассматриваемой в диссертационной работе вакноЗ научно-технической проблемы информатизации AT по разработке и внедрению математических моделей, методов и проблемно-ориентиро-

ваннах систем дробно-линейной оптимизации перевозочных процессов. Вопросами оптимизации и моделирования на AT занимаются уже более 30 лет. Тагам известные ученые, как А.А. Бакаев, Б.Л. Геронкмус, В.А. Житков, К.В. Ким, Б.С. Михалевич, С.А. Панов, И.В. Романовский, І.І.З. Шор, Г-Н. Ш и другие внесли существенный вклад в развитие математических методов, экономико-математических моделей и информационных технологий планирования и управления перевозочными процессам.

й?^ьр_и_здадчши_усслеао6дкия данной работы является решение научной проблемы', имеющей вакноа народнохозяйственное значение. Это разработка математических методов и алгоритмов решения общих задач дробно-линейного программирования (ДЛП) и дробно-линейных задач транспортного тина, разработка экономико-математических моделей линейного и' дробно-линейного программирования решения различных задач оптимизации на автомобильном транспорте, а также пробломно-ориентировашшх систем планирования и управления автомобильными грузоБымя перевозками.

В работе сформулированы и решены следующие оснозные задачи:

исследование задач ДЛП блочз'-чіагональной структуры и разработка деколшознщюнных алгоритмов їй решения;

разработка общих декомпозиционных методов решения задач ДЛП, основанных на схемах разложения по переменным и ограничениям с использованием'субградиентных методов;

исследование обобщенных задач ДЛП и разработка аффективных методов их решения, основанных на схемах декомпозиции Корнай -Лпптака в сочетании с субградлентными методами;

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

анализ и систематизация математических методов и программного обеспечения решения задач оптимизации перевозочного процесса на AT;

разработка информационных технологий моделирования транспортных сетей (ТС) и расчета кратчайших расстояний;

- разработка комплекса экономико-математических моделей
оптимизации структуры подвижного состава и грузовых перевозок
АТОП;

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

- разработка математических моделей и алгоритмов закрепления
маршрутов за автотранспортным предприятием (АТП);

разработка математических моделей и алгоритмов решения задач составления сменно-суточных заданий (ССЗ) по заявкам постоянной клиентуру;

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

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

разработка проблеміо-орпентировзшЕіХ систем оперативного планирования и управления автомобильными грузовыми перевозкам.

06^KTO^_r^c5g^iiiscmi5ja_r^^^H^jjcc^cto^ является автомобильный транспорт общего пользования со структурой его административных и производственных подразделений, системой планирования и управления транспортным процессом и комплексом взаимосвязанных задач, которые необходимо решать для повышения эффективности транспотпой системы в целом. Рассматриваются задачи ІУЇІІ специальной структуры и болыоп. размерностей, а также обобщенные и транспортные, задачи ДЛП.

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

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

pa, функщш Лагранжа, теории двойственности, методам декомпозиции и недифференцируемой оптимизации; информащюнше технологии и инструментарии програ%ашрования на ЭВМ различных модификации; созрзменше системы управления базами данных и языки программирования высокого уровня.

Связь с планахи нсщчщс исследований.. В основу исследований по данной проблема были полоаены результаты научно-исследовательских работ, проводимых автором по темам "Разработать систему экономико-математических моделей оптимального прогнозирования развития и размещения общественного производства Молдавской ССР на перспективу" (I960 - 1985 гг.) и "Разработать математические модели и методы решения нелинейных оптимизационных задач плэниро-Бания и управления в многоуровневых социально-экономических системах" (1936. - 1990 гг.), а такяе в рамках хоздоговорной работы с Министерством транспорта Республики Молдова "Разработка математического обеспечения (модели, алгоритмы и программы) оптимизации перевозочного процесса на автомобильном транспорте" (1987 - 1990 гг.).

Яд^н*да_ко6идау^иссеетаууи представляют . следующие основные результаты, которые выносятся на защиту:

информационная технология выбора оптимальных решений планирования и управления перевозочным процессом на AT;

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

декомпозиционные методы и алгоритмы решения различных классов задач ДЛП;

информационная технология и системы MS. KRS и SETRAZ моделирования ТС, расчета кратчайших расстояний и решения сетевых транспортных задач с ли-гиными и дробно-линейными функционалами;

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

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

комплекс матэматлческих модэ^ой, алгоритмов и прогреем (система PGP) определения годового клиентурного плана грузовых перевозок;

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

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

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

автоматизированное рабочее место диспетчера грузовых перевозок АШ GP;

математические модели и алгоритмы решения задач кольцевой маршрутизации, а такте системы АЬРАХ и JiK? оперативного планирования и управления автомобильными контейнерными перевозками:

модификации параметрического метода и эффективные алгоритмы типа Кармаркара - Дикияа решения задач ДЛП общего вида;

декомпозиционные методы решения задэт ДЛП, основгшше на схемах разложения по переменным и ограшгчениям в сочеташш с методом обобщенного градиентного спуска (ОГС);

декомпозиционные методы решения задач обобщенного ДЛП, основанные на схемах разложения по ограничениям, щэтнципе Корнай -Липтака и суОградиентных методах;

декомпозиционные алгоритмы метода ОГС для решения дробпо-линейных задач транспортного типа (обычная, производственная, распределительная и обобщенная транспортные задачи);

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

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

ЦШШ^^йІШ-ШЬМО!!іЬ-ШйО!Ш заключается в разработке и применении информационной технологии выбора эффективных управленческих решении на AT. базирующихся на использовании комплекса математических моделей, проблемно-ориентированных систем и математических методов ДЛП решения задач оптимизации автомобильных грузовых перевозок. Это позволяет повысить оперативность системы

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

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

Практическая реализации результатов работы. Основные результаты работы в виде проблемно-ориентированных систем внедрены в отраслевом Вычислительном центре (ВЦ), в Производственном объединении (ПО) "Мекавтотранс" и непосредственно на производственных объектах Министерства транспорта Республики Молдова (Минтранс РМ).

Основные внедрения:

алгоритм и программы на ЕС ЭВМ для решения задач маршрутизации междугородных перевозок массовых грузов (ВЦ и Управление грузовых перевозок Минтранса РМ. 1980 г.);

математическая модель, алгоритм и комплек. программ определения оптимального плана закрепления клиентуры за автохозяйствами (ВЦ и Управление грузовых перевозок Минтранса РМ, 1982 г.);

математическая модель, алгоритмы и программы на ЭВМ- для решения задач оптимизации структуры подвижного состава автопредприятий республики (ВЦ и Управление грузовых перевозок Минтранса РМ_С 1984 г.);

система оперативного планирования и управления междугородными автомобильными перевозками (Управление грузовых перевозок Минтранса РМ, 1988 г.);

моделирование транспортной сети и расчет матрицы кратчайших расстояний (ВЦ Минтранса РМ, 1990 г.);

математические метода и программное обеспечение решения задачи оптимизации структуры подвижного состава автотранспортных предприятий (ВЦ Минтранса РМ. 1990 г.);

автоматизированное рабочее место диспетчера грузовых перевозок (ПО "Бендертраяс" и АТП Минтранса РМ, 1990 г.);

автоматизированная система планирования и управления авто-

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

Ал^рОд^я_^бд^_х Основные положения диссертационной работы докладывались и обсуждались яа различных республиканских и всесоюзных научных конференциях: на 2-2 и 3-й Всесоюзной сколе-семл-наре "Проблемы управления и моделирования социально-эконсмичос-кого развития региона" (Свердловск. 1978, I960 гг.); на республиканской конференция "Проблемы создания и внедрения АСУ и средств вычислительной техники в условиях улучшения планирования и совершенствования хозяйственного механизма" (Киппкев, I960 г.); на Всесоюзной школе-семинаре "Дискретная оптимизация и ее приложения, в том числе экономические" (Ккшшев, 1933 г.); па 2-й Всесоюзной сколе-семинаре "Оптимизация и ее приложения к зконог.м-ке" (Аихабад, 1984 г.); на IX, X и XI Всесоюзной иколз-с::мпозпумэ "Системы программного обеспечения решения задач оптимального планирования" (Минск, 1986 г., Нарва. ІСЄС г., Кострома, ISS0 г.); на Республиканской научно-практической конференции "Пріме-нение эксномико-мзтематиче как методов и ВТ в планировании и управлении народным хозяйством МСС?" (Кшіикев, 1923 г.); на Всесоюзной конференции "Метода математического программирования и программно? обеспечение" (СвердлсЕск, I9S9 г.); на Республиканской научно - практической конференции "Проблемы математизации народного хозяйства НССР" (Кишинев. 1990 г.).

ОийбШ-Ш!:*. ^ результатам исследований опубликовано 35 научных работ в Известиях АН FM (серия технических и физико-математических наук; серия "Математика") и в трудах Института математики с ВЦ All РМ (серия "Математические исследования"). В издательстве "Штиинца" в 1929 году вышла монография з соавторстве с Шором Н.З.

Структура Оиесетпаиш. Диссертация является самостоятельно выполненным научным трудом и состоит из введения, семи глаз и приложения, содержит 17 рисунков, 5 таблицы и список литературы. включахшй 205 наименований. Основное содержание работы изложено на 346 страницах машинописного текста.

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

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

.Первые три главы диссертации посвящены вопросам разработки математических методов и эффективных вычислительных алгоритмов решения задач ДЛП, которые встречаются при оптимизации перевозочного процесса на AT. В первой и второй главах приводятся декомпозиционные метода решения общей задачи ДЛП, а в третьей - различные алгоритш решения задач ДЛП транспортного типа. По некоторым алгоритмам составлены программые модули, которые сданы в ГосФАП СССР и использованы в разработанных системах оптимизации на АГ.

Рассмотрим наиболее эффективные методы и алгоритмы решения задач ДЛП, предложенные в диссертационной работе.

Пусть задана обычная задача ДЛП Р/: найти

С(Х) n п

X ЩГ) D(X) j=1 ^{3 J} j=1 ^{3 3}

R(x) = С х: _±i х* = Ь_±. i=1 .m; Xj 1- 0. JH.nJ,

о которой предполагается, что D(x) > О для любого х є R(x), а многогранное выпуклое множество R(x) ограниченно.

Для решения задачи Р1 разработаны различные алгоритмы, которые условно можно разделить на пять групп: модификации симплекс-метод?, метод "линеаризации^н, параметрический метод, полиномиальные и декомпозиционные алгоритмы. Ниже приведем некоторую мо-дификацию алгоритма параметрического метода. Для этого рассмотрим

задачу Р2: найти mln { Z(x, X) = Сіх) - A. D(x) ). х є R(x)

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

Шелзар.ительный_1&_:й1_шаг_:. Берем \ = ц₀= 0 и находим оптимальное решение задачи 12 при А, = ^₀..

Общий^к^й^щагд Пусть имеется некоторый оптимальный план X^й"¹ задачи 72, полученный на предыдущем шаге алгоритма. Тогда:

определяем значение параметра Я = ^ = Pfar^-1;;

находим оптимальное решение х" задачи 72 при \ - \і^;

если 7(з?*-) = Ffr^4-1.). то план х* является оптимальны;,? для задачи 71.

Далее приводятся эффективные алгоритмы решения задач 71, основанные на модификациях алгоритмов типа Кармаркар - дикян. Если ввести обозначения х = (т., х_, ..., х ), с = (с,, с_, ... .... c_n), d = С<3₁, dg, ..., d_n J, b = fb₁, b₂, .... b_m), К = (A-₁, А._г, .... А,_гаЛ A = fa^), то общая схема таких алгоритмов имеет вид.

Первоначальный.Х^Я^щаг. Пусть х > О, удовлетворяющее Ах= = о, будет первоначальным допустимым решением задачи 71.

Общий., (k-й „шаг). Пусть х* - некоторое решение, полученное на предыдущем шаге. Тогда:

определяем B_k = dlagix^, х. .... х^);

находим \^= (AB^r^Atf, (С(х^)й - D(x*)c);

вычисляем новые значения а^*¹ > О по формуле

х*⁺¹= я* - Я

В^(С(х*)й - D(x*)c - А^г\) 1\(С(&Х1 - L(x*)c - А⁷\)Ц

где 0 < R < 1.

Особый интерес представляют собой декомпозиционные мбтоды решения задач ДЯП, основанные на схемах разложения по ограничениям и переменным с применением субградиентных методов. Сначала приводятся алгоритмы решения задач ДШІ блочно-диагональной структуры 73: найти

С(х) р р

nCn (Fix) = » ( Z с х + с₀) / ( Z А х. d₀ )).

X Ы(Х). D(X) J=1 ^{J 3} J=1 ^{3 J}

U(x) = (х: Z Д₃ х₃ * Ь. Sj =j $Ъ_}, з = ТТЬ": Xj > 0. з = TTpJ.

где е., d,, х - векторы размерностью n,; b - m-мерный вектор; Ь^ - векторы размерностью п^; А. - матриц размерностью man.;

В, - матрица размерностью m. х n^; с₀, d₀ - постоянные числа. Для задачи РЗ построим функцию Лагранжа

Ux,и) = (С(х) + (и, о - Ajc₃)) / D(x)

и рассмотрим задачу пах С L*(u) = min L(x.u) У. где
и 5= О х г Six)

и = (п., ... , и ) - множители Лагранжа для связующих ограни-

чзнкЗ, a S(x) = (х: В^ s b^, j=77p: х_} z 0. з=Т~р).

Тогда задача РЗ сводится к решению задачи max L*(u). На

и > О t-м шаге субградиентного метода необходимо провести ряд обязательных вычисления.

1. Решить задачу min Цх.и) при фиксированных значе-

X S(X)

киях и = и*. Для решения этой задачи применим параметрический метод и получим следующую блочную задачу параметрического линейного программирования: найти

min ( (с. - и* А. - \ d.} х.У.
3=1 ^{J 3 J 3}

X S(X) 1=

На кааком шаге параметрического метода при фиксированных значениях \ репаются р задач вида: найти

min ( (е., - и* А. - к dj ij,

X SjfXj) ^{3 3 3}

где SjCXj) = (Zy BjTj s bj, х ъ О У.

2. Определить значения обобщенного градиента функции L*(u) в

точке и* по формуле GCu*; = ( (Ъ - Y.A. х*(и*)) / Ш*(и^х)) У,

3=1 ^{3 3}

где х*(и^ь) - оптимальное решение задачи min Ъ(х,и*).

х S(x)

t+1

3. Вычислить новые значения

гаг f и, u* + ft_t+1 G fu¹; ;,

где ft_t+1 - величина шага.

Для решения задач ДЛИ с сепарабелышми функционалами

р ^ci ^хз * ^с:

?4: найти піп I Р(х) = У тг- У.

х.мсх) a₃x,<;d>.

F5: найти піп ( F(x) = rax —^:— — J

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

^с1 ^xi * ^ci

Tf'**?*¹'

min ( -

z s₃(x₃) a₃ x_{3 T} „j

Далее рассматривается задача дробно-вшгуклого програмісірова-

ния Рб: найти

С(х.у)

min ( F(x.y) = : f.(x,y) «О, і = i.m: У.

D(z.y) *

где x = Cr,, х_г. .... x_u) e г; у -- (y_y. y_?. .... y^) є F\ для

решения которой используется схема декомпозиции по перекеныюк

Обозначил через Н(х,у) множество значении переменных (х,у),

удовлетворяющих ограничениям задачи F6, и предположим, что для

всех (х,у) е М(х,у) С(х.у) z О и D(x.y) > О, а функции С(х,у),

-D(x,y), f_±(x,y), t = ТТй, - выпуклые и необязательно дифференцируемые по совокупности переменных г и у. Тогда функция Р(х,у) является квазивыпуклой на выпуклом множестве Н(х,у). Построим функцию Лагранжа задачи Рб по формуле

L(x.y.u) = ( С(х.уУ + u₁ f.(x.y) ) / D(x.y),

1-1 ^{х х} где и = (и^...., и ) - соответствующие множители Лагранжа.

Для задачи Рб выполняются- необходимые и достаточные условия Куна - Таккера и существует пара ((х*,у*),и*), которая является седловой точкой функции L(x.y.u). Для решения задачи Рб используется схема декомпозиции по переменным, для чего фиксируются

переменные х = х и рассматривается задача Р7: найти

С(х.у) _

min ( F(x.y) = —-— : f.(x.y) і О. і = i,m ;. D(x.y) ¹

Для тех значений х. для которых разрепима задача Р7, определим функцию Ф(хУ = min _ F (х. у), где R(x) - множества

У R(X)

значений переменных у, удовлетворяюще ограничениям задачи Р7.

Тогда функция ФГх.) является квазизыпуклой на некотором выпуклом подмножестве ff с . Если для некоторого х е if выполнено условие Слсіїгера, то обобщенный градиент функции ФГх J в точке х = х вычисляется по формуле Вф(х) = g(x,y(x)), где L - функция

Лагранха задачи Рб; у(х) - одно из оптимальных значений в задачи Р7; и = (и_±) - множители Лагранка задачи Р7, полученные в соответствии с теоремой Куна - Таккера; g^(x.y(x)) - проекция такого обобщенного градиента функции Z(z,u) = L(x,y,u) на подпространство Е^, у которого проекция на подпространство Е* равна нулю

(обобщенный градиент берется в точке z » (х,у(х))).

Таким образом, если предположить, что функция <й(х) определена для любого х W и имеется возможность вычисления обобщенного градиента g^(x) в произвольной точке х, то получим итеративный алгоритм решения задачи Рб, на t-м шаге которого необходимо:

- решить задачу Р7 при Ї » ? и определить вектор
мжжителей Лагранжа и(х*) = f и^х¹) > :

вычислить субградаент в$(х^х) функции <&(х) в точке х = х*;

определить новые значения x^t+1 = х* - 7i_{t t} g^fe*), где 7i_t+1 - величина шага.

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

Рд: найти піп Т(х,у),

(Х,у) S(X,y)

Р9: найти піп F(x,y),

(Х,у) ЩХ.у)

а функционал F(x,y) и мн^дества S(x,y) и М(х,у) имеют вид Р(х,у) = ( с, х. + с у ) / ( d, х. + d у ),

tffx,y;= f fx.y;; Z 4^ Xj + РоУ > b ,

^вз ^xj * ^Fi^y ^ ^bj> ³ = ^*>^: j/ > о, .х^ > о, з = T7p ;:

S(x,y) = { (x.y): B₃ x_: + ?., У « by з = Тії:

у > О, X. Ъ*0. 1 = ТТл J,

где с, d. у - векторы размерностью k: F₀ - матрица размерности и х к: Р. - матрицы размерностью n^ z к.

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

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

Для решения задач Р4 и Р5 может бить использована схема декошозиции типа Корнай - Липтака с последующим использованием субградиентных методов. Для этого представил вектор ресурсов в виде равенств

Ь = г, + г_г * ... ф г_в. Тогда задачи ?4 и Р5 разлагаются на р подзадач типа Р10: найти

min (Ф.(х.) = : А. х. = z., Bjc. і &., х. і О ).

Пусть xaz ) - оптимальнее решение задачи РЮ при заданном z., a ( u'uj ) - оптимальные значения мнокителей Лагранха. соответствующие связущим ограничениям, где функция Лагракаа определяется по формуле

^СЛ" ViV Wi* ^гз^иі* ^bi^v3 + ^со

ЪАх.. и.,, у.; = .

Для задачи Р5 определим функцию Q(z) = шах Ф.(х*,іг.)). Так

л J J J

как <&Jx'iz₃)) являются строго квазивыпуклыми, то функция $(z)

таюкэ является строго квазивыпуклой, а ее субградиент имеет вид

G$(z) = {g₃(z₃) = ( u^Zj) / (d₃ x₃(z₃) * a₀))).

Тогда задача P5 сеєдєтся к решению задачи минимизации строго квазивыпуклого функционала $(z) при линейных ограничениях, что позволит найти глобальный минимум. Для решения этой задачи монет быть использован субградиеятный метод с проектированием на линейные многообразия.

р , Относительно задачи ?л функция (z) = ЧЛхлг*)) не

3=1 ^{J 3 3} является квазивыпуклой, и поэтому данный алгоритм ее решения не

всегда обеспечит глобальный минимум.

Для решения задач ДЛП с переменными коэффициентами приводятся итеративные алгоритмы, основанные на методах Данцига-Вулфа и схемах декомпозиции по переменным и ограничениям.

В завершении второй главы рассматриваются некоторые классы обобщенных задач дробно-Еыпуклого программирования, в которых система ограничений имеет Олочно-диагональную структуру со связу-вдими ограничениями. Пусть имеются р групп переменных і, = ( і',

зг,..., х.->) е к >, образующих вектор X - (х_л, ..., I) R , где

³ р р .

п= п.. На множестве каддой группы переменных х. определяются
3=1 ^{J J}

следующие непрерывные функции: <р., ф., ff*, Q¹.: R ³ —> ж.

Рассматривается задачи Р11: найти піп Р (х), г = 777,

х S(x) ^г

в которых функции Р_г(х), г = 1,4, определяются по формулам

3=1 ^{g J}

max ;

і *₃(х₃)

3=1

р Ц>^₃) П ф^ '

а множество S(x) системы ограничений имеет блочно-диагональную структуру:

S(x) = (x: E T

&_л(х₃) s Ъ]. l = 7X: 3 = 77p: J.

_ < «г₁ ч₁

гдо а = Га,. .... а_ш; ; к , b.,= fb^ , ..., b^ .J є R ^J, .f = Up.

а функции !7j (і=йт), Q^ (l=~uq₃) - выпуклы.

В обдом случао задачи Р11 являются ^логоэхстрсмальными и для их ревония необходимо использовать метода глобальной оптадїззциг. Однако если для функций <-?Jx^) и ф/я..) штрэбопзть выполнена некоторых дополнительных услсЬий, то функционала ?^(х), F^(x), Р₃(х) и РДлг; будут кзазгетаг/кліна, а задачи Р?f стенут одномс-стремалъны?"!.

Пусть выполняются слэду?"п;:е условия: зсе функции к)_А(х.) -выпуклы, о ф/г.; - вогнуты; <р.(х ) > О и '\>Jx.) > О для" любого г с SW; *ЛС-jJ = ₁(z_i)'^> / tyjCZj) явдягтся одновременно монотонно возрзстакдп:-пі иди монотонно убызавдп.гл на 5fij. Тогда

функции F^(x), г=Т7ї. являются хзазкЕыпукдькг.' на Я(х,).

Такім образом, при данных предпэложшях глх&чіі РИ являются задачка кеззпе'.зг/кдого прогрр_.25іроввіі'Ліі, з которых > "обходжо мйнкмизпровать относешш віязуїсдих л зоглутн;: іїушсісіокзлсв на 1-210-ssctvj ограниченна специальной структуры. Для :іл репзгаїя пр^т.шо-дятсл ,"оі:с:'лозіін'.:с:лліо алгоритмі, оснозангко па схемо разлог:зіпя по огран/ічетляї н irp:am;nic ІСсрнап - Лкцт&ха с применением субгра-

В раздело задач ДЛП транспортного тзсга расс:<зтріЕ&отся сдэдущиэ задачи:

F12: наатп піп fFfx; = | с ^ / 1 V d.^J.

Г J(X) 1=1J=1 ^1Л *^J 1=1 J = 1 ^ —'

J=1

~ = ГГй; j = ЇГп J;

E x = b_Jf j = i.n; x. , > 0, i = i,

„« —J J і J

P13: иеигл n(n Ffr>,

<3ґ*; = fx_tJ: /„*„ <ь_л. ' = i.n:

^хі.і ~ ^ai* ¹ ~^1,m* ^хіз * ^{0> 1 = 1,m}* -¹ = ^1,n *

ти n

1=1j=l ^{13 13} 3=1 ^гз . ^u
PJ4: найти mtn і J;

(X,y) 5fX.y; ran n

1=1j=1 ^{13 13} j=i ^{3 3 u}

n . m

S(x,y) = (x_iy y₃: Z z_±i = ^-^{12 1}«ш; x^ = y^. з = 1 ,n;

lo .

^{3 3 3 13} I n і = l.m: J = l.n

m n

F15: найти mln ( F(x) + p. jc,. ).

X С M(X) 1=1 J=1 ^r"¹³

Для решения задач Р/Р - Р15 разработаны алгоритмы, основанные на методах потенциалов, покоординатного спуска, параметрического метода, декомпозиционные алгоритмы принципа Данцига - Вулфа и субградкентного метода. Для задачи Р14 приводится также прибли-езншй алгоритм метода вектора спада. .

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

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

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

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

модель ТС включает структуру и содержание файлов данных и предназначена для хранения параметров ТС в памяти ЗВМ и ее зашей в базу данных.

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

' Система KTS предназначена для автоматизации протеса моделирования ТС автомобильных дорог, расчета матриц и таблиц кратчайших расстояний и является основным инструментом подготовки информации о кратчайших расстояниях ео всех приведенных системах оптмизацки перевозочного процесса на AT. С помощью системы НТЗ смоделированы различные транспортные се ті: от республиканское ТС автомобильных дорог до районных и городских ТС.

Система КПЗ слугят для расчета кратчайших расстояний между пунктами погрузки-разгрузіш па базе смоделированной .танее ТС, базовой матрица кратчайших расстояний и таблицы привязки, а та:сг.;е для обеспечения импорта-экспорта файлов мезду системами !!S DOS, MTS и dBASE. Она является промежуточным этапом между системой ?iTS и прикладными системами, в расчетах которых используются кратчайшие расстояния.

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

Далее описываются математические модели, алгоритмы и система ТПЗ составления транспортного баланса и определения структур» и объемов грузовых перевозок экономического региона. Для построения транспортного баланса на перспективу, кроме информации о выполненных объемах производства и грузовых перевозках, задаются прогнозируемые обьеїн выпуска продукции на год планирования. После

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

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

Для решения общей задачи оптимизации структуры подвижного состава АТП используется следувдая основная базовая модель If): при ограничениях

a ^R3 ^ТгЗ ^Ь*3 ^ г. ^R3 ^ТгЗ ^ ^

Z Z Z ~г 4з * В; I Г р^₃ <_л « Р;

3=1 г=1 t=i D cr^ ^XJ 3=1 г=1 t=i ^ъз *^J

Z Г 2 <, <₃ < s; Z Z Z 1 n;

'-1 r=i t=1 ^{lJ J} 3=1 r=1 t=1 ^{J J} m і n p Tc n

1=1 D p_±7₀ 3=1 ^1J к=1 d^_ct₀ 3=1 *^J

Z* P?3Г = ^з^{: 3 = TT}"^:

R, T .

і _*-3 ^

*з т_Гз

^^ г 0. t=TTT_r;J: г=7ТІ\,: 3=ЇТЇі;

^{D 6}із Pi To « Уіз * ^D ^13 ^pi ⁷o- *^ ^J=TT*^:

^D \i ^ "To < ²k3 < ^D «Рад ^ To- ^te~*' ^3=T:"-
необходимо найти

I*:

n ^П3 ^Tr3 „ „ n m ^Cl *Н

¹ 3=1 r=i t=i *^J -^J 3=1 1=1 D PJq ^1J

- n p ^k n ^R3 ^ГгЗ _p ,.

⁺ E E z I; max ( F₂= Z Z Z P^ <_л

3=1 к=1 D ^7₀ ^k;i * 3=1 г=1 t=i ^³ ^

^R3 ^TrJ я!п f 7₃ = J, / P₂ }; шс{?_л= I f x^ <₃ j;

n V^TrJ ^3 _,

nor f J>₄ / №_e + E E E Г-7- <з ^{; ;: 0} 3=1 r=i t=i D a^j ^%i

n n ^СЛ p ^

nor f Р_д / №,+ E f E v_u + E 2_k j; ;,

где" 3_t и P_lc - количество транспортных единиц автомобилей і-й марки и прицепов k-й марки, которые необходимо распределить; p_t ті 1^ - коэффициент поставки автомобилей 1-й марки :і прицепов k-й марки; 7₀ - коэффициент выхода на линии новой техники: А". - объем транспортной работы прч перевозке грузов г-й линии 3-го АТП; Е^ и Qj. - количество транспортных единиц автомобилей 1-й марки й прицепов k-й марки, имеющихся в з-м АТП; р. - производительность работы t-ro транспортного агрегата при перевозке грузов на г-й линии з-го АТП; а^ - коэффициент, равный единице, если автомобиль 1-й марки з-го АТП входит в состав t-ro агрегата, г-й линии, и равный нули в противнем случае; b_t - коэффициент, указывающий количество прицепов или полуприцепов k-й марки з-го АТП, входящих в состав t-ro агрегата r-й линии; х - количестве транспортных единиц t-ro агрегата, используемых при" перевозкэ грузов не г-й линии з-го АТП; у и z_k - количество распределенных автомобилей 1-й марки и прицепов k-й марки з-му АТП; р_1Д и х^. - коэффициент выпуска на линию автомобилей 1-й марки п прицепов k-й марки автомобиля з-го АТП; в^ , 7_1;) ^и \у Ф^ ~ мини-мальное и максимальное количество автомобилей 1-й марки и прицепов k-й марки, которые мохно распределить з-му АТП; Ь^, - остаточная балансовая стоимость t-ro транспортного агрегата г-й линии 3-го АТП; CjD^- оптовые цены автомобилей 1-й марки и прицепов

к-й марки; s^_Jt я_а и й^ - себестоимость, прибыль и доходы выполненной транспортной работы t-м агрегатом при перевозке груза 1-й линии з-го АТП; сс^ - коэффициент выхода на линия t-ro агрегата г-й линии з-vo АТП; Ф₁ - общие основные фонда на конец года; Ф₀ - основные фонды на конец года без учета подвижного состава; К - выделенные капитальные вложения на приобретение новой техники; В - максимальная остаточная балансовая стоимость ПС; S - максимальные затраты на перевозку грузов; Р - максимальный объем транспортной работы; П - минимальная прибыль; D - количество календарных дней в планируемом периоде.

Математическая модель U1 мохет быть использована для решения следующих задач :_

1. определение оптимальной структуры подвижного состава;

2. распределение поставки новой техники;

3. определение оптимального плана использования подвитого состава на линиях перевозки;

4. перераспределение податного состава между АТП;

5. определение плана грузовых перевозок.

Для решения любой из перечисленных задач используется общая модель Ы1. Моделирование конкретной задачи осуществляется с помощью изменения значений правых частей системы ограничений модели и выбора необходимого критерия оптимальности. Линейные задачи модели М1 решаются пакетом ЛП-АСУ. Для решения дробно-линейных задачи- применяется метод "линеаризации" или параметрический метод сведения ее к линейным задачам с последующим применением пакета ЛП-АСУ.

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

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

"почасовых" автомобилей введем следующие обозначения: а_А -квартальше потребности в автомобилях по 1-й заявке: bf квартальные провозные возможности з-го АТП; x_tJ - количество автомо-билей з-го АТП, выделенных для обслуживания клиента 1-й заявки; ^dii ~ ^нУ^девыв пробеги между з-м АТП и пунктом расположения клиента 1-й заявки; c_±J - экспертная оценка производственно-договорных связей з-го АТП с клиентом 1-й заявки.

Тогда математическая модель имеет вид М2: найти

«Чп ( ЕЕ Vij^y ^ ^ciAi Z ^ххі = а . і = 77S; 1=13=1 ^{1J 1J} 1=13=1 ^{3 3} 3=1 ³

Е Х₁₃ 4 Ь₃ , 3 = -un; X_±J JO, 1 = Tm: 3 = ЇТії ).

Модель 112 является задачей транспортного типа с дробно-ли-евйным функционалом, для решения которой можно использовать алгоритмы метода потенциалов или параметрического метода. В случае, когда в каждом АТП можно варьировать количеством "почэсоеых" автомобилей, это даст возможность более свободного закрепления почасовых заявок без деления их объема по разным АТП. Если провозные возможности з-го АТП обозначить переменной у_ч, значения которой находятся в некотором заданном интервале [а*, р.], то математическая модель 12 имеет вид МЗ: найти

^{Ып (} 1з1 ^а±^' ' JJi ^{Аз :} її ^{X±i =а}^^{± =} ^

Модель U3 решается по приближенным алгоритмам метода вектора спада пли обобщенного градиентшго спуска.

При определении клиентурного плана грузовых перевозок для "сдельных" автомобилей формируются кольцевые маршруты, которые закрепляется за АТП по следующим моделям:

S4: найти mln Г Е Е Е Р<&* >'

X М(Х) 1=13=11=1 ^{3 3}

В5: найти таг ( Ё Е Е <%А_Л /ZEE ?1< Л

X М(Х) 1=13=11=1 ^{3 3} 1=13=11=1 ^{3 J}

П t

М(х) = (х. .: Е Е xi. = L.a.,i.= i.m; ^1J 3=11=1 ³

x^ < Ь\. j = i.n;^>0. і = 1.и: і - і.п: і = i.t J.

Здесь" о_± - квартальные объемы перевозки грузов на 1-м маршруте (заявке); Ъ_± - груженшФ пробег на 1-м маршруте; о* - квартальше провозные возможности з-го АТП по 1-му типу подвижного состава; Р±-> ^{Е d}iJ ~ np^iIBeA^SHBIie затраты и доходы на I ткм работы автомобилей 1-го типа подвижного состава з-го АТП при выполнении перевозок на 1-м марпруте; :г^ - объем транспортной работы, выполненный автомобилями 1-го ткпа подвитого состава j-ro АТП на 1-ы маршруте.

Линейная транспортная задача L'4 решается на минимум приведенных затрат при выполнении всех перевозок, а дробно-линейная транспортная задача М5 на максимум рентабельности перевозок. Для решения задач U4 и М5 используются метод потенциалов, параметрический и субградкентный методу. Кроме моделей 1!4 и 115 для составления клиентурного плана применяется поэтапный алгоритм, в котором задачи решаются для каадого типа подвижного состава в отдельности. Для решения на ЭВМ задач определения клиентурного плана разработана система PGP.

Последняя глава работы посвяцана вопросам математического моделирования и реиевия задач оперативного планирования и управления перевозочным процессом на автомобильном транспорте. Рассматриваются четыре взаимосвязанные мегдо собой системы SIGD1A, API! GP, ASPAK и ЫКР. в каздой из которых решаются три оптимизационные задачи: определение кольцевых маршрутов (задача маршрутизации), закрепление маршрутов за АТП (задача закрепления) и составление сменно-суточных заданий (ССЗ) выполнения грузовых перевозок по заявкам постоянной клиентуры.

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

Приведем математическую модель построения одного (к-ГО)

кольцевого маршрута, удовлетворяющего заданным ограничениям. Пусть заданы М пунктов погрузки, N пунктов разгрузки и R пунктов, в которых расположены АТП. Введем обозначения: с_±] - расстояние меаду 1-м пунктом погрузки и з-м пунктом разгрузки; 6.^ -расстояние между з-м пунктом разгрузки и 1-м пунктом погрузка; /^ - расстояние меаду г-м АТП и 1-м пунктом погрузки; f². -расстояние между з-м пунктом разгрузки и r-м АТП; К - количество всевозможных допустимых кольцевых маршрутов; я* - переменнзя, равная единице, если в k-й маршрут входит груженный пробег . и нулю в противном случае; z* - переменная, равная единице, если в к-й маршрут входит порожний пробег <зл>. и нулю в противном случае; /^ - переменная, равная единице, если в к-й маршрут входит нулевой пробег , и нулю в противном случае; f^, -переменная, равная единице, если в к-й маршрут входит нулевой пробег <з.г>, и нулю в противном случав.

Кольцевой (к-й) маршрут записывается в виде последовательности с _ г ,.1к . _к . „к . _к . . Jc . Jk . „2к ,

к" *»* 1 " 1 і * 1 і 1 1 Л 1 ^,и,1 1 ' У1 г>

^{К Г}0^Х1 ^l1³1 ³1^l2 ^Х2³2 ³t-1^lt ^Xt³t ³t^rO

Тогда математическая модель решения задачи определения одного (k-го) кольцевого маршрута имеет вид S6:

= ТЛ: = ТЛ;

^{* & J,'»«к * Д Л, ^ «s5 v}

Е Е Г 1 - Р₀-> ^сц ^i ~ Ї 2 Р₀ dji «?i -1=13=1 ^{и 1J 1J} j=ii=i ^{u J1 J1}

-E E P₀/rt«M- Ї 2 Ро-Іг^г⁵⁵⁰⁵

r=1 1=1 ^rl 1=1 r=1 ^{u Jr Jr}
M N . N U

«fV = E E a a + E E b z* ^K ,i=u=i ^{13 1J} j=ii=i ^{31 J}

+ E E 4i 4i ⁺ 2 E SX. У²^ » «or.

r=1 1=1 ^^{1 ra} 1=1 r=1 ^{Jr jr}

где *₁ - максимальное количество допустимых груженных ездок на маршруте; р₀ - максимальное значение коэффициенте использования пробега; 1₁ и Ъ^ - минимальная и максимальная протяженность маршрута; a_tJ, &„, g^ и g?_r - некоторые заданные числа, характеризующие эффективность выбранного маршрута.

Математическая модель U6 может быть использована в декомпозиционном алгоритме решения следущей задачи комплексной маршрутизации для определения оптимального маршрута при заданных ограничениях. Введем дополнительные обозначения: D - объем перевозки груза между 1-м и 1-м пунктами; А - провозные возможности j^-ro АТП; u>_k - интенсивность к-го маршрута. Тогда математическая модель решения задачи комплексной марорутизацки имеет вид МТ:

К М- И .

Е Е Гс^а* «

k=l 1=11=1 ^{iJ 13 k}

К ( И N Я М _k

ЕЕ Е с л* е Е а г*_± *

1с=Н1=11=1 ^{1J хг} 1=11=1 ^J1 -¹¹

Е Е Ґ_г1 v Е Е J% V% 1 ^

г=11=1 " ^rl 1=1г=1 ^{Jr Jr} J *

Е ^ »_k < 'D₁₃. і = Тї; і = О;

Г M

'"rl ^wk " "г-

Z Ё 1/1? «L = >L. r = 17E;

k=1l»1

ш_к ) 0, к = кі; ( а*_л. i%_t, 4Ї» У^г ^;- ^Sk' ^к = ^-Математическая модель U7 представляет собой обобщенную задачу ДЛП с неизвестными коэффициентами, для репения которой мокно применять декомпозиционные алгоритмы. Если задача Ы7 имеет небольшое число ненулевых D_1Jt то для ее решения используются методы декомпозиции Данцига - Вулф?.. Для более общего случая применяется алгоритм, основанный на схемах декомпозиции по ограничениям и переменным с использованием субградиентных методов.

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

ain ( (X) = Z Д.-..: х.= а., і = ТТ^;

x_ti = ay і = 1.п; х_и і 0, х_±і = х_п, і = і.п; з = і.п }.

Здесь а_± - объем перевозки по і-й заявке, /_±J - порожние пробеги на маршруте (i.j); х_%. - интенсивность маршрута (i.j).

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

Далее приводятся математические модели и алгоритмы решения
задач закрепления маршрутов за АТП и выбора оптимального подвиж
ного состава для выполнеьия грузовых перевозок по ним. В резуль
тате решения задачи двухзвенной кольцевой маршрутизации получаем
оптимальную систему маршрутов G = (g g_m), которые необхо
димо закрепить за АТП. В зависимости от производственной ситуации
и технологии выполнения перевозок задача закрепления может быть

решена различными математическими моделями и алгоритмами.

Рассмотрим модели решения задачи закрепления маршрутов, по которым перевозятся однородные грузы. Пусть заданы п АТП с провозными возможностями о., соответствухсими общим грузоподъем-ностям всех автомобилей з-го АТП. Если через с₁₃ обозначить коэффициент увеличения порожнего пробега при закреплении 1-го маршрута за з-м АТП, а через х_± . - объем закрепленого груза 1-го маршрута за з-м АТП, то математическая модель закрепления маршрутов за АТП будет иметь вад М9: найти

ntn ( Z Е с jv : I х = g_±. і = 7^; 1=13=1 ^{1J 1J} 3=1 ^J

E X_± ^ ^bj» І = ^a» ^xij » 0. і = 77m: 3 = T7n J. При решении задачи U9 находятся объемы перевозки для каждого АТП. Конкретный тип автомобилей и их количество определяются в АТП в зависимости от закрепленных маршрутов. Для каждого з-го АТП решается следующая математическая модель. В результате решения задачи М9 для каждого з-го АТП имеем: т. - количество закрепленных маршрутов за з-м АТП; g^ - объем перевозки по t-му маршруту 3-го АТП. Введем дополнительные обозначения: s-|_t. d^_t и у-^ -соответственно себестоимость, доходы и объемы перевозки 1-м автомобилем з-го АТП на t-м маршруте; ф^ и ф - максимально возможные величины отклонения объема перевозки от интенсивности t-ro маршрута з-го АТП. Тогда математическая модель выбора марки автомобилей и их количество на каждом маршруте имеет вид НЮ: найти

"з ^аз ^пз ^шз чах ( Z I ^_ty_lt /ЕЕ ЗУ : i=it=i ^±Ji ^ i=it=i ^х* ^АХ

_хЕ y_lt < в* * Ф?. .t = i._Bj; y_lt > g³_t - ф>. „ = ..»,.

t = 1.m.

п п

\^qi -

L 0 . 1 = 1.n.

e; u,t-*i-

_t . 'It - ^t« * " ""З" "It , n 1 , ,
ta=1 * i, о . 1 = 1 .п.; t = 1.0.

Задача маршрутизации может быть решена двухэтапным методом отдельно для- каждого типа подвижного состава. Пусть заданы ю маршрутов с интенсивностями g,, ^. ... » ^ и п АТП, в каждом из которых имеются t. типов подвижного состава с грузоподъем-

ностями cf: и в количестве к*Г транспортных единиц для каздого г-го тала автомобиля. Пусть с^ - коэффициент увеличения порожнего пробега при закреплении і~го типа подвижного состава j-го А'ГП за 1-м маршрутом; р_±- экспертная оценка штрафа за отклонение от интенсивности 1-го маршрута; Ь^ - общая грузоподъемность автомобилей 1-го типа з-го АТП; и_± и v_± - отклонения от интенсивности 1-го маршрута: т - объем груза 1-го маршрута, перевезенного і-м типом подвижного состава j-ro АТП. Тогда математическая модель закрепления маршрутов за АТП имеет вид М11: найти

Pi ( "і - V ^;

1.m;

^ = (0, kj q^;, і = i.m; і = i.n; г = i.t

J'

^ui * * ^и1** » ^{1 = 1 ,m}'

При решении двухкритериальной задачи М11 можно применить модель Н12г найти

ш n *J ^C1J , n *J

mtn f_ E. —^— *Zy I E ^ > в_±. і = і.»:

i=u=ir=i g^ ^1J j=ir=i

^{0 $} ^їj ^s /ij» *^»5 3=ЇТп; г=Т7г_л ;,

где /J = /j_± - nod Cg_lt <7pt i=TTm; j=77n; r=iTtj - максимальный объем 1-го маршрута, который может быть закреплен за r-м типом подвижного состава j-ro АТП.

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

много запретов, модель М12 эффективнее решать в сетевом виде.

Кроме задач маршрутизации и закрепления, при планировании грузовых переюзок решается задача составления ССЗ по заявкам постоянной клиентуры, в которых задаются минимальные и максимальные дневные объемы перевозки. Требуется распределить имещейся поданкной состав по заявкам и составить ССЗ с целью снижения затрат на перевозку и повышение доходов с обязательным выполнением минимальных дневных объемов по всем заявкам. Для описания общей математической модели решения данной задачи введем следующие обозначения: ш и п - количество заявок и автомобилей; і и і -индекс заявки и автомобиля: aj и а^' - минимальный и максимальный объем работы; p_L. - объем. выполненной работы (производительность); Cj. и d_LJ - затраты и доходы на единицу работы; x_ti -булева переменная. Тогда общая математическая модель закрепления автомобилей для выполнения грузовых перевозок по заявкам постоянной клиентуры будет иметь вид М13: найти

«in С II е.. р..*.. /ЕЕ «,,Р»1.

13 г_±і ~_хі

п.

Різ ^хіз > i- ^х = ¹-^m; h ^Р« ^Х13* 1 * ' ^Um:

L О , 1 = і.ш: 3 = 1 .п

Е х_Л1 < U з = 1.п; х_Л1 = \ ;.

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

Все перечисленные выше математические модели t алгоритмы используются в разработанных системах оперативного планирования и управления грузовыми перевозками при решении задач маршрутизации, закрепления и составления ССЗ.

Для автоматизации процесса оперативного планирования и управления междугородными автомобильными перевозками массовых грузов в пределах заданного региона разработана система БПЗША, которая позволяет организовать централизованный сбор и обработку заявок на междугородные перевозки: определить оптимальные кольцевые маршруты перевозки грузов на всей территории региона; распределить маршруты между АТП региона и закрепить оптимальный подвиж-

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

Информационное обеспечение системы SIGEJA состоит из трех частей. Это информация о ТС и кратчайших расстояниях, база нормативно-справочной информации (НСИ), заявки на междугородные перевозки и провозные возможности подвижного состава.

Моделирование ТС и расчет матриц кратчайших расстояний, таблиц привязки и соответствия осуществляются с помощью систем MTS и KRS. База НСИ формируется системой SIGEMA, а заявка на междугородные перевозки вводятся и корректируются оперативно. з каждом АТП системой ABM GP. Подготовленные заявки передаются системе SIGEMA для централизованной обработки и формирования кольцевых маршрутов. На основе этой информации решается задача маршрутизации, которая состоит из следующих этапов: подготовка необходимой информации о заявках, провозных возможностях и кратчайших расстояниях; решение задачи кольцевой маршрутизации; решение задачи закрепления маршрутов за АТП; анализ и корректировка маршрутов. Разработанные маршруты передаются в АТП и используются системой AM G? для расчета ССЗ.

Система AM GP предназначена для автоматизации процесса
оперативного планирования и управления автомобильными грузовыми
перевозками в АТП, завершающим этапом которой является состав
ление ССЗ для каждого автомобиля. Она может быть использована
автономно в каждом АТП в качестве автоматизированного рабочего
места диспетчера для ежедневного формирования ССЗ грузовых авто
мобилей или в сети с системой SIGSiA. ' _ '

Опишем общую схему применения системы АШ GP. Предварительно формируется база НСИ и готовится информация о ТС и кратчайших расстояниях. Ежедневно вводятся новые или корректируются стерне заявки' на перевозку грузов и провозные возможности подвижного состава. Планирование грузовых перевозок осуществляется на заданный дєеь и проводится в целом по АТП или в отдельности по филиалам, колоннам и бригадам. На основе полученных планов для междугородных, зональных я городских перевозок рассчитываются ССЗ для каждого автомобиля. Отдельно формируются ССЗ для автомобилей, работающих на условиях почасовой или сдельной оплаты по заявкам постоянной клиентуры. По каждому ССЗ рассчитываются временные и стоимостные показатели работы автомобиля, а также расстояния

перевозки и расход топлива.

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

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

Пусть имеется т заявок на перевозку, в которых с^ - количество контейнеров; р_± - пункт погрузки; q^ - пункт разгрузки. Построим множество всевозможно допустимых двухзвенных кольцевых маршрутов (i,J) кз і-й и j-2 заявок по следующим признакам: коэффициент использования на маршруте должен быть больше заданного числа, а количество контейнеров по 1-й заявке должно соответствовать количеству контейнеров по з-й заявке. Для этих маршрутов определяются значения коэффициентов с , которые приравниваются к порожним пробегам на маршрутах (i,J) и u_t , пришмапцие значение единицы, если в 1-х или i-z заявках, формирующих допустимый двух-звошшй кольцевой маршрут, хотя бы один из пунктов погрузки иди разгрузки совпадает с пунктом грузоотправителей или грузополучателей, указанным в товарно-транспортных накладных. Если через х_± обозначить переменную, принимающую значение единкш, если 1-я и з-я заявки фордируют двухзвенный кольцевой маршрут, и нуль в противном случае, то математические модели определения оптимальных двухзвенных кольцевых маршрутов будут иметь вид:

MU: найти nln ( Z Т. е.. х„ }; X R(x) 1=13=1 ^{1J хз}

MIS: найти яіп ( с x / й x );

X R(X) 1=1j=1 ^{13 13} 1=1 J=1 ^{13 1J}
m

R(x) = ( x. .: x. . = 1 . і = i.m: ³ j=i ^1J

E X.. = 1, 1 - 1.т; X. . Ъ 0, 1 = 1.га: 3 - 1 .n J.
1=1 ^{1J 3}

Задачи ifJ4 и M75 представляют собой задачи о Егзнзчес'яі. Если учесть запретные элементы моделей, то они могут быть .переформулированы в виде задачи о минимальном парасочетании в ориентированном двудольном графе.

Пусть в результате решения задачи М14 или Мт5 определена оптимальная система из й двухзвенных кольцевых маршрутов с интея-сивностями (g_r), где g^ - количество контейнеров, которые необходимо перевести по каждой заявке маршрута. Тогда для перевозки контейнеров по маршрутам необходимо закрепить их за ГАС и выбрать для них подходящий автомобиль. Пусть по всем ГАС имеется р заказанных автомобилей и для каждого из них изгестны провозные возможности Ъ_х, которые соответствуют количеству контейнерных мест на і-f автомобиле. Введем обозначения: у _х -переменная, принимавдая значение единицы, если на .т~м маршруте закрепляется 1-й автомобиль, и нуль в противном случае; /_г1 -величина изменения порожних пробегов, если на r-м маршруте закрепляется 1-й автомобиль; с _х и d_rl - затраты и доходы при перевозке контейнеров г-го маршрута 1-м автомобилем. , тогда для решения задачи закрепления автомобилей за маршрутами чспользуется одна из следухщих моделей:

М16: найти mln ( I f у };

у R(y) г=11=1 ^{гі гі}

1117: найти mln ( Z I с у / Y. I d У_г1 і:

У Щу) г=11=1 ^{Гі Гі} r=1l=1 ^{T1 Т1}
Р k

R(y) = ( у_г1: Е У_г1 = и * = i.t; Е У_, < и і = і.р;

У_г1 > 0, r = ГГк: 1 = Ї7р J.

Задачи 1И6 и ІИ7 также могут быть сведены к задачам о назначение.

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

Проблемно-ориентированная система ASPAZ предназначена для автоматизации основных функций организац"онного планироваиш и

управления автомобильными контейнерными перевозками- Она используется в качестве автоматизированного рабочего места диспетчера для оперативного формирования заданий водителям грузовых автомобилей и управления междугородными и городскими контейнерными перевозками. Основными функциями системы /SPAK является: прием и отправка контейнеров с площадки; регистрация контейнерных перевозок; оперативный учет использования контейнеров; инвентаризация контейнерного парка; учет выполнения клиентурного плана перевозок; расчет оплаты за предоставленные клиенту услуги; . ведение НСИ.

Система МКР предназначена для маршрутизации контейнерных перевозок в междугородных и технологических направлениях. Она информационно взаимосвязана с системой ASPAK и готовит для нее кольцевые маршруты. Кольцевые маршруты на междугородные перевозки определяются на базе полученных от КП заявок на перевозку. Информационные и вычислительные процессы соответствуют системе SIGMA. В МКР решаются математические модели М14 - U17. Построенные кольцевые маршруты передаются на КП. которые в дальнейшем используются в системе ASPAK при организации перевозочного процесса автомобильных контейнеров.

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