Задача маршрутизации транспорта

1.

Задача маршрутизации
транспорта

2.

Расстояние между пунктами
транспортной сети
• расстояние по прямой
x1, y1 , x2 , y2
x1 x2 y1 y2
2
• Манхэттенская, или городская метрика
x1, y1 , x2 , y2 x1 x2 y1 y2
M1, M 2 x1 x2 y1 y2
q
q
1
q
2

3.

«Французская железнодорожная
метрика»
x y , x P y P
x P P y , x y

4.

Задача коммивояжера
• Имеется n городов.
• Расстояния между любой парой городов i и j
известны и составляют cij .
• Коммивояжер выезжает из какого-либо
города и должен посетить все города побывав
в каждом только один раз и вернуться в
исходный город.
• Ставится задача определить такую
последовательность объезда городов, или
маршрут, при которой суммарная длина
маршрута была бы минимальной.

5.

Математическая постановка задачи
• xij = 1, если коммивояжер переезжает из
города i в город j, и
• xij = 0, если коммивояжер не переезжает из
города i в город j.
m n
F cij xij
• Найти минимум
i 1 j 1
• При ограничениях
n
xij 1, j 1,...,n
i 1
n
xij 1, i 1,...,n
j 1
ui u j nxij n 1, ui 0 i , j 2, n

6.

7.

8.

Пример
• 4 →2

9.

• 7 → 4 →2

10.

• 7 →4 →2 →1

11.

• 3→7 →4 →2 →1

12.

• 6→ 3→7 →4 →2 →1

13.

• 5→ 6→ 3→7 →4 →2 →1

14.

Метод стеклоочистителя
• Воображаемым лучом, исходящим из точки 0
и постепенно вращающимся по (или против)
часовой стрелке, начинаем "стирать" с
координатного поля изображенные на нем
пункты.
• Как только сумма заказов "стертых" магазинов
достигнет вместимости транспортного
средства, фиксируем сектор, обслуживаемый
одним кольцевым маршрутом, и намечаем
путь объезда пунктов.

15.

Пример

16.

Пример
Грузоподъемность 1000 по часовой с 12
Грузоподъемность 1500 против часовой с 12

17.

Метод Кларка-Райта
• Вначале строится план, состоящий из маятниковых
маршрутов, для каждого из которых назначается
автомобиль минимальной грузоподъемности (каждый
автомобиль обслуживает пока одного потребителя).
• Затем маршруты объединяют в один развозочный
(сборный, сборно-развозочный), обеспечивающий
наибольшее сокращение затрат на перевозку.
• Процесс длится до тех пор, пока не останется ни одной
пары маршрутов, которые целесообразно объединить в
один из-за отсутствия снижения затрат или автомобиля
увеличенной грузоподъемности (учитываются и другие
ограничения).

18.

Расстояние по городской метрике
i
0
1
2
3
4
5
6
7
8
9
10
11
12
xi
yi
0
0
7
-4
3
-1
9
-2
-6
7
2
-4
9
2
5
5
-7
10
-3
-2
4
-8
12
2
7
-2
qi
450
400
400
200
150
450
250
200
450
300
475
550
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
0
12
9
10
11
12
4
10
15
14
6
16
4
12
0
11
16
13
10
16
14
13
12
14
4
12
9
11
0
19
8
21
9
3
24
13
3
15
13
10
16
19
0
21
10
10
20
5
20
16
20
6
11
13
8
21
0
23
13
11
26
5
11
13
15
12
10
21
10
23
0
12
22
7
22
18
10
8
4
16
9
10
13
12
0
10
15
18
6
20
4
10
14
3
20
11
22
10
0
25
16
4
18
14
15
13
24
5
26
7
15
25
0
25
21
17
11
14
12
13
20
5
22
18
16
25
0
16
12
14
6
14
3
16
11
18
6
4
21
16
0
18
10
16
4
15
20
13
10
20
18
17
12
18
0
16
4
12
13
6
15
8
4
14
11
14
10
16
0
Экономия
r Pj , Pl Pj , P0 P0 , Pl Pj , Pl

19.

Пример
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
9
14
10
4
20
4
0
8
4
• 0→1 →0 и 0→1 →0
• 0→ 1→11 →0 (450+475=925)
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4

20.

Пример
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
• 0→3→0 и 0→8 →0
• 0→ 3→8 →0 (400+200=600)
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4

21.

Пример
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
• 0→4→0 и 0→9 →0
• 0→ 4→9 →0 (450+200=650)
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4

22.

Пример
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
• 0→ 3→8 →0 и 0→5 →0
• 0→ 3→8 →5 →0 (600+150=750)
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4

23.

Пример
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
• 0→ 2 →0 и 0→7→0
• 0→ 2→7 →0 (400+250=650)
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4
925+750>
1500
925+650>
1500

24.

Пример
925+600>
1500
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
925+650>
1500
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4
• 0→ 2 → 7 → 0 и 0→4→ 9→ 0
• 0→ 7→2 → 4 → 9 → 0 (650+650=1300)

25.

Пример
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4
• 0→ 3→8 →5 →0 и 0→12→ 0
• 0→ 12→ 3→8 →5 →0 (750+550=1300)
1300+300
>1500

26.

Пример
2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
• 0→ 1→11 →0 и 0→10→ 0
• 0→ 10→ 1→11 →0 (925+300=1225)
12
4
0
8
0
8
4
0
8
4
0
4
1300+925
>1500

27.

2
1 450 10
2 400
3 400
4 200
5 150
6 450
7 250
8 200
9 450
10 300
11 475
12 550
3
6
0
4
10
12
0
5
14
0
12
0
Ответ
• 0→ 10→ 1→11 →0
• 0→ 12→ 3→8 →5 →0
• 0→ 7→2 → 4 → 9 → 0
• 0→ 6→ 0
6
0
4
4
2
4
7
8
16
0
10
0
4
8
14
0
20
0
20
4
0
9
14
10
4
20
4
0
8
4
10
4
12
0
6
0
4
12
0
4
11
24
10
6
14
18
0
8
14
18
4
12
4
0
8
0
8
4
0
8
4
0
4