автореферат диссертации по транспорту, 05.22.01, диссертация на тему:Совершенствование информационной системы транспорта на основе оптимизационной технологии

УДК 629.76

На правах рукописи

ЕРОЩУК Николай Васильевич

СОВЕРШЕНСТВОВАНИЕ ИНФОРМАЦИОННОМ СИСТЕМЫ ТРАНСПОРТА НА ОСНОВЕ ОПТИМИЗАЦИОННОЙ ТЕХНОЛОГИИ

Специальность 05.22.01. «Транспортные и транспортно-технологические системы страны, ее регионов и городов, организация производства на транспорте»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

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

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

Научный руководитель:

доктор военных наук, доцент Родионов Михаил Александрович

Официальные оппоненты:

кандидат технических наук, доцент Зайцев Евгений Николаевич

Ведущая организация:

Санкт-Петербургский государственный инженерно-экономический университет

Защита состоится «20» мая 2005 года в 10 часов на заседании диссертационного совета Д.223.012.01 в Санкт-Петербургском государственном университете гражданской авиации по адресу: 196210, г. Санкт-Петербург, ул. Пилотов, 38.

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

Автореферат разослан «20» апреля 2005 года

Ученый секретарь

диссертационного совета Д.223.012.01 доктор физико-математических наук,

профессор Исаев СА

1. Общая характеристика работы

Актуальность исследования. В условиях рыночной экономики эффективность производства и конкурентоспособность промышленного предприятия имеют первостепенное значение. В последние годы для транспортных предприятий в интересах разработки и реализации мероприятий по повышению эффективности стали использоваться новые методы и технологии доставки товаров, которые базируются на концепции логистики, функциями которой является оптимизация всех операций по выполнению доставки товаров от поставщика к покупателю. Развитию логистических методов управления перевозками посвящены работы Канторовича Л.В., Беленького А.С., Кожина А.П., Мезенцева В.Н., Лукинского B.C., Смехова А.А., Миротина Д.Б. и других. Однако, методологически и практически проблема организации логистического обеспечения перевозок еще далека от своего решения.

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание выносимых на защиту основных положений:

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

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы прошли апробацию и получили одобрения на научно-технических конференциях студентов, аспирантов и молодых ученых Академии гражданской авиации, (2001,

2002г.г.) научно-практической конференции «Наука и образование - городу» (С-Петербург, 2002 г.) Международной конференции «Логистика в современном бизнесе» (Москва, май 2002г.), Российско-французском семинаре по логистике (С-Петербург, апрель 2002г.).

Реализация результатов исследования. Основные результаты работы реализованы в учебном процессе Академии гражданской авиации, Михайловской артиллерийской академии и научно-исследовательской работе Международной академии транспорта.

Внедрение программного обеспечения задач маршрутизации осуществлено на предприятии АРКТИДА.

Объем работы. Диссертационная работа изложена на 114 листах текста, содержит 17 рисунков, 16 таблиц, список литературы из 56 наименований и включает 3 приложения на 22 листах.

2. Основное содержание работы

Диссертационная работа состоит из введения, трех глав, заключения и приложений.

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

Транспортным средством от исходного пункта осуществляется доставка некоторой продукции в п пунктов назначения. При этом полагаются заданными:

G - грузоподъемность транспортного средства;

Ьц - потребности пунктов назначения, 3 = 1,2, ..., Л;

ёц - протяженность участков пути между пунктами, 1 = 0,1,...,П, ^ = О,I .,.,11, где 0 - индекс исходного пункта.

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

и вводятся переменные:

- количество груза, находящегося на транспортном средстве при его следовании от ьго пункта до пункта .¡;

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

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

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

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

Н Я

1хч=!>/■•

м м

2>/.=0;

/•I

Я

»-I

N

м

и

где:

9/.е {1.2г».я}>

. / Л1' ««*»>0''

^ [0, если ^=0.

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

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

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

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

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

(1.2)

(1.3)

(1.4)

(1.5)

(1.6) (1.7)

условие (1.7) , в котором qi или qj - очередность доставки груза в i-й или j-й пункт назначения, предотвращает появление внутренних подциклов на маршруте.

Видно, что данная задача имеет аналогию с транспортной задачей линейного программирования и с задачей коммивояжера. Сходство с транспортной задачей линейного программирования состоит в следующем :

во-первых, целевая функция (1.1) имеет такой же вид;

во-вторых, ограничения (1.2) - (1.4) носят линейный характер и имеют похожий смысл, что и ограничения транспортной задачи линейного программирования.

Сходство с задачей коммивояжера состоит в том, что ограничения (1.5) -(1.7) есть модифицированные для данной задачи путем добавления функции sign ограничения, предложенные в 1960 году.

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

Постановка задачи экспедитора в целочисленном представлении.

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

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

/•О /-1 i-I

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

(1.8)

(1.9)

£*о/=i. 2]*«5'>1=и.-.«;

у-1

(1.10)

(1.11)

г,-г]+пх> 1,05/5' У ¿я, где;

х, е {0,1}, I = 0,1,..,л;) = 1,2.....и;

ху = 1, если груз после пункта 1 доставляется в пункт ];

1, если г, <г.;

у*= п

0,есяы г,. > г/,

гк - очередность доставки груза в к-й пункт, г„ 6 {1,2,.., л}, к = 1,2.....я.

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

Целочисленная формулировка задачи (2.12) - (1.11) существенно отличается от традиционной модели Таккера для задачи о коммивояжере. Целевая функция (2.12) содержит принципиально новый сомножитель bkyik, который представляет собой сумму грузов, находящихся на транспортном средстве и не доставленных еще в пункты назначения. Ограничение (1.10) получено из аналогичного ограничения в задаче о коммивояжере заменой знака " = " на знак Это объясняется тем, что по условию задачи не оговариваются затраты на холостой пробег транспортного средства при возвращении его на исходный пункт.

Ограничения (1.9), (1.11) идентичны соответствующим ограничениям модели Таккера.

Комбинаторная модель задачи экспедитора

Задача (1.1) - (1.7) не может быть решена методами линейного программирования, так как часть ее ограничений носит нелинейный (1.5), (1.6) и комбинаторный (1.7) характер. Следовательно, для нее требуется разработка своего метода решения. Представляется, что задача может быть решена с использованием методов комбинаторной оптимизации. Анализ физической сущности задачи показывает, что можно перейти от ее математической формализации в терминах переменных ху к формализации на перестановках. На рис. 1 показаны возможные маршруты экспедитора для случая, когда количество пунктов назначения равно четырем.

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

(1.12)

Рис. 1. Возможные маршруты экспедитора

р1,р2, ...рп - элементы перестановки Р; рО - номер исходного пункта.

Преимущество формализации (1.12) состоит в том, что ограничения в явном виде отсутствуют и требуется указать такую перестановку, которая минимизирует эту целевую функцию. Отсутствие ограничений в явном виде объясняется тем, что они вошли в целевую функцию: перестановка пунктов объезда автоматически удовлетворяет ограничениям (1.5) - (1.7), а ограничения (1.2) - (1.4) неявно присутствуют во втором слагаемом целевой функции (1.12).

Итак, мы переформулировали задачу следующим образом:

Целевая функция (1.12) предполагает подсчет тонна-километров, начиная с исходного пункта. В этом случае вторая сумма заново пересчитывается при переходе к очередному пункту. Это является нерациональным при организации вычислительного процесса на компьютере. С этой точки зрения представляется целесообразным перейти к использованию свойства рекуррентности при подсчете тонна-километров от конечного пункта к начальному на основе формул:

Здесь, перед использованием формулы (1.13) переменная В в формуле (1.14) полагается равной нулю.

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

4.1 Ы

(1.13)

в=в=ь,

я-м'

(1.14)

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

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

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

определения маршрута по наибольшей потребности пунктов;

выбора маршрута по наименьшей удельной удаленности доставляемого

груза;

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

Основные положения диссертации опубликованы в следующих работах:

1. Ерошук Н.В., Анисимов Е.Г. Математическая постановка задачи экспедитора и ее комбинаторная модель. //Тезисы доклада на российско-французском семинаре по логистике 28 апреля 2002г. - С.-Петербург: Академия гражданской авиации, 2002г.

2. Ерощук Н.В., Анисимов Е.Г. Алгоритм формирования "плавающих" перестановок. //32 НТК студентов, аспирантов и молодых ученых. - С.Петербург: 2001 г.

3. Ерощук Н.В. Оценка эффективности переборных алгоритмов. //32 НТК студентов, аспирантов и молодых ученых. - С.-Петербург: 2001г.

4. Ерощук Н.В. Система показателей эффективности транспортно-логического обеспечения компании. //32 научно-техническая конференция студентов, аспирантов и молодых ученых. - С.-Петербург: 2001 г.

5. Ерощук Н.В. Повышение эффективности функционирования транспортной подсистемы. //НТС №5 «Информационные технологии в управлении». - СПб: МВАУ, 2004г.

6. Ерощук Н.В. Методика определения оптимистической оценки перспективности вершин дерева вариантов. //Сборник материалов Международной конференции 23-24 мая 2001 года.- Москва: 2002.

7. Ерощук Н.В. Алгоритм формирования маршрута по невозрастанию количества доставляемого груза. //НТС №5 «Информационные технологии в управлении». - СПб: МВАУ, 2004г.

8. Ерощук Н.В. Оптимизация маршрута служебной развозки. В сб.: Наука и образование городу. Ч. 1.- СПб.: Изд. мерии, 2002.

9. Ерощук Н.В. Определение последовательности доставки грузов. В сб.: Наука и образование городу. Ч. 2.- СПб.: Изд. мерии, 2002.

10.Ерощук Н.В., Анисимов Е.Г. Оптимизационная технология планирования в транспортных системах. //НТС №5 «Информационные технологии в управлении». - СПб: МВАУ, 2004г.

11.Ерощук Н.В., Капитонов В.В. О некоторых задачах управления производством вермикулита. //Вестник НИИ СУВПТ.- г. Красноярск: СУВПТ, 1999.

12.Ерощук Н.В., Капитонов В.В. Организация комплексного производства монокристаллического полупроводникового кремния на ГКХ Министерства РФ по атомной энергетике. //Сборник НТС ВАГШ ВС РФ. -Москва: ВАГШ, 1999г.

Подписано к печати 19.04.2005. Формат бумаги 60*90 1/16. Усл. печ. л. 1.1. Уч. -изд. л. 1.1. Заказ 423. Тираж 20. С.21. Тип. Университета ГА. 196210, С.Петербург, ул. Пилотов, дом 38.

05Л

19 МАЙ 2005