Оптимизация маршрутов в системах централизованного обслуживания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

<¡4. На правах рукописи

Л'

л БАБАЕВ

Валентин Александрович

ОПТИМИЗАЦИЯ МАРШРУТОВ В СИСТЕМАХ ЦЕНТРАЛИЗОВАННОГО ОБСЛУЖИВАНИЯ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Специальность: 01.01.09 - "Математическая кибернетика"

Санкт-Петербург 1998

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

Научный руководитель - доктор физико-математических наук,

профессор Петросян Л.А.

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

профессор Захаров В. В. кандидат физико-математических наук Сурвилло Т. Г.

Ведущая организация - Санкт-Петербургский Экономико-

математический институт РАН

Защита состоится 20 мая 1998 года в 17 часов на заседании диссертационного совета К-063.57.16 по защитам диссертаций на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, 10-я линия В.О., д. 2t3, ауд. 88.

С диссертацией можно ознакомиться в научной библиотеке им. A.M. Горького Санкт-Петербургского государственного университета.

Автореферат разослан апреля 1998 г.

УЧЕНЫЙ СЕКРЕТАРЬ ДИССЕРТАЦИОННОГО СОВЕТА

доктор физико-математических наук,профессор

В Ф. ГОРЬКОВОЙ

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

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

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

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

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

Научную новизну работы составляют:

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

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

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

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

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

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

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

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

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

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

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

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

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

г I

Апробация работы. Отдельные научные и практические результаты докладывались п обсуждались на I городской научно-практической конференции "Наука и образованно — городу" (Санкт-Петербург, 1997 г.), Международной конференции молодых ученых (Санкт-Петербург, 1996 г.), на научных конференциях и семинарах Санкт-Петербургского государственного университета и заседаниях кафедры математической статистики, теории надежности и массового обслуживания СПбГУ (1994 - 1997 г.г.).

Реализация результатов исследования. Основные результаты работы реализованы в учебном процессе СПбГУ п Михайловской артиллерийской академии. Внедрение программного обеспечения задач маршрутизации осуществлено в отделе АСУ предприятия ЛИВАС.

Публикация работы. Материалы исследований опубликованы в [1-5].

Объем работы. Диссертационная работа состоит нз введения, трех глав и заключения, изложенных на 114 листах текста п содержащих 16 рисунков, 17 таблиц и список литературы из 42 наименований, а также вкл'ючает 3 приложения с исходными текстами ПАСКАЛЬ-программ на 22-х листах.

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

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

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

Для формализации задачи введены следующие обозначения:

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

Ъ} - потребности пунктов назначения, ./ = 1,2, • • • ,п;

¿ц - протяженность учгстков пути между пунктами, г,з = 0,1, - • •, л;

О - индекс исходного пункта;

X{j - количество груза, находящегося на транспортном средстве при его следовании от г'-го пункта до пункта j;

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

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

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

г п

L - min £ Y. xíjdij- (1)

¡=0j=l

Ограничениями задачи будут являться:

í><y = £ty (2)

3=1 1

п

x¡0 = 0; (3)

i=l

n

£ (Xkj - Xjk) - bj, j = 1,2, • • •, 7»; (4)

i=0

n

][>ign (я0) = 1, j = 1,2, (5)

>=o

n n

£ sign {Щj) = 1; £ siga (x¡j) < 1, i = 1,2,-- • ,тг; (6) j=i j=i

dij >0, bj> 0, x¡j >0, г = 0,1, • • •, n; j =? 1,2,(7) , . f 1, если xa > 0: SlgQ^) = |o, если 4 = 0.

Целевая функция (1) задачи экспедитора совпадает с целевой функцией классической транспортной задачи. Но ограничения ее сугубо специфичны:

условие (2) заключается в том, чтобы из исходного пункта на транспортном средстве было вывезено ровно столько грузов, сколько их требуется в пунктах назначения; .. . 1 '

где

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

условие (4) показывает, что разница в нагруженностп транспортного средства перед прибытием в ¿-й пункт назначения п после убытия из ¿-то пункта назначения равна потребности этого пункта;

в условии (5) записано, что транспортное средство в каждый пункт назначения прибывает только по одному разу;

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

Задача (1) - (7) не может быть решена методами линейного программирования, так как ее ограничения (5), (6) носят нелинейный характер.

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

минимизировать целевую функцию /

л п п

¿ = ЕЕ£ь}Уч (8)

1=0у=1 ¿=1 при следующих ограничениях

£*у = 1, 7 = 1,2,...,п; (9)

<=о

£ 45 = 1, £ Щ < 1, .• = 1,2, • • • ,п; (10)

з=\ }=1

2; - + < П - 1, 1 < 2 ^ } < П, (11)

где: агу € {0,1}, г = 0,1, • • •, п; з = 1,2,- • • ,п;

XIj = 1, если груз после пункта г доставляется в пункт ]] г* - очередность доставки груза в к-й пункт, гк 6 {1,2,А = 1,2,---,п;

Г 0, если г* > г,-;

' УЧ ~ \ 1

11, в противном случае.

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

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

52 ЬР1 пиа, (12)

*=1 1=к

где: РиР2, • • • ,Рп ~ элементы перестановки Г\ Ро - номер исходного пункта, ро = 0.

Преимущество формализации (12) состоит в том, что ограничения в явном виде отсутствуют и требуется указать такую перестановку, которая минимизирует эту целевую функцию. Отсутствие ограничений объясняется тем, что перестановка пунктов объезда автоматически удовлетворяет ограничениям (5) - (6) и (11), а ограничения (2) - (4) и (9), (10) неявно присутствуют во втором слагаемом целевой функции (12).

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

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

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

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

ния. Вычислительный эксперимент проводился на персональном компьютере IBM с процессором Intel Pcutiura-133. Например, при решенпп задачи экспедитора с 11 пунктами назначения время полного перебора маршрутов методами вектора инверсий, циклического сдвига, лексикографического порядка, счетчика факториала, транспозиции п плавающих элементов составило: 74, 38, 19, 15, 9 и 3 сек соответственно.

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

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

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

Теорема 1. Если выполняются условия:

dij = Ж dik ~ о<У<?» ' J = 1'2'''''i=zi~ 1; (13)

(И)

"0,1 «1,2 «п-1 ,п

то перестановка Р — (1,2, • • •, п) является оптимальным маршрутом экспедитора, а минимальное значение целевой функции вычисляется по формуле

'^tdi-uiibj. (15)

1=1 , j—i

Теорема 2. Если некоторая перестановка Р = (Р1,Р2> ,Рп) минимизирует целевую функцию

4P)=tdP^tbPn (16)

t=i i=k

то эта же перестановка минимизирует и целевую функцию

Рк-т bpi + £ wpt L "p/i (17)

к=1 l=k Ь=1 /=Н 1

где: d*ij = djj—u; — Vj, j = 0,1, • ■ •, n, г = 0,1,• • • ,n; (18)

Wk = Щ + vk, к = 0,1,---,n; (19)

Ui = ßmin dij, i = 0,1, • • •, ra; (20)

Vj = min (dij - щ), j = 0,1, • • •, n. ' (21)

Справедливо и обратное утверждение.

Теорема 3. Оптимальное значение целевой функции (16) отличается от оптимального значения целевой функции (17) на величину

AL = L(P) - L*(P) = U + V,

n n

где: U - щ bk) V = J2 vkbk.

kr-. I ¿=1

Теорема 4. Если одновременно выполняются два условия:

> h. > ... > Ь.-

Wi ~ wi ~ ~ U>n d'oi = d* i2 = • • • = d*n_i,n = d*n, о = О, то перестановка Р* = (1,2,---,гг) является решением задачи. При этом минимальное значение целевой функции (17) вычисляется по формуле

I(P*)= £ ь,.

/Ь=1 f=*+l

В соответствии с теоремой 1 формула (15) может быть использована для вычисления оптимального значения целевой функции, если выполняются условия (13) и (14) или можно добиться их выполнения после некоторого переупорядочения пунктов назначения.

Теорема 2 дает право производить преобразования (18) - (21) исходных данных задачи экспедитора и определять при поиске оптимального маршрута нижнюю границу решения

Я8(Ре) = Я! + Я2 + Яз. : (22)

Теорема 3 позволяет достаточно просто вычислять первую составляющую нижней границы (22) по формуле

Я, = щ t h + t "кЬк. (23)

t=l Jb=l

Теорема 4 дает возможность определять вторую составляющую нижней границы

Я2 = Е wk ± Ь,. (24)

*=1 /=*+1

И в качестве третьей составлящей нижней границы на дереве вариантов для вершин s-ro яруса будет

Яз=Е d'Pi_lPl±bPl. (25)

*=i i=k

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

HS{PS) > 1 < s < п, (26)

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

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

Процедура поиска оптимального решения заканчивается тогда, когда условие (26) выполняется для всех неветвленных вершин на всех ярусах дерева вариантов. В этом случае рекордное значение целевой функции ¿° объявляется оптимальным.

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

района. При определении расстояний </,•; между пунктами предоставляется возможность пспользовать одну из применяемых в математике метрик:

евклидову = \jixi - Х})2 + (у, - !/;)2;

манхеттенскую = \xi — Xj¡ + \у, - г/;|; чебышевскую = тах(|г,- — Х]\, (?/,• —

аффинную ¿{} = /(а;,- - х^2 + 0.5(х,- - х^)(гл - щ) + (у; - у;)2,

где х,у - координаты соответствующих пунктов с индексами г,./'.

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

а jzi.ni 1 \ / — 4- К2/1 — щ)\, если г >

<1, = + 0.1то<1,ос), где с = | ^ + ^ _ |(у>. + ^ . < •

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

Количество перспективных вершин на каждом ярусе и общее количество

перспективных вершин на всем дереве вариантов:

'8

А„ = аА-1^-1 = П 5 = 1, • • •, п; (27)

¿=1

Л(п) = £ А, = ЕП^-ь (28)

в=1 «=1,7=1

где: се в - доля перспективных вершин ио ярусам, в — 1, - • •, п;

= п — з - степень ветвления вершин на ярусах в соответствии с принятой структурной схемой дерева вариантов, з = 0,1, • • •, п.

Количество отсеченных ветвей по ярусам и общее количество отсеченных ветвей на всем дереве соответственно равно:

• • ' «-1

>=1

Г(п) = £ ъ =£/?Л-1П(1 (30)

5=1 5=1 .

1 до Зц - доля отсеченных ветвей по ярусам, в = 1, •••, п.

Общее количество анализируемых вершин на каждом ярусе и на всем дереве вариантов удовлетворяет следующим формулам:

я

Л = А, 4- 7« = = П "j-ivj-i, « = 1, • • •. ">' (31)

j=1

Ф(и) = А(п) + Г(п) = ± ^ = ± П (32)

f-i »=ij=i

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

п

р(п)=]]оЛ-1. (33)

S=1

Средневзвешенный коэффициент перспективности вершин дерева вариантов вычисляется по формул?

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

г(п) = цп\[т1{п)]пщ ■ (35)

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

Из перечисленных параметров программным путем осуществлялся подсчет только количества отсекаемых вершин по ярусам, числа обновлений рекорда и затрачиваемого на решение задачи времени, а остальные характеристики вычислялись с использованием зависимостей (37) - (32). Это позволило установить полное совпадение экспериментального значения р{п) с его формульным значением (33), определить приближенное значение коэффициентов для зависимостей (34), (35) п вывести эмпирическую формулу для прогнозируемого времени (сек) решения задачи методом ветвей и границ при 12 < п < 24 на компьютере типа IBM PC

r(n) «/т![??(гс)]пп,

где: т}(п) и 0.275 - 0.005п; ц « 0.01 (для IBM Pentium-133).

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

границ. Например, для манхеттенской и чгбышевской метрик по сравнению с евклидовой и аффинной имеет место сокращение времени решения задачи в среднем на С%. Аналогичное сокращение проявляется во всех метриках при переходе от несимметричной матрицы расстояний к симметричной. Наблюдался некоторый рост времени решения при переходе от одной формы района расположения пунктов назначения к другой. Так, для районов 50 х 50, 100 х 2о и 250 х 10 км соответственно среднее время решения задач составляет пропорцию 1 : 1.2 : 1.4.

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

Ид1 я алгоритма ближайшего пункта состоит в том, чтобы осуществить попытку минимизировать целевую функцию следущим образом. Двигаясь из исходного 0-го пункта п пц-й ближайший пункт назначения, мы опрег деляем для целевой функции Ь произведение Ь\ = Д)(/о„и как ее первую частную составляющую, где:

п

ва - 52 ъ?, 4)™, = [»'Д ^оу-

Из тщ-го пункта назначения направляемся в тг-й ближайший пункт назначения и определяем вторую составляющую целевой функции Ьч = Вр/,,,,,,,,, при этом:

- Вй- ; (1т,тг - иЦп <1т,}.

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

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

Ье = Вч шп В, = В5_] - Ьтг

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

транспортного сродства М ~ (О,Ш1,••■,»?„) с приближенным значением целевой функции

л п п

Ь = £ Ьв = £ '¡т.^т. £ КН •

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

К,, > ЬГП2 > ■ • ■ > Ьтп.

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

Двигаясь из исходного 0-го пункта в тщ-й пункт назначения, мы определяем для целевой функции Ь произведение Ь\ — Ьт> 0\ как ее первую частную составляющую, где:

■ Ь<п 1 = гоах Ьу, Ох = ¿От,-

Из Ш1-го пункта назначения направляемся в т%-й пункт назначения и определяем вторую составляющую целевой функции Ь? = Ьтг-Ог, при этом:

Ьтг = тах 6,-; Дг = А + 4|пц-

I <?<п

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

Д, = ь, = Оа ыжЬу

Такая последовательность действий осуществляется до момента достижения последнего пункта назначения. Это дает возможность получить маршрут транспортного средства М = (О, Ш1, • • •, т„) с приближенным значением целевой функции

п п в

5=1 «=1 1 = 1

Смысл алгоритма маршрутизации по невозрастанию удельной удаленности груза заключается в следующем. На основе вычисления частного (/^/Ь;, где г - пункт, в котором в данный момент находится транспортное средство, определяется такой следующий пункт назначения для которого это частное является наименьшим. В отлично от двух предыдущих алгоритмов, где производился выбор по одному параметру, здесь мы стремимся достичь минимизации целевой функции «разу по двум сомножителям ее частных составляющих. В этом алгоритме заложено стремление получить такой маршрут следования транспортного средства, для которого выполнялось бы одно пз условии оптимальности

В алгоритме выбора лучших участков итерации проводятся на матрице удельной удаленности || (|, = 0,1,••• , п. Пусть наименьший элемент находится в А'-й строке и /-ом столбце матрицы. В этом случае участок (*:,/) вводится в список участков маршрута С как бинарное отношение < а],С] >, где «1 = к; с\ = I. Затем к-я строка и 1-й столбец исключаются из матрицы || ¿¡¡¡Ь^ || п осуществляется запрет возможного возникновения внутренних подциклов на маршруте путем замены соответствующего элемента (в данном случае элемента, находящегося на пересечении 1-й строки и к-то столбца) знаком оо.

Аналогичная процедура повторяется п раз по количеству пунктов назначения. В результате будет получен неупорядоченный по предшествований пунктов список маршрута С — {< а^С] >, < а-г, с2 >, ■ • •, < ап, сп >}.

Этот список упорядочивается так, чтобы соблюдались условия а\ = 0, а2 = С1, ■ • •, ап = сп-1. После чего маршрут экспедцтора представляется конечными пунктами соответствующих участков М = (0,С), • • ■ ,с„).

В соответствии с полученным маршрутом вычисляем первую составляющую целевой функции

п

= Х^т^го^тг »=1

Последующие составляющие 5 = 2,3, • • •, п определяется по формуле

; П

г=1

В итоге маршрут транспортного средства М = (0, тп}, ■ ■ •, тп) дает приближенное значение целевой функции

п П П—

. — £ — И £ Ьт^^йт^гщ.

«=1 «=1 >=1

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

Теорема 5. Нижняя граница количества нулей в модифицированной матрице расстояний || гу || равна 2п 4-1, где: щ = г/,;- - щ - V), г = 0,1, • • •, п; ./' = 0,1, • • •, п; и;, V) - приводящпе константы.

Приводящие константы выбираются таким обратом, чтобы выполнялось условие гу > 0, г = 0,1, • • •, п; ] = 0,1, • • •, п. Этого условия можно добиться. если последовательно произвести сначала вычитание из каждой строки матрицы || d¡j || минимального элемента этой строки, а затем на основе частично преобразованной матрицы || || из каждого ее столбца произвести вычитание минимального элемента этого столбца. Описанные действия гарантируют наличие хотя бы одного нуля в каждой строке ц каждом столбце матрицы || г,||. Затем с целью получения наибольшего числа нулей проводятся модифицирующие преобразования, чоторые в итоге позволяют повысить вероятность совпадения элементов маршрута экспедитора.с нулевыми элементами модифицированной матрицы расстояний, а, следовательно, и найти решение задачи экспедитора с меньшим значением целевой функции.

На основе вычисления отношений «^-/б,1, где и/у = щ ■+■ ] = 1,2, • • •, п, формируется такой маршрут следования транспортного средства, для которого выполняется условие . .

< < ... < Югп"

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

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

Прикладные аспекты задачи экспедитора исследовались на предприятии ЛЙВАС для планирования маршрутов доставки готовой продукции, что позволило рекомендовать предприятию оптимальное планирование процесса доставки на основе автоматизированного составления маршрутного листа в отделе АСУ.

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

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

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

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

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

предложена постановка транспортной задачи специального вида — задача экспедитора, отличная от известных постановок классических транспортных задач и различных моделей задач коммивояжера;

осуществлена математическая формализация задачи в трех модификаци ях — в терминах переменных х^, где щ - количество груза, перевозимого от »-го пункта к ^'-му пункту, в терминах целочисленных переменных где хц £ {0, 1} в зависимости от того, проходит ли маршрут из пункта i ь пункт з ив терминах перестановок Р, где Р — (рир2, • • • ,рп) ~ последовательность объезда пунктов;

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

исследованы возможные алгоритмы перечисления перестановок и разработан метод плавающих перестановок, превосходящий в 3 раза по быстро-

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

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

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

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

При проведении вычислительных экспериментов установлено, что переборные методы на основе перестановок для получения точных решений могут быть использованы в практических целях при п < 12. Использование алгоритмов на основе метода ветвей и границ позволило расширить диапазон размерности точно решаемых задач до п < 24. Ограничения на размерность задачи экспедитора для приближенных алгоритмов связано с емкостью оперативной памяти, в которой должна находиться входная информация по задаче. В частности, стандартные средства языка ПАСКАЛЬ позволили создать программу, которая за доли секунд выполняет решение задачи экспедитора со 170-ю пунктами.

Прикладные аспекты задачи экспедитора исследовались на предприятии ЛИВАС, что позволило рекомендовать отделу сбыта методику оптимального планирования процесса доставки производимой продукции на основе автоматизированного составления маршрутного листа.

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

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

СПИСОК ОСНОВНЫХ РАБОТ

1. Бабаев В А. Оптимизация маршрута служебной развозкп. В сб.: Наука и образование городу. Ч. 1.-СП6.: Изд. мерин, 1997.- С. 58.

2. Бабаев В.А. Определение последовательности доставки грузов. В сб.: Наука и образование городу. Ч. 2.-СП6.: Изд. мерин, 1997.- С. 10.

3. Бабаев В.А. Оптимизация обслуживания запросов в локальной вычислительной сети. В сб.: Актуальные вопросы развития РВиА СВ.- СПб.: МАА, 1996.- С. 246-248. Инв. Н-Ю4С0.

4. Бабаев В.А. Алгоритм формирования "плавающих" перестановок. Научно-технический сборник. N 11,- Тула: ТВАИУ, 1997.- С. 17-19.

5. Бабаев В.А. Исследовательская модель для задач маршрутизации. Известия Тульского государственного университета. Серия: математика, механика, информатика. Т. 3.- Тула: ТГУ, 1997.- С. 26-28.

Подписано в печать 13.04.98 г.. Формат 60x90715- Объем 1уч.-изд. л.

' . Зак. 1080