Существующий алгоритм для задач планирования?

Question

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

• Каждый водитель не должен управлять более чем в пять раз в неделю
• Там должны быть два водителя за рулем каждый день
• Они будут отдыхать один день каждую неделю (не будет конфликтовать с днем ​​других водителей отдыха)

Какой алгоритм будет использоваться, чтобы решить проблему, как это?

Я просмотрел несколько сайтов, и я нашел это:

1) Backtracking algorithm (brute force) 
2) Genetic algorithm 
3) Constraint programming 

Честно говоря, все это «культурный шок» для меня, как я никогда не узнал, какой-либо линейного программирования в прошлом. Есть две вещи, которые я хочу знать:

1) Какой алгоритм лучше всего подходит для сценария выше?

2) Какой будет самый простой алгоритм для решения этой проблемы?

3) Пожалуйста, предложите любые другие алгоритмы, которые я могу изучить для решения вышеуказанной проблемы.

Answer 1

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

Теперь вернемся к сравнению:

1. Грубая сила: худшее.

2. Генетика: не может гарантировать оптимальность. Алгоритм, возможно, не сможет решить проблему.

3. Программирование ограничений: определенно лучшее в этом случае (и во многих дискретных задачах оптимизации). Существует суперэффективная реализация его в IBM ILOG CPLEX solver (но она не бесплатна, она бесплатна для академических кругов или для тестирования).

Answer 2

1) Я согласен, что грубая сила - это плохо.

2) Ваша проблема - целочисленная проблема. Однако они могут быть решены с помощью линейного программирования.

3) Вы можете отличить 2 разных подхода: эвристику и точные подходы. Эвристика обеспечивает хорошие решения в разумные сроки вычислений. Они используются, когда существуют строгие требования к времени вычисления или если проблема слишком сложна для расчета оптимального решения. Генетические алгоритмы являются эвристическими.

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

4) Стандартный способ решения этой проблемы заключается в том, чтобы встроить линейную программу в ветвь & Связанное дерево поиска.На нем много литературы. Процедура может быть представлена ​​следующим образом:

1. Решить линейную программу с симплекс-алгоритм
2. Найти дробную переменную для разветвления. То есть х = 1,5
3. Создание двух новых узлов и добавить ограничения х < = 1 и х> = 2 соответственно
4. идти в одном узле (выбирается некоторой стратегией)
5. Перейти к точке 1

Кроме того, на каждом узле дерева после точки 1 алгоритмы проверяют, можно ли обрезать узел. Это означает, что остановить поиск «глубже» от этого узла на, потому что

а) проблема стала неосуществимой,

б) лучшее решение уже существует,

с) целым решением найдено. Это объективное значение этого решения используется для определения точки b.

Процедура завершается, когда все узлы обрезаны.

К счастью, как заявил Николас, существуют бесплатные реализации, которые делают именно это. Все, что вам нужно сделать, это создать свою модель. Изложите его цель и ограничения в каком-то инструменте и разрешите его решить.