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

Автор работы: Пользователь скрыл имя, 13 Мая 2013 в 09:38, курсовая работа

Описание работы

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

Содержание работы

1 ФОРМУВАННЯ ВХІДНИХ ДАНИХ 4
1.1. Генерація загальних обсягів замовлень для трьох можливих програм загальних вантажних перевезень F1, F2, F3 4
1.2. Генерація замовлень вантажу в кожному з вузлів (чіткі значення) 4
2 ФОРМУВАННЯ СИМЕТРИЧНОЇ МАТРИЦІ ВІДСТАНЕЙ МІЖ ЗАДАНИМИ ВУЗЛАМИ. 7
3 ФОРМУВАННЯ ПОСЛІДОВНОСТІ ОБХОДУ (ЗАДАЧА TSP – TRAVELING SALESMAN PROBLEM АБО ЗАДАЧА КОМІВОЯЖЕРА) НА ОСНОВІ SAVING-АЛГОРИТМУ 10
3.1 Формування saving-таблиці відстаней 10
3.2 Графічна візуалізація гамільтонового циклу сформованого за saving-алгоритмом 13
4 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ SAVING-АЛГОРИТМУ 14
5 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ МОДИФІКОВАННОГО SAVING-АЛГОРИТМУ 19
5.1 Програма F1 20
5.2 Програма F2 21
5.3 Програма F3 22
6 Формування послідовності обходу вузлів (задача tsp-комівояжера) на основі sweeping-алгоритму 24
6.1 Графічна візуалізація відповідного Гамільтонового циклу. 24
7 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ SWEEPING-АЛГОРИТМУ 25
7.1 Програма F1 26
7.2 Програма F2 27

Скачать архив (1.25 Мб) Сколько стоит заказать работу?
Файлы: 1 файл

курсак Дорошенко.docx

— 1.41 Мб (Скачать файл)

 

 

    1. Програма  F2

В табл. 11 занесена інформація про маршрути транспортних перевезень для програми F2.

Таблиця11. Маршрути транспортних перевезень для програми F2.

R

Номери вузлів, що входять  в маршрут

Lr

    

1

0-23-16-22-21-20-19-0

139,7403

1,8531

0,1469

2

0-13-18-3-11-17-0

103,4656

1,6070

0,3930

3

0-12-9-8-7-1-14-4-15-0

123,2126

1,7903

0,2097

4

0-5-6-25-2-24-10-0

71,0957

1,7770

0,2230

   

437,5142

    

 

Показник ефективності: E2 = 0,9266.

 

Рис. 8. Маршрути транспортних перевезень для програми F2.

 

 

 

 

    1. Програма  F3

В табл. 12 занесена інформація про маршрути транспортних перевезень для програми F3.

Таблиця12. Маршрути транспортних перевезень для програми F3.

R

Номери вузлів, що входять  в маршрут

Lr

    

1

0-23-16-22-21-0

104,6171

1,7638

0,2362

2

0-13-18-3-0

75,5032

1,4076

0,5924

3

0-9-12-17-11-0

84,3459

1,6593

0,3407

4

0-19-20-14-1-7-0

116,2988

1,4220

0,5780

5

0-6-5-0

37,0246

1,3782

0,6218

6

0-8-10-15-4-0

68,3110

1,7936

0,2064

7

024-2-25-0

41,2274

0,8118

1,1882

   

527,3281

    

 

Показник ефективності: E3 = 0,8819.

 

 

Рис. 9. Маршрути транспортних перевезень для програми F3.

Рис.  10. Залежність

для трьох програм F1, F2, F3 для модифікованого saving – алгоритму.

 

 

 

 

 

 

 

 

 

 

  1. Формування послідовності обходу вузлів (задача tsp-комівояжера) на основі sweeping-алгоритму

Даний алгоритм використовує полярні координати. Тому для побудови відповідного гамільтонового циклу нам потрібно перевести  дані координати в полярні та відсортувати їх по кутовій координаті.

    1. Графічна  візуалізація відповідного Гамільтонового циклу.

На рис. 11 зображений відповідний гамільтонів цикл:

Рис. 11 Гамільтонів цикл з використанням полярних координат

Гамільтонів цикл GSw має вигляд:

GSw={0-22-1-16-15-23-7-10-8-24-9-2-5-12-17-6-11-25-13-18-3-19-20-4-21-14-0}.

 

 

  1. ФОРМУВАННЯ  МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ  НА ОСНОВІ SWEEPING-АЛГОРИТМУ

 

На даному етапі відбувається формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі sweeping-алгоритму наступним чином. Визначається загальна кількість маршрутів R, що відповідає необхідній кількості транспортних засобів, довжини кожного маршруту Lr, r=1,...,R, кількість перевезеного вантажу та залишкова кількість вантажу DDr=Dmax- на кожному з маршрутів, сумарна довжина всіх маршрутів LS=r , та при повній реалізації кожної з програм F1, F2, F3, а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:

 

 

 

 

 

 

 

 

 

 

    1. Програма  F1

В табл. 13 занесена інформація про маршрути транспортних перевезень для програми F1.

Таблиця 13. Маршрути транспортних перевезень для програми F1

R

Номери вузлів, що входять  в маршрут

Lr

    

1

0-22-1-16-15-23-7-0

149,8988

1,8514

0,1486

2

0-10-8-24-9-2-0

100,9520

1,6025

0,3975

3

0-5-12-17-0

60,4440

1,9689

0,0311

4

0-6-11-25-0

51,2445

1,3871

0,6129

5

0-13-18-3-0

75,5032

1,3660

0,6340

6

0-19-20-4-21-14-0

122,4569

1,7568

0,2432

 

560,4994

    

 

Показник ефективності: E1 = 0,9257.

 

Рис. 12 Маршрути транспортних перевезень для програми F1

 

 

 

7.2 Програма F2

В табл. 14 занесена інформація про маршрути транспортних перевезень для програми F2.

Таблиця 14. Маршрути транспортних перевезень для програми F2

R

Номери вузлів, що входять  в маршрут

Lr

    

1

0-22-1-16-15-23-7-10-0

150,4226

1,5832

0,4168

2

0-8-24-9-2-5-12-0

140,7529

1,8507

0,1493

3

0-17-6-11-25-13-0

89,7123

1,8797

0,1203

4

0-18-3-19-20-4-21-14-0

157,5001

1,7138

0,2862

 

538,3879

    

 

Показник ефективності: E2 = 0,7916.

 

Рис. 13 Маршрути транспортних перевезень для програми F2

 

 

 

    1. Програма  F3

В табл. 15 занесена інформація про маршрути транспортних перевезень для програми F3.

Таблиця 15. Маршрути транспортних перевезень для програми F3

R

Номери вузлів, що входять  в маршрут

Lr

    

1

0-22-1-16-15-23-7-0

149,8988

1,9081

0,0919

2

0-10-8-24-9-2-0

100,9520

1,6515

0,3485

3

0-5-12-0

55,8375

1,4424

0,5576

4

0-17-6-11-0

65,7928

1,5638

0,4362

5

0-25-13-18-3-0

76,6623

1,8600

0,1400

6

0-19-20-4-21-14-0

122,4569

1,8105

0,1895

 

571,6003

    

 

Показник ефективності: E3 = 0,9541.

 

Рис. 14 Маршрути транспортних перевезень для програми F3

 

 

 

Рис.  15. Залежність

для трьох програм F1, F2, F3 для sweeping – алгоритму.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1.   ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ МОДИФІКОВАННОГО SWEEPING-АЛГОРИТМУ

        

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

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

Показник ефективності завантаження транспортних засобів E при реалізації кожної програми визначається за формулою:

 

 

 

 

 

 

 

 

 

 

 

    1.   Програма F1

В табл. 16 занесена інформація про маршрути транспортних перевезень для програми F1.

Таблиця 16. Маршрути транспортних перевезень для програми F1

R

Номери вузлів, що входять  в маршрут

Lr

    

1

0-4-21-14-22-1-16-0

125,7883

1,8464

0,1536

2

0-15-23-7-10-0

68,0950

1,2404

0,7596

3

0-8-24-9-2-5-0

113,1997

1,9413

0,0587

4

0-12-17-6-0

60,2300

1,8556

0,1444

5

0-11-25-13-0

69,0416

1,4756

0,5244

6

0-18-3-19-20-0

110,7517

1,5734

0,4266

 

547,1064

    

 

Показник ефективності: E1 = 0,9232.

 

Рис. 16 Маршрути транспортних перевезень для програми F1

 

    1.   Програма F2

В табл. 17 занесена інформація про маршрути транспортних перевезень для програми F2.

Таблиця 17. Маршрути транспортних перевезень для програми F2

R

 <td class="gen525866" width="240


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