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

Question

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

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

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

Любая помощь приветствуется.

Answer 1

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

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