Расчет оптимального маршрута задачи коммивояжера методом ветвей и границ

Одесса – Констанца – Стамбул – Пиреи – Сочи – Одесса

Протяженность линии составляет:

S  = 179 + 201 + 360 + 868 + 448 = 2056 мили

 

                                                    

 

Рис 1. Ветвление матрицы

 

 

Разработка и расчет параметров схем движения пассажирских судов

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

1. Одесса -179- Констанца -201- Стамбул -360- Пиреи -868- Сочи -448- Одесса = 2056 мили

    

 

2. Одесса -179- Констанца -483- Сочи -513- Стамбул -360- Пиреи -702- Одесса = 2237 миль

 

Пассажиропоток

Порты	Констанца	Стамбул	Пиреи	Сочи	Одесса	Кол-во отправ-ленных пасса-жиров	Кол-во отправ-ленных порожних мест	Пассажиров на судне на момент выхода из порта

Одесса

215

132

24

95

266

732

56

732

Констанца

 

138

37

16

26

217

54

734

Стамбул

─

 

74

58

118

250

74

714

Пиреи

─

─

 

53

113

166

43

745

Сочи

─

─

─

 

212

212

53

735

Кол-во прибывших пассажиров

215

270

135

222

735

1577

 

 

Кол-во прибывших порожных мест

56

54

74

43

53

 

280

 

Пассажиров на судне на момент входа в порт

732

734

714

745

735

 

 

1857

 

Как видно из таблицы по схеме 1 порожние пассажирские места отправляются из порта Одесса (56 пас. мест), порта Констанца (54 пас. мест), порта Стамбул (74 пас. мест), порта Пиреи (43 пас. мест), порта Сочи (53 пас. мест). По результатам косой таблицы строится диаграмма пассажиропотоков.

	Одесса                     -                2056 мили 1577 пасс                      -           Одесса

Расчет показателей

1. Объем перевозок, пас.:

ΣN_п = ΣN_пас + ΣN_пор,

где ΣN_пас – количество перевезенных пассажиров;

             ΣN_пор – количество перевезенных порожних мест.

 

ΣN_п=[(215+132+24+95+266)+(138+37+16+26)+(74+58+118)+(53+113)

+(212)]+[56+54+74+43+53] = 1857 пас.

 

2. Грузооборот, пасс-миль:

ΣN_пl = ΣN_пli,

 где N_пli – грузооборот каждого i-го участка схемы линии.

 

ΣN_пl=732*179+734*201+714*360+745*868+735*448=1511542 п-миль.

 

3. Средняя дальность перевозки, миль:

l = ΣN_пl / ΣN_п

 

l = 1511542 / 1857 = 814 миль.

 

4. потребный тоннаж, пасс-мест:

ΣW_п = N_max,

где N_max – максимальный пассажиропоток,

 

ΣW_п = 745 пасс-мест.

 

5. Протяженность линии, миль:

L = Σl_i,

где l_i – протяженность каждого i-го участка схемы.

 

L = 179 + 201 + 360 + 868 + 448 = 2056 миль

 

6. Техническая работа:

Р_тех = ΣW_п ∙ L,

 

Р_тех = 745 * 2056 = 1531720

 

7. Коэффициент использования пассажировместимости судна:

α = ΣN_пl / Р_тех

 

α = 1511542 / 1531720 = 0,987

 

8. Коэффициент сменности

β = L / l,

 

β = 2056 / 814 = 2,53

 

Сведем все результаты в таблицу 6:

Таблица 6. Параметры линии

Параметры линии	Обозначения	Схема 1	Схема 2
Объем перевозок	ΣNп, пас.	1857	1857
Грузооборот	ΣNпl, пасс-миль	1511542	1640415
Средняя дальность перевозки	l, миль	814	883
Потребный тоннаж	ΣWп, пасс-мест	745	745
Протяженность линии	L, миль	2056	2237
Техническая работа	Ртех	1531720	1666565
Коэффициент использования пассажировместимости	α	0,987	0,984
Коэффициент сменности	β	2,53	2,53

 

В качестве расчетной принимаем схему движения, на которой получен минимум технической работы, то есть схему 1.

 

Финансовый результат

∆F=F-R_общ

∆F=312686,3-256351,1 =56335,2 $

 

 

Расчет оптимального маршрута задачи коммивояжера методом ветвей и границ

 

Имеется 5 портов, расстояния между которыми заданы в таблице 1 в виде C = c_ij, i, j =(1… n). В таблице 1 каждому порту назначен номер от 1 до 5.

 

Таблица 1. Расстояния между портами

Порты отхода	Порты захода
	Одесса(1)	Констанца(2)	Сочи(3)	Стамбул(4)	Пиреи(5)
Одесса(1)	∞	179	448	347	702
Констанца(2)	179	∞	483	201	557
Сочи(3)	448	483	∞	513	868
Стамбул(4)	347	201	513	∞	360
Пиреи(5)	702	557	868	360	∞

 

Учитывая, что каждое значение c_ij является расстоянием между портом отхода i и портом захода j, их величины не могут иметь отрицательного значения, поэтому c_ij 0.

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

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

;                                  (1)

                                                                                (2)

                                                             (3)

Xij                                      (4)

Матрица С называется приведенной, когда все ее элементы неотрицательные, а каждый рядок и столбец имеет хотя бы один ноль. Привидение матрицы может быть осуществлено следующим образом:

Шаг 1: Привидение по строкам. По каждой строке i  найдем наименьший элемент min  c_ij = a_i. Тогда при переходе к приведенной матрице с^’= c_ij  – a_i.  Данные заносим в таблицу 2.

 

 

Таблица 2. Матрица, приведенная по строкам

	1	2	3	4	5	ai
1	∞	179	448	347	702	179
2	179	∞	483	201	557	179
3	448	483	∞	513	868	448
4	347	201	513	∞	360	201
5	702	557	868	360	∞	360

 

Шаг 2: Привидение по столбцам. В каждом столбце j, который не имеет нулевых элементов, находим наименьшее значение c_ij = b_j, которое отображено в заключительной строке b_j  приведенной матрицы. Тогда    c ^’’ _ij = c ^’ _ij  – b_j  . Данные заносим в таблицу 3.

 

Таблица 3. Матрица, приведенная по рядам

	1	2	3	4	5
1	∞	0	269	168	523
2	0	∞	304	22	378
3	0	35	∞	65	420
4	146	0	312	∞	159
5	342	197	508	0	∞
bj	-	-	269	-	159

 

Далее составляем приведенную матрицу. Данные заносим в таблицу 4.

 

Таблица 4. Приведенная матрица G₀

	1	2	3	4	5	ai
1	∞	0-0	0-35	168	364	179
2	0-22	∞	35	22	219	179
3	0-35	35	∞	65	261	448
4	146	0-0	43	∞	0-219	201
5	342	197	239	0-219	∞	360
bj			269		159

 

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

На пересечении итоговой строки i и столбца j находится величина, которая называется – «сумма приводящих констант», которая равна:

S = 179 + 179 + 448 + 201 + 360 + 269 + 159 = 1795 миль.

Между величинами L и L’ существует следующее соотношение:

L = L’ + S

Таким образом, L≥S, что определяет S как нижнюю границу целевой функции задачи коммивояжера.

Находим степени каждого из нулей приведенной матрицы.

Клетка с max степенью нуля определит дугу, в соответствии с которой будет выполняться последующее ветвление.

Максимальная степень нуля равна 219 и соответствует клеткам (4-5) и (5-4). Выбираем клетку (4-5). Таким образом эта дуга является претендентом на включение в гамильтонов контур.

Разбиваем множество всех гамильтоновых контуров на два подмножества: G1 и G2.

 

Матрица G1 (исключение дуги 4,5)

	1	2	3	4	5
1	∞	0	0	168	364
2	0	∞	35	22	219
3	0	35	∞	65	261
4	146	0	43	∞	∞
5	342	197	239	0	∞

 

Матрица G2 (включение дуги 4,5)

	1	2	3	4
1	∞	0	0	168
2	0	∞	35	22
3	0	35	∞	65
5	342	197	239	∞

 

Приведенная матрица G1 (4,5)

	1	2	3	4	5	ai
1	∞	0	0	168	145	0
2	0	∞	35	22	0	0
3	0	35	∞	65	42	0
4	146	0	43	∞	∞	0
5	342	197	239	0	∞	0
bj	0	0	0	0	219

 

S = 1795 + 219 = 2014 мили

 

 

Приведенная матрица G2 (4,5)

	1	2	3	4	ai
1	∞	0-0	0-35	146	0
2	0-0	∞	35	0-43	0
3	0-35	35	∞	43	0
5	145	0-42	42	∞	197
bj	0	0	0	22

 

S = 1795 + 197 + 22 = 2014 мили

Для дальнейшего ветвления выбираем любую из приведенных таблиц G1 или G2, так как расстояния равны. Выбираем матрицу G2. Блокируем клетки (5-2), чтобы не образовался цикл.

 

Матрица G2.1 (2,4)

	1	2	3
1	∞	0	0
3	0	35	∞
5	145	∞	42

 

Матрица G2.2 (2,4)

	1	2	3	4
1	∞	0	0	146
2	0	∞	35	∞
3	0	35	∞	43
5	145	∞	42	∞

 

Приведенная матрица G2.1 (2,4)

	1	2	3	ai
1	∞	0-35	0-0	0
3	0-138	35	∞	0
5	103	∞	0-103	42
bj	0	0	0

 

S = 2014 + 42 = 2056 мили

 

Приведенная матрица G2.2 (2,4)

	1	2	3	4	ai
1	∞	0-0	0-35	103	0
2	0-35	∞	35	∞	0
3	0-0	35	∞	0-103	0
5	103	∞	0	∞	42
bj	0	0	0	43

 

S = 2014 + 43 + 42 = 2099 миль

Для дальнейшего ветвления выбираем матрицу G2.1, так как она имеет наименьшее расстояние.

 

Матрица G3.1 (3,1)

	2	3
1	0	∞
5	∞	0

 

S = 2056 + 0 = 2056 миль

Таким образом получили гамильтонов цикл 1-2-4-5-6-1.

Круизная линия: