Ваша проблема имеет сложную динамику : новые рабочие места появляются постоянно; поездки и / или выполнение работ могут занять больше времени или меньше времени, чем ожидалось; количество активных работников может измениться из-за болезни; и т. д. Я думаю, что лучший подход к динамике обработки состоит в том, что каждый раз, когда приходит новая работа, сотрудник заканчивает работу или количество изменений активных сотрудников (и т. д.), программное обеспечение планирования перераспределяет каждая известная работа среди активных сотрудников и переопределяет их путь для всех назначенных им работ (на несколько дней вперед, если есть так много рабочих мест). И это должно быть сделано оптимальным способом (см. Ниже).
Теперь у нас есть более простая задача: распределить все рабочие места среди всех сотрудников и оптимально определить пути для них в данный момент времени . Программное обеспечение для планирования знает города, в которых находятся сотрудники, и где находятся незавершенные рабочие места, и может рассчитать оптимальный путь между любой парой этих городов. Под «оптимальным» я подразумеваю тот, который имеет минимальную стоимость, которая не всегда является самой короткой. Города и оптимальные пути между ними образуют взвешенный график: города - это узлы, пути - это ребра. Края имеют положительную стоимость (стоимость поездки) и узлы имеют отрицательную стоимость (доход после каждой работы в данном городе) .
Представьте, что у нас есть пересчитанный план , он отправлен сотрудникам, и они начинают его выполнять. Что они делают? У некоторых из них может быть незавершенная работа в их фактическом местоположении, некоторые из них поедут в следующий город, чтобы закончить работу там. Обратите внимание, что выполнение плана является непрерывным : в данный момент те сотрудники, которые работают на работе, генерируют отрицательные расходы, а те, кто путешествует, генерируют положительные затраты. Скорость, с которой каждый сотрудник генерирует стоимость, может быть легко рассчитана: для работающих сотрудников она составляет -[income after actual job] / [time required to complete the job], для путешествующих сотрудников - [cost of travel] / [travel time] (для более длинных планов периоды бездействия: ночи, выходные и праздничные дни также должны быть Учтено - это тоже генераторы затрат, вроде путешествий). В данный момент времени суммарный коэффициент генерации затрат (TCGR) является суммой коэффициента генерации затрат всех сотрудников. общая стоимость плана является интегральной величиной TCGR за общий промежуток времени плана (TTSP) . Я думаю, что наиболее разумной целью было бы минимизировать долю TCGR / TTSP, то есть найти план с минимальным средним TCGR (ATCGR) .
Как программное обеспечение для планирования должно определять план с минимальным ATCGR?
- Для каждого возможного плана программа может рассчитать ATCGR
легко, так что подход грубой силы , кажется, вариант.
К сожалению, у вас есть 25 сотрудников и 2000 ожидающих работы, что
означает, что существует слишком много возможностей найти оптимальный план
с грубой силой в разумные сроки.
- Другим простым вариантом является
жадный подход : при расчете ATCGR учитывайте только часть плана от начала плана до
момент первого перепланирования. Обратите внимание, что программное обеспечение будет пересчитать
планируйте каждый раз один из сотрудников заканчивает работу , поэтому в случае жадного подхода есть много
более короткие возможные планы и, следовательно, гораздо меньше возможностей. Я уверен, что жадное решение может быть найдено грубой силой.
- Я полагаю, что нет способа найти точное решение этой проблемы.
проблема, кроме подхода грубой силы, но применение грубой силы
сила невозможна (см. выше). Если вы не удовлетворены
жадный подход, и предпочел бы приблизительное решение
Вся проблема вместо того, чтобы вы могли разработать алгоритм, который
аналогичные приблизительные алгоритмы, разработанные для задача коммивояжера (TSP) . Это не легко, потому что у вас есть несколько «продавцов» для одного и того же набора городов.