03 января 2016г.
Аннотация. Работа посвящена математическим методам решения задачи маршрутизации, возникающей в транспортно-логистической сфере.
Ключевые слова: экономико-математические модели транспортно-логистических систем, транспортная задача в сетевой постановке, задача коммивояжёра, муравьиный алгоритм.
2014-й год стал переломным как в политическом плане, так и в экономической сфере для многих стран мира. Для России он ознаменовался не только радикальными сдвигами во внешнеполитической позиции, зримыми переменами в отношениях с рядом ведущих мировых держав, прежде всего, он ознаменовался осознанием качественно новых вызовов. Достойный и адекватный ответ на них становится важнейшей целью развития страны на ближайшие годы. Курс на повышение уровня взаимной интеграции регионов, активное развитие арктических территорий и Дальнего Востока позиционируется как одна из важнейших компонент государственной политики.
Проблема дисгармоничной зависимости российской экономики от экспорта энергоресурсов, с одной стороны, и импорта высокотехнологичной продукции, с другой, признана повсеместно. Одновременно рецепты еѐ преодоления носят более, чем общий характер и сводятся к декларациям о том, что «с нефтяной иглы нужно слезать», а «собственное производство нужно стимулировать».
Очевидно, что необходимым условием развития собственного производства является обеспечением конкурентоспособности российских товаров, по крайней мере, на внутреннем рынке. Важнейшим фактором, против конкурентных преимуществ товаров отечественного производства является высокий уровень транспортно-логистических издержек, обусловленный геополитическими условиями России.
Данное обстоятельство предопределяет кардинальную важность мер по снижению данного вида затрат как на уровне экономической системы страны, так и на уровне отдельных регионов. Такая работа предполагает непрерывное качественное совершенствование уровня научных исследований, разработку новых математических моделей, отражающих процессы движения транспортно-логистических потоков, и методов, позволяющих рационализировать и оптимизировать данные процессы.
Отметим, что за период, истекший с момента возникновения исследования операций, как научной дисциплины было разработано весьма значительное число оптимизационных задач и методов решений, так или иначе, имеющих отношение к транспортно-логистическим проблемам. Данные вопросы получили достаточно подробное отражение, как в научных первоисточниках (Канторович (1942)44, Данциг (1959)45), так и в учебной литературе, см., например, Абрамов, Капустин (1981)46, Ермольев (1979)47, Конюховский (2008)48.
В одной из наиболее простых своих постановок транспортная задача формулируется следующим образом. Товары, которые хранятся на «складе» (в более общем случае – нескольких складах), требуется доставить до пунктов потребления. При этом нужно выбрать маршруты, использование которых обеспечить минимальные издержки при выполнении условий на пропускные способности и грузоподъемность транспортных средств. В технологическом плане подобные задачи удобно формулировать в терминах теории графов. Предположим, что
имеющаяся транспортная сеть может быть описана неориентированным графом G(V, A), где
· V = {v0, v1 , … , vn }. – множество вершин графа: v0 – начальная точка (склад), откуда грузовые
транспортные средства развозят товары по пунктам потребления, соответственно, v1, … , vn – пункты потребления;
· A = (vi , vj |vi , vj ∊ V, i ≠ j} – ребра графа, показывающие переход из i - го пункта в j - й, условие i ≠ j
означает, что граф без циклов, что является логичным с содержательной точки зрения.
· C = cij – матрица стоимостей, которая показывает сколько «стоит» переход из i-го пункта в j-й, может
быть выражена непосредственно расстояниями между пунктами, или временем, которое необходимо для
перехода, или же затратами на переход;
· bi – потребность i - го пункта;
· Rk – маршрут для k – го транспортного средства;
· C(Rk ) – стоимость маршрута для k – го транспортного средства;
· m – количество транспортных средств (определяется, исходя из их грузоподъемности и общей
потребности в товарах).
Целью управления в рамках описанной ситуации является нахождение оптимального маршрута, т.е. маршрута для каждого транспортного средства, обеспечивающего минимальные издержки на доставку. Целевая функция будет выглядеть следующим образом.
К настоящему моменту разработано большое количество методов решения задачи (1). Однако все они, так или иначе, сталкиваются с принципиальной и труднопреодолимой проблемой, а именно, проблемой резкого возрастания объѐма вычислений при увеличении размерности задачи. По существу, каким бы эффективным и «изощрённым» ни был метод решения, он не может предоставить гарантий получения результата в «реальных» масштабах времени безотносительно к размерности задачи. Более того, методы, которые успешно конкурируют между собой в случае задач малой и средней размерности, как правило, оказываются равно полезными (и бесполезными) для «больших» задач.
Это в полной мере относится и к весьма популярному семейству методов, получившему название методов ветвей и границ. Методы, принадлежащие к нему, построены на двух «идейно несложных» процедурах:
· разбиения очередного рассматриваемого множества допустимых планов на подмножества, вследствие чего должны отсекаться неэффективные планы (маршруты);
· оценивания (получения границ) для множеств, образовавшихся в результате ветвления; при этом для очередного ветвления выбирается множество с наилучшей оценкой.
Нередко данные методы реализуются в комплексе с процедурами кластеризации. В частности, применяются т.н. двухэтапные эвристические методы. Они предполагают сочетание двух этапов. На первом этапе по какому-либо признаку производится разбиение пунктов транспортной сети на однотипные подмножества (кластеры). При этом разбиение ведѐтся в предположении, что пункты, оказавшиеся в одном кластере, могут быть обслужены одним транспортным средством. На втором этапе, осуществляется определение оптимального маршрута внутри кластера. Данная задача может быть сведена к классической проблеме коммивояжёра. На одном из методов еѐ решения мы и остановимся в данной работе.
44 Kantorovich L. On the translocation of masses // C. R. (Doklady) Acad. Sci. URSS (N. S.), 37:199-201, 1942.
45 Dantzig, G.B., Ramser, J.H. The Truck Dispatching Problem.Management, 1959.P. 80-91
46 Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л., 1981.
47 Ермольев Ю.М., Ляшко И.И., Михалевич В.С., Тюптя В.И. Математические методы исследования операций. Киев, 1979.
48 Конюховский П.В. Математические методы исследования операций в экономике / Санкт-Петербургский государственный университет.Санкт-Петербург, 2008.
Заметим, что процедура кластеризации может проводиться либо на основе очевидных (например, территориальных) признаков, либо основываться на специальных алгоритмах. В частности, в этой связи может быть упомянут алгоритм Джиллетта–Миллера, называемый также алгоритмом заметаний (sweepalgorithm).49
Алгоритм заметаний является эвристическим и предполагает проведение кластеризации на основе координат пунктов потребления. За точку начала координат принимается склад. Из начала координат проводится луч до самого отдаленного пункта. Далее при последовательном изменении угла наклона луча происходит добавление к маршруту новых пунктов (до достижения предела по грузоподъемности). Затем процесс кластеризации продолжается аналогичным образом для оставшихся пунктов.
Достаточно интересным и перспективным инструментом решения задачи коммивояжера является мета- эвристический алгоритм, получивший название муравьиного. Он был предложен М. Дориго (1992).50 Данный алгоритм показал свою эффективность на многих известных задачах.51 Напомним, что целью коммивояжера в рамках решаемой задачи является нахождение циклического маршрута с наименьшей стоимостью, охватывающего все пункты. При этом каждый пункт должен только лишь один раз входить в маршрут.
Рассмотрим ситуацию, когда коммивояжер находится в пункте i. У него есть задача попасть в следующий пункт и выбор, который он будет осуществлять, будет определяться вероятностью перехода. В зависимости от того, в каком пункте находится коммивояжер, будем присваивать ему индекс k, который показывает, из какого исходного пункта следует коммивояжер. Для коммивояжера с индексом kформируется вероятность попасть из i- го пункта в j-й, который он еще не посетил и к которому имеется прямой переход (есть соответствующее ребро из i в j). Вероятность попасть из i-го в j-й пункт определяется правилом
где
η𝑖𝑗 – обратное число длины маршрута из i в j (так называемая «видимость»), чем больше длина перехода, тем меньше желание коммивояжера сделать данный переход;
τ𝑖𝑗 – привлекательность ребра между вершинами i и j (матрица 𝜏 показывает некий накопленный опыт самого коммивояжера, то есть коммивояжер будет «делать свои расчеты», исходя не только из длины маршрута из i в j , но и руководствуясь своим опытом);
α – эластичность перехода по опыту, которая показывает то, в какой степени коммивояжер будет опираться на опыт при выборе следующего пункта (α=0 означает полное игнорирование накопленного опыта);
β – эластичность перехода по видимости, которая показывает то, в какой степени коммивояжер будет опираться на стоимость/длину перехода при выборе следующего пункта (β=0 означает, что коммивояжеру не важна стоимость перехода).
Итак, в числителе получается общая привлекательность перехода из i в j, в знаменателе – «сумма привлекательностей» перехода для всех допустимых переходов из i-й вершины. В итоге получаем некоторую долю привлекательности j-го пункта в совокупности всех допустимых пунктов. В результате получаются вероятности, по которым коммивояжер перейдет в тот или иной пункт. Далее следует объяснить, по какому правилу обновляется опыт коммивояжера.
Значение Δ𝜏𝑘 рассчитывается только по рѐбрам, вошедшим в маршрут. Параметр 𝑄отражает «меру учѐта» накопленного опыта и выбирается исходя из эмпирических соображений, 𝐿𝑘 – длина пройденного маршрута. При этом на следующей итерации опыт может частично «забываться». Степень «забывчивости» регулируется отдельным параметром 𝑝∈[0;1]. Таким образом, привлекательность ребра, соединяющего вершины i и j, принимает вид
49 Gillett B.E. A heuristic algorithm for the vehicle dispatch problem / B.E. Gillett, L.R. Miller // Operations Research. 1974. № 22. P. 340–349
50 Dorigo M., Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy, 1992
51 Штовба, С.Д. Муравьиныеалгоритмы// Exponenta Pro. Математика в приложениях, 2003, №4, с.70-75.
В результате, коммивояжер, последовательно выбирая вершины по рандомизированному правилу, обходит все пункты и возвращается в исходный. Так происходит на каждой итерации (в связи с тем, что на каждой итерации рассматриваются ситуации, в которых исходными пунктами коммивояжера являются разные вершины, то выбирается наилучший результат итерации). Процесс решения задачи коммивояжера представлен на Рисунке 1.
Рис.1. Зависимость между длиной маршрута и числом итераций решения задачи
Ещѐ раз подчеркнѐм, представленная постановка задачи маршрутизации является лишь единичным примером обширного множества транспортно-логистических
проблем. Почти столь же обширны и разнообразны семейства и методов,
которые могут быть использованы для их решения. Из этого в первую очередь вытекает необходимость дальнейшего совершенствования и развития методов решения транспортно-логистических задач.
Кратко остановимся на комплексе сопутствующих проблем, от успеха решения которых в существенной степени зависит решение задач оптимальной (рациональной) маршрутизации транспортных потоков. Нельзя не согласиться с тем, что результативность применения экономико-математических моделей и методов существенно зависит от качества (достоверности) исходных данных, закладываемых в основу расчѐтов
оптимальных планов. Неадекватность и погрешности во входной информации могут серьѐзно обесценить качество выводов независимо от свойств применяемой математической модели. Один из возможных вариантов решения может базироваться на методах работы со стохастическими данными, достаточно успешно зарекомендовавшими себя в финансовой сфере. Речь, в данном случае идѐт, о т.н. моделях стохастической динамики финансовых ресурсов52, а также о стохастических моделях оценки зависимостей между экономическими показателями.53
Также нужно принимать во внимание, что модели, ориентированные на некоторого абстрактного субъекта, способного осуществлять централизованное оптимальное управление исходя из некоторой абстрактно- обобщѐнной системы целей не вполне адекватны реалиям современной экономики. Она характеризуется острой конкуренцией разнообразных групп интересов, разнородных и разномасштабных в организационном плане и, очевидно, неуправляемых из единого центра. Для отражения данной специфики в транспортно-логистических моделях может быть использован инструментарий современной теории игр. В частности, достаточно эффективным может оказаться использование аппарата игр сотрудничества54,55, либо аппарата стохастических кооперативных игр56.
45 Конюховский П.В. Моделирование стохастической динамики финансовых ресурсов. СПб., Изд-во СПбГУ. 2002.
46 Конюховский П.В., Хованов Н.В., Чудовская Л.А.Оценка по экспертной информации функциональной зависимости финансово-экономических показателей // Вестник Санкт-Петербургского университета. Серия 5: Экономика. 2009. № 2. С. 121-133.
47 Конюховский П.В., Малова А.С. Применение методов теории игр в анализе отношений сотрудничества между экономическими субъектами// Вестник Орловского государственного университета. Серияновыегуманитарныеисследования. 2012, № 3 (23). C. 192-197.
48 Konyukhovskiy P.V., Malova A.S.Game-theoreticmodelsofcollaborationamong economic agents // Contributions to Game Theory and Management.2013. vol. 6. pp. 211-221.
49 Конюховский, П.В. Применение стохастических кооперативных игр при обосновании инвестиционных проектов // Вестник С. Петерб. ун-та. Сер. 5 «Экономика». -
2012. - Выпуск 4 (декабрь). C. 134-143.
Резюмируя сказанное, остаѐтся признать, что необходимым условием успешного решения задач, возникающих в транспортно-логистическом комплексе, является непрерывное совершенствование методов и алгоритмов, что, в свою очередь, предполагает активное расширение набора аппаратных средств и инструментов.
Список литературы
1.
Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л., 1981.
2.
Ермольев Ю.М., Ляшко И.И.,
Михалевич В.С., Тюптя В.И. Математические методы исследования операций. Киев, 1979.
3.
Конюховский П.В. Моделирование стохастической динамики финансовых ресурсов. СПб., Изд-во СПбГУ. 2002.
4.
Конюховский П.В., Хованов Н.В., Чудовская Л.А.Оценка по экспертной информации функциональной зависимости финансово-экономических показателей // Вестник Санкт-Петербургского университета. Серия 5: Экономика. 2009. № 2. С. 121-133.
5.
Конюховский П.В., Малова
А.С. Применение методов теории игр в анализе отношений сотрудничества между экономическими субъектами // Вестник Орловского государственного университета. Серия новые гуманитарные исследования. 2012, № 3 (23). C. 192-197.
6.
Конюховский, П.В. Применение стохастических кооперативных игр при обосновании инвестиционных проектов // Вестник С. Петерб. ун-та. Сер. 5 «Экономика». - 2012. - Выпуск 4 (декабрь). C. 134-143.
7.
Штовба, С.Д. Муравьиные алгоритмы// ExponentaPro. Математика в приложениях, 2003, №4, с.70-75.
8.
Dantzig, G.B., Ramser, J.H. The Truck Dispatching Problem. Management, 1959. P. 80-91.
9.
Dorigo M., Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy, 1992.
10. Gillett B.E. A heuristic algorithm for the vehicle dispatch problem / B.E. Gillett, L.R. Miller // Operations Research. 1974. № 22. P. 340–349.
11. Kantorovich L. On the translocation of masses // C.R. (Doklady) Acad. Sci. URSS (N. S.), 37:199-201, 1942.
12. Konyukhovskiy P.V., Malova A.S. Game-theoreticmodelsofcollaborationamong economic agents // Contributions to Game Theory and Management. 2013. vol. 6. pp. 211-221.
