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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2017
Автор:	Васянин, В.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут телекомунікацій і глобального інформаційного простору НАН України 2017
Назва видання:	Математичне моделювання в економіці
Теми:	Математичні та інформаційні моделі в економіці
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/131906
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети / В.А. Васянин // Математичне моделювання в економіці. — 2017. — № 1-2(8). — С. 74-92. — Бібліогр.: 3 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-131906
record_format	dspace
spelling	irk-123456789-1319062018-04-06T09:05:39Z Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети Васянин, В.А. Математичні та інформаційні моделі в економіці В работе предложены математические формулировки задач построения комбинированных и раздельных маршрутов для перевозки мелкопартионных грузов во внутренних зонах обслуживания магистральных узлов иерархической транспортной сети. Проведен обзор методов и алгоритмов решения подобных задач. Отмечается возможность решения сформулированных задач с помощью известных пакетов смешанного и целочисленного линейного программирования. В роботі запропоновані математичні формулювання задач побудови комбінованих і роздільних маршрутів для перевезення дрібнопартіонних вантажів у внутрішніх зонах обслуговування магістральних вузлів ієрархічної транспортної мережі. Проведено огляд методів і алгоритмів розв’язання подібних задач. Відзначається можливість розв’язання сформульованих задач за допомогою відомих пакетів змішаного і цілочисельного лінійного програмування. The paper presents mathematical formulations of the vehicle routing problems with simultaneous and split delivery and pickup of small-lot cargo in the internal service areas of trunk nodes of hierarchical transport network. A review of methods and algorithms for solving such problems is conducted. It is marked the possibility of solving the formulated problems by known packages of mixed and integer linear programming. 2017 Article Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети / В.А. Васянин // Математичне моделювання в економіці. — 2017. — № 1-2(8). — С. 74-92. — Бібліогр.: 3 назв. — рос. 2409-8876 http://dspace.nbuv.gov.ua/handle/123456789/131906 519.854.2 ru Математичне моделювання в економіці Інститут телекомунікацій і глобального інформаційного простору НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математичні та інформаційні моделі в економіці Математичні та інформаційні моделі в економіці
spellingShingle	Математичні та інформаційні моделі в економіці Математичні та інформаційні моделі в економіці Васянин, В.А. Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети Математичне моделювання в економіці
description	В работе предложены математические формулировки задач построения комбинированных и раздельных маршрутов для перевозки мелкопартионных грузов во внутренних зонах обслуживания магистральных узлов иерархической транспортной сети. Проведен обзор методов и алгоритмов решения подобных задач. Отмечается возможность решения сформулированных задач с помощью известных пакетов смешанного и целочисленного линейного программирования.
format	Article
author	Васянин, В.А.
author_facet	Васянин, В.А.
author_sort	Васянин, В.А.
title	Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_short	Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_full	Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_fullStr	Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_full_unstemmed	Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_sort	задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
publisher	Інститут телекомунікацій і глобального інформаційного простору НАН України
publishDate	2017
topic_facet	Математичні та інформаційні моделі в економіці
url	http://dspace.nbuv.gov.ua/handle/123456789/131906
citation_txt	Задачи построения комбинированных и раздельных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети / В.А. Васянин // Математичне моделювання в економіці. — 2017. — № 1-2(8). — С. 74-92. — Бібліогр.: 3 назв. — рос.
series	Математичне моделювання в економіці
work_keys_str_mv	AT vasâninva zadačipostroeniâkombinirovannyhirazdelʹnyhmaršrutovperevozkimelkopartionnyhgruzovvovnutrennihzonahierarhičeskojavtotransportnojseti
first_indexed	2025-07-09T16:23:28Z
last_indexed	2025-07-09T16:23:28Z
_version_	1837187160655003648
fulltext	~ 74 ~ Математичне моделювання в економіці, №1-2, 2017 УДК 519.854.2 В.А. ВАСЯНИН ЗАДАЧИ ПОСТРОЕНИЯ КОМБИНИРОВАННЫХ И РАЗДЕЛЬНЫХ МАРШРУТОВ ПЕРЕВОЗКИ МЕЛКОПАРТИОННЫХ ГРУЗОВ ВО ВНУТРЕННИХ ЗОНАХ ИЕРАРХИЧЕСКОЙ АВТОТРАНСПОРТНОЙ СЕТИ Аннотация. В работе предложены математические формулировки задач построения комбинированных и раздельных маршрутов для перевозки мелкопартионных грузов во внутренних зонах обслуживания магистральных узлов иерархической транспортной сети. Проведен обзор методов и алгоритмов решения подобных задач. Отмечается возможность решения сформулированных задач с помощью известных пакетов смешанного и целочисленного линейного программирования. Ключевые слова: задачи комбинаторной оптимизации, математические модели маршрутизации транспортных средств, автотранспортные перевозки, мелкопартионные грузы. Введение В настоящей работе, как и в [1], рассматривается иерархическая автотранспортная сеть перевозок мелкопартионных тарно-штучных грузов с известными географическими координатами расположения магистральных узлов и их внутренними зонами обслуживания. Узлы, находящиеся во внутренней зоне каждого магистрального узла, могут обмениваться грузами между собой и со всеми другими узлами иерархической сети только через магистральный узел. Ранее [1] для транспортировки мелкопартионных грузов были предложены математические постановки задач построения отдельных доставочных и сборочных маршрутов, но на практике может оказаться, что комбинированные маршруты, когда во внутренних узлах разрешена одновременная доставка и сбор грузов, экономически выгоднее. Кроме того, если разрешить и раздельную (расщепленную) доставку, и сбор, когда допускается дробление потоков грузов и каждый клиент может посещаться несколькими транспортными средствами, то экономия транспортных издержек может быть еще более значительной. В этом случае привлекательно и то, что запросы клиентов могут превышать грузоподъемность транспортных средств и при колебании величины потоков на определенных промежутках времени не придется приобретать или арендовать дополнительные транспортные средства. В работе предложены математические постановки задач построения комбинированных и раздельных маршрутов для перевозки мелкопартионных грузов с использованием неоднородного парка транспортных средств, основанные на известных моделях, а также приводится библиографический обзор методов и алгоритмов решения задач подобного класса. Для крупных магистральных узлов, когда на их территории нет возможности размещения депо, а количество обслуживаемых клиентов велико, приведена содержательная постановка задачи построения маршрутов с размещением Ó В.А. Васянин, 2016 ~ 75 ~ Математичне моделювання в економіці, №1-2, 2017 нескольких депо в доступных географических районах. Предложенные транспортные модели включены в состав математического обеспечения автоматизированной информационно-аналитической системы поддержки принятия решений (АИАС ППР) [2] и могут использоваться при формировании рабочего парка и проектировании маршрутов транспортных средств для обслуживания узлов во внутренних зонах магистральных узлов. 1. Содержательная постановка и математическая модель задачи построения комбинированных маршрутов (the Delivery and Collection Route, DCR). Обзор методов решения Пусть физическая сеть внутриузловых перевозок (см. рис. 1) задана связным ориентированным графом )~,~(~ PNG . Множество вершин }~,...,1{},...,1{}0{~ nnnN +ÈÈ= , перенумерованное от 0 до n~ , включает вершину }0{ – депо и магистральный узел, },...,1{ n – множество клиентов и }~,...,1{ nn + – множество транзитных пунктов, связывающих отдельные участки дорог. Транзитные пункты вводятся для того, чтобы учесть особенности отдельных участков дорог, соединяющих узлы во внутренней зоне магистрального узла. Участки дорог представлены противоположно направленными ориентированными дугами ),( ji , ),( ij , Nji ~, Î , ji ¹ , одна из которых может отсутствовать (например, из-за одностороннего движения по участку дороги или запрета проезда грузовым видам транспорта). а) б) в) Рисунок 1 – Физическая сеть внутриузловых перевозок а) внутриузловая сеть с центральным магистральным узлом и депо, места дислокации клиентов закрашены черным цветом, а транзитные пункты – серым, участки дорог показаны линиями; б) входящие и исходящие магистральные потоки (широкая стрелка), и внутриузловые потоки к клиентам и от клиентов (простая стрелка); в) два циклических маршрута транспортных средств Длины дуг заданы матрицей 1~1~ ~~ +´+ = nnijrR , 1~ Rrij Î , Pji ~),( Î . Пусть для дуг сети известны коэффициенты 1~ Rkij Î , 0.1~ ³ijk , характеризующие ~ 76 ~ Математичне моделювання в економіці, №1-2, 2017 географические особенности (подъем, спуск и пр.) и физическое состояние (качество покрытия) участков дорог. Определим элементы преобразованной матрицы '~R как ijijij rkr ~~'~ = , Pji ~),( Î и построим на ней все кратчайшие пути в )~,~(~ PNG . В результате получим матрицу длин кратчайших путей 1~1~ ~~ +´+ = nnijlL и справочную матрицу 1~1~ ~~ +´+ = nnijcC , каждый элемент которой ijc~ , ji ¹ определяет номер предпоследнего узла на кратчайшем пути от i до j ‚ 0~ =iic , 1~,1 += ni . С помощью справочной матрицы можно легко определить кратчайший путь между любыми вершинами исходного графа. По матрице L~ для множества },...,1{}0{ nÈ построим полный ориентированный граф ),( ANG с множеством вершин },...,1,0{ nN = и множеством дуг },,:),{( jiNjijiA ¹Î"= с известными длинами ijl , Aji Î),( . Очевидно, что для дуг построенного графа выполняется правило треугольника ijkjik lll ³+ . В дальнейшем все задачи будем формулировать на графе ),( ANG . Пусть для каждого клиента j , nj ,1= задано среднесуточное количество 0>ja и 0>jb , +Î Zba jj , единиц мелкопартионных грузов унифицированного размера, которое нужно в течение суток доставить клиенту из магистрального узла (депо) и отправить от клиента в магистральный узел ( 000 == ba ). В депо имеется K типов транспортных средств с различной грузоподъемностью +Î ZQk , Kk ,1= . Грузоподъемность измеряется в тех же единицах, что и потоки мелкопартионных грузов. Предполагается, что Kjjj Qba £},{max , а количество транспортных средств каждого типа может быть ограничено величиной km , Kk ,1= и не ограничено. Для каждого типа транспортного средства задана функция ),( kkV RSfF = , Kk ,1= , где kS – фиксированная стоимость приобретения транспортного средства типа k , а kR – расходы на обслуживание одного транспортного средства типа k в сутки. Для депо и клиентов задана функция затрат на погрузку-выгрузку ju грузов ),( jkL uQfF = , nj ,0= , Kk ,1= . Если эта функция не зависит от типа транспортных средств, то затраты на погрузку и выгрузку грузов могут быть вычислены независимо от переменных задачи следующим образом: åå == +++= n i ii n i iifull bafbafF 11 )())(( или )(2 1å = += n i iiLfull bacF , где Lc – стоимость погрузки-выгрузки единицы мелкопартионных грузов при принятии линейной зависимости jLL ucF = . Если же такая зависимость существует, то эти затраты должны быть связаны с неизвестными ~ 77 ~ Математичне моделювання в економіці, №1-2, 2017 переменными задачи. Пусть стоимость проезда транспортного средства типа k по дуге Aji Î),( задана функцией ),,,( L k avkijM kVQlfF = , где ijl – длина дуги в километрах, k avV – средняя скорость движения (км/час), Lk – коэффициент загрузки транспортного средства на дуге. Значение ]1,0[/ Î= kijL Quk , где iju – текущая загрузка транспортного средства. По существу функция MF определяет стоимость израсходованного топлива на передвижение по дуге ),( ji для каждого транспортного средства типа k . Во многих задачах маршрутизации принимается ijkM lcF = , где kc – удельная стоимость топлива транспортного средства типа k на один километр пути. Все функции затрат должны быть приведены к сопоставимому виду, например, за одни сутки или за заданный период времени текущего планирования. Если построенные функции затрат VF , LF и MF реально отражают производственные издержки, то их сумма будет достаточна близка к фактическим расходам транспортного предприятия на приобретение и эксплуатацию рабочего парка транспортных средств без учета накладных расходов. Примем, что при решении задачи эти функции рассчитываются и их соответствующие числовые значения kF , k jf и k ijf , nji ,0, = , Kk ,1= используются в целевой функции. Обозначим общую сумму затрат транспортного предприятия как CRDR FF + при проектировании только доставочных и сборочных маршрутов и рассмотрим задачу построения комбинированных маршрутов. В зарубежной литературе такая задача называется The Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery (HVRPSPD). Главная особенность этой задачи заключается в том, что при построении маршрутов важен порядок посещения клиентов с учетом грузоподъемности транспортного средства и возможности погрузки грузов в магистральный узел в зависимости от количества выгруженного груза в каждом узле маршрута. В этом случае для отдельных индивидуальных задач оптимизации может оказаться, что общие затраты DCRF при решении комбинированной задачи меньше или равны суммарным затратам CRDR FF + . Не исключен и вариант DCRCRDR FFF <+ . Поэтому при проектировании маршрутов транспортное предприятие должно использовать доставочные, сборочные и комбинированные модели. Обозначим },...,1{ nC = – множество клиентов, },...,1{ KV = – множество типов транспортных средств. Введем потоковые переменные ijy , определяющие количество грузов в транспортном средстве при его проезде к клиенту j после посещения клиента i , Nji Î, , и потоковые переменные jiz , определяющие количество грузов в транспортном средстве при его проезде к клиенту i после посещения клиента j , Nji Î, . Определим булевы переменные k ijx , 1=k ijx , если транспортное средство типа k ~ 78 ~ Математичне моделювання в економіці, №1-2, 2017 движется от клиента i к клиенту j и 0=k ijx в противном случае. Пусть å ÎCj k jx0 представляет собой суммарное количество используемых транспортных средств типа k . Сформулируем задачу. Требуется найти минимум функции åå ååå åå å Î Î ÎÎ Î ÎÎ Î +-+-+= Vk Nj Ci k ijijji k j Vk Nj Ci k jijiij k j Vk Cj k jkDCR xzzfxyyfxFF ))(())((0 k ij Vk Nji k ij xfå å Î Î + , , (1) при ограничениях 1=åå Î ÎVk Ni k ijx , CjÎ" , (2) 0=-åå ÎÎ Ni k ji Ni k ij xx , CjÎ" , VkÎ" , (3) åå ÎÎ = Cj j Cj j ay0 , åå ÎÎ = Cj j Cj j bz 0 , (4) j Ni ji Ni ij ayy =-åå ÎÎ , CjÎ" , (5) j Ni ij Ni ji bzz =-åå ÎÎ , CjÎ" , (6) åå ÎÎ -££ Vk k ijikij Vk k ijj xaQyxa )( , Nji Î" , , ji ¹ , (7) åå ÎÎ -££ Vk k ijjkij Vk k iji xbQzxb )( , Nji Î" , , ji ¹ , (8) k ij Vk iijjkijij xbaabQzy å Î ---£+ }),,0max{( , Nji Î" , , ji ¹ , VkÎ" , (9) }1,0{Îk ijx , 0, ³ijij zy и целые, Nji Î" , , VkÎ" . (10) Первая часть целевой функции (1) определяет фиксированные затраты на приобретение и обслуживание используемых транспортных средств, вторая – затраты на погрузку и выгрузку грузов, и третья – переменные затраты на транспортировку грузов. Ограничения (2) и (3) гарантируют, что каждый клиент j посещается только один раз каким-либо транспортным средством типа k и это транспортное средство после прибытия к клиенту должно обязательно его покинуть. Ограничения (4) означают, что общее количество грузов на выходе из депо и на входе в депо равно суммарным требованиям всех клиентов. Ограничения (5) и (6) означают, что при посещении клиента j груз ja должен быть выгружен (количество груза в транспортном средстве после посещения клиента j уменьшается на величину ja ), а груз jb должен быть погружен (количество груза в транспортном средстве после посещения клиента j увеличивается на величину jb ). Эти ограничения ~ 79 ~ Математичне моделювання в економіці, №1-2, 2017 обеспечивают выполнение требований всех клиентов и исключают циклы, не проходящие через депо. Ограничения (7) и (8) связывают переменные ijy , ijz и k ijx и означают, что никакие грузы не перевозятся из i в j , если ни одно транспортное средство не обслуживает связь между этими узлами, т.е. если 0=k ijx VkÎ" . Ограничения (9) гарантируют, что грузоподъемность транспортных средств не будет превышена, а (10) устанавливают область изменения переменных. Так же, как и в задачах построения доставочных и сборочных маршрутов из [1], в постановку задачи (1)–(10) могут быть добавлены ограничения на используемое количество транспортных средств каждого типа, максимальную продолжительность маршрутов по времени и временные окна. Кроме того, для нее могут быть сформулированы двухпродуктовые постановки, аналогично задаче VRPSPD (Vehicle Routing Problem with Simultaneous Pickup and Delivery) из диссертационной работы A. Subramanian [3]. Задача проектирования комбинированных маршрутов может рассматриваться как один из вариантов задачи пикап-доставки (Pickup and Delivery Problem, PDP). Общая схема классификации таких задач предложена Berbeglia и др. [4]. В соответствии с этой схемой задача VRPSPD отнесена к классу «один – ко многим – к одному» (one-to-many-to-one) с комбинированными требованиями клиентов. Задача VRPSPD впервые была сформулирована Min [5] в 1989 г. Для решения задачи распределения и сбора книг публичной библиотеки автор предложил эвристические алгоритмы, основанные на кластеризации клиентов в соответствии с их потребностями и грузоподъемностью транспортных средств и решении задачи коммивояжера (TSP) для каждого кластера. Обзор литературы по задаче VRPSPD до 2012 г. можно найти в [3]. В настоящее время в литературе описано немного точных аппроксимаций для решения задачи VRPSPD. Так, например, Dell'Amico и др. [6] (2006), разработан алгоритм ветвей и цен (branch-and price), в котором использованы две различные стратегии для решения подзадач ценообразования – точные методы динамического программирования и методы релаксации. Авторам удалось найти оптимальные решения для задач с 40 клиентами при использовании только идентичных транспортных средств. Ранее Angelelli и Manisini [7] (2002) также применили метод ветвей и цен к формулировке задачи VRPSPD в виде разбиения множества с дополнительными ограничениями на временные окна (time-windows constraints). В их работе подзадачи сформулированы как задачи нахождения кратчайших путей с ресурсными ограничениями и использован алгоритм расстановки меток. Были найдены точные решения для задач с 20 клиентами. Трехиндексные формулировки VRPSPD предложены Dethlof [8] (2001) и Montané и Galvão [9] (2006), однако только последние авторы провели экспериментальные исследования. Для решения задачи в их постановке был использован пакет CPLEX 9.0, с помощью которого за два часа счета удалось получить нижние границы для контрольных экземпляров индивидуальных задач с 50–400 клиентами. Subramanian [10] (2008) представил двухпродуктовую потоковую формулировку задачи VRPSPD, но никаких практических экспериментов не проводил. ~ 80 ~ Математичне моделювання в економіці, №1-2, 2017 Эвристические методы решения задачи VRPSPD были предложены в диссертации Halse [11] (1992), в которой автор разработал двухэтапный алгоритм, основанный на концепции cluster-first, route-second. Позднее Salhi и Nagy [12] (1999) предложили cluster insertion эвристики для задачи VRPB (VRP with Backhauls), которые в последующих работах использовались для решения задачи VRPSPD. Значительное число работ по задаче VRPSPD появилось после 2000 г. Так, в [13] (2001) Dethloff была предложена эвристика, основанная на вставках самого дешевого допустимого маршрута по критерию остаточной грузоподъемности. Кроме того, автор исследовал связь задачи VRPSPD с другими вариантами задачи VRP. Røpke и Pisinger [14] (2006) разработали Large Neighborhood Search (LNS) эвристику, связанную с метаэвристической процедурой, аналогичной Variable Neighborhood Search (VNS) для решения различных вариантов задач VRPB и VRPSPD. Для задачи VRPPD (Vehicle Routing Problem with Pickups and Deliveries) Nagy и Salhi [15] (2005) разработали эвристический алгоритм, в котором используется общая методология решения задачи VRP, но модифицировали ее для сокращения множества допустимых решений. Большинство эвристик, разработанных для решения задачи VRPSPD, основаны на методе поиска с запретами (Tabu Search, TS). Crispim и Brandão [16] (2005) предложили метаэвристическую процедуру, объединяющую методы поиска с запретами и Variable Neighborhood Descent (VND). Montané и Galvão [17] (2006) разработали алгоритм TS с применением схемы локального поиска в окрестностях, характерной для решения традиционной задачи VRP, и привели результаты экспериментальных расчетов для набора из 87 тестовых задач с числом клиентов от 50 до 400. Chen и Wu [18] (2006) предложили процедуру локального поиска на основе подхода record-to-record и списков запрета (tabu lists). Вычислительные эксперименты с гибридным эвристическим алгоритмом показали его высокую эффективность для решения задач небольшой размерности. Chen [19] (2006) представил эвристику, основанную на методах моделируемого отжига (Simulated Annealing, SA) и поиска с запретами, в которой использована новая процедура параллельной вставки, позволяющая уменьшить число итераций алгоритма между получением начального допустимого решения и «оптимальным» решением. Bianchessi и Righini [20] (2007) предложили ряд конструктивных и локальных эвристик поиска, а также процедуру поиска с запретами, которая использует переменную структуру окрестностей (variable neighborhood structure) с комбинированной схемой обмена узлов и дуг (node- exchange и arc-exchange) в проектируемых маршрутах. Wassan и др. [21] (2008) представили reactive-TS алгоритм поиска со следующими правилами построения окрестности: перемещение во вспомогательную структуру данных (Auxiliary Data Structure, ADS), обмен двух клиентов между двумя различными маршрутами и изменение направления движения по маршруту. Предложенный подход позволил сократить число возвратов для проведения повторного поиска. Zachariadis и др. [22] (2009) разработали алгоритм, который сочетает в себе принципы метаэвристик TS и ведомого локального поиска (Guided Local Search, GLS). Достоинство предложенного метода заключается в расширении пространства поиска оптимального решения и интенсификации поиска только в перспективных областях, избегая локальных оптимумов. Эффективность алгоритма была проверена на ~ 81 ~ Математичне моделювання в економіці, №1-2, 2017 эталонных задачах с числом клиентов от 50 до 400. Те же авторы [23] (2010) предложили алгоритм, основанный на использовании Adaptive Memory Procedure (AMP) и гранулированной TS эвристики. Рассмотренная стратегия использует инновационный механизм памяти и систематически максимизирует количество маршрутной информации, извлеченной из адаптивной памяти для ведения поиска в направлении перспективных областей пространства решений. Метаэвристический алгоритм был протестирован на эталонных задачах (число клиентов от 50 до 400). Для решения задачи VRPSPD были также разработаны некоторые эволюционные стратегии (Evolutionary Strategies, ES). Vural [24] (2003) в диссертационной работе предложил два генетических алгоритма, первый из которых основан на случайном поиске (random key representation [25]), а второй состоит из улучшенной эвристики «Or-opt» Dethloff [13]. Gajpal и Abad [26] (2009) разработали муравьиный алгоритм (Ant Colony, AC), который состоит из двух основных этапов: интенсивность следа и параметры инициализируются с использованием исходного решения, полученного в ближайшей окрестности конструктивной эвристики; муравей - решение генерируется для каждого муравья с использованием интенсивности следа, за которым следует локальный поиск в каждом муравьином решении и обновлении элитарных муравьев и интенсивности следа. Авторами был проведен обширный численный эксперимент на эталонных задачах, который показал хорошие результаты. Çatay [27] (2010) предложил муравьиный алгоритм, основанный на новых saving-based функции видимости и процедуре обновления феромона. Ai и Kachitvichyanukul [28] (2009) предложили алгоритм роя частиц (Particle Swarm Optimization, PSO) [29] с множественными структурами, который использует случайный поиск (random key representation). Способ декодирования в алгоритме начинается с преобразования роя частиц в приоритетный список клиентов и матрицу приоритетов транспортных средств, которые далее используются для построения маршрутов. Предложенный алгоритм протестирован и показал конкурентоспособность с другими известными алгоритмами решения задачи VRPSPD. Mingyong и Erbao [30] (2010) предложен улучшенный алгоритм дифференциальной эволюции (improved differential evolution algorithm) для решения задачи VRPSPD с временными окнами (VRPSPDTW). В алгоритме было принято новое десятичное кодирование для построения начальной популяции и использовались некоторые улучшенные дифференциальные операторы эволюции в отличие от существующих алгоритмов. В операции мутации применялся критерий целого порядка на основе метода кодирования натурального числа. Для неосуществимых решений вводились штрафные коэффициенты, а для итераций алгоритма был разработан вероятностный самоадаптирующийся кроссовер. Subramanian [10] (2008) и Subramanian и др. [31] (2008) предложили итерационный алгоритм локального поиска (Iterated Local Search, ILS), который использует метод спуска с переменными окрестностями (Variable Neighborhood Descent, VND) с детерминированным упорядочением окрестностей в локальной фазе поиска. Параллельный вариант этого алгоритма, в котором процедура VND имеет случайное упорядочение окрестностей (Variable Neighborhood Descent with Random neighborhood, ~ 82 ~ Математичне моделювання в економіці, №1-2, 2017 RVND), был впоследствии разработан Subramanian и др. [32] (2010). Алгоритм состоит из процедуры спуска по случайно упорядоченным переменным окрестностям и встроенной итерационной процедуры локального поиска. Эксперименты с алгоритмом проводились на кластере с многоядерной архитектурой, использующей до 256 ядер. В результате испытаний были получены новые рекорды для некоторых известных тестовых задач. Subramanian и Cabral [33] (2008) также применили комбинацию ILS-VND для решения VRPSPD с ограничениями на временную продолжительность маршрутов. Единая структура VRP задачи, разработанная в этой работе, послужила основой для дальнейшего развития предложенного метода. Souza и др. [34] (2010) также реализовали алгоритм ILS, но в сочетании с GENIUS [35] подходом. Предложенный ими алгоритм, протестированный на 72 эталонных задачах, для 9 задач показал новые улучшенные решения и для 49 задач – ранее известные решения. Новый алгоритм локального поиска на основе метаэвристики был предложен Zachariadis и Kiranoudis [36] (2011). Алгоритм способен исследовать широкие окрестности решения за счет формирования специальных структур данных. Для того чтобы избежать зацикливания и индуцировать диверсификацию, общий поиск координируется использованием концепции, основанной на методологии поиска с запретами с заданной константой времени, ограничивающей проведение локального поиска. Hezer и Kara [37] (2011) для решения задачи VRPSPD предложили бактериальный алгоритм (Bacterial Foraging Optimization Algorithm, BFOA), который представляет собой новый алгоритм оптимизации на основе поведения бактерии при поиске пищи. В основу алгоритма заложено поведение бактерии при поиске питательных веществ с наибольшей концентрацией, что может рассматриваться как процесс оптимизации при поиске решения. Для решения задачи VRPSPD Tasan и Gen [38] (2012) предложили новый генетический алгоритм. Генетический алгоритм для задачи с временными окнами, сформулированной в виде задачи смешанного целочисленного программирования, разработан Wang и Chen [39] (2012). Работоспособность и вычислительная эффективность их алгоритма проверена на ряде тестовых задач Соломона (Solomon’s benchmark) с использованием программного обеспечения CPLEX. В работе Jun и Kim [40] (2012) обсуждается эвристический алгоритм, состоящий из процедур начального построения и улучшения маршрутов и процедуры возмущения полученного решения. Алгоритм основан на построении лучших начальных решений и схем модификации маршрутов, за счет перестановок узлов и дуг внутри маршрутов и между различными маршрутами. Процедура возмущения используется для избегания локальных оптимумов путем удаления некоторых маршрутов и вставки новых в текущее решение. Авторы провели вычислительные эксперименты на эталонных задачах и получили ряд лучших решений. Goksal и др. [41] (2013) предложили модификацию алгоритма роя частиц (particle swarm optimization PSO), в котором локальный поиск осуществляется методом спуска с чередующимися окрестностями (VND). В алгоритме для ~ 83 ~ Математичне моделювання в економіці, №1-2, 2017 сохранения разнообразия роя реализована стратегия отжига. Эффективность алгоритма исследована экспериментально. Liu R. и др. [42] (2013) рассматривают задачу планирования маршрутов транспортных средств для материально-технического обеспечения медицинского обслуживания на дому. Задача состоит из доставки лекарственных препаратов и изделий медицинского назначения от аптеки и больницы по домам пациентов и обратной доставки неиспользованных лекарственных средств, изделий медицинского назначения и биологических образцов от пациентов. Задача сформулирована в виде VRPSPDTW и для ее решения предложены две модели смешанного целочисленного программирования, генетический алгоритм (GA) и алгоритм на основе метода поиска с запретами (TS). Генетический алгоритм основан на перестановке хромосом, процедуре расщепления и локальном поиске. Второй алгоритм для выбора маршрутов использует атрибуты пациентов, дополненные функцией затрат, реоптимизацию маршрутов и уровни аспирации на основе атрибутов пациентов. Алгоритмы апробированы на известных тестовых экземплярах VRPTW задач. Kececi и др. [43] (2014) предложены математическая модель задачи VRPSPD и гибридный эвристический алгоритм, основанный на методах моделируемого отжига (SA) и локального поиска (LS) для решения задач средней и большой размерности. По утверждению авторов, результаты проведенной серии экспериментов показали вычислительную эффективность и пригодность разработанного алгоритма для получения достаточно хороших решений. Работа Wang и др. [44] (2015) адресована решению задачи VRPSPDTW, сформулированной в виде смешанного целочисленного программирования. Предложена параллельная версия алгоритма моделируемого отжига (SA), включающая вставки на основе эвристик остаточной грузоподъемности (Residual Capacity) и радиальной доплаты (Radial Surcharge). Результаты расчетов представлены для 65 эталонных тестовых задач Wang и Chen [39], решенных генетическим алгоритмом (GA). Разработанный алгоритм SA для числа клиентов от 10 до 50 показал те же результаты (100% совпадение) по количеству используемых транспортных средств, что и генетический алгоритм Wang и Chen. Для 100 клиентов алгоритмом SA были получены лучшие результаты для 12 индивидуальных задач, а для остальных – те же решения. Из 44 тестовых задач с одинаковыми решениями по количеству транспортных средств в 16 задачах получены лучшие решения по суммарному пройденному расстоянию, чем у алгоритма GA, а для 7 задач – равные решения. Кроме того, были найдены решения для 30 задач с числом клиентов 200, 400, 600, 800 и 1000, которые могут служить новым ориентиром для задачи VRPSPDTW. Avci и Topaloglu [45] (2016) для задачи VRPSPD с гетерогенным парком транспортных средств разработали гибридный алгоритм локального поиска, в котором интегрированы немонотонная стратегия регулировки порога и поиск с запретами. Пороговая функция, используемая в алгоритме, имеет адаптивный характер, что делает ее самонастраиваемой. Реализация алгоритма очень проста, так как не требует настройки параметров за исключением длины списка запретов. Предложенный алгоритм протестирован на ряде случайно сгенерированных индивидуальных задач. ~ 84 ~ Математичне моделювання в економіці, №1-2, 2017 В работе Zachariadis и др. [46] (2016) рассматривается задача VRPSPD (Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two- Dimensional Loading Constraints, 2L-SPD), в которой одновременно с маршрутизацией выполняется упаковка прямоугольных грузов с различной длиной и шириной в заданную полезную площадь грузового отсека транспортных средств. Предполагается использование однородного парка транспортных средств с одинаковой грузоподъемностью и полезной площадью для погрузки и выгрузки. Габариты грузов не могут перекрываться, а грузы упаковываются только в плоскости грузового отсека. В предложенном подходе решения задачи объединены модели маршрутизации и двумерной упаковки (Two-Dimensional Bin Packing Problem) и используется двухэтапный алгоритм, состоящий из конструктивной эвристики локального поиска для генерации начального решения (в котором требования всех клиентов могут быть не удовлетворены) и трех операторов поиска окончательного решения. Для диверсификации поиска применяется простая структурированная схема на основе критериев аспирации метода поиска с запретами (tabu search). При решении задачи минимизируются издержки маршрутизации и определяются возможные шаблоны для погрузки перевозимых грузов для обеспечения выполнения требований всех клиентов. Шаблоны конструируются эвристическим алгоритмом двумерной упаковки. Кроме основной модели, авторами предложена ее модификация с учетом правила погрузки LIFO. Эффективность предложенных алгоритмов проверена на эталонных задачах. 2. Содержательная постановка и математическая модель задачи построения маршрутов с раздельной доставкой и неоднородным парком транспортных средств В классической задаче с раздельной (расщепленной) доставкой (The Split Delivery Vehicle Routing Problem, SDVRP), формулируемой на полном неориентированном графе ),( ENG , предполагается использование неограниченного однородного рабочего парка транспортных средств с одинаковой грузоподъемностью. Каждый клиент может посещаться несколькими транспортными средствами, а запрос клиентов может быть больше грузоподъемности транспортных средств. Каждое транспортное средство начинает и заканчивает свой тур в одном и том же депо. Заданы стоимости проезда по ребрам (длины ребер), которые удовлетворяют неравенству треугольника. Задача заключается в построении маршрутов, обслуживающих запросы всех клиентов без нарушения ограничений на грузоподъемность транспортных средств и имеющих минимальную стоимость. Естественно предположить, что расщепленная перевозка грузов наиболее характерна для реальных транспортных сетей и необходима при оперативном управлении перевозками в условиях ограниченной провозной возможности имеющегося парка транспортных средств и значительного колебания потоков. Впервые задача SDVRP была рассмотрена в 1989 г. M. Dror и P. Trudeau [47, 48], которые указали на возможность сокращения транспортных издержек за счет дробления потоков и их расщепленной доставки клиентам. C. Archetti и др. [49, 50] провели анализ максимально возможной экономии ~ 85 ~ Математичне моделювання в економіці, №1-2, 2017 транспортных издержек и представили результаты вычислительных экспериментов, показывающих, как экономия зависит от характеристик индивидуальных задач оптимизации. Было показано, что расщепленная доставка в отдельных случаях позволяет улучшить решение нерасщепленной задачи до 2 раз. Обзоры по классической задаче SDVRP можно найти в работах [51, 52], а отдельные методы и алгоритмы ее решения – в [53–61]. Сформулируем задачу SDVRP с неограниченным и ограниченным неоднородным парком транспортных средств. Известны объемы доставляемых мелкопартионных грузов +ÎZai , ni ,1= , измеряемые количеством единиц, количество km и грузоподъемность +ÎZQk транспортных средств типа VkÎ , },...,1{ KV = , Kk ,1= . Пусть, как и ранее },...,1,0{ nN = , },...,1{ nС = , а объемы грузов могут превышать грузоподъемность транспортных средств. Известны kF , k if и k ijf , nji ,0, = , Kk ,1= – соответственно фиксированные затраты на приобретение и обслуживание транспортных средств, переменные затраты на обработку и транспортировку грузов. Введем переменные k iy , определяющие количество единиц груза, доставленных клиенту i транспортным средством k , целочисленные переменные k iu для исключения подциклов, которые определяют порядковый номер элемента i в маршруте k и булевы переменные k ijx , 1=k ijx , если транспортное средство k движется от клиента i к клиенту j и 0=k ijx в противном случае. Требуется найти минимум функции k ij Vk Nji k ij Vk Ni k i k i Vk Cj k jkCDVRP xfyfxFF å åååå å Î ÎÎ ÎÎ Î ++= , 0 )( , (11) при ограничениях 1³åå Î ÎVk Ni k ijx , NjÎ" , (12) 0=-åå ÎÎ Ni k ji Ni k ij xx , NjÎ" , VkÎ" , (13) 1-£+- nnxuu k ij k j k i , Cji Î" , , VkÎ" , (14) å Î £ Nj k iji k i xay , CiÎ" , VkÎ" , (15) å Î = Vk i k i ay , CiÎ" , (16) k Ci k i Qy £å Î , VkÎ" , (17) }1,0{Îk ijx , Nji Î" , , VkÎ" , (18) 0, ³k i k i uy и целые, CiÎ" , VkÎ" . (19) ~ 86 ~ Математичне моделювання в економіці, №1-2, 2017 Ограничения (14) на запрет подциклов можно записать в виде 1-£åå Î Î Sx Si Sj k ij , CS Í" , 2³S , VkÎ" , где S – кластер (подмножество клиентов), обслуживаемый транспортным средством типа k . Для ограниченного парка транспортных средств к задаче добавятся ограничения k Cj k j mx £å Î 0 , VkÎ" . (20) Целевая функция (11) определяет общие затраты маршрутизации. Ограничения (12) и (13) гарантируют, что каждый клиент j посещается хотя бы одним транспортным средством типа k , и это транспортное средство после прибытия к клиенту и выгрузки его груза должно обязательно покинуть клиента. Ограничения (14) запрещают подциклы, не проходящие через депо, а ограничения (15)–(17) распределяют запросы клиентов среди транспортных средств. Постановка задачи (11)–(20) может быть расширена на случаи построения комбинированных маршрутов, введения дополнительных ограничений на продолжительность и длину маршрутов, временные окна и т.п. [62]. Одними из первых задачу с неоднородным парком транспортных средств и расщепленными поставками рассмотрели Tavakkoli и др. (2007) [63], в которой стоимость используемого рабочего парка зависит от общей незаполненной грузоподъемности и количества транспортных средств. Авторы сформулировали задачу в виде смешанного целочисленного линейного программирования и для ее решения разработали гибридный алгоритм моделируемого отжига (SA). Для экспериментального исследования алгоритма были сгенерированы тестовые задачи с числом клиентов от 6 до 100. Для задач небольшой размерности разработанный алгоритм показал конкурентоспособные результаты с алгоритмом ветвей и границ. На задачах большой размерности сравнивались нижние границы решения, полученные путем построения большого тура с посещением всех клиентов. Belfiore и Yoshizaki (2013) [64] разработали scatter-search алгоритм для решения задачи с неограниченным рабочим парком и временными окнами. В их алгоритме начальные решения формируются с помощью двух конструктивных эвристик, а процедуры scatter-search используются для диверсификации и интенсификации поиска лучших решений. Авторы протестировали свой алгоритм на эталонных задачах FSMTW Liu и Shen (1999) [65] и эталонных задачах Ho и Haugland (2004) [66] со 100 клиентами, для которых получен ряд известных решений. 3. Задача построения доставочных маршрутов с неоднородным парком транспортных средств, размещением депо и временными окнами В заключение статьи рассмотрим содержательную постановку важной задачи, в которой требуется выбрать места дислокации депо, определить состав парка транспортных средств и построить маршруты обслуживания клиентов с учетом ограничений на временные окна (The Fleet Size and Mix ~ 87 ~ Математичне моделювання в економіці, №1-2, 2017 Location-Routing Problem with Time Windows, FSMLRPTW). Такая задача может возникнуть при перспективном планировании распределенной сети перевозок мелкопартионных грузов в крупных магистральных узлах, когда на территории магистрального узла нет возможности разместить депо, а количество клиентов очень велико (например, в столице страны и областных центрах). Предполагается, что места размещения клиентов во внутренней зоне магистрального узла известны и заданы географические координаты точек строительства потенциальных депо. Задача заключается в определении подмножества депо, назначении каждому депо обслуживаемых клиентов и построении для каждого депо кольцевых маршрутов неоднородных транспортных средств. Каждый клиент должен посещаться только один раз в пределах заданного временного окна, а загрузка транспортного средства не должна превышать его грузоподъемности. Целевая функция задачи на минимум включает четыре составляющих: капитальные затраты на строительство депо, фиксированные затраты на приобретение и обслуживание транспортных средств, затраты на погрузку и выгрузку грузов и переменные эксплуатационные расходы на транспортировку. Все затраты должны быть приведены к сопоставимому виду за заданный период времени. В диссертационной работе Ç. Koç [67] и статье Ç. Koç и др. [68] приведены обзор по задаче FSMLRPTW, ее формулировка в виде целочисленного программирования с системой ограничений, представленной линейными неравенствами, и гибридный алгоритм эволюционного поиска (Hybrid Evolutionary Search Algorithm, HESA) с введением нескольких адаптивных процедур нахождения окрестностей поиска локальных экстремумов целевой функции (Location Heterogeneous Adaptive Large Neighborhood Search, L-HALNS). Предложены процедуры построения начальных решений, разбиения допустимых решений, обучения и схема диверсификации через процедуру мутации решений. В работах представлены также результаты решения задачи на известных эталонных примерах. Целочисленная задача решалась пакетом CPLEX 12.5. Алгоритм HESA был реализован на C++. Главной целью эксперимента было сравнение результатов решения задачи, полученных с помощью пакета CPLEX и алгоритмом HESA для индивидуальных задач малой, средней и большой размерности. Численные результаты на наборе эталонных задач, содержащих до 100 клиентов и 10 потенциальных депо, показали, что предложенный авторами алгоритм способен найти приближенное решение в пределах 0,05% от оптимального для задач малой размерности и за приемлемое время дает лучшие решения по сравнению с решателем CPLEX для задач большей размерности, что позволяет использовать разработанный алгоритм в практических приложениях. Выводы На основании проведенного обзора и анализа известных математических моделей предложены постановки задач построения комбинированных и раздельных маршрутов для перевозки мелкопартионных грузов во внутренних зонах магистральных узлов. Для решения сформулированных NP-трудных задач могут быть применены в основном метаэвристические ~ 88 ~ Математичне моделювання в економіці, №1-2, 2017 методы и алгоритмы. Учитывая иерархическую структуру магистральной сети перевозок и небольшое количество узлов во внутренних зонах магистральных узлов, для решения задач можно использовать универсальные точные методы и алгоритмы, предложенные R. Baldacci и др. [69–71], которые способны находить оптимальные решения многих задач маршрутизации с числом клиентов до 100. Кроме того, решение задач возможно и классическими методами ветвей и границ, ветвей и отсечений, ветвей отсечений и цен, генерации столбцов, разбиения множества, динамического программирования и т.п., реализованными в коммерческих и открытых пакетах программ смешанного и целочисленного линейного программирования, например, IBM ILOG CPLEX, GAMS, AIMMS, Gurobi Optimizer [72] и ABACUS, COIN-OR, GLPK, lp_solve [73]. Многие из них доступны на сервере NEOS (https://neos-server.org/neos/). СПИСОК ЛИТЕРАТУРЫ 1. Васянин В.А., Ушакова Л.П. Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети // Математичне моделювання в економіці. — 2016. — № 3-4. — С. 102-131. 2. Васянин В.А., Трофимчук А.Н. Автоматизация процессов принятия решений в многопродуктовых коммуникационных сетях с мелкопартионными дискретными потоками // Екологічна безпека та природокористування: Зб. наук. праць. — Київ, 2010. — Вип. 5. — С. 172-213. 3. Subramanian A. Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems. — Thesis presented to the Computing Graduate Program of the Universidade Federal Fluminense in partial fulfillment of the requirements for the degree of Doctor of Science, Niterói, 2012. — 152 p. 4. Berbeglia G., Cordeau J-F., Gribkovskaia I., Laporte G. Static pickup and delivery problems: a classification scheme and survey // TOP: Operations Research & Decision Theory, Springer-Verlag, 2007. — Vol. 15. — Issue 1. — P. 1-31. 5. Min H. The multiple vehicle routing problem with simultaneous delivery and pickup points // Transportation Research Part A: General. — 1989. — Vol. 23. — Issue 5. — P. 377-386. 6. Dell'Amico M., Righini G., Salani M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection // Transportation Science. — 2006. — Vol. 40. — Issue 2. — P. 235-247. 7. Angelelli E., Mansini R. The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery // In Quantitative Approaches to Distribution Logistics and Supply Chain Management, Springer, Berlin-Heidelberg, 2002. — Vol. 519. — P. 249-267. 8. Dethloff J. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up // OR Spektrum. — 2001. — Vol. 23. — Issue 1. — P. 79-96. 9. Montané F.A.T., Galvão R.D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service // European Journal of Operational Research. — 2006. — Vol. 33. — Issue 3. — P. 595-619. 10. Subramanian A. Metaheurística Iterated Local Search aplicada ao Problema de Rotetamento de Veículos com Coleta e Entrega Simultȃnea. — Master's thesis, Programa de Pós-graduação em Engenharia de Produção, Universidade Federal da Paraíba, João Pessoa, PB, Brazil, 2008. In Portuguese. https://neos-server.org/neos/ http://link.springer.com/journal/11750 ~ 89 ~ Математичне моделювання в економіці, №1-2, 2017 11. Halse K. Modeling and solving complex vehicle routing problems. — PhD thesis, Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Denmark, 1992. 12. Salhi S., Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling // Journal of the Operational Research Society. — 1999. — Vol. 50. — Issue 10. — P. 1034-1042. 13. Dethloff J. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up // OR Spektrum. — 2001. — Vol. 23. — Issue 1. — P. 79-96. 14. Røpke S., Pisinger D. A unified heuristic for a large class of vehicle routing problems with backhauls // European Journal of Operational Research. — 2006. — Vol. 171. — Issue 3. — P. 750-775. 15. Nagy G., Salhi S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries // European Journal of Operational Research. — 2005. — Vol. 162. — Issue 1. — P. 126-141. 16. Crispim J., Brandão J. Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls // Journal of the Operational Research Society. — 2005. — Vol. 56. — Issue 11. — P. 1296-1302. 17. Montané F.A.T., Galvão R.D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service // European Journal of Operational Research. — 2006. — Vol. 33. — Issue 3. — P. 595-619. 18. Chen J.F., Wu T.H. Vehicle routing problem with simultaneous deliveries and pickups // Journal of the Operational Research Society. — 2006. — Vol. 57. — Issue 5. — P. 579-587. 19. Chen J.F. Approaches for the vehicle routing problem with simultaneous deliveries and pickups // Journal of the Chinese Institute of Industrial Engineers. — 2006. — Vol. 23. — Issue 2. — P. 141-150. 20. Bianchessi N., Righini G. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery // Computers & Operations Research. — 2007. — Vol. 34. — Issue 2. — P. 578-594. 21. Wassan N.A., Wassan A.H., Nagy G. A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries // Journal of Combinatorial Optimization. — 2008. — Vol. 15. — Issue 4. — P. 368-386. 22. Zachariadis E.E., Tarantilis C.D., Kiranoudis C.T. A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service // Expert Systems with Applications. — 2009. — Vol. 36. — Issue 2. — P. 1070-1081. 23. Zachariadis E.E., Tarantilis C.D., Kiranoudis C.T. An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries // European Journal of Operational Research. — 2010. — Vol. 202. — Issue 2. — P. 401-411. 24. Vural A.V. A GA based meta-heuristic for capacity vehicle routing problem with simultaneous pick-up and deliveries. — Master's thesis, Graduate School of Engineering and Natural Sciences, Sabanci University, 2003. 25. Bean J.C. Genetic algorithms and random keys for sequencing and optimization // INFORMS Journal on Computing. — 1994. — Vol. 6. — Issue 2. — P. 154-160. 26. Gajpal Y., Abad P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup // Computers & Operations Research. — 2009. — Vol. 36. — Issue 12. — P. 3215-3223. 27. Çatay B. A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery // Expert Systems with Applications. — 2010. — Vol. 37. — Issue 10. — P. 6809-6817. 28. Ai T.J., Kachitvichyanukul V. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery // Computers & Operations Research. — 2009. — Vol. 36. — Issue 5. — P. 1693-1702. 29. Kennedy J., Eberhart R. Particle swarm optimization // In Proceedings of IEEE international conference on neural networks. — 1995. — Vol. 4. — P. 1942-1948. http://www.sciencedirect.com/science/article/pii/S0957417410002265 http://www.sciencedirect.com/science/article/pii/S0957417410002265 ~ 90 ~ Математичне моделювання в економіці, №1-2, 2017 30. Mingyong L., Erbao C. An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows // Engineering Applications of Artificial Intelligence. — 2010. — Vol. 23. — Issue 2. — P. 188-195. 31. Subramanian A., Ochi L.S., Cabral L.A.F. An efficient ILS heuristic for the vehicle routing problem with simultaneous pickup and delivery // Tech. rep. RT 07/08, Universidade Federal Fluminense. — 2008. — 17 p., available at http://www2.ic.uff.br/PosGraduacao/RelTecnicos/400.pdf. 32. Subramanian A., Drummond L.M.A., Bentes C., Ochi L.S., Farias R. A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery // Computers & Operations Research. — 2010. — Vol. 37. — Issue 11. — P. 1899-1911. 33. Subramanian A., Cabral L.A.F. An ILS based heuristic for the vehicle routing problem with simultaneous pickup and delivery and time limit // Proceedings of the Eighth European Conference on Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science. — 2008. — Vol. 4972. — P. 135-146. 34. Souza M.J.F., Mine M.T., Silva M.S.A., Ochi L.S., Subramanian A. A hybrid heuristic, based on iterated local search and GENIUS, for the vehicle routing problem with simultaneous pickup and delivery // International Journal of Logistics Systems Management. — 2010. — Vol. 10. — Issue 2. — P. 142-156. 35. Gendreau M., Hertz A., Laporte G. New insertion and postoptimization procedures for the traveling salesman problem // Operations Research. — 1992. — Vol. 40. — Issue 6. — P. 1086-1094. 36. Zachariadis E.E., Kiranoudis C.T. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries // Expert Systems with Applications. — 2011. — Vol. 38. — Issue 3. — P. 2717-2726. 37. Hezer S., Kara Y. Solving vehicle routing problem with simultaneous delivery and pick-up using bacterial foraging optimization algorithm // In Proceedings of the 41st International Conference on Computers & Industrial Engineering, University of Southern California, 23-26 October, Los Angeles, California. — 2011. — P. 380-385. 38. Tasan A.S., Gen M. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries // Computers & Industrial Engineering. —2012. — Vol. 62. — Issue 3. — P. 755-761. 39. Wang H.F., Chen Y.-Y. A genetic algorithm for the simultaneous delivery and pickup problems with time window // Computers & Industrial Engineering. — 2012. — Vol. 62. — Issue 1. — P. 84-95. 40. Jun Y., Kim B.-I. New best solutions to VRPSPD benchmark problems by a perturbation based algorithm // Expert Systems with Applications. — 2012. — Vol. 39. — Issue 5. — P. 5641-5648. 41. Goksal F.P., Karaoglan I., Altiparmak F. A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery // Computers & Industrial Engineering. — 2013. — Vol. 65. — Issue 1. — P. 39-53. 42. Liu R., Xie X., Augusto V., Rodriguez C. Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care // European Journal of Operational Research. — 2013. — Vol. 230. — Issue 3. — P. 475-486. 43. Kececi B., Altiparmak F., Kara I. The heterogeneous vehicle routing problem with simultaneous pickup and delivery: A hybrid heuristic approach based on simulated annealing // In CIE44 & IMSS’14 Proceedings, 14-16 October, Istanbul / Turkey. — 2014. — P. 412-423. 44. Wang C., Mu D., Zhao F., Sutherland J.W. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup & delivery and time windows // Computers & Industrial Engineering. — 2015. — Vol. 83. — P. 111-122. 45. Avci M., Topaloglu S. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery // Expert Systems with Applications. — 2016. — Volume 53. — Issue 1. — P. 160-171. http://www2.ic.uff.br/PosGraduacao/RelTecnicos/400.pdf http://www.sciencedirect.com/science/article/pii/S0360835211003482 http://www.sciencedirect.com/science/article/pii/S0360835211003482 http://www.sciencedirect.com/science/article/pii/S0360835211002476 http://www.sciencedirect.com/science/article/pii/S0360835211002476 http://www.sciencedirect.com/science/article/pii/S0957417411015995 http://www.sciencedirect.com/science/article/pii/S0957417411015995 http://www.sciencedirect.com/science/article/pii/S0377221713003585 http://www.sciencedirect.com/science/article/pii/S0377221713003585 http://www.sciencedirect.com/science/article/pii/S0360835215000625 http://www.sciencedirect.com/science/article/pii/S0360835215000625 ~ 91 ~ Математичне моделювання в економіці, №1-2, 2017 46. Zachariadis E.E., Tarantilis C.D., Kiranoudis C.T. The Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints // European Journal of Operational Research. — 2016. — Vol. 251. — Issue 2. — P. 369-386. 47. Dror M., Trudeau P. Savings by split delivery routing // Transportation Science. — 1989. — Vol. 23. — Issue 2. — P. 141-145. 48. Dror M., Trudeau P. Split delivery routing // Naval Research Logistics. — 1990. — Vol. 37. — Issue 3. — P. 383-402. 49. Archetti C., Savelsbergh M., Speranza M.G. Worst-case analysis for split delivery vehicle routing problems // Transportation Science. — 2006. — Vol. 40. — Issue 2. — P. 226-234. 50. Archetti C., Savelsbergh M.W.P., Speranza M.G. To split or not to split: That is the question // Transportation Research Part E: Logistics and Transportation Review. — 2008. — Vol. 44. — Issue 1. — P. 114-123. 51. Archetti C., Speranza M.G. The split delivery vehicle routing problem: A survey // In Golden B.L., Raghavan S., Wasil E.A. The Vehicle Routing Problem: Latest Advances and New Challenges, New York: Springer-Verlag. — 2008. — P. 103-122. 52. Gulczynski D.J., Golden B., Wasil E. Recent Developments in Modeling and Solving the Split Delivery Vehicle Routing Problem // Tutorials in Operations Research, INFORMS. — 2008. — P. 170-180. 53. Belenguer J., Martinez M., Mota E. A lower bound for the split delivery vehicle routing problem // Operations Research. — 2000. — Vol. 48. — Issue 5. — P. 801-810. 54. Archetti C., Hertz A., Speranza M.G. A tabu search algorithm for the split delivery vehicle routing problem // Transportation Science. — 2006. — Vol. 40. — Issue 1. — P. 64-73. 55. Boudia M., Prins C., Reghioui M. An effective memetic algorithm with population management for the split delivery vehicle routing problem // Hybrid Metaheuristics, Lecture Notes in Computer Science. — 2007. — Vol. 4771. — P. 16-30. 56. Chen S., Golden B.,Wasil E. The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results // Networks. — 2007. — Vol. 49. — Issue 4. — P. 318-329. 57. Aleman R.E., Hill R.R. A tabu search with vocabulary building approach for the vehicle routing problem with split demands // Int. J. Metaheuristics. — 2010. — Vol. 1. — Issue 1. — P. 55-80. 58. Archetti C., Bianchessi C., Speranza M.G. A column generation approach for the split delivery vehicle routing problem // Networks. — 2011. — Vol. 58. — Issue 4. — P. 241-254. 59. Berbotto L., Garcia S., Nogales F.G. A randomized granular tabu search heurstic for the split delivery vehicle routing problem // Annals of Operations Research. — 2014. — Vol. 222. — P. 153-173. 60. Khmelev A., Kochetov Y. A hybrid local search for the split delivery vehicle routing problem // International Journal of Artificial Intelligence. — 2015. — Vol. 13. — Issue 1. — P. 147-164. 61. Khmelev A., Kochetov Y. A hybrid VND method for the split delivery vehicle routing problem // Electronic Notes in Discrete Mathematics. — 2015. — Vol. 47. — P. 5-12. 62. Yin C., Bu L., Gong H. Mathematical model and algorithm of split load vehicle routing problem with simultaneous delivery and pickup // International Journal of Innovative Computing, Information and Control. — 2013. — Vol. 9. — Nu. 11. — P. 4497-4508. 63. Tavakkoli-Moghaddam R., Safaei N., Kah M.M.O., Rabbani M. A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing // Journal of the Franklin Institute. — 2007. — Vol. 344. — Issue 5. — P. 406-425. 64. Belfiore P., Yoshizaki H.T.Y. Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries // Computers & Industrial Engineering. — 2013. — Vol. 64. — Issue 2. — P. 589-601. http://www.sciencedirect.com/science/article/pii/S037722171501067X http://www.sciencedirect.com/science/article/pii/S037722171501067X ~ 92 ~ Математичне моделювання в економіці, №1-2, 2017 65. Liu F.H., Shen S.Y. A method for vehicle routing problem with multiple vehicle types and times windows // Proceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering. — 1999. — Vol. 23. — No 4. — P. 526-536. 66. Ho S.C., Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries // Computers & Operations Research. — 2004. — Vol. 31. — Issue 12. — P. 1947-1964. 67. Koç Ç. Heterogeneous Location- and Pollution-Routing Problems. — Thesis for the degree of Doctor of Philosophy in Management Science, University of Southampton, 2015. — 239 p. 68. Koç Ç., Bektaş T., Jabali O., Laporte G. The Fleet Size and Mix Location Routing Problem with Time Windows: Formulations and a Heuristic Algorithm // European Journal of Operational Research. — 2016. — Vol. 248. — Issue 1. — P. 33-51. 69. Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems // Mathematical Programming, Series A. — 2009. — Vol. 120. — Issue 2. — P. 347-380. 70. Baldacci R., Bartolini E., Mingozzi A., Roberti R. An exact solution framework for a broad class of vehicle routing problems // Computational Management Science. — 2010. — Vol. 7. — Issue 3. — P. 229-268. 71. Baldacci R., Toth P., Vigo D. Exact algorithms for routing problems under vehicle capacity constraints // Annals of Operations Research. — 2010. — Vol. 175. — Issue 1. — P. 213-245. 72. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html, http://www.gams.com/, http://aimms.com/, http://www.gurobi.com/. 73. http://www.informatik.uni-koeln.de/abacus/, http://www.coin-or.org/, http://www.gnu.org/software/glpk/glpk.html, http://groups.yahoo.com/group/lp_solve/info/. Стаття надійшла до редакції 30.11.16. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html http://www.gams.com/ http://aimms.com/ http://www.gurobi.com/ http://www.informatik.uni-koeln.de/abacus/ http://www.coin-or.org/ http://www.gnu.org/software/glpk/glpk.html http://groups.yahoo.com/group/lp_solve/info/

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

Репозитарії

Схожі ресурси