2020-05-25
149
Организация работы отдела доставки интернет-товаров связана с решением задач рационального использования рабочего времени менеджеров-курьеров.
Доставка интернет-товаров клиентам осуществляется с вокзального комплекса с возвращением курьера обратно. Представим вокзальный комплекс и места доставки интернет-товаров клиентам в виде связаного неориентированного графа G с вершинами n. Каждому ребру сопоставлено некоторое число, выраженное временем доставки и называемое весом ребра.
Пусть n=7. Вершина 1 – Вокзальный комплекс, 2-7 – клиенты.
Таблица 4.1. Исходные данные о времени доставки между клиентами.
| Путь | t, ч | Путь | t, ч |
| 1-2 | 3 | 2-7 | 5 |
| 1-3 | 5 | 3-4 | 1 |
| 1-4 | 5 | 3-5 | 1 |
| 1-5 | 1 | 3-6 | 5 |
| 1-6 | 2 | 3-7 | 4 |
| 1-7 | 3 | 4-5 | 3 |
| 2-3 | 1 | 4-6 | 1 |
| 2-4 | 2 | 4-7 | 1 |
| 2-5 | 5 | 5-6 | 5 |
| 2-6 | 2 | 5-7 | 5 |
| 6-7 | 4 | ||
Перебор всех возможных вариантов маршрута можно избежать, применив алгоритм Краскала. По алгоритму Краскала – минимальный по времени маршрут курьера с возвращением на ВК будет:
- минимальный остов графа: 1-5-3-2-4-6-7-1
|
|
|
W(O)=1+1+1+2+1+4+3=13 ч.
Далее нам необходимо распределить маршруты по 3 курьерам поровну.
W(O1): 1-2-3-1 W1=3+1+5=9 ч.
W(O2): 1-5-4-1 W2=1+3+5=9 ч.
W(O3): 1-6-7-1 W3=2+4+3=9 ч.
