| Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
| Все форумы / Microsoft SQL Server |
  |
||
 Построить алгоритм решения задачи
|
|
|
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: Построить алгоритм решения задачи
|
|||
|
iap Member Откуда: Москва Сообщений: 47052 |
|
||
| 6 июн 14, 11:54 [16131200] Ответить | Цитировать Сообщить модератору | |||
| Re: Построить алгоритм решения задачи
|
|
|
Maxx Member [скрыт] Откуда: Сообщений: 24290 |
Jaffar ,ваще похоже на обход графа... или задачу с рюкзаком. НО для того,чтоб все вот прониклись - надо исходные условия в виде таблицы и скрипта ее заполнения и желаемы результат. Сочинять за вас ваши исходные условия для такой задачи - имхо,всем будет влом..слишком много времени тратиться на ето. |
| 6 июн 14, 11:58 [16131241] Ответить | Цитировать Сообщить модератору | |
| Re: Построить алгоритм решения задачи
|
|
|
a_voronin Member Откуда: Москва Сообщений: 4805 |
Сделай в лоб, сгенерируй здоровый календарь-табель по часам или даже по 10 минут. Разверни маршруты по часам и получи здоровую матрицу -- календарь по одной оси маршруты по другой. Далее на матрицу накладывай кондукторов и аггрегатными функциями или аналитическими функциями просчитывай, насколько они пересекаются. Лучше наверное это визуализировать и дать диспетчерам на просмотр. Почитай про аналитические функции SUM() OVER(), LAG() LEAD(), RANK() DENASE_RANK() |
| 6 июн 14, 12:02 [16131267] Ответить | Цитировать Сообщить модератору | |
| Re: Построить алгоритм решения задачи
|
|
|
Владислав Колосов Member Откуда: Сообщений: 8353 |
Судя по тому, что количество информации небольшое, можно попробовать решить "в лоб", т.е. составить таблицу со всеми комбинациями маршрутов и сотрудников и выбрать из кучи по заданным условиям. Задача все же не "рюкзачная", т.к. расчет идет индивидуально для сотрудника. |
| 6 июн 14, 12:39 [16131590] Ответить | Цитировать Сообщить модератору | |
 Re: Построить алгоритм решения задачи
|
|||||
|
Jaffar Member Откуда: Сообщений: 633 |
а дальше ничего интересно и нет... |
||||
| 6 июн 14, 13:27 [16132121] Ответить | Цитировать Сообщить модератору | |||||
| Re: Построить алгоритм решения задачи
|
|||
|
Jaffar Member Откуда: Сообщений: 633 |
да я не прошу писать за меня код.... я бы хотел классифицировать задачу и дальше понять какие методы решения для них применять. |
||
| 6 июн 14, 13:30 [16132161] Ответить | Цитировать Сообщить модератору | |||
| Re: Построить алгоритм решения задачи
|
|||||
|
iap Member Откуда: Москва Сообщений: 47052 |
Слишком большая задача, в которую надо долго вникать. Вот просто бросить всё сейчас и - вникать |
||||
| 6 июн 14, 13:33 [16132196] Ответить | Цитировать Сообщить модератору | |||||
| Re: Построить алгоритм решения задачи
|
|
|
aleks2
Guest |
Алгоритмы требуют простоты. 1. Предполагаем, что с началом месяца "отработка" зануляется. 2. Начиная с первого дня месяца. 3. Для текущего дня месяца назначаем самый "долгий" маршрут "работающему" инкассатору с минимальной "отработкой" (если "отработка" равная, то берем первого по списку) и так далее по всем маршрутам дня. Кому маршрутов не хватило - выходной. 3. Пересчитываем "отработку" в соответствии с розданными маршрутами. 4. Переходим к следующему дню месяца и повторяем с п.3. |
| 6 июн 14, 13:59 [16132467] Ответить | Цитировать Сообщить модератору | |
| Re: Построить алгоритм решения задачи
|
|
|
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: Построить алгоритм решения задачи
|
|
|
Jaffar Member Откуда: Сообщений: 633 |
aleks2, я так пробовал. не получается суть моего подхода была такова сначала генерим все смены для каждого |
| 6 июн 14, 14:17 [16132624] Ответить | Цитировать Сообщить модератору | |
| Re: Построить алгоритм решения задачи
|
|||
|
a_voronin Member Откуда: Москва Сообщений: 4805 |
Чего-то у вас тут намудрено с комбинаторикой. Матрица 150 000 на 100 не такой большой объем. |
||
| 6 июн 14, 14:43 [16132861] Ответить | Цитировать Сообщить модератору | |||
| Re: Построить алгоритм решения задачи
|
|||
|
aleks2
Guest |
И чего "ниполучаецца"? ЗЫ. Суть своего подхода - засунь себе в задницу. |
||
| 7 июн 14, 05:52 [16136235] Ответить | Цитировать Сообщить модератору | |||
| Re: Построить алгоритм решения задачи
|
|
|
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: Построить алгоритм решения задачи
|
|
|
Paul Chabinsky Member Откуда: Сообщений: 322 |
Jaffar, Может вам не усложнять? Создать и заполнить на некий период данными календарь посещения маршрутов и календарь выхода на работу сотрудников. Тогда вы сможете одним запросом в рамках совпадения даты исполнения маршрута и даты выхода сотрудника подобрать более менее оптимальный план работы. При этом вы можете сделать редактирование и одного и второго календаря, после чего запускать перерасчет. |
| 8 июн 14, 22:55 [16139667] Ответить | Цитировать Сообщить модератору | |
| Re: Построить алгоритм решения задачи
|
|||
|
aleks2
Guest |
Алгоритм, страдалец, это конечная последовательность действий, детерминированно приводящая к результату. Если ты перечитаешь "мутный поток твоего сознания", то ты, возможно, поймешь - это не алгоритм. Это бред. |
||
| 9 июн 14, 06:31 [16140059] Ответить | Цитировать Сообщить модератору | |||
| Все форумы / Microsoft SQL Server | |
|
x