Синтез СППР для оптимізації парку транспортних засобів та оптимізації маршрутів вантажних перевезень в умовах невизначеності

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

Чорноморський державний  університет  
імені Петра Могили

Факультет комп’ютерних наук

Кафедра інтелектуальних  інформаційних систем

 

 

 

 

 

 

КУРСОВА РОБОТА

 

"Синтез СППР для оптимізації парку транспортних засобів та оптимізації маршрутів вантажних перевезень в умовах невизначеності"

Дисципліна "Системи підтримки прийняття рішень"

Спеціальність "Системи і методи прийняття рішень"

 

8.080400–КР.ПЗ.00–501м.2810104

 

 

 

 

 

 

 

 

Студент   _____________В.Ю. Гнатовський

    (підпис)

        _____________  

              (дата)

Викладач    ____________   д.т.н., професор

                      (підпис)   Ю.П. Кондратенко

                     ____________

    (дата) 

 

 

 

 

 

Миколаїв – 2012

 

АНОТАЦІЯ

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

1. Формування saving таблиці

2. Формування маршрутів на основі Saving алгоритму;

3. Формування маршрутів на основі модифікованого Saving алгоритму
4. Формування маршрутів на основі Sweeping алгоритму
5. Формування маршрутів на основі модифікованого Sweeping алгоритму
6. Оптимізація маршрутів за допомогою методу осереднених коефіцієнтів.
7. Формування матриці альтернативних рішень, що до кількості транспортних засобів.
8. Вибір оптимальної кількості транспортних засобів на основі класичних, похідних і комбінованих критеріїв прийняття рішень. 

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

 

ЗМІСТ

 

Чорноморський державний університет  ім. П.Могили

Факультет комп’ютерних наук

Кафедра інтелектуальних інформаційних  систем

ЗАВДАННЯ

на курсову роботу з дисципліни «Системи підтримки прийняття рішень»

студента Гнатовського Володимира Юрійовича

 групи 501м

 

Варіант №28

1. Тема курсової  роботи 

«Синтез систем підтримки прийняття рішень (СППР) для оптимізації парку транспортних засобів та маршрутів вантажних перевезень в умовах невизначеності»

2. Вхідні дані  до курсової роботи

1. Координати вузлів, в яких знаходяться  замовники вантажів.

2. Вантажомісткість транспортних  одиниць (гомогенний флот).

3. Генерація загальних обсягів  замовлень для 3 (трьох) можливих  программ загальних вантажних  перевезень {F₁, F₂, F₃}.

4. Генерація замовлень вантажу в кожному з вузлів (чіткі значення).

5. Дані для розрахунку матриці  рішень:

а) параметри С1, С2, С3, С4, С5;

б) закон розподілу {q₁, q₂, q₃ } зовнішніх станів (програм загальних вантажних перевезень). 

6.  Методи формування маршрутів:  а) sweeping-алгоритм,  saving-алгоритм.

7.  Визначення оптимального складу  транспортного парку, тобто оптимальної кількості

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

8.  Обчислювальне середовище для розробки СППР – MATLAB.

 

 

3. Зміст пояснювальної  записки до курсової роботи 

Анотація, завдання на проектування СППР, постановка задачі, розв’язок різними  методами (sweeping, saving) задач планування маршрутів CVRP з врахуванням обмеження  на вантажомісткість транспортних засобів, оптимізація маршрутів на основі розв’язання TSP та вибір найкращих маршрутів, формування матриці альтернативних рішень та результати її обробки за різнотипними критеріями, програмне забезпечення СППР для обчислювального середовища MATLAB, блок-схеми алгоритмів, інтерфейс СППР з характеристикою можливостей інтерактивної взаємодії ЛПР і СППР, висновки.

4. Перелік графічного  матеріалу курсової роботи 

Пояснювальна записка містить  рисунки, шо забезпечують ілюстрацію результатів проектування.

Power-Point презентація (18-20 слайдів).

5. Рекомендована література  для виконання курсової роботи 

1.  Арсеньев Ю.Н. и др. Принятие  решений: Интегрированные интеллектуальные  системы. - М.: ЮНИТИ, 2003.

2.  Герасимов Б.М., Тарасов В.А., Токарев И.В. Человеко-машинные системы принятия решений с элементами искусственного интеллекта. – К.: Наукова думка, 1993.

3.  Катренко А.В., Пасічник В.В. , Пасько В.П. Теорія прийняття  рішень. –К.: Видавнича група BHV, 2009.

4.  Мушик Е., Мюллер П. Методы принятия технических решений, Москва, 1990

5.  Ситник В.Ф. , Олексюк О.С., Гужва  В.М., Ріппа С.П., Олейко В.М. Системи  підтримки прийняття рішень. –  К.: Техніка, 1995. 

15.  Трахтенгерц Э.А. Компьютерная  поддержка принятия решений. - М.: Синтег, 1998.

 

Дата видачі завдання:                                         2012 р.

 

Дата здачі курсової роботи:                               2012 р.

Керівник  __________________________________ (підпис)  д.т.н., професор  Кондратенко Ю.П.

 

Завдання прийняв до виконання   ___________(підпис)  студент групи 501м Гнатовський В.Ю.

 

ВСТУП

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

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

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

 

1 ПОСТАНОВКА ЗАДАЧІ

Миколаївський завод ВАТ «Миколаївцемент» займається продажем та перевезенням цементу до покупців. Маємо 30 замовників-складів з їх відповідними координатами (див. табл. 1), куди необхідно доставити кількість цементу, що замовляється. Потреба кожного замовника в цементі невизначена, тому за 3-ма можливими програми замовлень маємо загальні обсяги для кожної програми (див. табл. 2) та замовлення по кожному складу окремо (див. табл. 3). Крім того, вантажомісткість транспортних засобів є обмеженою.

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

Усі вхідні дані зазначені у завданні.

 

2 ФОРМУВАННЯ ВХІДНИХ ДАНИХ

1. Координати вузлів, в яких знаходяться замовники вантажів.

 Загальна кількість вузлів = 30.

Таблиця 1

№ вузла	Xi	Yi	№ вузла	Xi	Yi	№ вузла	Xi	Yi
28	35	16	38	47	66	48	48	21
29	52	26	39	30	60	49	12	38
30	43	26	40	30	50	50	15	56
31	31	76	41	12	17	51	29	39
32	22	53	42	15	14	52	54	38
33	26	29	43	16	19	53	55	57
34	50	40	44	21	48	54	67	41
35	55	50	45	50	30	55	10	70
36	54	10	46	51	42	56	6	25
37	60	15	47	50	15	57	65	27

 

2. Вантажомісткість транспортних одиниць (гомогенний/ гетерогенний флот). Вантажомісткість Dmax транспортних одиниць (гомогенний флот) в тоннах:

Dmax = 14,5.

3. Генерація загальних обсягів замовлень для 3 (трьох) можливих программ загальних вантажних перевезень {F1, F2, F3}

Генерую в Matlab випадкові числа η₁, η₂, η₃ (η_і) [0, 1]:

Таблиця 2

F1	F2	F3
51,9825	80,9367	169,4652

 

 

 

4. Генерація замовлень вантажу в кожному з вузлів (чіткі значення)

а) В Matlab генеруємо 30 випадкових значень  , де j = 1..N; N = 30:

>> rand(1,30)

ans =

0.8147	0.9058	0.1270	0.9134	0.6324	0.0975	0.2785	0.5469	0.9575	0.9649
0.1576	0.9706	0.9572	0.4854	0.8003	0.1419	0.4218	0.9157	0.7922	0.9595
0.6557	0.0357	0.8491	0.9340	0.6787	0.7577	0.7431	0.3922	0.6555	0.1712

б) Знаходимо суму всіх генерованих  значень:

SUM =

= 7,2386 + 6,6022 + 5,8729 = 19,71.

в) Знаходимо нормалізований параметр для кожного з вузлів (табл.2):

Таблиця 2

0,04133	0,04596	0,00644	0,04634	0,03208	0,00494	0,01413	0,02775	0,04858	0,048955
0,00799	0,04924	0,04856	0,02463	0,04060	0,00719	0,02140	0,04646	0,04019	0,048681
0,03327	0,00181	0,04308	0,04739	0,03443	0,03844	0,03770	0,01989	0,03326	0,00868