РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ РАБОТЫ СЛУЖБЫ ДОСТАВКИ

Введение

На сегодняшний день широко распространены различные службы доставки. Их работу можно смоделировать при помощи теории графов. Курьеру необходимо быстро и грамотно спланировать свой маршрут, чтобы доставить товар в срок. Современные вычислительные машины, обладающие высоким быстродействием, могут ему в этом помочь.

Постановка проблемы

Зная необходимую информацию о маршрутах ( время в пути или расстояние между пунктами ), можно найти маршрут с наименьшими издержками. Поэтому цель нашей работы – написать программу, определяющую оптимальный маршрут доставки и его длину при заданных пунктах для посещения.

Общие сведения об алгоритме Дейкстры

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

- необходимо присвоить метку каждой вершине графа. Метка будет означать наименьшее расстояние от данной вершины до исходной.

- на каждом шаге алгоритм пытается уменьшить метки «соседей» выбранной вершины.

-когда все вершины будут посещены, алгоритм прекратит свое выполнение.

Проверим работу алгоритма на примере данного графа:

Рисунок 1. Граф с пронумерованными вершинами.

Пусть необходимо найти кратчайшие расстояния от вершины 0 до всех остальных.

Интуитивно, в работе алгоритма нет ничего сложного. На первом шаге вершине 1 присвоится метка «5». На втором шаге вершине 2 присвоится метка «8». Присвоили метки вершинам, смежным с нулевой вершиной. Теперь перейдем в вершину 1, поскольку ей присвоена наименьшая метка.  Вершина 5 на третьем шаге получит метку «14» (5 + 9). А вершина 3 – метку «17» ( 5 + 12 ). Пятым шагом шестая вершина получает метку «10». У пятой же вершины метка «14» перезаписывается на метку «12», поскольку 12<14. Четвертая вершина тем временем получает метку «16». Заходим в вершину 6 и понимаем, что ничьих меток уменьшить не можем. Та же ситуация складывается и в вершинах 5, 4 и 3. Мы посетили все вершины, а значит им присвоены минимальные метки:

1 – 5, 2 – 8, 3 – 17, 4 – 16, 5 – 12, 6 – 10.

Принцип работы программы

Из предложенного списка адресов: "A",''B","C","D","E","G","H","I","J","K","L","M","N","O", - выбирается 4 нужных адреса.

Рисунок 2. Двумерный массив для заполнения

Далее составляется двумерный массив размерностью [5]X[5], т.к. в данном случае имеем 4 адреса доставки. Первый индекс массива обозначает пункт отбытия (дом "F"), а индексы массива со второго по пятый обозначают выбранные пункты доставки.

Данный массив заполняется кратчайшими расстояниями между пунктами назначения и пунктом отбытия с помощью алгоритма Дейкстры. Таким образом элемент массива с индексами [1][4] обозначает кратчайшее расстояние между пунктом отбытия и 3 пунктом назначения, а элемент массива с индексами [3][5] обозначает кратчайшее расстояние между 1 пунктом назначения и 4 пунктом назначения.

Далее из 4!=1*2*3*4=24 вариантов (N!, где N - количество пунктов назначения) выбирается последовательность пунктов назначения, при которой суммарное расстояние будет наименьшим.

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

Код программы

Реализация алгоритма Дейкстры на языке программирования С++. Среда разработки - C++Builder.

int TCorierDelivery::Dijkstra(int GR[V][V], int st, int ts, bool flag)

{

         int distance[V], count, index, i, u;

         bool visited[V];

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

                   distance[i] = INT_MAX;

                   visited[i] = false;

         }

         distance[st] = 0;

         for (count = 0; count < V; count++) {

                   int min = INT_MAX;

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

                            if (!visited[i] && distance[i] < min) {

                                      min = distance[i];

                                      index = i;

                            }

                   u = index;

                   visited[u] = true;

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

                            if (!visited[i] && GR[u][i] && distance[u] != INT_MAX && distance[u] + GR[u][i] < distance[i])

                                      distance[i] = distance[u] + GR[u][i];

         }

         if (flag) {

                   int ind = ts;

                   stack<int> ret;

                   while (ind != st) {

                            for (int j = 0; j < V; j++)

                                      if (GR[ind][j] && distance[ind] - GR[ind][j] == distance[j])

{

                                               ind = j;

                                               break;

                                      }

                            ret.push(ind);

                   }

                   while (!ret.empty()) {

                       if ((ret.top() + 1)==1) {Label2->Caption = Label2->Caption + "A ";}

                       if ((ret.top() + 1)==2) {Label2->Caption = Label2->Caption + "B ";}

                       if ((ret.top() + 1)==3) {Label2->Caption = Label2->Caption + "C ";}

                       if ((ret.top() + 1)==4) {Label2->Caption = Label2->Caption + "D ";}

                       if ((ret.top() + 1)==5) {Label2->Caption = Label2->Caption + "E ";}

                       if ((ret.top() + 1)==6) {Label2->Caption = Label2->Caption + "F ";}

                       if ((ret.top() + 1)==7) {Label2->Caption = Label2->Caption + "G ";}

                       if ((ret.top() + 1)==8) {Label2->Caption = Label2->Caption + "H ";}

                       if ((ret.top() + 1)==9) {Label2->Caption = Label2->Caption + "I ";}

                       if ((ret.top() + 1)==10) {Label2->Caption = Label2->Caption + "J ";}

                       if ((ret.top() + 1)==11) {Label2->Caption = Label2->Caption + "K ";}

                       if ((ret.top() + 1)==12) {Label2->Caption = Label2->Caption + "L ";}

                       if ((ret.top() + 1)==13) {Label2->Caption = Label2->Caption + "M";}

                       if ((ret.top() + 1)==14) {Label2->Caption = Label2->Caption + "N ";}

                       if ((ret.top() + 1)==15) {Label2->Caption = Label2->Caption + "O ";}

                            ret.pop();

                   }

         }

         return distance[ts];

}

Графический интерфейс и пояснения к программе

Рисунок 3. Графический интерфейс программы.

После запуска программы, на экране монитора вашего ПК появится данное рабочее поле программы.

На фоне находится условная карта (района, поселка, города), на которой отражены все адреса возможной доставки (дома), а так же дороги с подписанным расстоянием между домами.

В поле "Выбор адреса доставки" под пунктами "1","2","3","4" указываются названия домов из предложенного списка: "A", ''B","C","D","E","G","H","I","J","K","L","M","N","O". Дом "F" в списке отсутствует, т.к является пунктом отбытия (например: пиццерия, почта, ресторан и т.д.).

После выбора адресов доставки необходимо нажать кнопку "Рассчитать маршрут", и в окне вывода результата работы программы появится кратчайший маршрут (порядок обхода всех домов с учетом промежуточных), а также длина этого кратчайшего маршрута.

Пример работы программы

Пример №1

Рисунок 4. Пример работы программы №1.

Адресами доставки являются дома: "A","G","L","O". Для выбранных адресов самым коротким обходом будет маршрут: "F", "G", "F", "C", "B", "A", "L", "M", "N", "O". Длина всего маршрута составит 54 км.

Пример №2

Рисунок 5. Пример работы программы №2.

Адресами доставки являются дома: "D","E","K","I". Для выбранных адресов самым коротким обходом будет маршрут: "F", "E", "I", "E", "B", "C", "D", "G", "K". Длина всего маршрута составит 48 км.

Заключение

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

Список литературы:

1. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. – 178 с.

2. Харари Ф. Теория графов. М.: Мир, 1973. – 21 с.