истории

6 квадриллионов и 183 нуля Как программа Orion просчитывает немыслимое количество маршрутов, чтобы доставить посылку

07:06, 19 февраль 2015

Источник: The Wall Street Journal

Американская компания UPS каждый день доставляет миллионы посылок. Чтобы управлять наземной доставкой в США, в корпорации разработали программу Orion для анализа бесчисленного количества маршрутов, которыми эти посылки могут быть доставлены. «Медуза», отталкиваясь от недавней публикации The Wall Street Journal, рассказывает, как работает эта система. 

UPS — United Parcel Service — гигантская корпорация, которая занимается доставкой грузов по всему миру. На бирже она стоит в два раза дороже российской «Роснефти». В компании работает около 400 тысяч человек. В США UPS располагает парком из 55 тысяч автомобилей. Каждый водитель доставляет от 120 до 175 посылок в день.

Если количество посылок просто огромно, то число вариантов, которыми их можно доставить, астрономически велико. По отдельным подсчетам, в нем 199 цифр, и у него даже нет названия. Для сравнения, Земля существует около четырех с половиной миллиардов лет — примерно 142009200000000000 секунд. В этом числе всего 18 цифр.

Раньше при доставке посылок водители полагались на свой опыт и советы руководства. Но человек физически не может просчитать такое количество вариантов, поэтому в начале 2000-х UPS начала думать, как повысить эффективность доставки программными методами. К 2008 году начались тесты программы Orion, которая рассчитывает для водителей маршруты. На ее разработку уже потрачены сотни миллионов долларов. Алгоритм программы насчитывает 1000 страниц.

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

Например, в начале дня для водителя запланирован маршрут длиной 189,7 километра. Но вдруг клиент меняет время доставки на 11:00 — 13:00, хотя изначально доставка его посылки была запланирована на 13:25. Тогда Orion пересчитывает маршрут, исходя примерно из 200 тысяч приемлемых вариантов. В итоге маршрут водителя окажется длиннее на два с лишним километра, и доставка обойдется компании дороже почти на два доллара. В течение дня Orion может менять маршрут сотни раз. В случае непредвиденных обстоятельств (вроде аварии на дороге) водитель может временно отключить Orion, а потом снова включить программу.

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

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

Благодаря разработанному в UPS алгоритму компании удается снижать затраты на бензин, сокращая длину маршрута. Сэкономленная тут и там пара долларов в итоге приводят к миллионному снижению затрат. К 2017 году, когда устройствами с Orion оснастят всех водителей, UPS планирует экономить по 300-400 миллионов долларов в год. 

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