Автоматизированная система поиска оптимального маршрута на транспортной сети

Рисунок 33 - портфолио Терентьева Данилы Андреевича

Заключение

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

Была разработана автоматизированная система (АС) поиска оптимального маршрута на транспортной сети (ТС). Решение принимается на основе сравнения расчетов, полученных двумя различными способами: алгоритму Дейкстры и жадному алгоритму.

Разработаны коды названных методов на языке С++. В ходе разработки АС применялась методология UML.

Было проведено сравнение методов оптимизации с аналогами.

Основное назначение АС - помощь в выборе оптимального маршрута для прохождения по транспортной сети.

Функциональными возможностями АС являются: создание транспортной сети нужного размера и типа, вывод оптимального маршрута.

Список используемых источников

1. Афанасьев Л.Л. Единая транспортная система и автомобильные перевозки: учебник для вузов / Л.Л. Афанасьев, Н.Б. Островский

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

3. Современные методы и средства проектирования информационных систем

4. Алгоритм Дейкстры

5. Жадный алгоритм - C++

6. Дерябкин В.П. Проектирование информационных систем по методологии UML [Текст]: метод. указания к уч.-лаборат. практикуму. /В.П. Дерябкин, В.В. Козлов; Самарск. гос. арх. строит. ун-т. - Самара, 2008.-42с.

7. Ник Рендольф, Дэвид Гарднер, Майкл Минутилло, Крис Андерсон. Qt Creator 5.4 для профессионалов = Professional Qt Creator 5.4. -- М.[Текст]: «Диалектика», 2011. -- С. 1184.

8. Бьёрн Страуструп. Язык программирования C++ = The C++ Programming Language [Текст]: Пер. с англ. -- 3-е изд. -- СПб.; М.: Невский диалект -- Бином, 1999. -- 991 с. -- 3000 экз.

9. ГрадиБуч. OMG Unified Modeling Language (UML) [Текст]: Superstructure, V2.1.2, p.154.

Приложение А

Листинг основных программных модулей

mainwindow.cpp

#include"mainwindow.h"

#include"ui_mainwindow.h"

#include"avtor.h"

#include"QTableWidget"

#include"QTableWidgetItem"

#include"QListWidget"

#include"QListWidgetItem"

#include"QMessageBox"

#include"QFile"

#include<QFileDialog>

#include<otchet.h>

#defineSIZE11

#defineNUMBER7

MainWindow::MainWindow(QWidget*parent):

QMainWindow(parent),

ui(newUi::MainWindow)

{

tableWidget=NULL;

ui->setupUi(this);

}

MainWindow::~MainWindow()

{

deleteui;

}

voidMainWindow::on_pushButton_clicked()

{

deletetableWidget;

n=ui->lineEdit_3->text().toInt();

tableWidget=newQTableWidget(this);

tableWidget->setRowCount(n);

tableWidget->setColumnCount(n);

for(introw=0;row!=tableWidget->rowCount();++row){

for(intcolumn=0;column!=tableWidget->columnCount();++column){

newItem=newQTableWidgetItem(tr("0"));

tableWidget->setItem(row,column,newItem);

}

}

ui->horizontalLayout->addWidget(tableWidget);

//ui->pushButton->setEnabled(false);

}

voidMainWindow::on_pushButton_2_clicked()

{

listwidget=newQListWidget(this);

intr,i,j,k=0,m,s,ss,K,L,l=0;

intflagr=0,flags=0;

intH[SIZE],G[SIZE],V[SIZE],M[SIZE],B[SIZE],Q[SIZE];

r=ui->lineEdit->text().toInt();

s=ui->lineEdit_2->text().toInt();

for(i=1;i<=n;i++){

H[k]=i;

for(j=1;j<=n;j++){

if(tableWidget->item(i-1,j-1)->text().toInt()!=0){

G[k]=j;

V[k]=tableWidget->item(i-1,j-1)->text().toInt();

k++;

H[k]=i;

}

}

}

K=k;

if(r==s){

msg.setText("pointscoincide!");

msg.exec();

return;

}

M[r]=0;//обнуление метки начала прохода

//расстановка меток из вершины начала прохода

for(i=0;i<K;i++)

//for(j=0;j<K;i++)

{

if(H[i]==r)//проверка внутри блока r

{

m=H[i];//m- номер вершины, откуда идет дуга

k=G[i];//k- номер вершины, куда идет дуга

M[k]=V[i];//массив меток

Q[k]=r;//массив вершин, из которых расставлялись метки

flagr=1;//есть вершина начала прохода

}

}

if(flagr==0)//в списках связей графа нет вершины начала прохода

{

msg.setText("pathdoesnotexist!");

msg.exec();

return;

}

//продолжение расстановки меток графа

for(i=0;i<K;i++)//проход по массивам H[],G[],V[]

{

if(H[i]==r)continue;//пропуск блока начала, т.к. от начала метки расставлены

m=H[i];

k=G[i];//ищем метку для вершины k

L=M[m]+V[i];//наращивание расстояния

if(L<M[k])

{

M[k]=L;//смена метки

Q[k]=H[i];//H[i]-вершина, откуда пришли

}

}

ss=s;

k=0;

B[k]=s;

L1:for(i=1;i<=n;i++)//i-номер вершины в Q[]

{

if(i==ss)

{

ss=Q[i];//Q[i]-вершина, откуда пришли в вершину ss

k++;

B[k]=ss;

if(ss==r)break;

elsegotoL1;

}

}

if(B[k]==0)

{

msg.setText("pathdoesnotexist!");

msg.exec();

return;

}

otchet*ot=newotchet(listwidget,0);

newQListWidgetItem(tr("wayfromrdos"),listwidget);

for(i=k;i>=0;i--){

//newQListWidgetItem(tr(""),listWidget);

newQListWidgetItem(QString::number(B[i]),listwidget);

}

newQListWidgetItem(tr("Расстановка меток вершинам по алгоритму Дейкстры"),listwidget);

for(i=1;i<=n;i++){

//newQListWidgetItem(tr(""),listWidget);

newQListWidgetItem(QString::number(M[i]),listwidget);

}

newQListWidgetItem(tr("Минимум целевой функции!"),listwidget);

newQListWidgetItem(QString::number(M[s]),listwidget);

ot->show();

}

voidMainWindow::on_pushButton_3_clicked()

{

exit(0);

}

voidMainWindow::on_pushButton_4_clicked()

{

QStringfilename=QFileDialog::getSaveFileName(this,tr("OpenFile"),

"C:/",

tr("Texts(*.txt)"));

QFilefile(filename);

if(file.open(QIODevice::WriteOnly))//Если файл открыт только для чтения

{

QDataStreamstream(&file);

qint32row(tableWidget->rowCount()),column(tableWidget->columnCount());//Объявляем переменные типа Integer для 32-битгных платформ

stream<<row<<column;//Заносим значения из файла соответствующие row и column

for(inti=0;i<row;++i)//циклприi=0,покаi<row,i увеличивается на единицу

for(intj=0;j<column;j++)//циклприj=0,покаj<row,j увеличивается на единицу

tableWidget->item(i,j)->write(stream);//Записываем данные в файл

file.close();//Закрываем файл

}

}

voidMainWindow::on_pushButton_5_clicked()

{

if(tableWidget==NULL){

QMessageBox::information(this,"Ошибка","Введитеколичествопунктов");

return;

}

deletetableWidget;

n=ui->lineEdit_3->text().toInt();

tableWidget=newQTableWidget(this);

tableWidget->setRowCount(n);

tableWidget->setColumnCount(n);

for(introw=0;row!=tableWidget->rowCount();++row){

for(intcolumn=0;column!=tableWidget->columnCount();++column){

newItem=newQTableWidgetItem(tr("0"));

tableWidget->setItem(row,column,newItem);

}

}

ui->horizontalLayout->addWidget(tableWidget);

QStringfilename=QFileDialog::getOpenFileName(this,tr("OpenFile"),

"Z:/Danil",

tr("Texts(*.txt)"));

QFilefile(filename);//Объявление переменной файлового класса

if(file.open(QIODevice::ReadOnly))//Если файл открыт только для чтения

{//Начало условия

QDataStreamstream(&file);

qint32row,column;//Объявляем переменные типа Integer для 32-битгных платформ

stream>>row>>column;//Берем значения из файла соответствующие row и column

tableWidget->setRowCount(row);//Устанавливаем кол-во строк равное row

tableWidget->setColumnCount(column);//Устанавливаем кол-во столбцов равное column

if(row!=n&&column!=n){

QMessageBox::information(this,"Ошибка","Количество пунктов не соответствует сохраненным данным");

return;

}

for(inti=0;i<row;++i)//циклприi=0,покаi<row,i увеличивается на единицу

for(intj=0;j<column;j++)//циклприj=0,покаj<row,j увеличивается на единицу

tableWidget->item(i,j)->read(stream);//Устанавливаем значения ячеек

file.close();//Закрываем файл

}//Конец условия

tableWidget->repaint();

}

voidMainWindow::on_pushButton_6_clicked()

{

listwidget=newQListWidget(this);

inti,kk=0,mm=0,ln,ll,j,imin=0,e;

intsum=0,min=0;

boolflag=0;//признак повтора

intLL[NUMBER];//массив верш информируемого прохода

intA[SIZE],B[SIZE],G[SIZE];

ln=ui->lineEdit->text().toInt();

e=ui->lineEdit_2->text().toInt();

for(i=1;i<=n;i++){

A[kk]=i;

for(j=1;j<=n;j++){

if(tableWidget->item(i-1,j-1)->text().toInt()!=0){

B[kk]=j;

G[kk]=tableWidget->item(i-1,j-1)->text().toInt();

kk++;

A[kk]=i;

}

}

}

for(i=0;i<=SIZE-1;i++){

LL[i]=0;//начальные присвоения

}

LL[0]=ln;

//поиск ll -индекса в массивах (вершины начала пути)

while(mm!=NUMBER-1)

{

for(i=0;i<=SIZE-1;i++)

if(A[i]==ln)//вершина найдена

{

ll=i;//запоминание номера столбца

break;

}

min=1000;//максимальный вес

kk=0;

//поиск числа вариантов прохода из точки l l

for(i=ll;i<=SIZE-1;i++){

if(A[i]==ln){

kk++;//подсчет числа вариантов

}

}

//cout<<"\nk="<<k;

//поиск ребра с минимальным весом

for(i=ll;i<ll+kk;i++)

{

if(G[i]<min)

{

for(j=0;j<=mm;j++){

if(B[i]==LL[j]){

flag=1;

}

}

//вершина уже есть в LL[]

if(flag==0)

{

min=G[i];

imin=i;

}

}

flag=0;

}

mm++;//индекс вершины в пути LL[]

LL[mm]=B[imin];

//if(LL[mm]==e)break;

sum+=G[imin];

ln=B[imin];//новая вершина продолжения пути

if(LL[mm]==e){

break;

}

}//возвратвцикл

otchet*ot=newotchet(listwidget,0);

newQListWidgetItem(tr("Result:"),listwidget);

for(i=0;i<=mm;i++){

newQListWidgetItem(QString::number(LL[i]),listwidget);

}

newQListWidgetItem(tr("summa"),listwidget);

newQListWidgetItem(QString::number(sum),listwidget);

ot->show();

//ui->horizontalLayout_2->addWidget(listwidget);

}

Приложение Б

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ» (СГАСУ)

«УТВЕРЖДАЮ»

Зав. кафедрой ИРОСТ

__________ С.А. Пиявский

«____»___________2016 г.

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

Руководство пользователя

ЛИСТ УТВЕРЖДЕНИЯ

02068389.40100.009.И3.01.1-1 ЛУ

Листов 1

Руководитель разработки:

__________ Прохорова О.В.

Разработчик:

Студент группы ГИП-112

__________Терентьев Д.А.

Самара 2016

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙУНИВЕРСИТЕТ» (СГАСУ)

УТВЕРЖДЕНО

02068389.40100.009.И3.01.1-1 ЛУ

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

Руководство пользователя

02068389.40100.009.И3.01.1-1

Листов 11

Б.1 Введение

Б.1.1. Область применения

Требования настоящего документа применяются при:

- предварительных комплексных испытаниях;

- опытной эксплуатации;

- промышленной эксплуатации.

Б.1.2. Краткое описание возможностей

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

Б.1.3. Уровень подготовки пользователя

Пользователь автоматизированная системапоиска оптимального маршрута на транспортной сети должен иметь опыт работы с ОС MS Windows (7/8/10), а также обладать следующими знаниями:

- знать основы соответствующей предметной области;

- понимать основы методов оптимизации;

- знать и иметь навыки работы с приложениями калькуляторами.

Квалификация пользователя должна позволять:

- заполнить матрицу стоимостей на основе собственных данных;

Б.2 Автоматизированная система поиска оптимального маршрута на транспортной сети

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

Б.3 Подготовка к работе

Б.3.1. Состав и содержание дистрибутивного носителя данных

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

- deikstra.exe (Исполняемый файл);

- Установленные Qt Creator;

Б.3.2. Порядок загрузки данных и программ:

1. Необходимо зайти на сайт

2. Нажать на кнопку «Скачать» и дождаться загрузки файла «debug.rar»;

3. Разархивировать файл «debug.rar»;

Б.3.3. Порядок проверки работоспособности

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

Открыть файлdeikstra.exe, находящий в разархивированной папке.

Если программа успешно запустилась можно начинать работу.

Если появилось окно с ошибкой следует обратиться в службу технической поддержки.

Б.4. Описание операций

Б.4.1. Выполняемые функции и задачи

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

Таблица Б.1 - Функции и задачи

Б.4.2. Описание операций технологического процесса обработки данных, необходимых для выполнения задач.

Ниже приведено описание пользовательских операций для выполнения каждой из задач.

Задача: «Ввод начальных данных»

Операция 1: Запуск автоматизированной системы поиска оптимального маршрута на транспортной сети

Условия, при соблюдении которых возможно выполнение операции:

автоматизированной системой поиска оптимального маршрута на транспортной сети функционирует в автономном режиме.

Подготовительные действия:

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

Основные действия в требуемой последовательности:

На файле «deikstra.exe» произвести двойной щелчок левой кнопкой мышки.

Заключительные действия:

Не требуются.

Ресурсы, расходуемые на операцию:

2-10 секунд.

Операция 2: Ввод начальных данных

Условия, при соблюдении которых возможно выполнение операции:

Успешный запуск приложения.

Подготовительные действия:

Не требуются.

Основные действия в требуемой последовательности:

В окне авторизации необходимо заполнить поля «логин» и «пароль» и нажать кнопку «Вход» как показано на рисунке Б.1:

При успешном входе открывается главное окно работы программы, в котором необходимо ввести количество пунктов в соответствующее поле и нажать кнопку «ОК» (рисунок Б.2):

После этого необходимо заполнить появившуюся матрицу стоимостей, либо загрузить ранее использованную матрицу стоимостей, нажав кнопку «Загрузить» (рисунок Б.3), (рисунок Б.4):

Рисунок Б.1 -- Авторизация пользователя

Рисунок Б.2 -- Ввод количества пунктов

Рисунок Б.3 -- Загрузка ранее использованной матрицы стоимостей

Рисунок Б.4 -- Заполненная матрица стоимостей