Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Построить алгоритм решения задачи  [new]
Jaffar
Member

Откуда:
Сообщений: 633
Добрый день.
Прошу помочь построить алгоритм решения задачи.

Распределение инкассаторов по маршрутам.

1.Есть некоторый набор маршрутов, который характеризуется временем(в часах).
Напр.
Маршрут № 1 - 13,5 часов
Маршрут № 2 - 12,5 часов
Маршрут № 3 - 12,0 часов
Маршрут № 4 - 10,0 часов
Маршрут № 5 - 7,25 часов
и т.д.....


2.Есть распределение маршрутов по дням недели.
т.е. для каждого дня недели есть свой набор маршрутов
Напр.
Пн 1, 2, 3
Вт 1, 2, 4
......
Сб 6, 9 и т.д.....

3.Есть набор инкассаторов, которые ездиют по маршрутам.
Один инкассатор может в день выйти только на 1 маршрут.
Все кто не задействованны на маршрутах - выходные(отдыхают).

Необходимо таким образом построить график выходов на маршруты, чтобы соблюдались следующие условия(в порядке приоритетности):
1.Чтобы между инкассаторами в мес. была мин. разница в кол-ве смен и часов
Например:(кол-во раб. смен может отличаться на 1 и кол-во часов не более чем на 10 часов) - или макс. приближенное к этому исходя из первичных условий.
2.Чтобы было макс. возможное кол-во спаренных выходных.
При этом условие № 1 имеет более высокий приоритет чем 2.

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

И запращивает оптимальное распределение на период(месяц).

В итоге должна получиться такая таблица.
дни месяца 1 2 3 4 5 6 7 8 9 10 .... ИТОГО | ИТОГО
дни недели пн вт ср чт пт сб вс пн вт ср .... СМЕН | ЧАСОВ
-----------------------------------------------------------------
1.Инкассатор № 1 |
2.Инкассатор № 2 |
3.Инкассатор № 3 |
4.Инкассатор № 4 |
5.Инкассатор № 5 |
6.Инкассатор № 6 |


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

Пробовал вертеть и так и эдак - результат не получаетя приемлемым:
Не удалсь построить алгоритм котоый приводит к результату.
Хотя пользовтаели руками строят(фактически они занимаются перебором)

Хотелсь бы понять :
1.как класс таких задач называется в математике, к чему его можно свести - чтобы можно было почитать теорию на этот счет.
2.Думал над нейронными сетями - но тут нет достаточного кол-ва данных для обучения.
3.Проблема не в том чтобы запрограммировать - а в том чтобы придумать сам алгоритм который приводит к решению.
6 июн 14, 11:50    [16131165]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
iap
Member

Откуда: Москва
Сообщений: 47052
Jaffar
ездиют
Дальше не читал
6 июн 14, 11:54    [16131200]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
Maxx
Member [скрыт]

Откуда:
Сообщений: 24290
Jaffar ,ваще похоже на обход графа... или задачу с рюкзаком.
НО для того,чтоб все вот прониклись - надо исходные условия в виде таблицы и скрипта ее заполнения и желаемы результат. Сочинять за вас ваши исходные условия для такой задачи - имхо,всем будет влом..слишком много времени тратиться на ето.
6 июн 14, 11:58    [16131241]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4805
Сделай в лоб, сгенерируй здоровый календарь-табель по часам или даже по 10 минут. Разверни маршруты по часам и получи здоровую матрицу -- календарь по одной оси маршруты по другой. Далее на матрицу накладывай кондукторов и аггрегатными функциями или аналитическими функциями просчитывай, насколько они пересекаются. Лучше наверное это визуализировать и дать диспетчерам на просмотр.

Почитай про аналитические функции SUM() OVER(), LAG() LEAD(), RANK() DENASE_RANK()
6 июн 14, 12:02    [16131267]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8353
Судя по тому, что количество информации небольшое, можно попробовать решить "в лоб", т.е. составить таблицу со всеми комбинациями маршрутов и сотрудников и выбрать из кучи по заданным условиям. Задача все же не "рюкзачная", т.к. расчет идет индивидуально для сотрудника.
6 июн 14, 12:39    [16131590]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
Jaffar
Member

Откуда:
Сообщений: 633
iap
Jaffar
ездиют
Дальше не читал


а дальше ничего интересно и нет...
6 июн 14, 13:27    [16132121]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
Jaffar
Member

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



да я не прошу писать за меня код....
я бы хотел классифицировать задачу и дальше понять какие методы решения для них применять.
6 июн 14, 13:30    [16132161]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
iap
Member

Откуда: Москва
Сообщений: 47052
Jaffar
iap
пропущено...
Дальше не читал


а дальше ничего интересно и нет...
Без обид.
Слишком большая задача, в которую надо долго вникать.
Вот просто бросить всё сейчас и - вникать
6 июн 14, 13:33    [16132196]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
aleks2
Guest
Алгоритмы требуют простоты.

1. Предполагаем, что с началом месяца "отработка" зануляется.
2. Начиная с первого дня месяца.
3. Для текущего дня месяца назначаем самый "долгий" маршрут "работающему" инкассатору с минимальной "отработкой" (если "отработка" равная, то берем первого по списку) и так далее по всем маршрутам дня.
Кому маршрутов не хватило - выходной.
3. Пересчитываем "отработку" в соответствии с розданными маршрутами.
4. Переходим к следующему дню месяца и повторяем с п.3.
6 июн 14, 13:59    [16132467]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
Jaffar
Member

Откуда:
Сообщений: 633
Jaffar,

Про решение в лоб:

имеем в день примерно 6 маршрутов.
* 30 дней
сотрудников ~ 10
==> число вариантов расположить сотрудников в месяце будет примерно таким:

N = (10 ! )/(10 - 6) ! = 151 тыс.
и так в каждый день. => 151 тыс ^ 30
select power(10 * 9 * 8 * 7 * 6 * 5, 30) = ~ 2.4*10^156 вариантов - так что не катит.
6 июн 14, 14:13    [16132592]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
Jaffar
Member

Откуда:
Сообщений: 633
aleks2,

я так пробовал.
не получается

суть моего подхода была такова
сначала генерим все смены для каждого
6 июн 14, 14:17    [16132624]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4805
Jaffar
Jaffar,

Про решение в лоб:

имеем в день примерно 6 маршрутов.
* 30 дней
сотрудников ~ 10
==> число вариантов расположить сотрудников в месяце будет примерно таким:

N = (10 ! )/(10 - 6) ! = 151 тыс.
и так в каждый день. => 151 тыс ^ 30
select power(10 * 9 * 8 * 7 * 6 * 5, 30) = ~ 2.4*10^156 вариантов - так что не катит.


Чего-то у вас тут намудрено с комбинаторикой. Матрица 150 000 на 100 не такой большой объем.
6 июн 14, 14:43    [16132861]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
aleks2
Guest
Jaffar
aleks2,

я так пробовал.
не получается

суть моего подхода была такова
сначала генерим все смены для каждого


И чего "ниполучаецца"?

ЗЫ. Суть своего подхода - засунь себе в задницу.
7 июн 14, 05:52    [16136235]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
SSn888
Member

Откуда:
Сообщений: 340
Jaffar,

1. Блин, ну Вы же не новичок на форуме.. Что за "вырвиглаз" на старте темы?

2. ИМХО - все же ветка не та выбрана в форуме. Тут скорей "Программирование"

3. Гугл... "travelling salesman genetic" , "задача китайского почтальона", "задача Эйлера" (она же "7 мостов Кениксберга")
Не совсем 100% что надо, но может - подкинет идеи

4. https://www.sql.ru/forum/45505/optimizaciya-sostavlenie-marshruta-dvizheniya-avtotransporta

5. Что же касается "нужна именно математика" - ну так и задайте вопрос на форуме спецов в этой области :)
http://mathhelpplanet.com/viewforum.php?f=62 , к примеру
7 июн 14, 13:48    [16136634]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
Paul Chabinsky
Member

Откуда:
Сообщений: 322
Jaffar,

Может вам не усложнять? Создать и заполнить на некий период данными календарь посещения маршрутов и календарь выхода на работу сотрудников.
Тогда вы сможете одним запросом в рамках совпадения даты исполнения маршрута и даты выхода сотрудника подобрать более менее оптимальный план работы.
При этом вы можете сделать редактирование и одного и второго календаря, после чего запускать перерасчет.
8 июн 14, 22:55    [16139667]     Ответить | Цитировать Сообщить модератору
 Re: Построить алгоритм решения задачи  [new]
aleks2
Guest
Paul Chabinsky
Может вам не усложнять? Создать и заполнить на некий период данными календарь посещения маршрутов и календарь выхода на работу сотрудников.
Тогда вы сможете одним запросом в рамках совпадения даты исполнения маршрута и даты выхода сотрудника подобрать более менее оптимальный план работы.
При этом вы можете сделать редактирование и одного и второго календаря, после чего запускать перерасчет.


Алгоритм, страдалец, это конечная последовательность действий, детерминированно приводящая к результату.

Если ты перечитаешь "мутный поток твоего сознания", то ты, возможно, поймешь - это не алгоритм. Это бред.
9 июн 14, 06:31    [16140059]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить