Планирование heusristic для моего скаутского лагеря

Question

Я планирую лагерь для разведчиков и вам необходимо автоматизировать планирование.

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

Среди ограничений:

• Наличие палатки (они установлены и сняты с охраной в течение всего лета)
• Наличия разведчика
• Цветой палатки
• Цвета Предпочтение отдается разведчикам
• и др.

У меня более 500 разведчиков и около 20 палаток.

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

Любое предложение о том, на что я должен смотреть? Табу? Имитация отжига? Другие эвристики?

Answer 1

Хорошо, если вы говорите, что существует множество ограничений, то MILP будет лучшим способом для этого. Однако, если ограничения, о которых вы упомянули, являются единственными, то можно подумать о следующем подходе.

Моделируйте это как проблему транспортировки.

Сначала вы отфильтровываете недоступные палатки и недоступные скауты.

Для каждого цвета палатки вычислите общую емкость = суммирование (палатка) для каждой палатки цвета. Этими цветами являются пункты назначения.

Группируйте учеников в соответствии с их предпочтительным цветом для палаток. Это должны быть источники.

В матрице источника/назначения, поставить стоимость транспортировки студента предпочтительного цвета палатки нулю, и стоимость других цветов 1.

ИМО это может быть решена с помощью транспортной задачи, решая технику: http://www.me.utexas.edu/~jensen/models/network/net8.html

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

Answer 2

Это очень похоже на hospital bed planning (и распределение тюремной кровати и размещение гостиничных номеров в этом отношении). В основном, пациенты - разведчики, кровати - спальные мешки, а в комнатах палатки.Ищите реализаций INRC2011, таких как this one:

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