Оптимизация Маршрутизации Героев (ОМГ)
 

Связь с другими VRP задачами

Следуя постановке и легенде соревнования, мы решаем VRPTW-подобную (Vehicle Routing Problem with Time Windows, маршрутизация транспортных средств с ограничениями по времени) задачу оптимизации: 

• В классическом VRP имеется депо и курьеры, которые развозят заказы в соответствие с матрицей расстояний. В нашем случае в роли депо выступает замок с таверной, в роли курьеров — герои, в роли заказов — водяные мельницы (они же водяные колеса, далее для простоты, будем писать просто мельница), и матрица очков хода (в роли матрицы расстояний/времени).
• В классическом VRPTW у заказов появляются временные окна, в рамках которых заказ должен быть доставлен. В дополнение к матрице расстояний добавляется матрица времени (и расчеты идут по ней), а также появляется дополнительный параметр времени обслуживания (время на вручение заказа). В нашем случае в роли временных окон выступают дни доступности мельниц, матрица очков хода в роли роли матрицы времени, и стоимость посещения ("захода") в очках хода. 
• В дополнение к классическому VRPTW, здесь используется “гетерогенный” парк курьеров. В нашем случае это означает, что у разных героев разный запас ежедневных очков хода. Для простоты считаем что этот ежедневный (восполняемый) запас очков хода у героя не меняется.
• В рамках геройской специфики, в задаче действует глобальный счетчик дней (очки хода восполняются на новый день). Есть "правила таверны" на строгую последовательность в найме героев. А также, в задаче действует правило "последнего шага" (ласт-мув). 

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

Данные и их обозначения

Сами данные, их описания и публичные решения доступны на странице “Данные”.

Для формулирования всех правил и условий, стоит задать рамку и описания самих данных:

1. data_heroes.csv — данные о героях. Всего героев можно нанять до 100 штук. Содержит столбцы hero_id (идентификатор героя, int от 1 до 100) и move_points (дневной запас очков хода, int от 1300 до 1900).
2. data_objects.csv — данные о золотоносных объектах (водяных мельницах). Всего мельниц 700 штук. Содержит столбцы object_id (идентификатор объекта, int от 1 до 700), day_open (день “появления” объекта когда он дает награду, int от 1 до 7), и reward (награда за посещение, int и в наших данных для всех равен 500).
3. dist_start.csv — данные о расстояниях от замка (депо) до каждой из мельниц (объектов/заказов) в очках хода. Содержит 700 строк и 2 столбца:  object_id (идентификатор объекта, int от 1 до 700) и dist_start (расстояние в очках хода, int). 
4. dist_objects.csv — данные о попарных расстояниях между каждой из мельниц в очках хода. Матрица 700 х 700 с header-ом, все значения целочисленные (int). 

Глобальные параметры для задачи:

• visit_cost = 100 — стоимость посещения мельницы в очках хода (аналогично времени обслуживания).
• hero_cost = 2500 — стоимость найма героя в таверне (используется для расчета метрики).

Условия, правила и ограничения на маршруты
 

VRP - совместимые условия

1. Все герои начинают в стартовом замке/таверне (депо)
- Расстояния от замка до каждой из мельниц определяется dist_start из dist_start.scv.
- Замок считается объектом 0 в маршруте. Его не требуется напрямую указывать в своих маршрутах.

2. Маршрутизация героев
- Все герои должны передвигаться исключительно по дискретному маршруту между замком и мельницами.
- Иные перемещения помимо заранее заданного списка мельниц (объектов) запрещены и не рассматриваются.

3. Уникальность посещений
- Каждую мельницу (объект) можно посетить не более одного раза за все дни маршрута всех героев.

4. Число героев 
- В отличие от оригинальной игры, вы можете использовать любое количество героев из data_heroes.csv, хоть  всех 100, с первого дня.

5. Увольнение героев
- Если вам понадобится избавиться от героя, это можно сделать, добавив в его маршрут объект 0 (он же замок/депо).
- Увольнение происходит моментально, с сжиганием всех остававшихся у героя очков хода.
- Уволенные герои уходят навсегда и больше не участвуют в игре.
- Увольнение опционально и в рамках базовой постановки не обязательно.

Тематические VRPTW условия

6. Глобальная смена дней
- Аналогично игре, счетчик дней глобален для всех задействованных героев. 
- В начале дня все герои полностью восполняют свои очки хода move_points. 
- День заканчивается в тот момент, когда каждый из героев исчерпал свои очки хода (будь то завершив путь “последним шагом”, “заночевав” перед ожидаемой мельницей,  будучи “уволенным”, либо оказавшись посреди пути к следующей мельнице). 
- Сами глобальные дни работают как временные окна в VRPTW задачах.

7. Очки хода героев
- У каждого героя есть свой запас очков хода move_points, у кого-то он больше, у кого-то меньше (медиана 1560). 
- В начале дня запас очков хода полностью восстанавливается. Изменения в восстанавливаемом числе очков хода (как посещения конюшен или водопоев) не предусмотрены. 
- В конце дня неиспользованные очки хода либо сгорают, либо используются в соответствие с условиями посещения “последним шагом” или приездом заранее. 

8. Путешествие героев
- Перемещение от одной мельницы к другой отнимает очки хода в соответствии с матрицей  расстояний dist_objects.csv.
- Если остающихся очков хода не хватает для достижения мельницы текущим днем, мы считаем что герой прошел ровно столько очков сколько у него оставалось в данный момент (и закончил свой ход с 0 остающимися очками хода). Недостающий остаток будет вычтен из путешествия до интересующей героя мельницы уже на следующий день.
- Подобный перенос очков хода с текущего дня на следующий работает автоматически. Изменение своего маршрута на полпути между объектами на старте следующего дня запрещено. 

VRPTW - совместимые условия

9. Стоимость посещения мельницы (объекта)
- При посещении мельницы, при условии что она уже появилась, всегда стоит ровно visit_cost = 100 очков хода.
- В рамках этой задачи действует специальное исключение (пункт 14) про правило “последнего шага”. Если у героя осталось хотя бы одно очко хода, но ему не хватает всех 100 очков для посещения, то мы считаем что посещение успешно состоялось и герой завершает ход с 0 очков хода.

10. Раннее прибытие к мельнице (объекту) и ожидание на месте
- Если герой прибыл к месту появления мельницы заранее (до ее day_open), он принудительно стоит на месте и ожидает появления мельницы.
- Пока герой ждёт, его оставшиеся очки хода сгорают. Это относится и к очкам хода за текущий день, и к очкам хода последующих дней, в случае если мельница появится не на следующий день, а через 1 или более. 
- То есть, герой “ночует”, стоя на месте ровно до наступления дня day_open.
- После ожидания, очки хода полностью восстанавливаются, с героя списываются visit_cost очков хода за посещение, и начисляется награда reward за успешное посещение мельницы. 

11. Своевременное прибытие к мельнице (объекту) 
- Если герой прибывает к мельнице вовремя (тем же днем что и day_open), то с него списывается visit_cost очков хода, начисляется награда reward, и герой отправляется дальше по своему маршруту к следующей мельнице. 

12. Позднее прибытие к мельнице (объекту) 
- Если герой прибывает к мельнице с опозданием (днём позднее чем day_open), то с него все равно списывается visit_cost очков хода, но награда не начисляется. Опоздавший герой герой отправляется дальше по своему маршруту. 
- Учитывая уникальность посещений (пункт 3), в общем маршруте всех героев данное посещение просто сожгло очки хода, хотя могло бы быть посещено другим героем вовремя. 

Специальные геройские условия

13. Последовательный найм геров ("правила таверны")
- Герои нанимаются по порядку, в последовательности их hero_id.
- Это значит, что если у вас пока есть только герой 1, и вы хотите вывести собирать золото героя 3, то вам все равно нужно нанять героя 2. Вы можете отправить героя 2 по своему маршруту, либо сразу же уволить его. Но чтобы нанять героя 3, вам все равно нужно потратить золото и на найм героя 2. 
- В рамках условностей, можно считать что все ваши нанятые герои стартуют в первый день, но покидают таверну ровно в день появления day_open их первой мельницы (не вылезают из таверны пока дорога не позовет). 
- Учитывая это правило, в итоговой метрике вашего собранного золота, достаточно знать максимальный идентификатор героя hero_id(так как вам все равно пришлось бы нанять всех предшествующих ему).
- Это условие реализует правила геройской таверны. Если вам встретилась “таверна мечты” с Уфретином и Стракером, вам все равно придется тратить золото.

14. Посещение "последним шагом" (на-ласт-мув)
- Если у героя осталось от 1 до 100 очков хода и посещение мельницы еще возможно (но на само посещение очков хода не хватает), то посещение считается успешным, а очков на конец хода остается ровно 0. 
- Ранее посещение мельниц (объектов) последним шагом умышленно запрещается. Мы считаем что мельница еще не появилась, поэтому и зайти в нее даже на последний шаг нельзя. 
- Это условие реализует геройскую механику с легендарными “на-ласт-мувы” действиями героев. 

15. Конец игровой недели и подведение итогов
- Игровая неделя заканчивается в конце седьмого дня.
- Все что будет происходить после не имеет значения, так как доступных мельниц после 7 дня больше нет. 
- Можно считать что все герои тоже исчезают, но это не имеет значения в рамках метрики задачи соревнования. 
- Как и в игре в Герои, на все-про-все (геройский VRPTW) ровно 1 неделя. 

Метрика и проверка решений

Официальная метрика соревнования называется VRPTW Score. Вы можете читать ее как Gold Score — сколько золота вам удастся собрать за игровую неделю, за вычетом суммарного золота, потраченного на найм героев. 

$$\text{VRPTW | Gold Score} =  \sum_{i=1}^\text{700} \text{reward}_i  \cdot \mathbf{1}_{ \text{on-time}_i} -  max(\text{hero_id}) \times 2500 $$

$$\text{Где:}$$

$$\text{reward}_{i} \text{ — награда за объект i (500)},$$

$$\text{on-time}_{i} \text{ — индикатор того, что мельница i была посещена в день ее появления day_open},$$

$$\text{hero_id} \text{ — идентификатор героя}.$$

Ограничение на маршруты (решения)

• В качестве решений принимаются .csv файлы с 2 столбцами: hero_id и object_id. 
• Можно использовать только те id, которые есть в предоставленных файлах. hero_id от 1 до 100, object_id от 1 до 700 (0 считаем за депо, его явно указывать в качестве первого объекта не нужно). Все строки с невалидными id удаляются. 
• Каждый object_id может использоваться ровно 1 раз. Все строки-дубликаты удаляются. 
• Порядок посещения object_id важен и является основой задачи. Осторожнее работайте с сортировкой строк. 
• В отличие от классического VRPTW, в ваших решениях разрешено игнорировать мельницы (аналог заказов). В большинстве реальных приложений это запрещается, но в рамках учебной геройской задачи здесь это разрешено.