Введение к работе
Актуальность. В диссертационной работе предложена постановка новой задачи комбинаторной оптимизации — задачи экспедитора. Экспедитор — это работник, занимающийся отправкой по назначению какого-либо товара или корреспонденции. Задача экспедитора заключается в том, чтобы указать такой маршрут доставки некоторых грузов из исходного пункта в пункты назначения, при котором расход моторесурсов транспортного средства, выраженный в тонна-километрах, будет минимальным.
В теории исследования операций комбинаторные задачи, связанные с нахождением оптимальных вариантов на некоторых комбинаторных множе-сгвах, недостаточно изучены, с алгоритмической точки зрения они обладают большой временной сложностью, универсальных и эффективных методов для их решения не предложено.
В настоящее время объективный процесс возрастания роли математических моделей испытывает внешнее стимулирук'цее воздействие со стороны широкой компьютеризации, которая значительно расширяет возможности и области приложений математических моделей, что, в свою очередь, повышает пх полезность. Теоретические исследования при этом играют роль ориентиров, концептуальных основ, а также естественных ограничений для экспериментальных разработок и прикладных программных реализаций. В связи с этим актуальность темы исследований определяется возрастанием роли вычислений комбинаторного характера в прикладных задачах и необходішостью разработки методов нахождения оптимальных решений комбинаторных задач.
Целью диссертационной работы является исследование новой задачи комбинаторного типа, заключающейся в определении маршрута доставки транспортным средством некоторого груза из пункта отправления в пункты назначения при минимальном расходе моторесурса, и разработка точных и приближенных методов для ее решения на основе существующего математического аппарата комбинаторной оптимизации.
Научную новизну работы составляют:
анализ особенностей планирования доставки продукции в производственно-коммерческих системах, а также условий и факторов, влияющих на качество плановых решений, и вытекающие из них требования к методам и алгоритмам оптимизации маршрутов доставки грузов;
обоснование необходимости оптимизационного подхода к задачам маршрутизации и содержательная постановка задачи экспедитора; разработка математических моделей задачи экспедитора, их срашштоль-
ный анализ и выбор предпочтительного варианта формализации в виде комбинаторного представления;
исследование возможностей применения методов перебора перестановок для нахождения оптимального маршрута в задаче экспедитора и разработка нового метода на основе.плавающих элементов перестановки;
выбор структуры построения дерева вариантов, стратегии ветвления вершин и разработка метода вычисления оптимистической оценки их перспективности при решении задачи экспедитора по схеме ветвей и границ;
разработка приближенных методов решения задач экспедитора большой размерности;
построение стандартной модели задания исходных данных для верифит кации п оценки эффективности разработанных алгоритмов и программ.
На защиту выносятся следующие основные положения:
постановка задачи экспедитора и ее формализация в виде оптимизационной комбинаторной модели;
метод перебора перестановок, использующий схему переноса крайних элементов и обладающий более высокой производительностью по сравнению с известными методами;
метод вычисления оптимистической оценки перспективности вершин на дереве вариантов при решении задачи экспедитора по комбинаторной схеме ветвей и границ;
формулировка и доказательство теорем о правомочности эквивалентных преобразований матрицы расстояний между пунктами в задаче экспедитора, о нижней границе числа нулевых элементов в модифицированной матрице расстояний, о формулах для вычисления оптимистической оценки перспективности вершин на дереве вариантов;
алгоритмы приближенного решения задачп экспедитора при большом количестве пунктов назначения.
Теоретическая значимость диссертационного исследования определяется новизной постановки и формализации математической модели задачп экспедитор..., разработкой точных и приближенных методов ее решения, оценкой эффективности разработанных методов и выработкой рекомендаций по их применению.
Практическая ценность диссертации заключается в том, что полученные результаты, могут использоваться в программном обеспечении персональных компьютеров и компьютерных сетей автоматизированных систем планирования п управления деятельностью производственно-коммерческих структур с централизованным обслуживанием, а также в учебном процессе СШІ^'и других вузов.-
г I
Апробация работы. Отдельные научные и практические результаты докладывались и обсуждались на I городской научно-практической конференции "Наука и образование — городу" (Санкт-Петербург, 1997 г.), Международной конференции молодых ученых (Санкт-Петербург, 1996 г.), на научных конференциях и семинарах Санкт-Петербургского государственного университета и заседаниях кафедры математической статистики, теории надежности и массового обслуживания СПбГУ (1994 - 1997 г.г.).
Реализация результатов исследования. Основные результаты работы реализованы в учебном процессе СПбГУ п Михайловской артиллерийской академии. Внедрение программного обеспечения задач маршрутизации осуществлено в отделе АСУ предприятия ЛИВАС.
Публикация работы. Материалы исследований опубликованы в [1-5].
Объем работы. Диссертационная работа состоит из введения, трех глав и заключения, изложенных на 114 листах текста и содержащих 16 рисунков, 17 таблиц и список литературы из 42 наименований, а также вкл'ючает 3 приложения с исходными текстами ПАСКАЛЬ-программ на 22-х листах.