автореферат диссертации по транспорту, 05.22.10, диссертация на тему:Разработка методики оптимизации развозочных маршрутов

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

О

ПРОКОФЬЕВА Оксана Сергеевна

РАЗРАБОТКА МЕТОДИКИ ОПТИМИЗАЦИИ РАЗВОЗОЧНЫХ МАРШРУТОВ

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

АВТОРЕФЕРАТ

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

Иркутск - 2004

Работа выполнена в Иркутском государственном техническом университете.

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

доктор технических наук, профессор Головных Иван Михайлович.

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

доктор технических наук, профессор Гудков Владислав Александрович.

кандидат технических наук, доцент Непорада Александр Владимирович.

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

Департамент по развитию коммуникационного комплекса администрации Иркутской области.

Защита диссертации состоится 05 ноября 2004 г. в 12 часов на заседании диссертационного совета Д 212. 028. 03 в Волгоградском государственном техническом университете по адресу: 400131, г. Волгоград, проспект им. В.И. Ленина, 28.

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

Автореферат разослан « Ю » 2004 г.

Ученый секретарь диссертационного совета

Ожогин В.А.

26* *9й

2005-4 3

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

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

В связи с развитием малого и среднего бизнеса, которое привело к значительному увеличению числа как грузоотправителей, так и грузополучателей, объем перевозок грузов автомобильным транспортом до 2005 года может быть увеличен на 36,5%. В то же время происходит непрерывный процесс увеличения стоимости единицы перевозимого груза.

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

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

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

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

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

Научная новизна исследования заключается в следующих положениях:

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

Автор выражает глубокую признательность к т N.. доценту С В Колганову за оказанную помощь при анализе и обсуждении полученных результатов

БИБЛИОТЕКА

«ншашммттшт

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

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

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

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

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

Результаты выполненного исследования могут быть использованы предприятиями производственной инфраструктуры при доставке продукции от поставщиков до потребителей, в том числе организациями транспортной отрасли. А также в учебном процессе для студентов специальностей 240100.01 «Организация перевозок и управлении на транспорте» и 240400.0) «Организация и безопасность движения», направление подготовки 653400 - Организация перевозок и управление на автомобильном транспорте.

Реализация работы. Основные результаты теоретических и экспериментальных исследований приняты к практическому использованию в МУП «Спецавтохозяйство» г. Иркутска при планировании вывоза твердых бытовых отходов, при проектировании маршрутов доставки продукции с ОАО «Иркутского масложиркомбината» и в учебном процессе на кафедре «Менеджмент на автомобильном транспорте» Иркутского Государственного Технического Университета.

Апробация работы. Основные положения диссертационной работы доложены и получили одобрение на ежегодных научно-технических конференциях ИрГТУ (г. Иркутск, 2000 - 2003 гг.); на смотре конкурсе НИР, НИРС и НТТМ молодых ученых и специалистов (г. Иркутск, 2001 г.); на 5-ой межреги шальной научно-практической конференции «Интеллектуальные и материальные ресурсы Сибири» (г. Иркутск, 2002 г.); на региональной научно-практической конференции «Актуальные проблемы АПК» (г. Иркутск, 2002 г.); на II международной научно-технической конференции «Современные научно-технические проблемы транспорта России» (г. Ульяновск, 2002 г.); на региональной научно-практической конференции «Роль предприятий и отраслей транспортной системы в социально-экономическом развитии Прибайкальского региона» (г. Иркутск, 2003 г.); на X международной научно-практической конференции «Социально-экономические проблемы развития транспортных систем городов и зон их влияния» (г. Екатеринбург, 2004 г.).

.4» . -

Публикации. Основные положения и результаты диссертационной работы изложены в 12 публикациях.

Структура и объем диссертации. Диссертация состоит го введения, четырех глав, выводов, списка литературы и двух приложений. Работа изложена на 169 стр. машинописного текста, содержит 31 таблицу и 46 рисунков. Библиография на 10 стр включает 124 наименования, в том числе 25 на иностранном языке.

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

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

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

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

Оценивая динамику изменения торговых точек в г. Иркутске на 1000 жителей (рис. 1) можно, сделать вывод о неуклонном их возрастании, средний темп прироста, рассчитанный как среднее арифметическое за период с 1998 г. по 2003 г., составил 12,78%. Увеличение доли торговых точек указывает на то, что объем перевозок мелких партий грузов возрастает.

Рис 1 Динамика изменения торговых точек в г Иркутске на 1000 жителей по годам

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

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

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

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

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

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

Задача маршрутизации перевозок мелких партий грузов известна в двух постановках: как «задача коммивояжера», и как «задача развозки».

«Задача коммивояжера» возникает тогда, когда

0 = (1) где Q - суммарный объем вывоза груза от отправителя, т;

N

Х<7;», - суммарный объем завоза груза каждому N получателю, т;

п-1

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

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

Вторая постановка задачи маршрутизации перевозок мелких партий грузов -«задача развозки» возникает тогда, когда

ч7*4<в> (2)

где q™ - максимальный объем завоза в один из N пунктов (если q <q™, то в такие

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

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

шг =£с; =£(/0 , +1/, ч-о)^"« о)

при ограничениях:

Х>я ч ч

лч^+Л^.+Л^ (5)

= ку, (4)

(6) (7)

^ = (в)

-С; (9)

¿>„-С>; (Ю)

п> = 0; (11)

Ь<=Х (12)

Запись (3) указывает, что должен быть составлен план развоза грузов всем N потребителям, обеспечивающий минимальный пробег автомобиля. Количество маршрутов, необходимых для завоза грузов всем потребителям, представлено соотношением (4). Запись (5) указывает на то, что число пунктов завоза груза на всех маршрутах должно быть равно сумме числа пунктов завоза на каждом из маршрутов, учитывая, что объемы завоза груза разным потребителям неодинаковы (6) и число пунктов завоза в каждом маршруте может быть различным (7). Соотношение (8) представляет собой ограничение на грузоподъемность автомобиля, которое требует, чтобы загрузка автомобилей при выезде его на маршрут не превышала допустимой для данной марки. Условия (9) и (10) представляют собой соответственно то, что суммарные объемы завоза груза на всех маршрутах должны быть равны объему вывоза груза от отправителя и суммарный объем завоза груза потребителям должен быть равен объему вывоза от поставщика. Запись (11) накладывает на переменные 1цк условия целочисленности. Условие (12) представляет собой множество X, определяющее список допустимых маршрутов. Решением задачи (3) - (12) является набор развозочных маршрутов.

Таким образом, решение «задачи развозки» распадается на два этапа:

• необходимо определить, какие из N пунктов транспортной сети будут входить в 1-ый, 2-ой, ..., к-ый маршруты;

• необходимо оптимизировать последовательность объезда пунктов, вошедших в каждый к-ый маршрут.

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

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

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

При запуске алгоритма поиска вызывается процедура, которая выполняет первичное разбиение: исходя из грузоподъемности автомобиля и необходимого объема перевозок грузов мелкими партиями; определяется необходимое число маршрутов движения автомобиля для выполнения задания на поставки. Таким образом, осуществляется разбиение общего количества пунктов - получателей на несколько натуральных чисел всеми возможными способами (числа будут обозначать количество пунктов в одном маршруте). При этом необходимо учитывать то что, если сумма груза по любым к пунктам больше грузоподъемности автомобиля, то разбиения, включающие в себя число, большее или равное к, можно не перебирать. Кроме того, если известно, что сумма груза по к + /, пунктам всегда меньше грузоподъемности, то разбиения, включающие одновременно числа к и / так»1 г можно отбросить.

Далее для каждого разбиения числа N - 1 на несколько натуральных чисел N1, нужно перебрать все способы, которыми можно выбрать ..., Ык пунктов из общего числа, т.е. проводится рекурсивный перебор всех возможных вариантов длин циклов с учетом количества пунктов перевозок. При этом учитывается, что два варианта не имеют принципиальных отличий, т.к. порядок, в котором выполняются маршруты, не существенен. Затем для каждого из вариантов запускается следующая процедура, которая на основании сформированных циклов рекурсивно перебирает все возможные комбинации пунктов перевозок по циклам (т.е. какие пункты входят в конкретный маршрут). Эта процедура разбивает пункты на подмножества с числом элементов Л',, ..., А^, но если среди N1, ..., Л^ есть равные числа, то соответствующие подмножества не разделяются. Чтобы разбить множество на подмножества заданной мощности, первая процедура отбирает первое из подмножеств, а затем вызывает себя. В свою очередь вторая процедура перебора выполняет разделение нескольких равных по мощности подмножеств. Отличие от первой процедуры состоит в том, что первый элемент из оставшихся выбирается всегда, для того чтобы исключить перестановки. После этого для каждой из этих комбинаций проверяется наличие превышения максимального объема перевозимого груза, т.е. находится суммарный объем требуемых грузов по каждому из циклов и сравнивается с грузоподъемностью

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

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

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

< Предложенная методика оптимизации маршрутов перевозки мелких партий

грузов позволяет найти оптимальное решение путем перебора пунктов транспортной сети при помощи процедуры рекурсии и сравнения на оптимальность всех возможных комбинаций маршрутов при использовании метода «ветвей и границ». В соответствии с данной методикой разработана компьютерна программа, обеспечивающая получение оптимальных маршрутов при перевозках мелких партий грузов, написанная на языке программирования «Borland Delphi б 0» под операционную систему Windows 98/Ме/2000/ХР.

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

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

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

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

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

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

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

Экспериментальные исследования проводились в два этапа. На первом этапе проведена оценка разработки развозочных маршрутов доставки мелких партий груза автотранспортными средствами в городском сообщение на предприятиях г. Иркутска, занимающихся обслуживанием населения: ОАО «Иркутский хлебозавод №1» и ОАО «Иркутский масложиркомбинат». За основу была взята информация служб эксплуатации (откуда, куда, сколько и какого груза нужно перевезти, и автомобиль какой марки выполняет данную заявку). Разработка плана перевозок производилась для той части клиентов, которым груз поставляется ежедневно и объемы поставок не изменяются в течение года, а также для заявок, которые носят случайный характер, т.к. зависят от спроса и предложения (таких заявок оказалось большинство).

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

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

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

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

в)

1

гв 2в 24 Я 20 18 1в

т?10а-б-4 20 2 4

г)

г

/

\|

34 23 20 «а (в <4 II Ю 4

Рис 2 Эмпирические и теоретические частоты отклонения суммарной длины маршрутов при сочетании маршрут составленный с использованием методики - а'1 маршрут составленный с использованием кратчайшей связываюшей сети; б) маршрут составленный с использованием метода суммирования по столбцам, в) маршрут составленный с использованием метода Кларка - Райта, г) маршрут составленный с использованием метода «ветвей и границ»

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

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

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

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

• статистическая обработка (при помощи пакета прикладных программ «ЭТАИБПКА») собранных данных, включающая представление их форме статистического ряда, проверка согласия теоретического и эмпирического распределения по соответствующим критериям.

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

а)

)* 0 ' 0 9 11 1 11719 I 1 3 2' 2729 3

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

б)

I: ™ »

«

7 15 21 21 25 27 29 31 1} Л

суммарный объен вывоза груза от поставщика т

В)

10 II II и

количество пунктов завоза (грузополучателей)

1 10 10 II 12 13 !■

20 18 22 20 23

число пунктов завоза груза и число звеньев транспортной сети

Рис 3 Зависимость суммарной длины маршрута доставки груза от - а) грузоподъемности автомобиля; б) суммарного объема вывоза груза от поставщика, в) количества пунктов завоза груза, г) числа пунктов завоза грузов и числа звеньев транспортной сети

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

а)

б)

« 2 1 2» 2< 2Т 29 }

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

суммарный объем вывоза груза от отправителя т

В)

Г)

300000000

гиишхю

2000000« 190000000

МО 10 2 12 I*

I* 20 18 22 20 2»

число пунктов завоза груза и число звеньев транспортной сети

2 3 4 5 6 количество маршрутов доставки грузов

Рис 4 Зависимость количества комбинаций маршрутов доставки грузов от - а) грузоподъемности автомобиля; б) суммарного объема вывоза груза от поставщика; в) числа пунктов завоза груза и числа звеньев транспортной сети, г) зависимость суммарной длины маршрута доставки грузов от количества маршрутов

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

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

перечня факторов, влияющих прямо или косвенно, на итог решения «задачи развозки»:

• число пунктов завоза груза;

• соотношение числа пунктов завоза груза и числа звеньев транспортной сети;

• суммарный объем вывоза груза;

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

• число маршрутов.

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

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

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

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

Проверка разработанной методики оптимизации развозочных маршрутов подтвердила эффективность в вопросах совершенствования качества оперативного планирования предприятиях. В результате опытного внедрения разработанного по предложенной методики оперативного плана перевозо продукции ОАО «Иркутского масложиркомбината» получено сокращение общего пробега подвижного состава на 13% и затрат на перевозки - на 8,7%,

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

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

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

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

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

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

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

5 На базе предложенного метода решения «задачи развозки» разработана компьютерная программа, которая обладает быстродействием (25 сек. машинного времени затрачивается на просмотр 237112 тыс. комбинаций маршрутов при решении задачи на ЭВМ AMD Athlon (tm) ХР 1800 + 1,53ГГц 128МБ ОЗУ) и экономичностью.

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

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

8. Проверка разработанной методики подтвердила эффективность в вопросах совершенствования организации работы автомобилей на развозочных маршрутах. В результате опытного внедрения разработанного по предложенной методике плана перевозок продукции с ОАО «Иркутского масложиркомбината» получено сокращение общего пробега подвижного состава на 13% и транспортных затрат на 8,7%.

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

1. Прокофьева О.С. О некоторых проблемах совершенствования

мелкопартионных перевозок // Интеллектуальные и материальные ресурсы Сибири:

Сб. науч. тр. 4.2. (Экономика). - Иркутск: Изд-во ИГЭА, 2002. - С. 93-96.

2. Колганов C.B., Прокофьева О.С. Анализ методов планирования перевозок мелкопартионных грузов // Интеллектуальные и материальные ресурсы Сибири: Сб. науч. тр. 4.2. (Экономика). - Иркутск: Изд-во ИГЭА, 2002. - С. 96 - 100.

3. Прокофьева О.С. Планирование маршрутов при помощи упорядоченного перебора пунктов транспортной сети // Актуальные проблемы АПК. Материалы региональной научно-практической конференции, ч.2 - Иркутск, изд-во ИГСХА, 2002. - С. 75-77.

4. Прокофьева О.С. Методика планирования развозочных и сборочных маршрутов перевозок мелких партий грузов // Современные научно-технические проблемы транспорта России. Сборник материалов И международной научно-технической конференции. - Ульяновск: УВАУ ГА, 2002. - С. 249 - 252.

5. Головных И.М., Прокофьева О.С. Алгоритм определения рациональных маршрутов движения грузовых автомобилей // Международный вестник стипендиатов DAAD №2. Иркутск: Изд-во ИрГТУ, 2002. - С. 26 - 32.

6. Прокофьева О.С. Оценка предполагаемого эффекта от повышения точности планирования // Роль предприятий и отраслей транспортной системы в социально-экономическом развитии Прибайкальского региона: Материалы научно-практической конференции. - Иркутск: Изд-во БГУЭП, 2003. - С. 47 - 51.

7. Прокофьева О.С. Оперативное планирование работы автомобилей на развозочных маршрутах // Роль предприятий и отраслей транспортной системы в социально-экономическом развитии региона: Сб. науч. тр. - Иркутск: Изд-во БГУЭП, 2003.-С. 120-127.

8. Прокофьева О.С., Колганов C.B. Эффективность методики оптимизации автомобилей при перевозке мелких партий грузов // Роль предприятий и отраслей транспортной системы в социально-экономическом развитии региона: Сб. науч. тр. -Иркутск: Изд-во БГУЭП, 2003. - С. 114 - 120.

9. Колганов C.B., Прокофьева О.С. Методические указания по выполнению курсового проекта «Разработка системы транспортного обслуживания экономического района грузовыми автомобилями». - Иркутск: Изд-во ИрГТУ, 2003. - С. 16.

10. Прокофьева О.С. Оценка эффективности маршрутизации перевозок грузов в транспортных системах городов // Материалы X международной (тринадцатой екатеринбургской) научно-практической конференции. Социально-экономические проблемы развития транспортных систем городов и зон их влияния. - Екатеринбург: Изд-во АМБ, 2004г. - С. 229 - 234.

11. Прокофьева О.С. Логистические аспекты функционирования автомобильного транспорта // Развитие и формирование транспорта и связи в новых экономических условиях: Сб. науч. тр. - Иркутск: Изд-во БГУЭП, 2004 - С. 163 - 168.

12. Головных И.М., Прокофьева О.С. Роль и место автомобильного транспорта в функционировании логистической системы // Международный вестник стипендиатов DAAD №3. Иркутск: Изд-во ИрГТУ, 2004. - С. 6 - 12.

Подписано в печать 21.09.2004. Формат 60x84'/, Бумага офсетная. Печать трафаретная. Гарнитура Times. Усл. печ. л. 1,0 Уч.-изд. л.0,9. Тираж 80 экз. Заказ № 1572

Отпечатано в Глазковской типографии 664039, г.Иркутск, ул. Гоголя, 53.Тел. 38-78-40.

1 <

í

I

I (

,! i

i !

i t

1,

№18 6 0 6

РНБ Русский фонд

2005-4 12702

ВВЕДЕНИЕ

ГЛАВА 1 СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

1.1 Современное состояние внутригородских перевозок мелких партий грузов

1.2 Обзор методов решения задач планирования перевозок мелких партий грузов

1.3 Цель и задачи исследования

ГЛАВА 2 ТЕОЕРТИЧЕСКИЕ ПРЕДПОСЫЛКИ

ПЛАНИРОВАНИЯ ПЕРЕВОЗОК МЕЛКИХ ПАРТИЙ ГРУЗОВ

2.1 Математическая модель задачи планирования перевозок мелких партий грузов

2.2 Алгоритм упорядоченного перебора пунктов транспортной сети

2.3 Оптимизация последовательности объезда пунктов

2.4 Выводы по 2 главе

ГЛАВА 3 КОМПЬЮТЕРНАЯ ПРОГРАММА И МЕТОДИКА ПРОВЕДЕНИЯ ЭКСПЕРИМЕНТАЬНЫХИССЛЕДОВАНИЙ

3.1 Методика оптимизации развозочных маршрутов

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

3.2.1 Цель и задачи экспериментальных исследований

3.2.2 Методика проведения эксперимента

3.3 Экспериментальные исследования по выявлению влияния факторов на главный критерий оптимизации

3.3.1 Цель и задачи экспериментальных исследований

3.3.2 Условия внутригородских перевозок мелких партий грузов

3.3.3 Методика проведения эксперимента

3.4 Выводы по 3 главе

ГЛАВА 4 ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА ТЕОЕРЕТИЧЕСКИХ ПОЛОЖЕНИЙ И ОЦЕНКА

ЭФФЕКТИВНОСТИ ИССЛЕДОВАНИЙ

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

4.1.1 Обработка экспериментальных данных на предприятиях

4.1.2 Обработка экспериментальных данных по результатам моделирования

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

4.3 Проверка экономической эффективности методики оптимизации развозочных маршрутов

4.4 Выводы по 4 главе 130 ЗАКЛЮЧЕНИЕ 131 СПИСОК ЛИТЕРАТУРЫ 134 ПРИЛОЖЕНИЕ

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

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

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

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

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

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

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

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

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

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

• проведение экспериментальных исследований с целью оценки эффективности предлагаемой методики;

• определение эффекта от использования предлагаемой методики.

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

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

Научная новизна исследования заключается в следующих положениях:

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

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

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

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

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

Результаты выполненного исследования могут быть использованы предприятиями производственной инфраструктуры при доставке продукции от поставщиков до потребителей, в том числе организациями транспортной отрасли. А также в учебном процессе для студентов специальностей 240100.01 «Организация перевозок и управлении на транспорте» и 240400.01 «Организация и безопасность движения», направление подготовки 653400 -Организация перевозок и управление на автомобильном транспорте.

Реализация работы. Основные результаты теоретических и экспериментальных исследований приняты к практическому использованию в МУП «Спецавтохозяйство» г. Иркутска при планировании вывоза твердых бытовых отходов, при проектировании маршрутов доставки продукции с ОАО «Иркутского масложиркомбината» и в учебном процессе на кафедре «Менеджмент на автомобильном транспорте» Иркутского Государственного Технического Университета.

Апробация работы. Основные положения диссертационного исследования были представлены:

• на ежегодных научно-технических конференциях ИрГТУ (г.

Иркутск, 2000 - 2003 гг.);

• на смотре конкурсе НИР, НИРС и НТТМ молодых ученых и специалистов (г. Иркутск, 2001 г.)

• на 5-ой межрегиональной научно-практической конференции «Интеллектуальные и материальные ресурсы Сибири» (г. Иркутск, 2002 г.);

• на региональной научно-практической конференции «Актуальные проблемы АПК» (г. Иркутск, 2002 г.);

• на II международной научно-технической конференции «Современные научно-технические проблемы транспорта России» (г. Ульяновск, 2002 г.);

• на региональной научно-практической конференции «Роль предприятий и отраслей транспортной системы в социально-экономическом развитии Прибайкальского региона» (г. Иркутск, 2003 г.);

• на X международной научно-практической конференции «Социально-экономические проблемы развития транспортных систем городов и зон их влияния» (г. Екатеринбург, 2004 г.).

Публикации. Основные положения и результаты диссертационной работы изложены в 12 публикациях.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, выводов, списка литературы и двух приложений. Работа изложена на 169 стр. машинописного текста, содержит 31 таблицу и 46 рисунков. Библиография на 10 стр. включает 124 наименования, в том числе 25 на иностранном языке.

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

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

К основным выводам следует отнести следующее:

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

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

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

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

5. На базе предложенного метода решения «задачи развозки» разработана компьютерная программа, которая обладает быстродействием (25 сек. машинного времени затрачивается на просмотр 237112 тыс. комбинаций маршрутов при решении задачи на ЭВМ AMD Athlon (tm) ХР 1800 + 1,53ГГц 128МБ ОЗУ) и экономичностью.

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

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

8. Проверка разработанной методики подтвердила эффективность в вопросах совершенствования организации работы автомобилей на развозочных маршрутах. В результате опытного внедрения разработанного по предложенной методике плана перевозок продукции ОАО «Иркутского масложиркомбната» получено сокращение общего пробега подвижного состава на 13% и транспортных затрат на 8,7%.

1. Автоматизированная система оперативного планирования грузовых перевозок «Сопка». Экспресс-информация ЦБНТИ Минавтотранса РСФСР, сер. Грузовые перевозки автомобильным транспортом, 1984. Вып.1. с. 1 —4.

2. Автотранспорт на рубеже XXI века. Автомобильный транспорт, 2000. №8. с. 6-8.

3. Автотранспорт на рубеже XXI века. Автомобильный транспорт, 2000. №4. с. 6-8.

4. Агульник Е.И., Меламед И.И. Минимизация числа транспортных средств в задачах развозки. В сб.: Проблемы управления автотранспортными системами. -М., 1980. с. 152- 160.

5. Азизов Ф.Х., Ахмедов А.И., Кочеулов В.П. Применение математических методов при планировании перевозок товаров. М.: Госторгиздат, 1963. - 104с.

6. Айзенберг Е. Планирование перевозок молока и молочных продуктов. -Автомобильный транспорт, 1964. № 8. с. 37 38.

7. Альбеков А.У., Митько О.А. Коммерческая логистика / Серия «Учебники, учебные пособия» Ростов-на-Дону: Феникс, 2002. - 416с.

8. Аникеич А.А., Грибов А.Б., Сурин С.С. Сменно-суточное планирование работы грузовых автомобилей на ЭВМ. М.: Транспорт, 1976. - 152с.

9. Анисимов А.П. Организация и планирование работ автотранспортных предприятий. М.: Азимут-центр, 1992.

10. Артюх В. Планирование перевозок торговых грузов. Автомобильный транспорт, 1968. № 9. с. 18 — 19.

11. Беллман Р. Применение динамического программирования к задаче о коммивояжере. Кибернетический сборник, 1964. Вып. 9. с. 219 - 222.

12. Бережной В.И. Методы и модели логистического подхода к управлению автотранспортным предприятием. Ставрополь: Ставроп. гос. техн. ун., Интеллект-сервис, 1997.

13. Беспалов Н., Лихтик М., Харшан Н. Определение потребности в подвижном составе при обслуживании крупного транспортного узла. Автомобильный транспорт, 1973. №3. с. 19-21.

14. Брайко Н. Деловое содружество основа трудовых успехов. -Автомобильный транспорт, 1982, № I.e. 19-20.

15. Бураков В.И., Колодин B.C. Основы коммерческой логистики. Учебное псобие. Иркутск, изд-во БГУЭП, 2003. 432с.

16. Вадас П. Новые методы по разработке маршрутов с помощью ЭВМ. -Перевод № Б-832/2, М.: ВЦП, 1982. 31с.

17. Вельможин А.В. и др. Теория организации и управления автомобильными перевозками: логистический аспект формирования перевозочных процессов: Монография / А.В. Вельможин, В.А. Гудков, Л.Б. Миротин; Волгоград, гос. тех. ун-т. Волгоград, 2001. - 178с.

18. Вельможин А.В. и др. Технология, организация и управление грузовыми автомобильными перевозками: Учебник для вузов. 2-е изд., доп. / А.В. Вельможин, В.А. Гудков, Л.Б. Миротин; Волгоград, гос. тех. ун-т. - Волгоград, 2000. - 304с.

19. Вензик Н.Г. Торговля и транспорт // БТИ, 1999. №4. с. 13-15.

20. Вентцель Е.С. Теория вероятностей. М.: Наука, 1992. - 576с.

21. Верховский И.А. Планирование и анализ себестоимости автомобильных перевозок. М.: Транспорт, 1966. - 215с.

22. Волков О.И. Экономика предприятия. М. ИНФРА, 2000.

23. Вопросы планирования и учета транспортных затрат в народном хозяйстве / ЦНИИ МПС. Вып.454. М.: Транспорт, 1972. - 111с.

24. Воркут А.И. и др. Транспортное обслуживание торгово-оптовых баз. -Киев: Техшка, 1985. 112с.

25. Воркут А.И. Моделирование эффективности территориальной концепции перевозок партионных грузов. Автомобильный транспорт: Респ. межвед. научн.-техн. сб., 1986. Вып. 23. с. 3 5.

26. Выступление президента АСМАП Ю.С. Сухина. Автомобильный транспорт, 2000. №1. с.7 - 9.

27. Гаджинский A.M. Логистика. Учеб. для студентов высших и средних специальностей учебных заведений, 3-е изд. М: ИВЦ «Маркетинг», 2000.

28. Гаджинский A.M. Основы логистики: Учеб. пособие. М.: ИВЦ «Маркетинг», 1996. - 122с.

29. Галушко В.Г. Случайные процессы и их применение на автотранспорте. — Киев: Вища школа, 1980. — 271с.

30. Гарманов Е.Н. Экономика дорожного хозяйства. М.: Транспорт, 1990. — 247с.

31. Геронимус Б.Л. Совершенствование планирования на автомобильном транспорте. М.: Транспорт, 1985. - 222с.

32. Геронимус Б.Л., Царфин Л.В. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 1982. - 192с.

33. Говорущенко Н.Я. Основы управления автомобильным транспортом. — Харьков: Вища школа, 1978. 224с.

34. Голден Б.Л., Магнанти Т.Л. Составление маршрутов для комплекса транспортных средств. Перевод № 1 - 23272. - М.: ВЦП, 1981. - 53с.

35. Голобородкин Б.М., Закураев А.Ф. Комплексное планирование автомобильного транспорта. Нальчик: Эльбрус, 1986. - 140с.

36. Голубев С., Бречко А. Доставка молока в торговую сеть. Автомобильный транспорт, 1973, № 1. с. 23 - 24.

37. Гордон М.П., Карнаухов С.Б. Логистика товародвижения. М.: Центр экономики и маркетинга, 1998.

38. Государственная транспортная политика РФ. Автомобильный транспорт, 1998. №1. с.65 - 72.

39. Грузовые автомобильные перевозки / Воркут А.И. 2-е изд., перераб. и доп. - К.: Вища школа. Головное изд-во, 1986. - 447с.

40. Житков В.А. Планирование автомобильных перевозок грузов мелкими партиями. -М.: Транспорт, 1976. 112с.

41. Житков В.А., Ким К.В. Методы оперативного планирования грузовых автомобильных перевозок. М.: Транспорт, 1984. - 218с.

42. Завадский Ю.В. Планирование эксперимента в задачах автомобильного транспорта. М.: МАДИ, 1978. - 156с.

43. Завадский Ю.В. Решение задач автомобильного транспорта и дорожно-строительных машин с помощью регрессионного анализа. М.: МАДИ, 1981. — 116с.

44. Зарецкий J1.C. Решение задачи коммивояжера и задач развозки методом коррекции функции состояния. В сб.: Методы оптимизации перевозочного процесса на автотранспорте. - М.: 1976. с. 70-83.

45. Конюховский П.В. Математические методы исследования операций. СПб: Питер, 2001.- 192с.

46. Космынин В. Внедрение контейнеров. Автомобильный транспорт, 1983. №8. с. 18-19.

47. Кузнецов Е.И., Маркин А.В. Рациональное использование автомобилей и автопоездов КамАЗ в народном хозяйстве. В сб.: Совершенствование перевозочного процесса на автомобильном транспорте. - М.: Транспорт, 1977. с. 18-28.

48. Левиков Г.А. Глобализация мировой экономики и логистика // БТИ, 2002. №8. с.22 29.

49. Левиков Г.А. Транспортная логистика // БТИ, 1999. №11-12. с. 13-17.

50. Литтл Дж. и др. Алгоритм решения задачи коммивояжера. Экономика и математические методы, 1965. № 1. с. 94 - 107.

51. Ловецкий С.Е., Житков В.А., Плотинский Ю.М. Задачи маршрутизации перевозок на транспортной сети. Итоги науки и техники, сер. Организацияи управление транспортом, 1980. Т. 2. с. 74 128.

52. Логистика: управление в грузовых транспортно-логистических системах: Учеб. пособие / Под ред. д.т.н., проф. Л.Б. Миротина. М.: Юристъ, 2002. -414с.

53. Логистика и ее применение на предприятиях / И. Сергеев // Российский экономический журнал. 1994. - № 9. - с. 41 - 44.

54. Локшина Н., Сааташвили М., Толкачев Л. Совершенствование системы транспортного обслуживания складских комплексов. Автомобильный транспорт, 1983. № 12. с. 15 - 16.

55. Лукинский B.C. Логистика автомобильного транспорта: концепция, методы, модели / Лукинский B.C., Бережной В.И., Бережная Е.В. и др. М.: Финансы и статистика, 2002. - 280с.

56. Малов В.И. Повышение качества грузовых автомобильных перевозок // Социально-экономические аспекты развития AT // Автомобильный транспорт в условиях рыночных отношений: Сб. науч. трудов. Л.: ЛИЭИ, 1988. с. 18-21.

57. Малышев Экономика AT. М.: Транспорт, 1983. - 333с.

58. Миротин Л.Б., Ташбаев Ы.Э. Логистика для предпринимателя: Учеб. пособие для транспортных вузов. М.: ИНФРА-М, 2002.

59. Ненахов В. Доставка продуктов в торговую сеть. Автомобильный транспорт, 1982. № 6, с. 22 - 23.

60. Неруш Ю.М. Коммерческая логистика. -М.: Изд-во «ЮНИТИ», 1997.

61. Неруш Ю.М. Логистика: Учеб. для вузов. М.: ЮНИТИ-ДАНА., 2000.

62. Нефедова Н.Н. Построение алгоритма сменно-суточного планирования перевозок мелкопартионных грузов. В сб.: Методы системного анализа в задачах автомобильного транспорта. - М.: МАДИ, 1985. с. 25 - 31.

63. Николайчук В.Е. Логистика. СПб: Питер, 2001. - 160с.

64. Охремцов Б., Яковлев В. Использование вычислительной техники. — Автомобильный транспорт, 1984. № 6, с. 16 17.

65. Палмер Скотт. Delphi: Библиотека программиста / Руководство по программированию на языке Delphi. / Пер. с англ. под общей ред. Г.Русакова. — М.: ТАИС, 2000.-497с.

66. Перевозка грузов — прогрессивную технологию. Проспект Ворошиловского областного управления грузового автотранспорта, 1984. - 4с.

67. Пешков А. Доставка продовольственных товаров в торговую сеть. — Автомобильный транспорт, 1971. № 12. с. 17 18.

68. Поставка товаров народного потребления. Сборник нормативных актов. — М.: Юридическая литература, 1986. 128с.

69. Просов С.Н. Повышение эффективности планирования перевозок по сборно-развозочным маршрутам. Дисс. канд.техн.наук. М.: МАДИ, 1985. — 125с.

70. Резолюция Всероссийской научно-практической конференции «Транспорт России на рубеже веков». Автомобильный транспорт, 2000. №1. с. 21.

71. Роджер Х.Н. Теория рекурсивных функций и эффективная вычислимость. — М.: Кибернетика, 1972. 589с.

72. Роль транспорта в экономике страны в последние годы постоянно возрастает. Автомобильный транспорт, 2000. №1. с. 17 - 20.

73. Ромашко М.В. Метод исследования материального потока в транспортно-складских логистических цепях // БТИ, 2001. №10. с. 31 36.

74. Рынок и логистика / Под ред. М.П. Гордона. М.: Экономика, 1993.

75. Сакульева Т.Н. Внешняя среда транспортного предприятия // БТИ. 2001. №7, с. 31-33.

76. Семенов Е.В. и др. Составление на ЭВМ графика подачи автомашин под погрузку и доставку готовой продукции в торговую сеть с одновременным подбором оптимальных маршрутов. Труды ВНИИМП, 1970. Вып. 27. с. 212 — 215.

77. Сергеев В.И. Менеджмент в бизнес-логистике. М.: «Филинъ», 1997. -772с.

78. Смехов А.А. Ведение в логистику. М.: Транспорт, 1993.

79. Смехов А.А. Основы транспортной логистики. М.: Транспорт, 1995.

80. Солдатов И., Шпрейнер Г. Использование вычислительной техники. — Автомобильный транспорт, 1984. № 4. с. 17-19.

81. Справочник по математике для научных работников и инженеров. Корн Г., Корн Т. М.: Наука. Главная редакция физико-математической литературы. — 1984.-831с.

82. Сыроежин И.М. Планомерность. Планирование. План: теоретические очерки. М.: Экономика, 1986. - 248с.

83. Табарин Н. Система надежности. — Автомобильный транспорт, 1984. № 3. с. 16-17.

84. Таблицы планов эксперимента для факторных и полиноминальных моделей. / В.З. Бродский, Л.И. Бродский, Т.И. Голикова и др. М.: Металлургия, 1982. -752с.

85. Теория транспортных процессов и систем: Учеб. для вузов / А.В. Вельможин, В.А. Гудков, Л.Б. Миротин М.: Транспорт, 1998. - 167с.

86. Тиверовский В.И. Современные информационные технологии в логистике // БТИ, 2002.№7. с. 28 34.

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

88. Транспорт объединяет в единый комплекс все отрасли экономики. — Автомобильный транспорт, 2000. №1. с. 2 4.

89. Транспортная логистика: Учебник для транспортных вузов. / Под общей редакцией Л.Б. Миротина. М.: Изд-во «Экзамен», 2003. - 512с.

90. Уваров С.А. Логистика. СПб.: «Инвест-НП», 1996. - 235с.

91. Улицкий М.П. Организация, планирование и управление в автотранспортных предприятиях. М.: Транспорт, 1994.

92. У сков Н.С., Рубанова И.Н. Логистическое моделирование систем транспортного обслуживания // БТИ, 2003. №4. с. 25 29.

93. Фарбер С., Дьяконов Б. По оптимальным маршрутам, ситуационным методом. Автомобильный транспорт Казахстана, 1984. № I.e. 14 - 15.

94. Хелд М., Карп Р. Применение динамического программирования к задачам упорядочения. Кибернетический сборник, 1964. Вып. 9. с. 208 - 218.

95. Цветков В. Централизованная доставка товаров. — Автомобильный транспорт, 1972. № 10. с. 27 28.

96. Чалый А, Рыбак Б. Ситуационные методы планирования и управления перевозками мелкопартионных грузов. Автомобильный транспорт, 1982. № 9. с. 16-19.

97. Чеботаев А.А., Кийченко И.М. Транспорт в логистических технологиях // БТИ, 2000. №9. с.28 32.

98. Чеботаев А.А., Эдиев С.А., Кийченко И.М. и др. Генезис грузового автомобильного парка России // БТИ, 2002. №12, с. 27 37.

99. Balinski М., Quandt R. On an integer program for a delivery problem. — Operational Research, 1964. V. 12. №2. p. 300 304.

100. Beltrami E., Bodin L. Networks and vehicle routing for municipal waste collection. Networks, 1974. V. 4. №1. p. 65 - 94.

101. Calozynski A., Kiedrowicz G. Nome koncepcje rozwia-zywania zadan racionalizacji rozwozki towarow w duzych osrod-kach miegskych. Materialy па IV Konferencje naukowa. Ser. 2. Ekonomika transportu. - Warszawa, 1985. nr. 342 -351.

102. Christofides N., Eilon S. Algorithm for large-scale traveling salesman problems. Operational Research Quarterly, 1972. V. 23. №4. p. 511 - 518.

103. Christofides N., Eilon S. An algorithm for the vehicle dispatching problem. -Operational Research Quarterly, 1969. V. 20. №2. p. 309 318.

104. Clark G. Wright J. Sheduling of vehicles from a central depot to an umber of delivery points. Operational Research Quarterly, 1964. V. 12. №4. p. 568 - 581.

105. Dantzig G. Ramser J. The truck dispatching problem. Management Science, 1959. V. 6. №1. p. 81-91.

106. Evans S.R., Norback J.P. The impact of a decision-support system for vehicle routing in foodservice supply situation. Operational Research Quarterly, 1985. V. 36. №4. p. 467 - 472.

107. Foster B.A., Ryan D.M. An integer programming approach to the vehicle scheduling problem. Operational Research Quarterly, 1976. V. 27. №2. p. 367 — 384.

108. Gillett В., Miller L. A heuristic algorithm for the vehicle dispatch problem. -Operational Research, 1974. V. 22. №3. p. 340 349.

109. Groes G. A method for solving traveling salesman problems. Operational Research, 1958. V. 6. №5. p. 791 - 812.

110. Hong S., Padberg M. A note on the symmetric multiple traveling salesman problems with fixed charges. Operational Research, 1977. V. 25. №5. p. 871 - 874.

111. Karg R. Thomson C. A heuristic approach to solving traveling salesman problems. Management Science, 1964. V. 11. №2. p. 225 - 248.

112. Krolak P., Felts W., Nelson J. A man-machine approach toward solving the generalized truck-dispatching problem. Transportation Science. 1972. V. 6. №2. p. 149-170.

113. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulation of traveling salesman problems. Computer Machnery, 1960. V. 7. №4. p. 326 - 329.

114. Mole R., Jameson S. A sequential route building algorithm memo employing a generalized saving criterion. Operational Research Quarterly, 1976. V. 27. №2. p. 503-511.

115. Robertson B. Route optimization is the better way to bigger profits: Walls. — Motor truck. 1984. V. 53. №5. p. 27 28.

116. Rusenhrt J. Chr.Erfolgs-Erlebnis. Last auto Omnibus, 1984. №8. s. 26 - 27.

117. Russels R. An effective heuristic for then M-tour traveling salesman problem with some side conditions. Operational Research, 1977. V. 25. №3. p. 517 - 524.

118. Tuhrparkreserven aktivien. Reiniger + Wascher. 1984. №6. s. 20-23.

119. Warren P., Sheffi Y. The load planning problem of motor carries: problem description and a proposed solution approach. Transportation Research, 1983. V. 17A. №6. p. 470-480.

120. Waters C.D. Interactive vehicle routing. Operational Research Quarterly, 1984. V. 35. №9. p. 821 -826.

121. Wildehain G. Robotron-Systemunterlagem zur Losung von Problemen der Transport-Optimierung. Information. 1982. s. 52 - 58.

122. Wong K.F., Beasley J.E. Vehicle routing using fixed delivery areas. Omega. 1984. V.12. №6. p. 591 - 600.

123. Wren A., Holliday A. Computer scheduling of vehicle from one or more deports to a number of delivery points. Operational Research Quarterly, 1972. V. 23. №3. p. 333 - 344.

124. МЕТОДИКА ОПТИМИЗАЦИИ РАЗВОЗОЧНЫХ МАРШРУТОВ

125. Министерство образования и науки Российской Федерации

126. Иркутский Государственный Технический Университет

127. МЕТОДИКА оптимизации развозочных маршрутов1. Иркутск 2004г.1. Введение

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

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

130. Методика оптимизации развозочных маршрутов 1. Сущность методики

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

132. Второй этап решения задачи маршрутизации партионных перевозокгрузов был реализован с помощью разновидности наиболее перспективного метода «ветвей и границ», который за конечное число итераций дает точное решение (см. глава 2).

133. Программа написана на языке программирования «Borland Delphi 6.0» под операционную систему Windows 98/Ме/2000/ХР.

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

135. Описание интерфейса программы

136. ДЛя расчетов необходимо пвкти следующие данные

137. Количество грузополучателей )12 Груз-: гкдъснв -сть йвТ'>1йо6йля jl,? Суммарный объем вывоза; |з : -Т j Т 1 j:1. Ввод J CXIoSiai1. Рис. 1 Форма ввода данных

138. Для проверки суммарного объёма вывоза груза от грузоотправителя ориентируйтесь на значение ячейки A3. В этой ячейки введена формула, суммирующая все объёмы завоза груза у каждого грузополучателя.

139. Объем вывоза груза из пункта А Обозначения пункте в и объемы завоза грузов в них1. В С D Е F G И / J к L М3,0 0,2 0,3 0,4 0,1 0,3 0,2 0,1 0,2 3,3 0,4 0,2 0,3

140. Рис. 2 Форма заполнения объемов завоза груза к каждому получателю