Использование теории графов в задаче маршрутизации транспортных средств

Question

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

Идея состоит в том, чтобы минимизировать время в пути транспортных средств из депо.

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

Любая помощь будет высоко ценится.

Answer 1

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

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