проведений аналіз методів вирішення завдань транспортної логістики. У результаті проведеного дослідження було розроблено чотири модифікованих алгоритму пошуку оптимального маршруту в транспортній мережі з можливістю завдання широкого спектра додаткових умов і обмежень.
У результаті проведеного аналізу найбільш вартими уваги з точки зору практичного використання були визнані: нерекурсивний пошук в глибину і багатопотоковий пошук ширину. Перший з них менш вимогливий до оперативної пам'яті і орієнтований на виконання в системах, що базуються на процесорі з одним ядром. Другий має великі вимоги до оперативної пам'яті, але за рахунок використання багатопоточності може бути більш швидкодіючим в системах, що базуються на багатоядерних процесорах.
Так само була розроблена власна модель для внутрішнього представлення транспортної мережі.
В якості середовища розробки був обраний пакет Visual Studio 2010. Реалізація велася з використанням мови програмування високого рівня C #. Для зберігання транспортної мережі використовувалися принципи серіалізациі об'єктів і формат XML.
На основі розробленого модифікованого алгоритму і моделі внутрішнього представлення даних був створений програмний комплекс, що володіє наступними можливостями:
. Створення, модифікація, завантаження, збереження транспортної мережі.
. Візуалізація транспортної мережі з можливістю з можливістю тимчасового приховування окремих її частин.
. Завдання умов пошуку і критеріїв оптимальності пошуку маршруту.
. Здійснення пошуку маршрутів з урахуванням заданих обмежень.
Одним з подальших напрямків розвитку даного курсового проекту може бути більш докладне дослідження многопоточной версії алгоритму пошуку в ширину і визначення такого максимального кількості працюючих паралельних потоків, яке б забезпечувало і високу швидкість роботи і не допускало б пробуксовки.
алгоритм транспортний маршрут граф
СПИСОК ЛІТЕРАТУРИ
1. Оре, О. Теорія графів. М .: Наука, 1968.
. Харарі, Ф. Теорія графів. М .: Світ, 1973.
. Вілсон, Р. Введення в теорію графів. Пер з англ. М: Світ, 1977.
. Емелічев, В.А., Лекції з теорії графів. М .: Наука, 1990.
. Кормен, М. Частина VI. Алгоритми для роботи з графами//Алгоритми: побудова й аналіз. М .: «Вільямс», 2006.
. Сербін, В.Д. Основи логістики. Таганрог: ТРТУ, +2004.
. Сток, Р. Стратегічне управління логістикою. М .: Инфра-М, 2005.
. Хемді, А. Введення в дослідження операцій. М .: «Вільямс», 2007.
. Вентцель, С.Є. Дослідження операцій: завдання, принципи, методологія. М .: Наука, 1980.
. Мудров, В.І. Завдання про комівояжера. М .: «Знання», 1969.
. Ананій, В. Алгоритми: введення в розробку й аналіз. М .: «Вільямс», 2006.
. Муртаф, Б. Сучасне лінійне програмування. М .: Світ, 1984.
. Стівен, С. Олімпіадні задачі з програмування. М .: ІД Кудіц-образ, 2005.
. Меньшиков, Ф. Олімпіадні задачі з програмування. Спб .: Питер, 2006.
. Дейтл, Х. C #. СПб .: БХВ-Петербург, 2006.
. Павловська, Т.А. C #. Програмування на мові високого рівня. СПб .: Питер, 2007.
ДОДАТОК А
Функція отрисовки транспортної мережі
public void Draw (bool showInvisible, bool showDeleted)
{
//отрисовать граф
//перо для отрисовки
Pen dcPen=new Pen (Color.Black, 1);
//кисть для отрісовкіdcBrush=new SolidBrush (Color.White);
//якщо необхідно змінити розмір компонента перед отрисовкой
if (this.pb.Width!=this.width || this.pb.Height!=this.height)
{. pb.Width=this.width; .pb.Height=this.height; .pb.Image=new Bitmap (this.width, this.height) ;. dc=Graphics.FromImage (this.pb.Image);
}
//отрисовка вед? ться у високому качестве.SmoothingMode=
System.Drawing.Drawing2D.SmoothingMode.HighQuality; .TextRenderingHint=
System.Drawing.Text.TextRenderingHint.SingleBitPerPixel;
//заливаємо всю картинку білим цветом.dc.FillRectangle (dcBrush, 0, 0, this.width, this.height);
