Оптимизация сетки бронирования автопарка.

← →
Дмитрий С © (2015-07-29 21:20) [0]

Есть автопарк, который сдает автомобили в аренду.

Для каждого автомобиля задаются его параметры: Класс, Цвет, Размер багажника, ...

Есть сетка бронирования автопарка:
по-горизонтали - дни
по-вертикали - автомобили некого автопарка

При бронировании клиенты указывают:
- Класс автомобиля
- Дату "С" и дату "ПО"
а также пожелания:
- Конкретный автомобиль (например, если брал прошлый раз, или хочет продлить использование не меняя авто)
- Цвет автомобиля
- Размер багажника.
- Конкретная модель автомобиля.
- Одинаковый цвет с другим бронированием
- Одинаковая модель автомобиля с другим бронированием (например, если кто-то хочет взять в аренду два автомобиля одинаковой марки, но не важно какой именно).

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

Администратор может назначить любое пожелание клиента обязательным к исполнению.

В этой же сетке находятся записи об арендованных автомобилях. А также вывод автомобилей из эксплуатации, например, для прохождения ТО или ремонта.

Бронирования, аренды, ремонты автомобилей в сетке накладываться друг на друга не должны.

За каждое выполненное пожелание клиента парк получает определенное количество очков (зависит от пожелания, от клиента, от брони).

За каждое повышение класса автомобиля парк штрафуется на определенное количество очков. (например, когда клиента бронирует авто эконом класса, а получает премиум. Количество очков зависит от исходного класса и назначенного класса).

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

Парк "сферический в вакууме": 10000 автомобилей и бронирование на 2 года вперед. Поэтому процесс оптимизации должен быть таким, чтобы в него не вмешивался человек, а также чтобы с ним справлялся бытовой компьютер в реальном времени. Сетка оптимизируется при каждом изменении любой брони или при добавлении/удалении новой. Эти операции должны выполнятся не дольше 3х секунд.

Вопрос: Куда копать, что читать/изучать?

← →
Игорь Шевченко © (2015-07-29 21:22) [1]

> что читать/изучать?

программирование очевидно

> Куда копать

на сайты фрилансеров

← →
Pavia © (2015-07-29 21:23) [2]

Комбинаторику.

← →
кгшзх © (2015-07-29 21:46) [3]

а откуда такая сферическая классификация критериев заказа?

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

- "хочу зеленый и с багажником 650 литров"

вместо :

- октавия есть?
- есть.
- зарезервируйте!

← →
кгшзх © (2015-07-29 21:58) [4]

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

неа.

самая первая задача - сначала сделать эту сетку, чтобы не получить кратного бронирования одного и того же ресурса.

и вот тогда все клиенты получат свои автомобили.

← →
кгшзх © (2015-07-29 22:13) [5]

а вообще прикольный и парк и задачка.
10 киломашин, планы на джва года вперед, бытовой целерончик под столом ....

← →
Pavia © (2015-07-29 23:34) [6]

Удалено модератором
Примечание: Уважаем русский язык

← →
кгшзх © (2015-07-29 23:47) [7]

да не.
юмор был не про целерончик. он справится за глаза. я думаю справится даже рядовой смарт.

имелось ввиду почему бы не иметь парк в 9999 машин.
10к минус один логан, вместо которого был бы не целерон

← →
Slider007 © (2015-07-30 07:07) [8]

> За каждое повышение класса автомобиля парк штрафуется

А при понижении премируется? :)

Лет несколько назад возникала тут тема по поводу создания автоматизированного школьного/институтского расписания. Пришли к выводу, что в общем случае задача нерешаемая.
По моему данная задача очень похожа.

← →
кгшзх © (2015-07-30 08:31) [9]

да ладно.
как запрограммировать автономного курьесити лет на 10 вперед - так это можно.
а как автопарк так сразу и нельзя?

← →
Kerk © (2015-07-30 08:56) [10]

Задача составления расписания - это классика. Относится к классу NP-полных. То есть в общем случае решается только полным перебором. Но человечество не унывает и решает ее с помощью различных эвристик.

Вот по-моему прямо про проблему автора:

Другой пример—задача составления оптимального расписания работы агентов, обслуживающих клиентов. Обслуживание заключается в доставке (сборе) некоторых объектов или предоставлении услуг. Каждый объект может иметь несколько характеристик (например, массу, размер, стоимость и т. д.). Для каждого агента заданы начало и конец движения, интервал работы, ограничения на суммарные характеристики объектов. Для каждого клиента заданы интервал времени, в течение которого должна быть оказана услуга, время, затрачиваемое на оказание услуги, и характеристики объекта, который он хочет получить или отдать. Под расписанием будем понимать график работы каждого агента: выбор маршрутов движения и времени обслуживания. Графики должны быть составлены так, чтобы были обслужены все клиенты и выполнены ограничения по времени и характеристикам объектов.

http://mech.math.msu.su/~fpm/ps/k03/k031/k03114.pdf

← →
Sergey13 © (2015-07-30 08:58) [11]

>Задача: необходимо наилучшим образом оптимизировать сетку бронирования, так чтобы сдать все клиенты получили автомобили заказанного или выше класса, а также парк получил максимально возможное количество.

Это, ИМХО, надо выходить на самый верх и становиться обслуживающей организацией для бюджетных госслужб. Только так можно гарантировать, что бы было 10к клиентов на 10к машин. При этом конечно наверх уйдет Х очков.

Возможно как оптимизацию можно будет провести создание диспетчерской службы.

Так же задачу оптимизации можно упростить. Форд вроде заявлял, что автомобиль может быть любого цвета, при условии, что этот цвет - черный. Вот и тут - можно купить 10к серых Логанов.

← →
Юрий Зотов © (2015-07-30 09:20) [12]

> Куда копать, что читать/изучать?

Ключевые слова - целевая функция.

Сначала нужно понять, какие конкретно параметры мы хотим оптимизировать. Например, мы хотим максимизировать прибыль.

Потом нужно составить эту самую целевую функцию в виде уравнения или системы уравнений. Например:
Прибыль = F(x1, x2, ... xN)

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

Этот алгоритм вряд ли получится аналитическим (аналитическим он обычно получается только в очень простых задачах). Значит, нужно выбрать и применить необходимые численные методы.

И, наконец, написать программу, реализующую эти численные методы.

← →
Inovet © (2015-07-30 10:17) [13]

> [9] кгшзх © (30.07.15 08:31)
> автономного курьесити

Он разве автономный?

← →
кгшзх © (2015-07-30 10:27) [14]

Он разве автономный?

нет конечно.
унутри у него неонка, два здоровенных негра из джорджии, плюс команда обслуги из тамошних местных аборигенов.
и все его обслуживают.

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

← →
Inovet © (2015-07-30 11:31) [15]

> [14] кгшзх © (30.07.15 10:27)

Так ты и говорил про запрограммировать на 10 лет. Расписание и маршруты он сам себе всё же не составляет.

← →
han_malign © (2015-07-30 11:40) [16]

> алгоритм вряд ли получится аналитическим

- ключевые слова - "динамическое программирование".
На хабре много статей(про олимпиадные задачи) - с картинками...

← →
Дмитрий С © (2015-07-30 11:42) [17]

С учетом того, что в сетка должна работать уже "вчера" и с учетом изученного материала, я принял решение разбить задачу на три:

1. Подзадача размещения новой брони в сетке. Для этой подзадачи я уже придумал алгоритм.

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

3. Предварительная оптимизация всей сетки с целью удовлетворить максимальное количество клиентов как сейчас, так и в будущем.

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

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

← →
Kerk © (2015-07-30 12:35) [18]

> Дмитрий С © (30.07.15 11:42) [17]

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

← →
кгшзх © (2015-07-30 12:42) [19]

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

я седня пришел, и вы разместили мне бронь на 30 сентября на черный инфинити
я ушел.

постоянно работающий в фоне "эвалюционный или генетический алгоритм" работает

в понедельник он решает, что всем будет лучше, если треть сетки переколбасить.
мне при этом придется брать синюю теану и лучше не 30, а 29 сентября

вы обзваниваете всех кого коснулось и утрясаете вопрос

в понедельник (который после того первого понедельника) алгоритм снова решает, что надо переколбасить четверть сетки.
и мне достается красная камри.

вы обзваниваете всех кого коснулось и утрясаете вопрос .....

во вторник .....

← →
кгшзх © (2015-07-30 13:17) [20]

и потом как это эвалюционное чудо собирается оптимизировать (да еще с такими абстрактными критериями заказа)?

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

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

ваш чудо алгоритм поалгоритмил, и так как он видит что мне нужна была "чорная любая" решает что мне подойдет черный кольт в который холодильник не влезает

здесь как бы все скажут, что "так надо было сразу думать"
а я скажу: так если вы заморачиваетесь осчастливить как можно больше народу, то какого фига вы запускаете ваши алгоритмы оптимизации которые рушат планы и счастье заказчиков?

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

← →
Игорь Шевченко © (2015-07-30 13:30) [21]

> С учетом того, что в сетка должна работать уже "вчера" и
> с учетом изученного материала, я принял решение

Найти программиста, который это умеет писать без вывертов и дать ему денег. Это единственно правильное решение

← →
Сергей Суровцев © (2015-07-30 14:40) [22]

>Дмитрий С ©
>Задача: необходимо наилучшим образом оптимизировать сетку бронирования,
>так чтобы сдать все клиенты получили автомобили заказанного или выше
>класса, а также парк получил максимально возможное количество.

Что значит "оптимизировать"? По какому параметру? По цене авто? По прибыли с авто? По цвету авто? Что вообще можно оптимизировать если клиент выбрал авто конкретной марки на конкретную дату? Вопрос цены за услуги аренды вообще не стоит в задаче, почему?

>2. Постоянно работающий в фоне эвалюционный или генетический алгоритм для нахождения наиболее желаемого варианта размещения.

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

← →
Сергей Суровцев © (2015-07-30 15:05) [23]

>Игорь Шевченко © (30.07.15 13:30) [21]
>Найти программиста, который это умеет писать без вывертов и дать ему денег. Это единственно правильное решение

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

← →
Дмитрий С © (2015-07-30 15:20) [24]

> Сергей Суровцев © (30.07.15 14:40) [22]

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

← →
кгшзх © (2015-07-30 15:54) [25]

а также парк получил максимально возможное количество баллов.

в вопросе только парк и заказчик

а тут оказывается есть незримая третья сторона, которая "раздает баллы парку"

ЗЫ
нельзя программистам поручать автоматизацию. это слишком серьезное дело.

← →
кгшзх © (2015-07-30 16:24) [26]

За каждое повышение класса автомобиля парк штрафуется на определенное количество очков.

(например, когда клиента бронирует авто эконом класса, а получает премиум. Количество очков зависит от исходного класса и назначенного класса).

что это за муть ?
кем штрафуется?
что значит "бронировал эконом, а получил премиум" ?
это как?
это я прихожу за логаном, мне говорят что логана нет, ничего не хотим дальше слышать, Вы получите премиум!
А я : ну тогда вам штраф!!!

Или:
- мне нужен логан!
- вот вам логан!
- вот вам три штуки за аренду! И вот вам сто баллов за исполнение желаний!!!
- ой спасибо!

йомайо.
ну как можно с таким киселем в мозгах работать в ойти?

← →
Дмитрий С © (2015-07-30 16:35) [27]

Ответ на свой вопрос я уже получил. За что спасибо, принявшим участие.

Уважаемые критики, разрешите полюбопытствовать, как оценивают результаты ваших трудов ваши работодатели в денежном эквиваленте? А также, какого масштаба задачи решаете вы в своих трудах?

← →
Сергей Суровцев © (2015-07-30 17:05) [28]

>Дмитрий С © (30.07.15 15:20) [24]
>так чтобы сдать все клиенты

Для начала расшифруйте эту загадочную фразу.

>необходимо наилучшим образом оптимизировать сетку бронирования,

Повторяю вопрос, по какому параметру или параметрам?

От Вас и Вашего приложения никоим образом не зависит, какие авто будут наиболее востребованы. Что Вы собираетесь оптимизировать??? Наглядность?

>а также парк получил максимально возможное количество баллов.

Что за баллы? Как они начисляются и снимаются, за что и в каком количестве?

Замена оговоренной с клиентом модели на более дорогой класс может при нормальных условиях произойти ТОЛЬКО если заказанная модель повреждена в период между днем заказа и днем выполнения. Иначе при нормальной логике приложения клиент НЕ ДОЛЖЕН ИМЕТЬ ВОЗМОЖНОСТЬ заказать более дешевый класс если его на этот день НЕТ.

>Ответ на свой вопрос я уже получил.

Очень сомневаюсь. Скорее это кажется таковым на данном уровне понимания задачи.

у чувака талант генерации "интересных" вопросов

как оценивают результаты ваших трудов ваши работодатели в денежном эквиваленте?

Там это.... если не у "ИП сахарцова" трудишься, то в конторе есть всякие руководящие документы. Их много, и в том числе некоторые регулируют вопрос оценки в денежном эквиваленте

А также, какого масштаба задачи решаете вы в своих трудах?
масштаба своего предприятия (внезапно)

>кгшзх © (30.07.15 17:15) [29]
Возможно он имеет ввиду "в баллах"?

>Дмитрий С ©
Оптимизация относительно ручного учета этой задачи заключается в том, что ничего не будет забыто или упущено. И клиенту при нормальных условиях не будет предложен невыполнимый вариант. То есть в данном виде задачи автоматизация=оптимизация.

Возможно он имеет ввиду "в баллах"?

Возможно. Только для оценки в баллах тоже есть руководящие документы.

Оптимизация относительно ручного учета этой задачи

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

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

Это на службу такси похоже. Машины в лизинг, поэтому клиенту заказавшему "эконом" присылать "бизнес" - потеря денег. Баллы раздают клиенты. При этом клиенты фильтруют машины по критериям вроде "детское кресло, не курящий салон, оплата кредиткой" и хочется минимизировать простой.

Правда, количество не сходится. 10000 - это очень много. Что это вообще за автопарк такой?

В газете вон пишут, что на весь Нью-Йорк приходится только 13587 официальных желтых такси.

>Kerk © (30.07.15 17:47) [33]
>и хочется минимизировать простой.

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

Автопарк реально бешеный, 10000 это на всю страну минимум, в одном городе нереально. Плюс к этому если с таким автопаркам они ТАК подходят к реализации автоматизации своей деятельность, то это несерьезно по определению.

не.
вангую: "третий невидимый субъект" - такой же невладелец ресурса.
он ему вменен как и сама деятельность по управлению им.
просто потому что в его мотивации нет экономической состовляющей.
он вообще не субъект экономической деятельности.
в парке сидят менеджеры тачек, а раздающий баллы - это суперменеджер менеджеров тачек.

иначе бы "раздаватель баллов" не штрафовал "парк" за то что клиент хотел логан, а в итоге уехал на камри.

и значит все печально и ввязываться в такое не стоит.

автор декларирует цель оптимезеца как "все во имя клиента, все должны поехать"
на самом деле там за это выщемляют баллы.

недекларируемых целей мы не знаем.
экономических интересов ни у раздавателя ни у парка здесь нет.
что надо оптимизировать - не знают даже они.

точнее все знают, что надо сделать "чтобы всем было хорошо и чтобы в мире было меньше бездомных енотов"

чота ржу.
до меня дошло что это за проект и кто все эти люди

по порядку.
1. почему нужно чтобы "заработало вчера": об этом ниже. (гулить по "sarah connor")
2. почему так много машин: потому что в парламенте местного скопления галактик много депутатов
3. почему нет экономической логики: потому что денег нет вообще и действие происходит в см. п.1
4. Кто раздает баллы: спикер думы
5. "парк" - это аппарат спикера и управделами
6. почему штрафуют за камри вместо логана (сложный и интересный вопрос): потому что в далеком будущем склонность к роскоши, понтам и программированию на яве фиксят в момент зачатия нанохирургическим вмешательством на генном уровне. Иначе говоря если депутат заказал логан для служебной командировки на тау кита, то это значит, что для выполнения своей задачи ему хватает логана. Причем не "за глаза и за уши", а только "тютя-в-тютю". На калине туда уже просто не доехать. И давая ему камри вместо логана, "парк" нарушает принцип "от каждого по способностям каждому по потребностям"
7. Оптимизировать надо распределение ресурсов в постклассовом коммунистическом будущем.
7. Все это раскрылось после неосторожного вопроса подрядчика проекта "а масштабы-то какие у вас самих?"

Как видите, сходится абсолютно все, и никаких непоняток не остается.

Оптимизация сетки бронирования автопарка. Найти похожие ветки