Логистика

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

Всем привет, меня зовут Алексей Савостин. Я занимаюсь направлением антифрода в Яндекс.Маркете и сегодня расскажу, как мы строили антифрод для маркетплейса Беру, который с октября стал частью Маркета. (...)

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

Расскажу подробнее о том, какие направления есть у фрода маркетплейса и какие источники убытков существуют.



Самое крупное направление реселлеры, дальше идут магазины конкурентов, пункты самовывоза и кардеры.

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

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

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

Резерв стоков. Были случаи, когда товары попадали в акцию с большой скидкой, реселлеры без оборотных средств делали закупки с разных аккаунтов, используя ПВЗ Маркетплейса либо партнеров как склады.

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

Недобросовестные конкуренты, которые хотят чаще попадать на карточку товара, могут отправить товар других поставщиков в Сибирь или на Дальний восток, а у нас и у наших партнеров есть ограниченное количество товаров на складе. Почему это так работает? Есть набор поставщиков, которые хотят продать свой товар на маркетплейсе. У каждого поставщика есть определенная цена, с которой он готов работать и выставляться в магазине. У кого-то цена может быть выше, у кого-то ниже из-за большого оборота этих товаров и запасов на складе.

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

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

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

Как ведут себя фродеры по этим трем направлениям? Практически все они ведут себя примерно схоже и пытаются спрятаться одинаково, за исключением реселлеров. Но реселлеры в нашем конкретном кейсе используют эмуляторы Android и вторые пространства Android, чтобы получить больше бонусов. Это скорее наш внутренний кейс. Чтобы получить бонус, надо скачать наше приложение. Фактически все остальные направления у всех видов фродеров одинаковые они пытаются регистрировать очень много новых аккаунтов, представляясь разными лицами; использовать VPN, режим инкогнито, вымышленные имена и адреса доставки.



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

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

Что мы делаем, чтобы противоборствовать фродерам?

Мы используем скоринг пользователей. В процессе скоринга мы собираем все данные об активности и те, которые нам доступны на момент создания аккаунта, проведения авторизации и всего остального. Склеиваем все эти данные и объединяем их в кластеры.



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

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

Как это выглядит на схеме:



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

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

Если это злонамеренные действия и мы определили фрод, возможно применение мер противодействия, таких как блокировка аккаунта и отмена заказов, которые созданы с нарушением правил сервиса и в будущем повлекут убытки для наших партнеров либо для маркетплейса.

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

В своем развитии антифрод может не только выступать как ограничитель, но и улучшить пользовательский опыт доверенным пользователям. Новые и не доверенные пользователи у нас совершают покупки с 3-D Secure, а те, кто уже совершал покупки, становятся доверенными, и мы для их заказов с известными историческими данными можем предоставлять больше инструментов лояльности. Например, давать возможность провести оплату без 3-D Secure для больших сумм. При этом мы не несем рисков при приходе кардеров.



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

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

Близость телефонных номеров и почтовых адресов. Фродеры часто используют одни и те же адреса, потому что эти ПВЗ для них удобны, они делают много заказов на один адрес либо на очень близкие. А так как товарные категории тоже будут близки, это можно достаточно просто обнаружить.

Как я уже сказал в предыдущем пункте, смотрите на всплески по редким товарам.

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

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

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

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

Это всё. Спасибо, что прочитали или прослушали мой доклад.

Всем привет, меня зовут Алексей Остриков, я руковожу разработкой в Яндекс.Маркете. Когда-то я много-много писал код, затем полтора года руководил группой бэкенда одного из сервисов Маркета, а сейчас отвечаю за разработку курьерской платформы Маркета.

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


На фото команда курьерской платформы десять месяцев назад. В те времена она помещалась в одной комнате. Сейчас нас стало в 5 раз больше.

Зачем мы всё это делали

Разрабатывая курьерскую платформу, мы хотели прокачать три главные вещи.

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

Второе прозрачность. Когда что-то идёт не так (происходят переносы, срывы сроков), то мы не знаем, почему они произошли. Мы не можем пойти и подсказать: Ребят, давайте делать вот так. Мы и сами не видим, и клиенту не можем показать какие-то дополнительные вещи. Например, что заказ приедет не к восьми, а в интервале 15 минут. А всё потому, что в процессе нет такого уровня прозрачности.

Третье деньги. Когда мы работаем с подрядчиком, есть договор, в котором прописаны суммы. И мы можем менять эти циферки в рамках договора. А когда мы отвечаем за весь процесс от а до я, то можно видеть, какие части системы спроектированы экономически невыгодно. И можно, например, поменять провайдера SMS или формат документооборота. Или можно заметить, что у курьеров слишком большие пробеги. И если строить маршруты кучнее, то в итоге получится развозить больше заказов. Благодаря этому можно ещё и сэкономить деньги доставка станет более эффективной.

Это и были те три цели, которые мы ставили во главу всего.

Как выглядит платформа

Давайте посмотрим, что у нас получилось.



На изображении показана схема процесса. У нас есть большие склады, на которых хранятся сотни тысяч заказов. С каждого склада вечером уезжают фуры, доверху набитые заказами. Там может быть 56 тысяч заказов. Эти фуры едут в здания поменьше, которые называются сортировочные центры. В них за несколько часов большая куча заказов превращается в маленькие кучки для курьеров. И когда с утра приезжают курьеры на машинах, то каждый курьер знает, что ему нужно забрать кучку вот с этим QR-кодом, загрузить себе в машину и поехать развозить.

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


Как это видит курьер

У курьеров есть приложение для Android, написанное на React Native. И в этом приложении они видят весь свой день. Они чётко понимают последовательность: на какой адрес ехать сначала, на какой потом. Когда позвонить клиенту, когда отвезти возвраты в сортировочный центр, как начать день, как закончить. Они всё видят в приложении и практически не задаются лишними вопросами. Мы им очень помогаем. По сути, они просто выполняют задания.



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

Кстати, про бэкенд. Мы в Маркете очень любим Java, в основном версию 11. И все бэкенд-сервисы, про которые пойдёт речь, написаны на Java.

Архитектура

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

Второй узел это сервис, который коммуницирует с внутренними сервисами Яндекса. Все сервисы это классические RESTful-сервисы со стандартной коммуникацией. Когда вы сделаете заказ на Маркете, через какое-то время к вам прилетит документ в JSON-формате, где будет всё написано: когда доставляем, кому доставляем, в какой интервал. И у нас это состояние сохранится в базу данных. Всё просто.

Помимо этого, второй узел также коммуницирует с другими внутренними сервисами, уже не Маркета, а Яндекса. Например, за уточнением геокоординат мы уходим в геосервис. Чтобы отправить push-уведомление, идём в сервис, который рассылает push и SMS. Для авторизации используем другой сервис. Для расчёта маршрутизации на завтра ещё один сервис. Таким образом осуществляется вся коммуникация с внутренними службами.

Этот узел также является входной точкой, у него есть API, в которую стучится наша админка. У неё есть свой endpoint, который называется, скажем, /partner. И наша админка, всё состояние системы, конфигурируется через коммуникацию с этим сервисом.

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

И в центре всего находится база данных, в которой, собственно, и хранится всё состояние. Все сервисы входят в одну базу данных.

Отказоустойчивость

У Яндекса есть несколько дата-центров, и наш сервис регионально распределен по трём дата-центрам. Как это выглядит.

База данных это три хоста, каждый в своём дата-центре. Один хост мастер, две другие реплики. В мастер мы пишем, с реплик читаем. Все другие Java-сервисы это также Java-процессы, которые крутятся в нескольких дата-центрах.

Один из узлов это наш API. Он крутится во всех трёх дата-центрах, потому что поток сообщений больше, чем из внутренних сервисов. Более того, такая схема позволяет вам довольно легко горизонтально масштабироваться.

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

Балансеру придётся просто делить трафик на большее количество точек, которые выполняют запросы. И у нас сейчас, например, не один узел, а по два узла в каждом дата-центре.

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

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

Все сервисы в Яндексе устроены схожим образом, мы все умеем переживать отказ одного из дата-центров. Как это реализовано, что такое graceful degradation и как сервисы в Яндексе переносят отключение одного из дата-центров, мы уже рассказывали.

Итак, это была архитектура. А теперь начинаются истории.

История первая про Яндекс.Ровер

Недавно у нас была Yet another Conference, там Роверу уделили много внимания. Я продолжу тему.

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

Яндекс.Ровер это маленький робот размером со среднюю собачку. Туда можно положить еду, пару коробок заказов, он поедет по городу и привезёт заказы без помощи человека. Там есть лидар, робот понимает своё положение в пространстве. Он умеет доставлять малогабаритные заказы.

И мы подумали: а почему бы и нет? Уточнили детали эксперимента: на тот момент нужно было проверить гипотезу, что людям это понравится. И мы решили довезти 50 заказов за полторы недели в очень лайтовом режиме.



Мы придумали максимально простой флоу, когда человеку приходит SMS с предложением нестандартного способа доставки не курьер привезёт, а Ровер. Весь эксперимент проходил во внутреннем дворе Яндекса. Человек выбирал подъезд, к которому Ровер подъедет. Когда робот приезжал открывалась крышка, клиент брал заказ, закрывал крышку, и Ровер уезжал за новым заказом. Всё просто.

Затем мы пришли к команде Ровера, чтобы договориться про API.

В API Ровера есть простые методы: открыть крышку, закрыть крышку, поехать в такую-то точку, получить состояние. Классика. Тоже JSON. Очень просто.

Что ещё очень важно: и такие маленькие истории, и любые большие истории лучше делать через featureflags. Фактически у вас есть рубильник, по которому вы можете в production включить эту историю. Когда она вам больше не нужна, эксперимент завершен успешно или не успешно, либо заметили какие-то баги, вы просто вырубаете её. И вам не нужно делать ещё один деплой новой версии кода на прод. Эта штука здорово облегчает жизнь.

Казалось бы, всё просто и всё должно работать. Там даже две недели нечего разрабатывать, можно за несколько дней сделать. Но посмотрите, где собака зарыта.

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

И в этот момент мы отправим SMS человеку, например, что Ровер ждёт на месте. Это невозможно сделать синхронно, и нужно как-то решить эту проблему.

Есть много разных подходов. Мы сделали максимально простой вариант.

Мы решили, что можно запустить самый обычный фоновый Java-тред либо задачу в Executer. Этот фоновый тред тут же запускается отслеживать процесс. И как только процесс выполнен, мы отправляем уведомление.



Выглядит это, например, так. Это практически копия кода с production, за исключением вырезанных комментариев. Но есть подвох. Нельзя делать таким образом серьёзные системы. Допустим, мы выкатываем новую версию на бэкенд. Хост перезагружается, состояние теряется, и всё, Ровер уезжает в бесконечность, его больше никто не видит.

Но почему? Если мы знаем, что наша цель доставить 50 заказов за полторы недели, мы сами выбираем время, когда следим за бэкендом. Если что-то пойдёт не так, можно вручную что-то изменить. Для такой задачи это решение более чем достаточное. И в этом кроется мораль первой истории.

Существуют ситуации, для которых нужно делать минимальную версию функционала. Не нужно огород городить и овер-инжинирить. Лучше делать максимально отчуждаемо. Так, чтобы не очень сильно изменять логику внутренних объектов. И избыточная сложность, ненужный технический долг не накапливались.

История вторая про базы данных

Но сначала несколько слов о том, как устроены основные сущности. Есть сервис Яндекс.Маршрутизация, который в конце дня строит маршруты курьерам.

Каждый маршрут состоит из точек на карте. И на каждой точке у курьеров есть задание. Это может быть задание выдать заказ, или позвонить клиенту, или с утра загрузиться на сортировочном центре, забрать все заказы.

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

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



Это очень аккуратная модель данных. Мы не придумали ни одной новой сущности, и сильно не схлопывали уже существующие.

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

Единственное излишество, которое мы сделали в самом начале создания платформы, такое. У нас был один вид заданий на доставку. Но мы поняли, что в будущем появятся другие задания. И мы заложили небольшую архитектурную гибкость: у нас есть задания, и одно из видов заданий доставка заказа.

Затем добавили трекинг и Ровер. Всего лишь по две таблички. В трекинге курьер отправляет свои координаты, мы их фиксируем в отдельной табличке. И есть трекинг заказа со своей моделью состояний, есть дополнительные штуки, типа SMS ушла / не ушла. Не стоит это добавлять прямо в задание. Лучше вынести в отдельную табличку, ведь этот трекинг нужен не для всех типов заданий.



В Ровере его координаты и доставка. У нас доставка Ровером это трекинг как бы для Ровера. Можно его добавить в трекинг заказа, но зачем? Ведь когда мы избавимся от этого эксперимента, когда он будет выключен, эти опции навсегда останутся в сущности трекинга. Там будут null-поля.

Может возникнуть вопрос: а зачем делать табличку с координатами? Один Ровер доставляет пять заказов в день. Не нужно хранить координаты в базе данных, можно просто ходить в API Ровера и получать их на runtime.

Суть в том, что так и было сделано изначально. Этой таблички не было, мы сразу ходили на сервис и всё это брали. Но во время тестов мы увидели, что много людей открывают карту с катящимся Ровером, и нагрузка на этот сервис кратно возрастает. Допустим, семь человек открыли. А там на страничке каждые две секунды Java Script запрашивает координаты. И коллеги нам писали в чат: Откуда такая нагрузка? У вас же там один человек должен кататься.

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

Эту историю можно было сделать с помощью 20 таблиц. Можно было использовать две таблицы: курьер и заказ. Но в первом случае это был бы over-engineering, а во втором случае это было бы слишком сложно поддерживать. Сложная логика, сложно тестировать.

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

Суть истории в том, что есть аспекты, которым лучше уделять дополнительное внимание. Первое особое внимание уделяйте структуре API и БД. Старайтесь замечать, какие у вас сущности есть в реальной жизни. Пытайтесь переложить эту структуру примерно таким же образом в цифровом виде. Старайтесь не сильно её сокращать, не сильно расширять.

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

1. дойти до всех клиентов, обеспечить обратную совместимость;
2. выкатить новый API, всех клиентов переключить на новый API;
3. выпилить старый код о клиентах, выпилить старый код на бэкенде.

Это очень затратно.

Ошибки в коде по сравнению с этим вообще ерунда. Код вы просто переписали, прогнали тесты. Тесты зелёные вы запушили в мастер. А вот API базы данных уделяйте особое внимание.

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



Есть один совет. Когда вы очень быстро разрабатываете что-то, в базе данных возникают неточности, иногда не хватает внешнего ключа или появляется дубль поля. Поэтому иногда, раз в два-три месяца, просто смотрите только на базу. Та же Intellij IDEA умеет генерировать классные схемы. И там это всё видно.

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

История третья про качество

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

Например, у нас есть один процесс, который крайне важен для платформы. Весь день мы набираем заказы на завтрашний день, но вечером срабатывает пометка, что после 22:00 мы не набираем заказы, а до 01:00 готовимся к завтрашнему дню. Потом начинается распределение заказов по сортировочным центрам. Мы идём в Яндекс.Маршрутизацию, она строит маршруты.

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

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

Мы понимали, что если процесс не завершится с десяти вечера до часу ночи, то сортировочные центры даже не будут знать, как им сортировать заказы, на какие кучки. Там будет всё простаивать. Курьеры выйдут позже, и у нас будут провалы по качеству.

Такие процессы лучше сразу делать максимально хорошо, продумывая каждый шаг, где может что-то пойти не так. И подкладывать везде максимальное количество соломки.

Расскажу про один из вариантов, как можно настроить такой процесс.

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



Например, день закончился, мы хотим рассчитать маршруты на завтра. Мы отправляем запрос в первую очередь: сформируй задание и запусти расчёт. Consumer забирает первое сообщение, идёт в сервис маршрутизации. Это асинхронный API. Consumer получает ответ, что задача взята в работу.

Он кладёт этот ID в базу, а в очередь с заданиями в обработке кладет новое задание. И всё. Из первой очереди сообщение исчезает, просыпается второй consumer. Он берёт второе задание на обработку, и его задача регулярно ходить в маршрутизацию и проверять, не выполнилась ли еще эта задачка на расчёт.

Задача уровня создай маршруты для 200 курьеров, которые развезут несколько тысяч заказов в Москве занимает от получаса до часа. Это действительно очень сложная задача. И ребята из этого сервиса очень крутые, они решают сложнейшую алгоритмическую задачу, которая требует большого количества времени.

В итоге consumer второй очереди будет просто проверять, проверять, проверять. Через какое-то время задача выполнится. Когда задача выполняется, мы получаем ответ в форме нужной структуры завтрашних маршрутов и смен для курьеров.

Мы кладём то, что рассчиталось, в третью очередь. Сообщение исчезает из второй очереди. И просыпается третий consumer, берёт этот контекст с сервиса Яндекс.Маршрутизация и на его основе создаёт state завтрашнего дня. Он создаёт задания курьеров, он создаёт заказы, создаёт смены. Это тоже немалая работа. Он тратит на это какое-то время. И когда всё создано, эта транзакция завершается и задание из очереди удаляется.

Если на любом участке этого процесса что-то идёт не так, сервер перезагружается. При последующем восстановлении мы просто увидим тот момент, на котором мы закончили. Допустим, прошла первая фаза и вторая. И перейдём к третьей.

С такой архитектурой последние месяцы у нас всё идёт довольно гладко, проблем нет. Но раньше был сплошной try-catch. Непонятно, где процесс сбоился, какие статусы поменяли в базе данных и так далее.

Есть вещи, на которых лучше не экономить. Есть вещи, с которыми вы сэкономите себе кучу нервных клеток, если сразу сделаете всё хорошо.

Что мы сделали в офлайне

Я описал большую часть того, что происходит на нашей платформе. Но кое-что осталось за кадром.

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

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

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

Когда у нас есть первая и вторая часть пазла, мы просто можем арендовать какое-то здание, нанять курьеров на машинах. Сказать им, как нажимать, что нажимать, как пикать, какую коробку куда класть, и всё. Благодаря этому мы уже запустились в семи городах, у нас больше десяти сортировочных центров.

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

Итоги

В начале я говорил, зачем мы начинали создавать собственную курьерскую платформу. Теперь расскажу, чего мы достигли. Это невероятно, но при использовании нашей платформы мы смогли приблизиться почти к 100% попадания в интервал. Например, за последнюю неделю качество доставляемости в Москве было порядка 9598%. Это значит, что в 9598% случаев мы не опаздываем. Мы укладываемся в интервал, который выбрал клиент. И мы даже не могли мечтать о такой точности, когда полагались исключительно на внешние службы доставки. Поэтому сейчас мы постепенно распространяем нашу платформу на все регионы. И будем улучшать доставляемость.

Мы получили нереальную прозрачность. Эта прозрачность нужна и нам. У нас всё логируется: все действия, весь процесс выдачи заказа. У нас есть возможность вернуться в историю на пять месяцев и сравнить какую-то метрику с текущей.

Но также мы дали эту прозрачность клиентам. Они видят, как к ним едет курьер. Они могут взаимодействовать с ним. Им не нужно звонить в службу поддержки, говорить: Где мой курьер?

Вдобавок получилось оптимизировать издержки, потому что у нас есть доступ ко всем элементам цепочки. В итоге сейчас довезти один заказ стоит на четверть дешевле, чем это было раньше, когда мы работали с внешними службами. Да, траты на доставку заказа уменьшились на 25%.

И если обобщать все идеи, о которых шла речь, можно выделить следующее.

Вы должны чётко понимать, на каком этапе развития находится ваш текущий сервис, ваш текущий проект. И если это состоявшийся бизнес, которым пользуются миллионы людей, которым пользуются, возможно, в нескольких странах, вы не можете всё делать на таком уровне, как с Ровером.

Но если у вас эксперимент Эксперимент отличается тем, что в любой момент, если мы не показываем обещанных результатов, нас могут закрыть. Не взлетело. И это нормально.

И в таком режиме мы находились около десяти месяцев. У нас были отчётные интервалы, каждые два месяца мы должны были показывать результат. И у нас всё получилось.

В таком режиме, мне кажется, вы не имеете права делать что-то, инвестируя в long-term и не получая ничего на короткой дистанции. Столь сильно закладываться на будущее в таком формате работы нельзя, потому что будущее может просто не наступить.

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

Если говорить коротко, постарайтесь делать максимально просто, но оставляя возможности для расширения.

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

И последнее. Я рассказывал про Ровер, что хорошо подобные процессы делать с помощью featureflags (фиче-флагов). Советую послушать доклад Марии Кузнецовой с митапа по Java. Она рассказывала, как устроены фиче-флаги в нашей системе и мониторинге.

В ноябре было объявлено о результатах клинических испытаний американо-германской вакцины от коронавируса, разработанной совместно компаниями Pfizer (США) и BioNTech (Германия). Она была признана эффективной в создании иммунитета от COVID-19 [недавно её одобрили соответствующие министерства Великобритании и Швейцарии / прим. пер.]. Эти новости на пике второй волны пандемии были восприняты с воодушевлением, а также стали основой для политического маневрирования.

Для нас интересен тот факт, что вакцину от Pfizer/BioNTech требуется хранить при чрезвычайно низких температурах перед введением. Давайте разберёмся в деталях проблемы подобного охлаждения.

Особые холодильники с температурой -80 C

Шрам, оставшийся у автора статьи после вакцинации от оспы. Современной молодёжи это не нужно, поскольку всеобщая вакцинация уничтожила это заболевание к 1980-му году

Данную вакцину необходимо хранить при температуре -80 C до момента непосредственного введения [российскую вакцину Спутник-V, массовое внедрение которой начато на этой неделе, нужно хранить при температуре -18 C / прим. пер.]. Для программы массовой вакцинации это представляет серьёзную проблему. В смысле производства холодильников, способных поддерживать температуру в -80 градусов, проблем нет однако их нечасто встретишь в медицинских организациях. Такие холодильники можно встретить в лабораториях и крупных госпиталях, однако даже в развитых странах терапевтам, которым придётся заниматься вакцинацией населения, до недавнего времени подобное оборудование просто не было нужно. Если такая проблема встречается даже в местах с обилием ресурсов, она окажется кратно сложнее в менее богатых регионах мира ведь для эффективной борьбы с пандемией крайне важно вакцинировать всю планету, чтобы не осталось мест, где инфекция сохранится.

Я не биолог, но в любом школьном курсе биологии преподают базовые основы того, как работают вакцины. В конце XVIII века доктор Эдвард Дженнер успешно сделал мальчику прививку коровьей оспы, чтобы у него появился иммунитет к оспе. На этой базе развилась иммунология. Почти все мы получали похожие вакцины, смысл которых, как упрощённо описывается в курсе биологии, основан на введении ослабленных или менее активных родственников возбудителей болезни. То, что убивавшие ранее людей заболевания сейчас остались лишь в фольклоре, свидетельствует об успешности этого метода.

Подобные уколы в моём Оксфордшире доктора ставят тысячами, и защищают целые поколения британских детей, обходясь при этом относительно стандартным холодильником. Что такого особенного в новой вакцине от Pfizer/BioNTech? Ответ кроется в схеме её работы: она не подвергает нас воздействию патогена; вместо этого это т.н. РНК-вакцина. В ней содержится фрагмент генетического материала вируса, который после введения проникает в наши клетки, вызывая иммунный ответ на коронавирус. Проблема заключается в хрупкости РНК для защиты её от деградации требуется чрезвычайно холодный холодильник.

Логистика криогенного транспорта последней мили

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

Следующий вопрос инженера очевиден: что такого особенного в холодильниках на -80 C? Мы чувствуем себя увереннее, рассуждая о принципах работы холодильника. Это тепловой насос с радиатором, расширительным клапаном и конденсатором, через который компрессором прокачивается хладагент. Конденсация хладагента вызывает охлаждение внутренностей холодильника, а изъятая таким образом энергия излучается радиатором как тепло. На разницу температур, которую можно получить при помощи такого насоса, существуют ограничения, поэтому у холодильников на -80 градусов есть два насоса, стоящих последовательно. Они менее эффективны и более дороги в производстве по сравнению с вашим домашним холодильником, однако их производство прекрасно налажено. Их просто не хватает там, где они нужны, поэтому интересно будет задуматься о последствиях этого факта.


Вероятно, импровизация в стиле Парка юрского периода тут не подходит

Можно подумать, что очевидным решением будет обеспечить всех врачей подходящими холодильниками на -80 градусов. С точки зрения обычных людей они не дёшевы (судя по информации из Google, их стоимость начинается от $10 000), но для правительств, разбрасывающих миллиарды долларов на борьбу с пандемией, это будет не так уж и дорого. Однако проблема состоит в цепочке поставок. Глобальный рынок для них был недостаточно большим во время, предшествовавшее пандемии, для того, чтобы производственные мощности могли справиться с неожиданно возросшим спросом. Маловероятно, что фабрики по производству домашних холодильников можно оборудовать для производства новых аппаратов в разумное время. Поэтому перспектива того, что новенький холодильник на -80 вдруг привезут к двери моего доктора, кажется слишком призрачной. Можно было бы ожидать, что подобные устройства реквизируют у их текущих владельцев, университетов и исследовательских лабораторий, однако тут встаёт другая проблема. Вакцины нужно вводить в пациентов, поэтому их нужно содержать в стерильности. Идея о том, чтобы взять холодильник из химической лаборатории, в котором кандидаты наук хранили токсичные металлоорганические составы, не кажется здравой в рамках необходимости уберегать пациентов от серьёзных рисков.

Ещё один вариант отказаться от холодильников в пользу пассивного охлаждения при помощи жидкого азота. Производственных мощностей для изготовления этого вещества в промышленных масштабах хватает, кроме того, оно уже широко используется в медицине. Загвоздка лишь в том, что оно используется в потребительских направлениях типа заморозки бородавок для их удаления, а не для перевозки и хранения лекарств. Для такого использования потребовалось бы создавать новую инфраструктуру с нуля. С коробками для перевозки замороженных веществ проблем нет. Но во-первых, могут возникнуть проблемы при внезапном появлении спроса на десятки тысяч их экземпляров. А во-вторых, они могут гарантировать низкую температуру перевозимого материала только пока азот не испарится полностью. Сами по себе они не заменят инфраструктуру из холодильников, поддерживающих температуру в -80, хотя и могут удлинить последний этап доставки.

Плюс истории в том, что вторая вакцина, которую разрабатывает Moderna, не требует глубокой заморозки и может храниться при температуре от 2 до 8 C до месяца. С её помощью можно будет добраться до дальних уголков мира, где нет инфраструктуры для глубокой заморозки. Но в краткосрочной перспективе нам потребуются оба варианта вакцины, причём столько доз, сколько получится произвести и доставить. Ведь для каждого жителя земли, которых уже почти 8 млрд, требуется по две дозы вакцины.

На примере действий американского правительства в течение нескольких месяцев мы, без сомнения, убедимся в том, что у неожиданной проблемы широкомасштабного внедрения криогенной вакцины нет волшебных решений. В Британии [где живёт автор / прим. перев.] наверняка появятся центры распространения вакцины в крупнейших госпиталях, где уже есть подобные холодильники. Оттуда каждое утро на места будут отправляться ежедневные партии вакцин. Но наша страна относительно маленькая, с плотно живущим населением. Её проблемы не сравнить с проблемами большой страны, где жители распределены по огромным территориям, и тем более с проблемами в некоторых развивающихся странах. Неожиданностью стало осознание того, что решение такой глобально важной задачи оказалось не только в руках учёных, создающих вакцины, но и в руках инженеров холодильных установок, отвечающих за безопасную доставку вакцин на место применения.

Всем привет, меня зовут Дмитрий Кузин (Application Development Senior Analyst в Accenture), и в своей статье я делюсь историей о том, как запрос на решение задачи в корпоративной рассылке привел к освоению Python библиотеки DOcplex от IBM, предназначенной для решения оптимизационных задач.

Я бы хотел поделиться личным опытом решения транспортной задачи с применением Python-библиотеки DOcplex от IBM. Если вкратце, то это задача про то, как с наименьшими затратами доставить продукцию или товары от производителей к покупателям, учитывая предложение первых и спрос вторых. В статье я дам основные определения транспортной задачи, покажу, как правильно сформулировать её условие, а также приведу пример решения на Python.


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

Что же за транспортная задача, и как её решать?



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

Транспортная задача это математическая задача по нахождению оптимального распределения поставок однородного товара (груза, вещества) между пунктами отправления и назначения при заданных, численно выраженных затратах (стоимостях, расходах) на перевозку.
В условиях современной рыночной экономики логистика основа успешного бизнеса.
Как производство товара или услуги, так и её реализация напрямую зависят от качества работы отдела логистики. Залогом успешной деятельности логиста на микро- и макроуровне является умение решать оптимизационные задачи, то есть найти наилучшее решение из всех допустимых [3].

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

Итак, условие задачи



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

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

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

Каждый покупатель приобретает фиксированное количество продукта каждый месяц. Примем, что покупатель гарантированно меняет поставщика, если ему предлагается цена на ниже той, по которой он покупает в настоящее время.

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

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



Также, для упрощения восприятия условий задачи, сформируем их в виде трёх таблиц.







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

Математическая модель задачи линейного программирования состоит из трёх основных элементов.

1. Целевая функция. Данную функцию будем обозначать через Z. Она должна количественно отражать значение цели в зависимости от значений неизвестных переменных. Целевая функция может быть на нахождение максимального значения (прибыль предприятия) или минимального значения (себестоимость, затраты).
2. Ограничения. В реальной экономической системе существуют ограничения, например, на объём используемых ресурсов, которые должны быть учтены при построении математической модели. Ограничения должны быть записаны в виде математических соотношений (уравнений или неравенств).
3. Условия неотрицательности переменных. Неизвестные переменные задачи отражают некоторые реальные параметры экономической системы, которые, как правило, не могут принимать отрицательных значений, поэтому соответствующие неизвестные переменные должны быть положительными или нулевыми.

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

$$display$$Z=_i^n_j^m(y_ij-k_ij )x_ijh_ij+_i^n(d-z_i )p_i,$$display$$

где
цена за тонну продукта -го производителя -му покупателю;
количество тонн продукта, поставленного от -го производителя -му покупателю;
затраты на ж.д. перевозку и производство продукта от -го производителя -му покупателю;
есть или нет (1-есть, 0-нету) поставка продукта от -го производителя -му покупателю;
количество тонн продукта, поставленного от -го производителя в порт;
фиксированная цена на продажу продукта в порту;
затраты на ж.д. перевозку и производство 1-ой тонны продукта от -го производителя в порт;
количество производителей;
количество покупателей.

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

1. Первое ограничение. Каждый производитель не может суммарно поставить покупателям или в порт количество продуктов больше, чем он сам производит.
   
   • для 1-го производителя:
   • для 2-го производителя:
   • для 3-го производителя:
   
   
2. Второе ограничение. Покупатели приобретают ровно то количество продуктов, которое им требуется в месяц.
   
   • для 1-го покупателя:
   • для 2-го покупателя:
   • для 3-го покупателя:
   • для 4-го покупателя:
   
   
3. Третье ограничение. Для каждого покупателя цена не может превышать 100 USD.
   
   • для каждого покупателя:
   
   
4. Четвёртое ограничение. Количество поставляемого продукта для любого покупателя не может быть отрицательным.
   
   • 
   
   

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

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

Наименее выгодная цена для производителей при поставке покупателям

Теперь, когда задача записана математически, можно приступить к реализации решения. Для решения этой задачи я выбрал Python библиотеку от IBM DOcplex (Decision Optimization CPLEX).

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

Моё решение задачи началось с поиска имеющихся готовых инструментов для решения задач линейного программирования. В итоге по душе мне пришёлся довольно мощный программный продукт от IBM под названием IBM ILOG CPLEX Optimization Studio. Он включает в себя среду разработки и решения различных оптимизационных задач, в том числе задач линейного программирования. Содержит хорошую документацию и, самое главное, множество разнообразных примеров решения типовых оптимизационных задач. Также в комплект программного продукта IBM ILOG CPLEX Optimization Studio входит Python библиотека DOcplex и примеры её использования в Jupyter Notebook. Ниже рассмотрим ход моего решения задачи в Jupyter Notebook.

Ход решения в Jupyter Notebook



Как всегда, начинаем с импорта необходимых стандартных библиотек. Из дополнительных библиотек подключаем docplex о ней мы уже сказали выше, и networkx эта библиотека поможет нам построить наглядное решение нашей задачи в виде графа.

import pandas as pdimport docplex.mp as dpximport matplotlib.pyplot as pltimport numpy as npimport seaborn as snsimport networkx as nximport warningswarnings.filterwarnings('ignore')boldText = '\033[1m'

Далее, задаём исходные данные условия задачи из таблиц 1-3.

1. Исходные данные

# Данные по поставщикамNProds = 3            #Количество производителейNBuyers = 4           #Количество покупателейd = 50                  #Константная цена товара в ПортуBuyersMaxPrice = 100    #максимальная цена# ПроизводителиProdIndex=[]for i in range(NProds):    ProdIndex.append('P'+ str(i+1))ProdData = {'Possibilities': [890,534,1153],            'SupplyPort': [18,13,18],            'ProdCost': [12,21,10],            'PortPrice': [d,d,d],            'Overhead': [18+12,13+21,18+10]            }Producers = pd.DataFrame(ProdData, ProdIndex)# ПокупателиBuyIndex = ['B1','B2','B3','B4']BuyData = {'Scenario1': [78,121,94,85], 'Scenario2': [117,670,193,279]}Buyers = pd.DataFrame(BuyData, BuyIndex)#выбор сценарияScenario = Buyers.columns[0] # 0 - Scenario1                             # 1 - Scenario2print(Scenario)# Тарифы на железнодорожные перевозкиRailData = {'P1':[14,23,21,42], 'P2':[26,10,19,36], 'P3':[15,38,18,15]}RailFares = pd.DataFrame(RailData, BuyIndex)totCost = RailFares + Producers['ProdCost']

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

minCostProd = np.zeros((NProds, NBuyers)).astype(int)for j in range(NBuyers):    min_idx = np.argmin(totCost.values[j,:])    minCostProd[min_idx, j] = totCost.values[j,min_idx]minCostProd = pd.DataFrame(data=minCostProd, index=totCost.columns, columns=totCost.index)# Тарифы на жд перевозки от i-го производителя j-му покупателю + себестоимость производства i-го производителяk = np.zeros((NProds, NBuyers)).astype(int)i=0j=0for prod, pcost in zip(RailFares, Producers['ProdCost']): # перебор по Producers    j=0    for rfares in RailFares[prod]:        k[i,j] = rfares + pcost        j+=1    i+=1

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

# Тарифы на жд перевозки в порт + себестоимость производства i-го производителя z = np.empty(NProds).astype(int)i=0for SupplyPort, ProdCost in zip(Producers['SupplyPort'], Producers['ProdCost']):    z[i] = SupplyPort + ProdCost    i+=1

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

#Наименее выгодная цена для производителей при поставке покупателямProdBestPrices = np.zeros((NProds, NBuyers)).astype(int)for j in range(NBuyers):    i=0    for portPrice, supplyPort, supplyProd in zip(Producers['PortPrice'], Producers['SupplyPort'], k[:,j]):#       print(portPrice, supplyPort, supplyProd)        ProdBestPrices[i,j] = portPrice-supplyPort+1+supplyProd        i+=1

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

#Матрица спроса покупателейh = np.zeros((NProds, NBuyers)).astype(int)for j in range(NBuyers):    min_idxs = np.argmin(ProdBestPrices[:,j])    h[min_idxs, j] = 1

Далее импортируем из библиотеки docplex модель Model, являющуюся вычислительным ядром нашей оптимизационной задачи.

2. Модель

from docplex.mp.model import Modelmdl = dpx.model.Model("ChemProd")

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

# матрица решений, показывающая количество тонн продукта поставленное от i-го производителя j-му покупателю# столбец-производитель; строка-покупательx = mdl.integer_var_matrix(NProds, NBuyers, name=lambda ij: "ProdVol_to_Buyer%d_%d" %(ij[0], ij[1]))# матрица решений, показывающая цену за тонну продукта i-го производителя j-му покупателю# столбец-производитель; строка-покупательy = mdl.integer_var_matrix(NProds, NBuyers, name=lambda ij: "ProdPrice_to_Buyer%d_%d" %(ij[0], ij[1]))# вектор решений - количество продукта перевнзённое в портp = mdl.integer_var_list(NProds, name='ProdVol_to_port')

3. Ограничения модели

1. Ограничения по количеству тонн производимого продукта для производителей

# 1. Ограничения по количеству тонн производимого продукта для производителейfor i, possib, cts_name in zip(range(NProds), Producers['Possibilities'], Producers['Possibilities'].index):    mdl.add_constraint(mdl.sum(x[i,j] for j in range(NBuyers)) + p[i] <= possib, ctname='Possib'+cts_name)

2. Ограничения по потребностям покупателей

# 2. Ограничения по потребностям покупателейfor j, req, buyer in zip(range(NBuyers), Buyers[Scenario], Buyers[Scenario].index):    mdl.add_constraint(mdl.sum(x[i,j] for i in range(NProds)) == req,  ctname=buyer+'Need')

3. Ограничения по цене продукта

# 3. Ограничения по цене продуктаfor i in range(NProds):    for j in range(NBuyers):        #mdl.add_constraints( [y[i,j] <= BuyersMaxPrice, y[i,j] >= 0], ['BuyersMaxPrice', 'BuyersMinPrice'])        mdl.add_constraint( y[i,j] == ProdBestPrices[i,j], 'ProdBestPrices')

Для данной задачи четвёртое ограничение о неотрицательности переменных выполняется исходя из первых 3х ограничений.

Теперь, когда ограничения нашей модели созданы, сформируем нашу целевую функцию и зададим её максимизацию.

#Доставка покупателямSalesBuyers = mdl.sum( (y[i,j]-k[i,j] )*x[i,j]*h[i,j] for i in range(NProds) for j in range(NBuyers) ) #Доставка в портSalesPort = mdl.sum( (d-z[i])*p[i] for i in range(NProds) )#Целевая функцияmdl.maximize(SalesBuyers + SalesPort)

4. Решение модели

%%timeassert mdl.solve(), "!!! Solve of the model fails"prodsVol = np.zeros((NProds, NBuyers)).astype(int)prodsPrice = np.zeros((NProds, NBuyers)).astype(int)VolPrice = np.zeros((NProds, NBuyers)).astype(int)VolPricePort = np.zeros((NProds, 1)).astype(int)for i in range(NProds):    #VolPricePort[i] = int((d - z[i])*p[i].solution_value)    VolPricePort[i] = int(p[i].solution_value*d)    for j in range(NBuyers):        prodsVol[i,j] = x[i,j].solution_value        prodsPrice[i,j] = y[i,j].solution_value        #VolPrice[i,j] = (y[i,j].solution_value - k[i,j])*x[i,j].solution_value        VolPrice[i,j] = y[i,j].solution_value*x[i,j].solution_value#Количество тонн продукта от i-го производителя j-му покупателюVolData = dict(zip(ProdIndex, prodsVol))DecisionVol = pd.DataFrame(VolData, BuyIndex)#Количество тонн продукта от i-го производителя в портVolPricePortData = dict(zip(ProdIndex, (VolPricePort)))DecisionVolPort = pd.DataFrame(VolPricePortData, index=['Pt'])#Цена за тонну продукта i-го производителя j-му покупателюPriceData = dict(zip(ProdIndex, prodsPrice))DecisionPrice = pd.DataFrame(PriceData, BuyIndex)#Объём продаж i-го производителя j-му покупателю за вычетом затрат на доставку товараVolPriceData = dict(zip(ProdIndex, VolPrice))DecisionVolPrice = pd.DataFrame(VolPriceData, BuyIndex)

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



Как я уже писал выше, для наглядности полученного решения представим его в виде графа, отображающего сложившуюся ситуацию на рынке. Для этого используем библиотеку networkx и следующий скрипт.

G = nx.Graph()#Морской портfor p in ProdIndex:    G.add_edge(p, 'Pt', w=DecisionVolPort[p]['Pt'])    #Продавцы / покупателиfor b in BuyIndex:    for p in ProdIndex:        G.add_edge(p, b, w=DecisionVolPrice[p][b])nodeKeys = []nodePos = []num_buy = 0num_prod = 0for p in ProdIndex:        x_prod = int(-NProds/2)+num_prod        num_prod+=1        nodeKeys.append(p)        nodeKeys.append('Pt')                nodePos.append([x_prod,1])        nodePos.append([0,2])        for b in BuyIndex:    num_prod = 0    x_buy = int(-NBuyers/2)+num_buy    num_buy+=1    for p in ProdIndex:        x_prod = int(-NProds/2)+num_prod        num_prod+=1        nodeKeys.append(p)        nodeKeys.append(b)                nodePos.append([x_prod,1])        nodePos.append([x_buy+0.5,0])               pos = dict(zip(nodeKeys, nodePos))            elarge = [(u, v) for (u, v, d) in G.edges(data=True) if d['w'] > 0]esmall = [(u, v) for (u, v, d) in G.edges(data=True) if d['w'] == 0]plt.figure(figsize=(16, 8))plt.subplot(1,2,1)nx.draw_networkx_nodes(G, pos=pos, node_size=7000/((NProds+NBuyers)/2))nx.draw_networkx_edges(G, pos=pos, edgelist=elarge, width=2, edge_color='black')nx.draw_networkx_edges(G, pos=pos, edgelist=esmall, width=2, alpha=0.3, edge_color='gray', style='dashed')edge_values = []for (u, v, d) in G.edges(data=True):    if d['w']>0:        edge_values.append(int(d['w']))        labels = dict(zip(elarge, edge_values))nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=labels, font_size=12, font_color='black')# labelsnx.draw_networkx_labels(G, pos=pos, font_size=70/((NProds+NBuyers)/2), font_color='white')plt.axis('off')plt.subplot(1,2,2)plt.grid(True)sns.barplot(x=DecisionVolPrice.columns,            y=sumBuyPort,            palette="deep").set_title('Суммарный объём продаж')plt.show()

После выполнения скрипта на экране сформируется граф нашего моделируемого виртуального рынка согласно результатам решения задачи. На рёбрах графа отображено произведение количества поставляемых продуктов на их цену, а в вершинах графа расположены участники рынка: Pt морской порт; P1-P3 производители; B1-B4 покупатели.



Заключение.

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

Ссылки на источники.

1. Решение закрытой транспортной задачи с дополнительными условиями средствами Python;
2. Решение задач линейного программирования с использованием Python;
3. Дыбская В.В., Зайцев Е.И., Сергеев В.И., Стерлигова А.Н. MBA Логистика. М.: Эксмо, 2009;
4. Avinash K. Dixit, Barry J. Nalebuff The Art of Strategy: A Game Theorist's Guide to Success in Business and Life.