Несколько исходных-множественных мест назначения

Question

У меня вопрос оптимизации.

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

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

Основная цель - свести к минимуму общее время опоздания всех транспортных средств, чтобы добраться до места назначения.

Идеи на пути к решению этого?

Answer 1

Это AINT полное решение, но я надеюсь, что обеспечит направление спуска:

я думаю, что вы должны использовать «Maximum Flow Problem»
на Flow-сети, как

1. Учитывая «п» число транспортных средств
2. определить S - источник
3. определить O1, O2, O3 ..., On - Происхождение транспортных средств. при условии происхождения является первым Пересечением в пути
4. определяют край S- (O1, O2, O3 ... О) - Capacity = 1 на каждое происхождение, равного общее количество автомобилей
5. определения E - Раковина
6. определить D1, D2, D3, ..., Dn - Направления
7. определяют край (D1, D2, D3, ..., Dn) -E - Емкость = 1 в пункт назначения
8. каждое пересечение, образованную двумя вершинами (дюйм) и (выкл.) с краевой крышкой = 1

Это поможет вам найти хороший маршрут для всех грузовиков, но будет av oid проходит через «использованное» пересечение вообще ...
Я думаю, что приращение указанной пропускной способности пересечения сразу после прохождения должно быть близко.