Использование бионики для решения проблемы доставки на последней миле в розничной Интернет–торговле

С результатами работы исследователей в области бионики мы сталкиваемся каждый день. Несчётное количество изобретений было сделано благодаря данной науке. Совершенно неполный список интересных открытий включает [49]:

· Застежки-липучки, как результат прикрепления семян репейника к шерсти собаки исследователя Георга де Местраля;

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

· Появление камуфляжной одежды, что также заимствовано из природы и таких животных и насекомых, как, например, стрекозы, которые предпочитают занимать визуальное поле жертвы;

· Строение тела пингвинов, которое послужило прототипом создания дирижаблей после осознания того, что данная форма характеризуется чрезвычайно низким сопротивлением;

· Материал паутины, являясь прочнее и эластичнее, чем те, из которых сейчас производят бронежилеты, дает ученым надежду исследовать на нано-уровне нити и сконструировать материал подобной прочности в будущем;

· Флуоресцентные материалы, в частности светоотражающие поверхности, во многом обязаны светлячкам;

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

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

В настоящее время бурно процветают исследования в области робототехники и автоматизации. Эта индустрия серьезно преуспела благодаря исследованиям, вдохновителем которых была природа. Марсоходы и иные перемещающиеся роботы, а также протезы и прототипы органов - всё это имеет элементы бионики. Стоит отметить, что сегодня можно наблюдать тренд смещения фокуса данного научного направления в сторону создания новых материалов и новых продуктов, нежели чем выявление новых формализованных моделей, структур и принципов организации. [50]

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

Некоторые исследователи утверждают, что всю деятельность в области бионики достаточно ясно можно отнести к трем основополагающим направлениям. Определяют следующие направления бионики [7]:

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

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

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

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

Рис. 2.1. Классификация направлений бионики

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

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

2.2 Роль бионики в решении комплексных логистических задач

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

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

Было предпринято несколько попыток в исследовательском сообществе провести библиометрический анализ, а именно детально изучить состояние научной мысли, соединяющей бионику и логистику. Первое количественное исследование источников, упоминающих применение природных закономерностей по отношению к аспектам логистики и управления цепями поставок, было произведено Даниэлом Тинеллом и другими его учеными-коллегами из Австрии и Германии [48]. Исследование заключалось в том, чтобы проследить за развитием научной мысли в данном направлении через анализ источников из таких баз, как Scopus, Web of Science и Google Scholar, выделить основополагающие работы. Исследователи также обратили внимание на географическое распределение научных работ. В поиске были использованы комбинации таких понятий, как «логистика», «управление цепями поставок», «материальный поток», «транспорт», «производство» и ные термины со стороны логистики; «самоорганизация», «муравьиный алгоритм», «пчелиный алгоритм», «роевой интеллект» и другие со стороны биологии и бионики. В дальнейшем были составлены такие пары слов, как, например, вдохновленное природой (англ -bio-inspired) и логистика (англ - logistics), для поиска публикаций. Также важно, что исследование было направлено и основано на изучении опыта иностранных деятелей науки и англоязычной литературы. [47]

Говоря о результатах, в период с 1990 по 2013 года было определенно, что, исключая наличие цитирования и упоминания работ по теме в иных целях, на тот момент существовало 335 публикаций в рамках исследуемой темы. Первые упоминания пересечения логистики и биологических принципов были еще в 1990 году, однако до 2003 года динамика была низкой, и в свет выходило малое количество публикаций на данную тему (иногда менее 2). За период 1990 - 2002 года вышло всего 8 журнальных статей и опубликованных докладов на конференциях. После 2003 года количество публикаций стало заметно расти, а в 2008 году начался настоящий «бум», исследователи «распробовали» потенциал темы (рис 2.2).

Рис. 2.2. Количество и динамика выхода публикаций о бионике и логистике, 1990 - 2013 гг.

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

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

Рис. 2.3. Пересечение тем биологии и логистики в публикациях

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

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

Стоит заметить, что когда точные методы поиска решения (методы, гарантирующие нахождение оптимального решения) не всегда эффективны в применение в виду существенных временных затрат, используются эвристические алгоритмы. Такие алгоритмы, или методы, разработаны для поиска «хорошего» решения, однако они не гарантируют нахождение единственного оптимума. В течение последних 30 лет исследователи разработали метаэвристические методы - эвристические подходы, которые работают независимо и подходят для решения любой проблемы. Применение особенно актуально в рамках логистики. [31]

Среди наиболее часто встречающихся возможностей применений биологии к логистике можно выделить зональное и пространственное планирование, а также решение задачи построения оптимального маршрута. Существует достаточно много исследовательских работ на данные темы. Так, зональное и пространственное планирование, а именно задачи о назначениях, исследователи предлагают решать посредством применения таких интересных природных явлений, как расположение пчелиных сот, строение различных членистоногих и методом организации паутины. Дело в том, что задача о назначениях предполагает размещение n-го количество оборудования на n-ом количество мест с учетом передвижения потока и расстояния между ними, принимая за целевую функцию сокращение общих расходов. Интересно то, что, изучив методы передвижения паука по паутине и способы построения пчелами сот, а также их свойств, исследователей оказались способными создать впечатляющие решения для зонального и пространственного планирования. Несмотря на то, что после ряда экспериментов доказано, что инструменты бионики еще не так эффективно справляются с задачей о назначениях в области пространственного планирования, как классические методы. Однако исследователи комментируют, что при росте сложности задачи, в частности при необходимости, например, организации нелинейного материального потока, инструменты бионики, например, способ двойной спирали Фибоначчи (англ. - fibonacci double spiral procedure),раскрывают свой потенциал и в некоторых моментах справляются намного лучше, чем классические способы решения данной задачи. Такую же ситуацию можно наблюдать в применении бионики для оптимизации. Такие эвристические методы бионики, как «муравьиный алгоритм», генетический алгоритм, метод имитации отжига существенно преуспевают в нахождении оптимального решения целевой функции, не уступая классическим методам, а, зачастую, и существенно обгоняя их при увеличении сложности задачи. [32]

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

Алгоритмы, основанные на социальном поведении насекомых, были предложены для решения сложных вычислительных задач. Ярким примером данного явления может служить применение «муравьиного алгоритма» для решения задачи дискретной оптимизации. Такие алгоритмы и их модификации применяются для решения таких проблем, как построение оптимального маршрута при транспортном обслуживании или проблема маршрутизации в телекоммуникационной сети. [31]

2.3 Разработка системы мер по повышению эффективности доставки заказов на «последней миле»

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

Так как большая доля товаров, купленных в интернете, обычно представляют собой предметы небольшого веса и размера, в большинстве случаев целесообразно использовать экспресс-доставку. В целом, данный вариант уже используют почти 100% интернет-магазинов при доставке товаров по территории России. В целом, под понятием экспресс-доставки предполагается комплексная услуга, предоставляемая для доставки товаров или иных грузов в режиме «до двери» (англ. - door-to-door delivery) в течение минимального срока. [30]

Многие исследователи, высоко оценивают потенциал рынка экспресс-доставки по отношению к обслуживанию рынка электронной коммерции. Выделяют, например, такие преимущества, как [22, 30]:

· Цена. Формируется из понятных для расчета тарифов параметров, таких как вес груза, его размеры, а также адреса отправки и получения;

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

· Быстрота. В то время как покупатели ожидают получить свой товар как можно скорее, обычно в течение 2-х дней, и экспресс-доставка является одним из способов, которым можно осуществить доставку товара в течение двух дней в любую точку мира;

· Территориальное покрытие. Крупные международные игроки рынка осуществляют доставку почти во все населенные пункты мира;

· Доставка товара до клиента. Обычно компания-перевозчик, осуществляющая экспресс-доставку, берет на себя все этапы перемещения товара от расчета маршрута до вручения товара.

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

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

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

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

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

Рис. 2.4. Основные способы совершенствования процесса доставки на «последней миле»

Основные преимущество и недостатки рассмотренных выше способов совершенствования процесса доставки на «последней миле» представлены в табл. 2.1:

Таблица 2.1. Преимущества и недостатки способов совершенствования процесса доставки на «последней миле»

Способ совершенствования	Преимущества	Недостатки
Экспресс-Доставка	Предсказуемые и четкие тарифы; Высокий уровень надёжности; Быстрая доставка; Максимальное географическое покрытие; Door-to-door delivery; Сосредоточение в рамках одной компании	Зависимость рынка экспресс-доставки от инфраструктурных проблем; Сильная зависимость рынка интернет-торговли от рынка экспресс-доставки;
Курьерская служба	Профессиональные сотрудники; Door-to-door delivery; Быстрота доставки.	Высокая стоимость; Небольшое географическое покрытие.
Построение оптимального пути доставки	Способность значительного сокращения затрат на доставку	Сложность задачи; Существенное время на поиск и тестирование возможного инструмента для применения
Сокращение времени на передачу товара клиенту	Способность сокращения времени на доставку	Стохастические особенности, обусловленные поведением людей
Сокращение времени на загрузку транспортного средства	Способность сокращения времени на доставку	Инфраструктурные особенности склада

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

Исследование применения бионики в логистике показало, что в области управления цепями поставок до сих пор практически не применялись подходы, основанные на биомиметике, за исключением отдельных направлений. Этот результат интересен тем, что логистика представляет собой типичную область для применения методов оптимизации, среди которых наблюдаются алгоритмы созданные с ориентиром на живую природу [50]. Социальные насекомые и птицы имею различные подходы к решению сложных комбинаторных задач дискретной оптимизации. Примерами создания моделей данной оптимизации включают деятельности в рамках роя муравье и процесс кормления и собирания семян голубями, на котором основан аналитический инструмент «метод роя частиц» (англ. - Particle Swarm optimization algorithm), основанный на вычислении вероятностей и применимый в области электричества. Основанные на биологии оптимизационные алгоритмы также используются в решении задач маршрутизации. Результат исследований показывают, что механизмы, лежащие в основе живой природы и поведения таких насекомых, как муравьи, которые передвигаются от источника пищи к муравейнику по оптимальным маршрутам, оправданно могут называться эффективными. Такие механизмы стоит использовать и брать за основу при желании достичь такой же цели исполнения задания посредством запараллеливания работы систем, состоящих из одинаковых элементов. Более доступно это можно объяснить примером муравьев в рамках муравьиного роя - децентрализованных объектов в рамках эффективно-функционирующей системы [34]. Самое интересное для исследователей-первопроходцев было установление, каким же все-таки образом почти не обладающие зрением насекомые строили оптимальные маршруты на пути к источнику пищи и обратно.

В следующей главе рассматривается применение инструмента бионики для совершенствования процесса доставки на «последней миле» посредством поиска оптимального маршрута.

3. Совершенствование процесса доставки заказов клиентам на основе «муравьиного алгоритма»

Проблема доставки товара на «последней миле» во многом заключается в выборе маршрута, который будет оптимальным при необходимости доставить заказы большому количеству клиентов. Так, при доставке 52 клиентам, выбор оптимального маршрута складывается из 3,6 квадриллиона возможных комбинаций, а при доставке 56 клиентам централизованным способом возможен выбор из более чем 86 квадриллиона вариантов. Вдобавок к факту наличия столь огромного числа вариантов, которые нужно просчитать, существенно растут временные затраты на поиск оптимального решения. В первом случае с 52 клиентами поиск оптимального решения может достигать часа, а 56 - до целого дня, используя, при этом, высокопроизводительное программное и техническое обеспечение. [4]

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

Задача построения оптимального маршрута для доставки на «последней миле» имеет вид задачи коммивояжёра (англ. - Travelling Salesman Problem). Основами данной задачи является нахождение самого короткого замкнутого маршрута, который проходит через все города (в данной работе города будут названы понятием «вершины» графа или «точки») только один раз, возвращаясь в стартовую точку (иными словами, совершение гамильтонова цикла). Данная задача признана труднорешаемой в дискретной оптимизации и считается NP-полной, согласно временной сложности алгоритмов. [21] Это означает, что время ее решения растет экспоненциально по мере увеличения количества вершин. Считается, что известные алгоритмы, способные решить данную задачу, работают эффективно только в том случае, если размерность не высока, например, до 20 вершин. Однако зачастую бывают ситуации, когда оптимальный маршрут необходимо построить среди ста и более вершин [24]. Задачи дискретной оптимизации, применимые к реальной деятельности человека, действительно характеризуются большим количеством переменных и большим пространством поиска. Данная ситуация не оставляет возможным перебрать все возможные решения за небольшое время, однако и нахождение глобального оптимума не всегда необходимо. Часто, чтобы решить такие задачи оптимизации, необходимо получить лишь какой-то близкий к оптимальному результат. С этим справляются комбинаторные алгоритмы, которые основаны на эвристических схемах. [29]

Также здесь стоит остановиться на таком понятии, как эвристика. Эвристика - это множество методов исследования, которые способствуют упрощению решения задач различного рода. Для решения задачи коммивояжёра часто используют эвристические методы поиска, среди которых находится и «муравьиный алгоритм». Эвристические алгоритмы основываются на практических методах, не являются абсолютно достоверными, но дают приемлемый и достаточный (близкий к оптимальному) результат для решения поставленной задачи [35, 46].

«Муравьиный алгоритм» действительно является средством решения комбинаторной задачи коммивояжёра, процесс поиска оптимального маршрута легко объясним. [14]

3.1 Применение классического «муравьиного алгоритма» при решении задачи коммивояжёра

«Муравьиный алгоритм» основывается на копировании способов самоорганизации муравьиной колонии. Как известно, муравьи называются социальными насекомыми, так как эффективно они способны действовать только в коллективе. Посредством прямого обмена информацией, который включает визуальный и химический, а также непрямого (стигмержи - именно данный обмен используется в алгоритме) муравьиный рой функционирует и приходит к самоорганизации. Непрямой обмен - это распространённое во временном промежутке взаимодействие. Данный вид обмена происходит тогда, когда один субъект изменяет какую-либо часть среды, а остальные особи используют этот факт только впоследствии, когда находятся вбзизи данной среды. В случае муравьиной колонии по мере изменения траектории движения муравей оставляет специальное химическое вещество - феромон. Когда остальные муравьи приближаются к области измененной траектории, они способны воспринимать след из данного вещества. Чем выше его концентрация, тем предпочтительнее движение по данному пути. Адаптация поведения под условия внешней среды происходит благодаря способности испарения неиспользуемых феромонов (рис. 3.1) [34].

Рис. 3.1. Поведение роя муравьев, как снова для нахождения кратчайшего пути

Некоторыми правилами, на которые опирается алгоритм, являются:

1. Имеется понятие «память» (англ. - tabu list). Переход к каждой вершине должен быть осуществлен определенное количество раз;

2. У муравьев есть «зрение» или «видимость». Желание посетить вершину, зрение обратно пропорционально расстоянию между вершинам;

3. Также есть «обоняние», благодаря которому муравьи замечают феромоны, подтверждают желание перейти от одной вершины к другой; [55].

Теперь рассмотрим математическую модель «муравьиного алгоритма» для решения задачи коммивояжёра [36].

Допустим, мы имеем несколько вершин, тогда расстояние между ними будет обозначено, как L, соответственно, расстояние между вершинами i и j будет обозначено как . Количество феромонов на том или ном пути обозначим буквой , а количество феромона между вершинами i и j - . Стоит также ввести понятие «время жизни колонии», которое будет обозначено как Tmax и будет отражать количество циклов работы алгоритма - количество итераций. При решении задачи параметр Tmax устанавливает ЛПР.

Количество феромона на итерации t между вершинами i и j обозначим , где . Тогда, получим следующие формулы, составляющие математический алгоритм:

,

где - это вероятность перехода от i-го клиента к j-му,

- это параметр, обратный расстоянию между клиентами. Данный параметр является отражением понятия «видимости» и выражает эвристическое желание перейти из вершины i в вершину j. Соответственно, чем меньше расстояние между вершинами, тем выше желание муравья сделать переход,

- это параметры для корректировки механизма, задающие веса следа феромона,

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

Параметры являются регулируемыми. При выборе параметра б = 0 выбор будет сделан в пользу ближайшего города (алгоритм становится жадным). Если параметр в обозначить равным 0, тогда в работу вступает только так называемое феромонное усиление. Это влечет за собой «быстрое вырождение маршрутов к одному субоптимальному решению» или застревание муравья в локальном оптимуме [55].

Расчёт показывает лишь вероятность перехода из вершины i в вершину j. Непосредственный выбор направления перехода происходит посредством генерации случайных чисел и выявления области перехода согласно диапазону, в который попало случайное число. Данный шаг алгоритма также приближает его к математической интерпретации поведения муравьев, которые в природе выбирают направление движения случайным образом. Несмотря на то, что в данном алгоритме присутствует понятие случайности, оно корректируется и приближено к реальности: чем больше диапазон, тем выше вероятность перехода муравья к данной вершине. [42]

Длина пути вычисляется следующим образом:



Чем больше расстояние, тем меньше феромона на нем отложится. Новое значение феромона будет равно:

,

где - это константа изменения количества феромона на всем имеющемся пути на итерации t,

p - это коэффициент забывчиваемости алгоритма (или коэффициент испарения феромонов),

Q - это константа, подбираемая для сопоставления с предыдущими значениями,

формула (3.1) - для расчета нового значения феромона на пройденном пути в данном цикле (на данной итерации),

формула (3.2) - для расчета нового значения феромона на пути, оставшемся незатронутым в данном цикле.

Константа Q подбирается таким образом, чтобы она была одного порядка с длиной оптимального маршрута. Для того чтобы исследовать все пространство решений, необходимо обеспечить так называемое испарение феромона или уменьшение количества феромона с течением времени. Оно обозначено параметром p и принадлежит отрезку [0;1].

Стоит отметить, что параметры , коэффициент p и константа Q для конкретной модели подбираются методом экспертной оценки.

Общий вид алгоритма выглядит следующим образом [35]:

0. Определение количества вершин. Определение расстояния между вершинами, количества феромона на участках. Размещение муравьев в вершинах (в классическом, простом «муравьином алгоритме» количество муравьев равно количеству вершин);

1. Нахождение вероятности для перехода от стартовой точки во все другие возможные точки;

2. Выбор варианта перехода на основе случайных чисел (на основе попадания случайного числа в соответствующий интервал);

3. Нахождение вероятности перехода от точки, выбранной на этапе 2 во все возможные точки;

4. Выбор варианта перехода на основе случайных чисел;

… повтор действий до завершения цикла (итерации);

m. Обновление феромонов;

k. Совершение последующих циклов (итераций) и обновления феромонов Tmax раз;

n. Нахождение оптимального маршрута.

Рассмотрим работу данного алгоритма (рис 3.2) на примере. Допустим, имеется следующая информация (размещен один муравей) (табл. 3.1):

Таблица 3.1. Исходные данные для примера (итерация 1)

k-j
1 - 2	25	3
1 - 3	45	1
1 - 4	35	2
2 - 3	20	3
2 - 4	40	1
3 - 4	20	3

Для вычисления задачи экспертной оценкой было установлено, что коэффициенты равными 1.

Стартовой точкой является первая точка. Вычислим вероятности перехода от 1-ой точки ко 2-ой:

От 1-ой к 3-ей:

От 1 - ой к 4-ой:

Рис. 3.2. Схема работы классического варианта «муравьиного алгоритма»

Следующий шаг - выбор варианта с помощью случайных чисел. Классический «муравьиный алгоритм» заключается в совершении выбора направления перехода выбора на основе случайных чисел.

Допустим, разыгранное случайное число составило 0,890, что попало в диапазон распределения вероятности перехода к 4-му клиенту (рис. 3.3).

Рис. 3.3. Попадание случайного числа при переходе из 1-ой точки

Далее, вычислим вероятности перехода от 4-ой точки ко 2-ой (при этом более переход к 1-ой точке невозможен):

От 4-ой к 3-ей:

Разыгранное случайное число равно 0,82, соответственно, совершаем переход к 3-ей точке, так как значение случайного числа попало в диапазон вероятности перехода по данному направлению (рис. 3.4).

Рис. 3.4. Попадание случайного числа при переходе из 4-ой точки

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

Экспертной оценкой для рассматриваемой задачи было установлено, что константа Q равна 50, а коэффициент испарения феромона равен 0,1, тогда:

Для задействованных направлений ;

Для незадействованных -

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

Таблица 3.2. Исходные данные для примера (итерация 2)

k-j
1 - 2	25	3,4
1 - 3	45	0,9
1 - 4	35	2,3
2 - 3	20	3,4
2 - 4	40	0,9
3 - 4	20	3,4

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

Экспериментально доказано, что эффективность данного алгоритма увеличивается с увеличением размерности, соответственно, чем больше у нас транспортных средств (муравьев) по доставке и клиентов, тем эффективней работа данного алгоритма [29]. Работа «муравьиного алгоритма» показывает отличные результаты при работе с нестационарными системами, в которых параметры имеют свойства меняться. Это также доказывает пригодность данного алгоритма к работе в сфере логистики Интернет-торговли, где состояние заказов может меняться посредством добавления новых клиентов в текущую сеть, изменения места доставки или отказа от заказа.

3.2 Модификация «муравьиного алгоритма» с учётом особенностей логистической поддержки розничной интернет-торговли

Существует достаточно много модификаций «муравьиного алгоритма», которые в основном придуманы для того, чтобы улучшить временные характеристики и увеличить скорость сходимости. [16] Стоит отметить, что в целом время оптимизации данным алгоритмом представляет собой полиномиальную функцию от размерности. [23]

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

,

где

- коэффициент элиты или значение «авторитета» элитных муравьев.

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

Оптимальное значение коэффициента зависит от таких факторов, как количество вершин (размерность), от количества муравьев в колонии и от времени жизни колонии. Значение в целом определяет, с какой скоростью будет осуществляться сходимость. Этот коэффициент является чрезвычайно важным для бизнеса в целом, и для логистики Интернет-торговли в частности, так как зачастую в реальной жизни необходимо искать баланс между временем выполнения задачи и качеством ее решения. [16]

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

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

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

Современные исследования показывают, что критерий времени для клиентов играет далеко не последнюю роль при выборе интернет-магазина. Многие клиенты онлайн-шоппинга ожидают получить приобретенный товар как можно скорее, набирает популярность услуга доставки день в день. Вдобавок к этому, покупатели ставят на второе место «доставку в срок» в качестве фактора или мотива, который привел их к повторной покупке в интернет-магазине [26]. Также, почти все интернет-магазины, входящие, согласно сервису DataInsight, в топ-6 на начало 2018 года, представляют своим клиентам услугу выбора интервала доставки, минимальная величина которого без доплаты составляет 3 часа. Среди данных магазинов находятся Wildberries.ru, Ситилинк.ру, DNS.ru, Lamoda.ru. В магазине Эльдорадо.ру услуга выбора интервала времени доставки не предоставляется, а в Мвидео.ру за выбор определенного интервала времени требуется дополнительная оплата. Таким образом, становится понятно, что «окно доставки» становится важным элементом при выборе интернет-магазина и является востребованной услугой у покупателей.

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

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

,

Где - время, которое занимает путь от клиента i до клиента j в оптимальном маршруте;

- скорость движения транспортного средства на участке от клиента i до клиента j в определенное время на оптимальном маршруте;

- длина пути от клиента i до клиента j при оптимальном маршруте.

Узнав время доставки до каждого клиента, не составляет труда определить «окно доставки». Для этого необходимо поэтапно отсчитать срок перемещения до каждого клиента с начала осуществления доставки. Допустим, работа осуществляется с 8:00, время, которое занимает путь до первого клиента, составляет 25 минут, а от первого до второго на путь необходимо потратить 1 час 10 минут. Это означает, что доставка первому клиенту будет осуществлена в 8:25, а второму клиенту в 9:35. Исходя из погрешности, которую устанавливает ЛПР, может быть определено «окно доставки». Оно может находиться в разбросе от десятков минут до нескольких часов. В первом случае клиенту товар будет доставлен в окно между 8:20 и 8:40, а во втором случае клиенту будет доставлен товар между 9 и 10 часами утра. Таким образом, данная реализация основывается на самом коротком маршруте, что призвано сократить издержки компании. Есть существенная вероятность того, что самый короткий маршрут не будет самым быстрым. Однако если перед ЛПР не стоит задачи поиска самого быстрого маршрута, этот вариант модификации обладает преимуществами в силу своей простоты и добавочного характера.

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

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

,

где

- время, которое занимает путь от клиента i до клиента j на x-ом шаге итерации. Здесь появляется шаг x, так как в течение дня средняя скорость движения транспортного средства по дорогам может быть разной. Для упрощения возможна классификация шага по времени суток, например утро (x = 1), день (x = 2), и вечер (x = 3). Данным уровнем детализации можно пренебречь в целях экономии времени расчетов, однако в конечном итоге необходимо будет увеличить интервал времени доставки клиенту в связи с увеличением погрешности;

- скорость движения транспортного средства на участке от клиента i до клиента j на x-ом шаге итерации;

- длина пути от клиента i до клиента j.

Далее получаем, что

,

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

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

Время в пути вычисляется следующим образом:

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

,

где формула (3.3) - для расчета нового значения феромона на пройденном пути на данной итерации,

формула (3.4) - для расчета нового значения феромона на пути, оставшемся незатронутым на данной итерации.

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

Таким образом, Общий вид алгоритма выглядит так (рис. 3.5):

0. Определение количества вершин. Определение расстояния между вершинами, скорости движения на участках (при необходимости учёта: в зависимости от времени суток), количества феромона на участках. Размещение муравьев в вершинах;

1. Нахождение вероятности для перехода от стартовой точки во все другие возможные точки;

2. Выбор варианта перехода на основе случайных чисел (на основе попадания случайного числа в соответствующий интервал);

3. Нахождение вероятности перехода от точки, выбранной на этапе 2 во все возможные точки;

4. Выбор варианта перехода на основе случайных чисел;

… повтор действий до завершения цикла (итерации);

m. Обновление феромонов;

k. Совершение последующих циклов (итераций) и обновления феромонов Tmax раз;

n. Нахождение самого быстрого маршрута с учётом количества затраченного времени;

n+1. Расчет интервалов доставки клиентам на основе размера «окна».

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

Рис. 3.5. Схема работы модифицированного «муравьиного алгоритма»

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

Таблица 3.3. Исходные и расчетные данные для примера (модификация алгоритма)

k-j
1 - 2	25	3	5	5
1 - 3	45	1	10	4,5
1 - 4	35	2	7	5
2 - 3	20	3	10	2
2 - 4	40	1	10	4
3 - 4	20	3	5	4

Далее, необходимо рассчитать вероятности перехода из первой (начальной) точки во все возможные варианты:

Вероятность перехода от 1-ой точки ко 2-ой:

От 1-ой к 3-ей:

От 1 - ой к 4-ой:

Далее, по аналогии с классическим вариантом алгоритма необходимо выбрать вариант перехода. Разыгранное число составило 0,24, следовательно, совершаем переход ко второй точке.

Далее, вычисляем вероятности перехода от 2-ой точки ко всем возможным для перехода точек.

От 2-ой к 3-й (при этом вернуться назад к 1-ой точке невозможно):

От 2-ой к 4-ей:

Случайное число, разыгранное на данном этапе, составило 0,49. Таким образом, необходимо совершить переход к 3-ей точке.

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

Экспертной оценкой для рассматриваемой задачи было установлено, что константа Q равна 8, а коэффициент испарения феромона равен 0,1, тогда:

Для задействованных направлений ;

Для незадействованных -

Далее так же выполняем следующие циклы Тmax-1 раз для того, чтобы найти наиболее быстрый маршрут и определить интервалы доставки. В данном случае разброс значений возможен от 16 до 17,5 единиц времени. По окончании работы алгоритма будет определен не только наименьший по времени маршрут (16 единиц времени), но и «окно доставки».

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

В случае если компания предоставляет своим клиентам возможность выбора «окна доставки», желаемый интервал времени будет являться входной информацией для компании. В данной ситуации также возможно применение классического «муравьиного алгоритма» для точек доставки, выделенных в рамках одного или другого «окна». Таким образом, деление на части - кластеризация - заявок клиентов позволит строить маршруты с учетом пожеланий клиентов по времени доставки (рис. 3.6).

...