ВВЕДЕННЯ

У теперішній час на ринку транспортних послуг конкуренція здобуває якісно нові риси: на фоні підвищення витрат на перевезення, жорсткості вимог до автотранспортних засобів підвищилися вимоги до якості перевізного процесу. У таких умовах функціонування підприємства неможливо без наявності ефективної системи керування. Сьогодні питання автоматизації транспортних компаній перестає бути питанням технологій, зараз це стає засобом підвищення ефективності бізнес-процесів, засобом нової організації економічної діяльності.

Одним з найбільш ефективних варіантів рішення завдань зниження витрат і поліпшення якості перевізного процесу є впровадження інформаційних систем маршрутизації, обліку та планування на автотранспортному підприємстві. Зокрема, таким реальним інструментом розвитку є система оптимізації вантажних перевезень.

1 АКТУАЛЬНІСТЬ ТЕМИ

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

Якщо створені оптимальні маршрути та дотримуються строки поставки, то виробничі запаси споживачів можуть скорочуватися в 1.5-2 рази, знижуючи тим самим витрати на складування. Необхідність маршрутизації перевезень вантажів обґрунтовується ще й тим, що маршрути дають можливість складання проектів поточних планів та оперативних заявок на транспорт, що виходять з дійсних обсягів перевезень.

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

2 ЗВ'ЯЗОК РОБОТИ З НАУКОВИМИ ПРОГРАМАМИ, ПЛАНАМИ, ТЕМАМИ

Кваліфікаційна робота магістра виконувалася протягом 2008-2009 р. відповідно до наукових напрямків кафедри "Автоматизовані системи управління" Донецького національного технічного університету.

3 МЕТА ТА ЗАДАЧІ ДОСЛІДЖЕНЬ

Так як мається велика кількість об'єктів доставки, те необхідно оптимізувати маршрути перевезень та оперативно реагувати на всі зміни. Отже, можна визначити мету роботи: Розробити алгоритм оптимізації вантажних перевезень з урахуванням тимчасових вікон і вантажопідйомності транспортних засобів. Для досягнення поставленої мети необхідно вирішити наступні основні завдання:

1. сформулювати математичну постановку завдання маршрутизації транспорту з умовою обмежень;
2. вибрати (розробити) критерії оптимізації;
3. з урахуванням розв'язуваної задачі розробити спосіб кодування рішень, проблемно-орієнтовані оператори кросинговеру та мутації;
4. розробити модифікований генетичний алгоритм оптимізації вантажоперевезень із урахуванням тимчасових вікон і вантажопідйомності транспортних засобі;
5. експериментально перевірити ефективність роботи алгоритму.

Об'єктом досліджень є маршрути вантажних перевезень транспортного підприємства.

Предметом досліджень є методи та алгоритми для рішення завдання маршрутизації транспортних засобів.

Методи досліджень. У роботі використані методи системного аналізу, метод Кларка-Райта, евристичні методи вставок і генетичні алгоритми.

4 НАУКОВА НОВИЗНА

Наукова новизна роботи полягає в розробці нового підходу до рішення завдань оптимізації маршрутизації транспортних засобів. Ідея даного підходу полягає в спільному використанні методу Кларка-Райта, евристичних методів і модифікованого генетичного алгоритму. За допомогою методу Кларка-Райта та евристичних методів вставки пропонується знаходити ефективні початкові рішення, формуючи в такий спосіб вихідну популяцію. А модифікований генетичний алгоритм дозволяє уточнювати вихідні рішення, наближаючи їх до оптимального.

5 ПРАКТИЧНЕ ЗНАЧЕННЯ ОТРИМАНИХ РЕЗУЛЬТАТІВ

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

6 ОГЛЯД ДОСЛІДЖЕНЬ І РОЗРОБОК ПО ТЕМІ

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

Розглянемо існуючі методи та інструментальні засоби, які застосовуються для рішення даної задачі на глобальному рівні.

6.1 Огляд існуючих методів

6.1.1 Метод Кларка-Райта

Метод Кларка-Райта був розроблений двома британськими вченими Г. Кларком (G. Clarke) і Дж.В. Райтом (J.W. Wrіght) [1]. Незважаючи на давнину розробки, він дотепер залишається одним з самих популярних методів для рішення даної задачі, про що свідчить практика його застосування. Метод Кларка-Райта належить до числа наближених, ітераційних методів і призначається для комп'ютерного рішення завдання розвезення. Цей алгоритм використовує поняття виграшів, щоб оцінити операції злиття між маршрутами. Виграш - міра скорочення вартості, отримана комбінуванням двох маленьких маршрутів в один великий маршрут. Достоїнствами методу є його простота, надійність та гнучкість. Погрішність рішення не перевершує в середньому 5-10% [2]. Однак, з огляду на жадібний характер алгоритму Кларка-Райта, отримані рішення мають часто недостатню якість щодо більш складних підходів. Необхідно також урахувати, що після перших декількох ітерацій у завданнях з багатьма обмеженнями ймовірність злиттів маршруту може рішуче зменшитися, ми не маємо можливості контролювати кількість маршрутів.

6.1.2 Евристичні методи вставок

Найкраще рішення для конкретних вихідних даних може бути знайдене шляхом послідовного застосування різних евристичних методів, використовуючи для порівняльної оцінки якості наближення довжину отриманого маршруту [3]. Розглянемо 4 найбільш популярних евристичних алгоритми:

1. метод найближчого сусіда (Nearest Neіghbor) [4];
2. метод найближчого міста (Nearest Town) [4];
3. метод найдешевшого включення (Most Cheap Іnclusіon) [4];
4. метод мінімального остовного дерева (Mіnіmum Spannіng Tree) [4].

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

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

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

Однак будь-який евристичний метод базується на формально не обґрунтованих міркуваннях, тому неможливо довести, що евристичний алгоритм для будь-яких вихідних даних знаходить рішення близькі до оптимального.

6.1.3 Табу-пошук

Основоположником мета-евристичного алгоритму табу пошуку  є Ф. Гловер, що запропонував принципово нову схему локального пошуку [5]. Табу пошук є мета-евристичним алгоритмом, що веде місцевий пошук, щоб уберегти його від влучення в пастку передчасних місцевих оптимумів, забороняючи ті переміщення, які повертають пошук до попередніх рішень та приводять до циклічної роботи [6]. Основним механізмом, що дозволяє алгоритму уникати локальний оптимум, є табу список, що оновлюється наприкінці кожної ітерації. Вибір кращого рішення в околиці відбувається таким чином, що він не приймає жодного з заборонених атрибутів. Алгоритм табу пошуку є досить перспективним, однак введення штрафів на порушення всіх видів обмежень у цільову функцію не дає гарантій знаходження припустимих рішень.

6.1.4 Метод гілок та границь, метод відсікань

Метод гілок та границь - добре відомий варіант пошуку з поверненням та є лише спеціальним типом пошуку з обмеженнями [3,6,7]. Обмеження ґрунтуються на припущенні, що кожне рішення пов'язане з певною вартістю, і що потрібно знайти оптимальне рішення (рішення з найменшою вартістю). Для застосування цього методу вартість повинна бути чітко визначена для часткових рішень. Ми можемо відкинути часткове рішення, якщо його вартість більше або дорівнює вартості раніше обчислених рішень [8]. Ця перевірка усуває перегляд деяких частин дерева, але насправді вона досить слабка та допускає глибоке проникнення усередину дерева до того, як гілки обриваються, тому метод гілок та границь і метод гілок з відсіканнями не ефективні за часом виконання. А той факт, що дані методи належать до класу точних методів, робить неможливим їх застосування до нашої задачі великої розмірності.

6.1.5 Мурашині алгоритми

Мурашині алгоритми являють собою імовірнісну жадібну евристику, де ймовірності встановлюються виходячи з інформації про якість рішення, отриманої з попередніх рішень [9]. Ідея мурашиного алгоритму - моделювання поводження мурах, пов'язаного з їх здатністю швидко знаходити найкоротший шлях від мурашника до джерела їжі та адаптуватися до умов, що змінюються, знаходячи новий найкоротший шлях. При своєму русі мураха мітить шлях феромоном, і ця інформація використовується іншими мурахами для вибору шляху. Це елементарне правило поведінки і визначає здатність мурах знаходити новий шлях, якщо старий виявляється недоступним. Гарні результати, які багато в чому залежать від початкових установок параметрів, даний алгоритм забезпечує тільки при застосуванні додаткових методів, таких як локальних пошук [10].

6.1.6 Генетичні алгоритми

Алгоритм рішення завдань оптимізації, заснований на ідеях спадковості в біологічних популяціях, був вперше запропонований Джоном Холландом (1975 р.) [9,11]. У ГА кожна особина представляє потенційне рішення деякої проблеми. Кожна особина кодується рядком генів - хромосомою. Безліч особин - потенційних рішень - становить популяцію. Пошук (суб)оптимального рішення задачі виконується в процесі еволюції популяції - послідовного перетворення однієї кінцевої безлічі рішень в іншу за допомогою генетичних операторів репродукції, кроссинговера й мутації. Наявність у генетичних алгоритмів цілої "популяції" рішень разом з імовірнісним механізмом мутації, дозволяють припускати меншу ймовірність знаходження локального оптимуму та більшу ефективність роботи на багатоекстремальному ландшафті. Результати застосування генетичних алгоритмів представлені в статтях [12,13].

6.2 Огляд існуючих інструментальних засобів

6.2.1 ArcLogistics 9.3

Даний програмний продукт розроблений відомою американською фірмою ESRІ. Корпорація ESRІ (США) - один зі світових лідерів у розробці, створенні та просуванні геоінформаційних систем. Сьогодні в ESRІ працює 2 700 службовців у США, 1 900 з яких базуються в його корпоративному штабі в Каліфорнії. Керівники впевнені, що технологія географічної інформаційної системи повинна постійно розвиватися, щоб зустріти потреби, бізнесу, промисловості, уряду та освіти, що постійно змінюються.

ArcLogіstіcs 9.3 - це інструмент для планування та оптимізації роботи парку транспортних засобів: імпорту замовлень, розрахунку оптимальних маршрутів, створення маршрутних аркушів, побудови звітів, аналізу ефективності роботи. Основні переваги ArcLogіstіcs 9.3: розподіл замовлень по парку транспортних засобів, наявність дорожніх даних на всю територію Європи, сумісність з іншими програмними продуктами ESRІ, використання безлічі складів, облік тимчасових вікон, велика кількість характеристик транспортних засобів, інструменти зв'язку із зовнішніми системами через ODBC, робота з парними замовленнями, різноманітні звіти. Вартість даного продукту становить 12,5 тис доларів.

6.2.2 TruckStops

TruckStops - програмний продукт, розроблений фірмою MіcroAnalytіcs. TruckStops - провідне програмне забезпечення для маршрутизації транспортних засобів та планування. Воно проектовано для компаній, що використовують 5 або більше транспортних засобів. Ви можете одержати вигоду в: повному часі поїздок, кілометрах, оплаті водіям, обслуговуванні транспортного засобу та вартості палива. Використання TruckStops дозволяє фірмам зменшувати вартість поставки, поліпшує надаваний клієнтові сервіс, робить ефективні за вартістю маршрути, збільшує адміністративне керування. Вартість програми становить 1650 доларів.

6.2.3 Ділова карта

Ділова карта - програмний продукт, розроблений фірмою ІНГІТ. Вона має потужний та гнучкий механізм розрахунку доставки вантажів. За рахунок своєї гнучкості цей механізм можна застосувати практично до будь-якої конкретної задачі - розвезення вантажів із центрального складу, завезення вантажів з різних місць на центральний склад, розвезення з декількох складів, завезення на кілька складів, а також до задач, що не мають центральних точок - доставка кореспонденції з різних місць у різні місця, перевезення меблів при переїздах і т.д. Однак, у гнучкості є й зворотна сторона - для постановки завдання необхідно велика кількість вхідних даних. Головна особливість даної програми - вона вбудовується й працює із системою 1С. Вартість програми - 1200 доларів.

Однак програмні продукти всіх цих фірм мають один загальний недолік - велика вартість, що робить неприйнятним їх використання. Їх покупка спричиняє величезну переплату за функціональні можливості системи, якими немає необхідності користуватися. Крім того, замовлення та установка продуктів закордонних виробників спричинять додаткові транспортні витрати, і їх ціна значно зросте. Зберігаючи авторське право, будь-який куплений програмний продукт поставляється без вихідних кодів програмних модулів, і кожне додаткове настроювання або зміна будь-яких умов роботи пов'язані з додатковою оплатою. Також ми не маємо можливості одержати достовірну та повну інформацію про метод, що використається в програмі, і це не дозволяє нам оцінити оптимальність знайденого рішення, а отже й ефективність використання даного програмного продукту. У Ділової карти є ще один вагомий недолік - вона розроблена для інтегрування в систему 1С, використання якої є небажаним чинником для нашого підприємства.

7 МАТЕМАТИЧНА ПОСТАНОВКА ЗАДАЧІ МАРШРУТИЗАЦІЇ ТРАНСПОРТУ

Задача маршрутизації транспортних засобів (ЗМТ) є NP-складною комбінаторною задачею оптимізації. Дана задачу з обмеженнями за часом і вантажопідйомністю можна описати в такий спосіб [14].

Є один центральний склад О, що використає деяку кількість незалежних транспортних засобів поставки з ідентичною вантажопідйомністю Q для обслуговування попитів di від N клієнтів, . Для кожного транспортного засобу потрібно скласти маршрут, по якому воно може обслуговувати ряд клієнтів, при чому кожен клієнт повинен бути обов'язково обслужений тільки однією машиною. Є матриця відстаней між клієнтами та складом і розрахованою собівартістю одного кілометра шляху з урахуванням витрат на паливо, технічне обслуговування машин, зарплати водіям та ін. На підставі цих даних розраховується матриця вартостей відстаней між клієнтами та складом, проілюстрована на рисунку 7.1.

Рисунок 7.1 - Матриця вартостей відстаней

Транспортні засоби повинні виконати поставки з мінімальною повною вартістю довжини всіх маршрутів S. Вартість відстаней між клієнтами симетрична, тобто, , де є вартістю відстані від клієнта i до клієнта j, де . Рішення для ЗМТ може бути представлене у вигляді поділу N попитів в K маршрутах , К --> min, при чому кожен маршрут починається та закінчується на складі. Тоді задача оптимізації вантажних перевезень може бути сформульована як мінімізація загальної вартості всіх маршрутів з урахуванням виконання обмежень:

	(7.1)
	(7.2)
	(7.3)
	(7.4)
	(7.5)

де – подмаршрут від клієнта i до клієнта j, верхнім індексом k позначається відповідний маршрут, де , К – кількість маршрутів.

Обмеження (7.2) полягає в тому, що кожен клієнт обслуговується тільки одним транспортним засобом і тільки один раз. Обмеження (7.3) визначає, що транспортний засіб не може обслужити більше клієнтів, чим дозволяє його вантажопідйомність. di, – попит відповідного клієнта, N - кількість клієнтів. Обмеження (7.4) - це обмеження за часом; прибуття машини до клієнта не повинне бути пізніше встановленого строку. – це час прибуття відповідної k-ї машини до і-го клієнта, – крайній строк часу обслуговування і-го клієнта.

8 ВИБІР ТА ОБҐРУНТУВАННЯ КОМБІНОВАНОГО ПІДХОДУ ДЛЯ ОПТИМІЗАЦІЇ МАРШРУТІВ

Як алгоритм завдання оптимізації вантажних перевезень було запропоновано використати новий удосконалений евристичними методами генетичний алгоритм із модифікованими проблемно-орієнтованими операторами. Загальна структура запропонованого алгоритму представлена на рисунку 8.1.

Рисунок 8.1 - Укрупнений алгоритм удосконаленого генетичного підходу

З огляду на характер задачі генетичний матеріал особини повинен містити кілька маршрутів, кожний з яких складений з упорядкованої підмножини клієнтів. Як приклад, хромосома на рисунку 8.2 кодує рішення, представлене на рисунку 8.3.

Рисунок 8.2 - Приклад кодування рішення в хромосомі

Рисунок 8.3 - Приклад рішення ЗМТ
(анімація: об'єм - 8000 байт; розмір - 450х315; складається з 113 кадрів; затримка між кадрами - 80 мс; затримка між останнім та першим кадрами - 0 мс; кількість циклів повторення - 0)

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

(8.1)

де – штраф, пов'язаний з порушенням тимчасових обмежень для і-го клієнта. Якщо поставка запланована в строк, то штраф дорівнює нулю, інакше він росте зі збільшенням затримки часу обслуговування. В основі даної фитнес-функции лежить ідея табу-пошуку для оцінки рішень - накладення штрафів за порушення обмежень.

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

Для створення нащадків був запропонований модифікований оператор кроссинговера, що враховує специфіку досліджуваного завдання. Кількість батьків, що беруть участь у схрещуванні визначається числом M, збільшення M дозволяє більш ефективно передавати властивості (маршрути) батьків нащадкам, збіжність алгоритму збільшується, але це грозить небезпекою влучення в локальний мінімум. При зменшенні M росте розмаїтість у популяції. Оптимальне значення параметра M варіюється в межах від 2 до 4. Оператор кроссинговера полягає в наступному:

1. Маршрути з обраних особин поєднуємо в одне рішення. Дане рішення назвемо об'єднаним рішенням;
2. Поки в об'єднаному рішенні є маршрути, робимо наступне: вибираємо маршрут і вставляємо його в нове рішення, для цього беремо випадкове число в межах від 0 до кількості маршрутів в об'єднаному рішенні, дане число й буде вказувати номер маршруту в об'єднаному рішенні; видаляємо обраний маршрут в об'єднаному рішенні; видаляємо в об'єднаному рішенні всі маршрути, у яких є клієнти з обраного рішення;
3. Вставляємо не обслужених клієнтів у нове рішення з використанням методу найдешевшого включення з урахуванням вантажопідйомності. Якщо вставка не можлива - створюється новий маршрут. Рисунок 8.4 ілюструє даний оператор кросинговеру.

На підставі аналізу сучасних досліджень ведучих учених в області питання про оптимальну маршрутизацію транспортних засобів та особливостей даної задачі був розроблений ряд операторів мутації, які застосовуються з відповідними ймовірностями, які не повинні суперечити наступному обмеженню:

(8.2)

Величина у даній формулі являє собою загальну ймовірність мутації в хромосомі, і дорівнює 7%.

Оператори мутації:

1. обмін: у хромосомі вибирають двох клієнтів та міняють їх. Обрані вузли можуть належати тому самому або різним маршрутам. Якщо знову створене рішення є неприпустимим, то застосовуємо оператор коректування;
2. інверсія: вибирають подмаршрут та реверсують порядок приналежних йому клієнтів. Якщо це погіршило значення фитнес-функции для даного рішення, то даний оператор скасовується;
3. переміщення: вибирають подмаршрут і вставляють його в інше місце. Цей оператор може виконати внутрішнє або зовнішнє переміщення;
4. вторинна вставка маршрутів: з рішення віддаляються маршрути цілком, потім клієнти з вилучених маршрутів заново уставляються в рішення;
5. вторинна вставка клієнтів: з рішення віддаляються окремі клієнти, і потім заново вставляються в маршрут;
6. відновлення: видаляє клієнтів, що порушують тимчасові обмеження з їх маршрутів. Вилучені клієнти потім повторно уставляються, використовуючи метод найдешевшого включення з урахуванням вантажопідйомності;
7. переупорядкування клієнтів: процедура інтенсифікації, що намагається зменшити повну відстань припустимих рішень, переупорядковуючи клієнтів у межах маршруту за допомогою евристичного методу вставок.

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

Оператор редукції відбирає в нову популяцію 5% елітних хромосом, потім методом рулетки формуємо відсутню кількість особин.

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

ВИСНОВОК

У результаті науково-дослідної роботи були зібрані та вивчені матеріали з питань, пов'язаних з темою магістерської роботи. Були досліджені застосовувані методи та алгоритми оптимізації маршрутизації транспортних засобів та розробки провідних фірм, пропоновані інструментальні та програмні засоби, принципи їхньої побудови. Були виявлені достоїнства та недоліки існуючих комп'ютерних систем, методів оптимізації, що належать до різних класів. Як результат були визначені проблеми, невирішені в цих напрямках, можливі шляхи, методи та засоби їх вдосконалювання. На підставі результатів аналізу був обраний напрямок власних досліджень в області знаходження оптимальних маршрутів транспортних засобів для здійснення вантажоперевезень, сформульована математична постановка завдання. Для рішення запропонованого завдання був розроблений комбінований генетичний алгоритм, заснований на еволюційному підході з використанням методу Кларка-Райта для формування початкової популяції та евристичних методів вставок, які використовуються, як механізм розвитку популяції та коректування рішень, що порушують обмеження. Програмна реалізація запропонованого алгоритму була виконана мовою високого рівня в середовищі С++ Builder 6.0 [15]. Результатом роботи програми є набір оптимізованих маршрутів, які представляються у вигляді маршрутних аркушів із вказівкою необхідних даних про замовлення та клієнтів. Подальша робота полягає в плануванні та проведенні експериментальних досліджень та оцінці ефективності алгоритму оптимізації вантажних перевезень.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. Clarke G. Scheduling of vehicles from a central depot to a number of delivery points / G. Clarke, J.W. Wright // Journal of Operations Research Society. - 1964. – Vol.12, № 4. – pp. 568–581.
2. Battarra M. Tuning a Parametric Clarke-Wright Heuristic via a Genetic Algorithm / M. Battarra, B. Golden, D. Vigo // Journal of Operations Research Society. - 2008. – Vol.59, № 11. – pp. 1568–1572. / - Режим доступа к статье: http://or.ingce.unibo.it/ricerca/technical-reports-or-ingce/papers/gacw-sito.pdf.
3. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика. / Э.Рейнгольд, Ю. Нивергельт, Н. Део; пер. с англ. Е.П. Липатова. - М.: Мир, 1980. — 476 c.
4. Пушкарёва Г.В. Исследование и применение бионических методов и моделей для автоматизированного проектирования маршрутов обхода геометрических объектов [Электронный ресурс] // Компьютерная графика и представление GraphiCon ‘2005: науч.-техн. конф., 20-24 июня 2005г. : - 2005. / - Режим доступа к статье: http://www.graphicon.ru/2005/proceedings/papers/Pushkaryova.pdf.
5. Glover F. Tabu Search/ F. Glover, M. Laguna // Journal of the Operational Research Society. - 1999. – Vol.50, № 1. – pp. 106–107. / - Режим доступа к статье: http://glossary.computing.society.informs.org/notes/spanningtree.pdf.
6. Сухарев А.Г. Курс методов оптимизации: Учебное пособие. - [2-е изд]. / А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. – М.: ФИЗМАТЛИТ, 2005. – 368 с.
7. Blasum U. Application of the Branch and cut method to the Vehicle Routing Problem [Электронный ресурс] / U. Blasum, W. Hochstattler. - 2000. / - Режим доступа к статье: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.9887&rep=rep1&type=pdf.
8. Харчистов Б.Ф. Методы оптимизации: учебное пособие / Б.Ф. Харчистов. – Таганрог.: ТРТУ, 2004. – 140 с.
9. Макконелл Дж. Основы современных алгоритмов: учебное пособие / Дж. Макконелл; пер. с англ. С.К. Ландо. – [3-е изд.]. - М.: Техносфера, 2004. — 368 c.
10. Штовба С.Д. Муравьиные алгоритмы / С.Д. Штовба // Exponenta Pro. Математика в приложениях. - 2003. – № 4. – С. 70-75 / - Режим доступа к статье: http://soft.mail.ru/journal/pdfversions/32150.pdf.
11. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский; пер. с польск. И.Д. Рудинский – М.: Горячая линия-Телеком, 2006. – 452 с.
12. Pereira F.B. GVR: Vehicle Routing Problem: Doing it the Evolutionary Way / F.B. Pereira, J. Tavares, P. Machado, E.Costa // Proceedings of the Genetic and Evolutionary Computation Conference – 2002. – p. 690. / - Режим доступа к статье: http://osiris.tuwien.ac.at/~wgarn/VehicleRouting/GECCO02_VRPCoEvo.pdf.
13. Pereira F.B. GVR: a New Genetic Representation for the Vehicle Routing Problem / F.B. Pereira, J. Tavares, P. Machado, E.Costa // Proceedings of the 13th Irish Intern. Conf. on Artificial Intelligence and Cognitive Science – 2002. – pp. 95-102.] / - Режим доступа к статье: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.5248.
14. Смехов А.А. Основы транспортной логистики. / А.А. Смехов. - М.: Транспорт, 1995. - 197 с.
15. Архангельский А.Я. Программирование в C++Builder 6 / А.Я. Архангельский. – М.: БИНОМ, 2003. – 1152 с.

ДОГОРИ

При написанні даного автореферату магістерська робота ще не завершена. Дата кінцевого завершення роботи: 1 грудня 2009 р. Повний текст роботи та матеріали за темою можуть бути отримані у автора або у його наукового керівника після вказаної дати.