Вкр. Факультет прикладной математики процессов управления Кафедра математического моделирования энергетических систем Широких Вячеслав Андреевич
 Скачать 1.83 Mb.
|
|
Таблица 6. Различные показатели результатов экспериментов. Показатель ALNS DALNS Интервал Среднее Интервал Среднее Улучшении при кооперации: Среднее 1,1% 25,1% 12,24% 2,18% 20,65% 9,77% Минимум -17,88% 27,78% 11,64% -3,7% 24,13% 9,52% Пересечение интервалов 0% 100% 71,06% 0% 100% 65,4% Улучшение DALNS - - - 0,014% 43,95% 15,25% 49 4.6. Анализ устойчивости коалиций Для дальнейшего анализа, введём в рассмотрение некоторые понятия из кооперативной теории игр. Определение. Дележом выигрыша коалиции 𝑆 в кооперативной игре называется вектор 𝑥 𝑆 = (𝑥 1 , 𝑥 2 , … , 𝑥 |𝑆| ), удовлетворяющий условиям: 𝑥 𝑖 ≤ 𝑐({𝑖}), ∀𝑖 ∈ 𝑆 (индивидуальная рациональность) ∑ 𝑥 𝑖 𝑖∈𝑆 = 𝑐(𝑆) (коллективная рациональность) Определение. Будем говорить, что коалиция 𝑆 устойчива относительно дележа 𝑥, если для 𝑥 выполнены условия дележа, а также выполняется условие: 𝑥 𝑖 𝑆 < 𝑥 𝑖 𝑇 , ∀𝑖 ∈ 𝑆, ∀𝑇 ≠ 𝑆, 𝑖 ∈ 𝑇 (условие стабильности) Целью дальнейшего анализа является исследование свойств устойчивости полной коалиции: 𝑆 = 𝑀. Задача построения не имеет единственного «правильного» решения, поскольку, используя различные принципы «справедливости» разделения выигрыша, можно получить различные векторы дележей. Поэтому, для более объективного анализа, будем рассматривать четыре различных метода построения: вектор Шепли, MSC-вектор, вектор метода разницы цен и вектор метода равных доходов. Вектор Шепли [48] был предложен L.S.Shapley в 1953 году. Идея метода состоит в том, чтобы разделить выигрыш согласно математическому ожиданию вклада каждого игрока в формирование полной коалиции. Элемент вектора Шепли вычисляется следующим образом: 50 𝑆ℎ 𝑖 = ∑ |𝑆|! (𝑛 − |𝑆| − 1)! 𝑛! (𝑐(𝑆⋃{𝑖}) − 𝑐(𝑆)) 𝑆⊆𝑁∖{𝑖} MSC-вектор, или Marginal Subcore element [49] был предложен В.В.Захаровым в 2008 году. Этот метод позволяет выбирать вектор из С-ядра игры согласно относительному (marginal) вкладу игрока в выигрыш коалиции. Элемент MSC-вектора вычисляется с помощью следующих формул: 𝑀𝑆𝐶 𝑖 = 𝜉 𝑖 0 + 𝛼 𝑖 𝑚𝑠𝑐 (𝑐(𝑁) − ∑ 𝜉 𝑗 0 𝑗∈𝑁 ), 𝛼 𝑖 𝑚𝑠𝑐 = ∑ (𝑐(𝑆⋃{𝑖})−𝑐(𝑆)) 𝑆⊆𝑁∖{𝑖} ∑ ∑ (𝑐(𝑆⋃{𝑗})−𝑐(𝑆)) 𝑆⊆𝑁∖{𝑗} 𝑗∈𝑁 , 𝜉 𝑖 0 : max(∑ 𝜉 𝑖 𝑛 𝑖=1 ) , 𝑠𝑏𝑗. 𝑡𝑜: ∑ 𝜉 𝑖 𝑖∈𝑆 ≤ 𝑐(𝑆), ∀𝑆 ≠ 𝑁. Метод разницы цен, или Cost Gap Method [50] был предложен S.H.Tijs & T.S.H.Driessen в 1986 году. Идея метода состоит в том, чтобы распределять неразделимые затраты игроков согласно их функциям ценовой разницы, отражающим их индивидуальный вклад. Элементы вектора вычисляются по следующим правилам: 𝐶𝐺𝑀 𝑖 = 𝑚 𝑖 + 𝑤 𝑖 𝑔(𝑁), 𝑚 𝑖 = 𝑐(𝑁) − 𝐶(𝑁\{𝑗}), 𝑔(𝑆) = 𝑐(𝑆) − ∑ 𝑚 𝑗 𝑗∈𝑆 , 𝑤 𝑖 = 𝑊 𝑖 ∑ 𝑊 𝑗 𝑗∈𝑁 , 𝑊 𝑖 = arg min 𝑆:𝑖∈𝑆 𝑔(𝑆). Метод равных доходов, или Equal Profit Method [51] был предложен M. Frisk в 2010 году. Идеей данного подхода является попытка равного разделения относительных доходов игроков (относительно их индивидуальных выигрышей). 51 Вектор дележа в данном методе получается при решении следующей задачи минимизации: 𝐸𝑃𝑀 𝑖 = 𝑥 𝑖 : min 𝑓 , при ограничениях: 𝑓 ≥ 𝑥 𝑖 𝑐({𝑖}) − 𝑥 𝑗 𝑐({𝑗}) , ∀(𝑖, 𝑗), ∑ 𝑥 𝑖 𝑖∈𝑁 = 𝑐(𝑁), ∑ 𝑥 𝑖 𝑖∈𝑆 ≤ 𝑐(𝑆), ∀𝑆 ≠ 𝑁. Для анализа были использованы данные вычислительных экспериментов п.5.4. Данные экспериментов рассматривались в двух измерениях: по методу выбора решения из статистической выборки – рассматривались средние и минимальные значения, и по алгоритму решения – ALNS и DALNS. В качестве первого и исходного набора данных рассматривался случай, в котором эвристические значения 𝑓 ℎ были приняты в качестве характеристической функции. Для второго набора данных на основе значений 𝑓 ℎ для построения характеристической функции был использован метод прямой индукции коалиций (DCI). Таким образом, для каждого из 18 тестовых примеров было рассмотрено 8 возможных ситуаций: согласно методу нахождения решения (ALNS или DALNS), методу выбора решения из выборки (среднее или минимальное) и методу построения характеристической функции (с = 𝑓 ℎ или 𝑐 = 𝐷𝐶𝐼(𝑓 ℎ )). В таблице 7 представлены частоты строгой устойчивости и строгой неустойчивости полной коалиции в разрезах разных измерений и в целом по набору данных при использовании четырёх различных методов построения дележа. Таким образом, по представленным результатам можно сравнить устойчивость решений по различным показателям. Отметим, что сумма одинаковых показателей в левой и в правой части таблицы не всегда соответствует общему числу примеров, поскольку существуют также ситуации, 52 в которых игрокам безразлично, участвовать в коалиции или работать индивидуально, так как их индивидуальные затраты при этом не изменяются – это ситуации, в которых ∃𝑇 ≠ 𝑆: 𝑥 𝑖 𝑆 = 𝑥 𝑖 𝑇 Таблица 7. Результаты анализа устойчивости Частоты устойчивости Частоты неустойчивости Shapley MSC CGM EPM Shapley MSC CGM EPM 𝑓 ℎ 41 28 39 41 31 44 33 25 DCI 45 28 42 41 23 42 26 21 ALNS 46 30 42 42 25 41 29 21 DALNS 40 26 39 40 29 45 30 25 Среднее 47 32 47 42 25 40 25 22 Минимум 39 24 34 40 29 46 34 24 В общем 86 56 81 82 54 86 59 46 Всего % 59.7% 39% 56.3% 57% 37.5% 59.7% 41% 32% Полученные результаты показывают значительную выгоду использования метода DCI для построения субаддитивной характеристической функции: построенные с помощью этого метода игры обладают большей степенью устойчивости. По результатам анализа, можно наблюдать, что эффективность алгоритма также вносит существенный вклад в обнаружение нестабильности. Так, более эффективный DALNS показывает меньшую степень устойчивости среди исследуемых ситуации. Однако, учитывая, что решения DALNS ближе к оптимальному, это более правдоподобно отражает реальную картину в кооперативной игре. Наконец, можно видеть, что устойчивость коалиций существенно зависит от использованного для дележа метода. Среди использованных методов, наиболее устойчивым оказались дележи при помощи вектора Шепли: в 59,7% случаев полная коалиция была устойчива. Наименее устойчивым оказался MSC- 53 вектор: при его использовании, только в 39% ситуаций наблюдалась устойчивость полной коалиции. Заключение Таким образом, была проведена работа по обширному исследованию различных математических моделей задач маршрутизации и был проведён сравнительный анализ экспериментальных показателей в разных задачах. В ходе работы была разработана эффективная реализация на языке C++ современного алгоритма эвристической оптимизации ALNS, и была проведена адаптация этого алгоритма на широкий круг различных задач. На базе созданной реализации была собрана обширная база экспериментальных данных по нескольким актуальным задачам маршрутизации. Был проведён анализ всех полученных данных, по результатам которого были сделаны выводы: об эффективности нового метода Динамической адаптации и актуальности его использования в тех или иных задачах, основываясь на новом методе экспериментальной оценки Состоятельности во времени; о существенных перспективах исследования и выгоде практического применения новой модели Кооперативной игры маршрутизации запасов; об устойчивости различных подходов к кооперации, основанных на различных методах дележа и различных методах построения характеристической функции игры; о важности вычисления характеристической функции по новому методу Прямой индукции коалиций для повышения устойчивости кооперации в задачах маршрутизации. 54 По результатам проведённой в совокупности научной работы были опубликованы работы «Dynamic adaptive large neighborhood search for inventory routing problem» в журнале Modelling, Computation and Optimization in Information Systems and Management Sciences издательства Springer, «Heuristic evaluation of the characteristic function in the Cooperative Inventory Routing Game» в Journal on Vehicle Routing Algorithms издательства Springer и подготовлена статья «Проблема формирования устойчивых коалиций в кооперативной игре маршрутизации и управления запасами» в журнал Математическая теория игр и её приложения. Список литературы 1. Модели и методы теории логистики: Учебное пособие / Под ред. В. С. Лукинского. СПб.: Питер, 2007. 448 с. 2. Задача коммивояжёра. // https://ru.wikipedia.org/wiki/Задача коммивояжёра 3. Dantzig G., Fulkerson R., Johnson S. Solution of a large-scale traveling-salesman problem // Journal of the operations research society of America. 1954. Vol. 2, No 4. P. 393-410. 4. Flood M. M. The traveling-salesman problem // Operations Research. 1956. Vol. 4, No 1. P. 61-75. 5. Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. – Springer, Boston, MA, 1972. – С. 85-103. 6. Dantzig G. B., Ramser J. H. The truck dispatching problem //Management science. – 1959. – Т. 6. – №. 1. – С. 80-91. 7. Clarke G., Wright J. W. Scheduling of vehicles from a central depot to a number of delivery points // Operations research. 1964. Vol. 12, No 4. P. 568-581. 8. Wilson N. H. M. et al. Scheduling algorithms for a dial-a-ride system. – Massachusetts Institute of Technology. Urban Systems Laboratory, 1971. 55 9. Stein D. M. Scheduling dial-a-ride transportation systems //Transportation Science. – 1978. – Т. 12. – №. 3. – С. 232-249. 10. Assad A., Golden B., Dahl R., Dror M. Design of an inventory routing system for a large propane-distribution firm // Proc. of Southeast TIMS Conference, 1982. P. 315-320. 11. Bell W. J., Dalberto L. M., Fisher M. L., Greenfield A. J., Jaikumar R., Kedia P., Mack R. G., Prutzman P. J. Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer // Interfaces. 1983. Vol. 13, No 6. P. 4-23. 12. Dumas Y. et al. An optimal algorithm for the traveling salesman problem with time windows //Operations research. – 1995. – Т. 43. – №. 2. – С. 367-371. 13. Bräysy O., Gendreau M. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms //Transportation science. – 2005. – Т. 39. – №. 1. – С. 104-118. 14. Dumas Y., Desrosiers J., Soumis F. The pickup and delivery problem with time windows //European journal of operational research. – 1991. – Т. 54. – №. 1. – С. 7-22. 15. Liu S. C., Lee W. T. A heuristic method for the inventory routing problem with time windows //Expert Systems with Applications. – 2011. – Т. 38. – №. 10. – С. 13223-13231. 16. Picard J. C., Queyranne M. The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling //Operations Research. – 1978. – Т. 26. – №. 1. – С. 86-110. 17. Malandraki C., Daskin M. S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms //Transportation science. – 1992. – Т. 26. – №. 3. – С. 185-200. 56 18. Xiang Z., Chu C., Chen H. The study of a dynamic dial-a-ride problem under time- dependent and stochastic environments //European Journal of Operational Research. – 2008. – Т. 185. – №. 2. – С. 534-551. 19. Cho D. W. et al. An adaptive genetic algorithm for the time dependent inventory routing problem //Journal of Intelligent Manufacturing. – 2014. – Т. 25. – №. 5. – С. 1025-1042. 20. Gendreau M., Laporte G., Séguin R. Stochastic vehicle routing //European Journal of Operational Research. – 1996. – Т. 88. – №. 1. – С. 3-12. 21. Zhu L., Sheu J. B. Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands //European Journal of Operational Research. – 2018. 22. Bertazzi L. et al. A stochastic inventory routing problem with stock-out //Transportation Research Part C: Emerging Technologies. – 2013. – Т. 27. – С. 89-107. 23. Mavrovouniotis M., Yang S. Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors //Applied Soft Computing. – 2013. – Т. 13. – №. 10. – С. 4023-4037. 24. Pillac V. et al. A review of dynamic vehicle routing problems //European Journal of Operational Research. – 2013. – Т. 225. – №. 1. – С. 1-11. 25. Berbeglia G., Cordeau J. F., Laporte G. Dynamic pickup and delivery problems //European journal of operational research. – 2010. – Т. 202. – №. 1. – С. 8-15. 26. Coelho L. C., Cordeau J. F., Laporte G. Heuristics for dynamic and stochastic inventory-routing // Computers & Operations Research. 2014. Vol. 52. P. 55-67. 27. Nagata Y., Bräysy O., Dullaert W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows //Computers & operations research. – 2010. – Т. 37. – №. 4. – С. 724-737. 57 28. Ropke S., Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows //Transportation science. – 2006. – Т. 40. – №. 4. – С. 455-472. 29. Erdoğan S., Miller-Hooks E. A green vehicle routing problem //Transportation Research Part E: Logistics and Transportation Review. – 2012. – Т. 48. – №. 1. – С. 100-114. 30. Soysal M., Çimen M., Demir E. On the mathematical modeling of green one-to- one pickup and delivery problem with road segmentation //Journal of Cleaner Production. – 2018. – Т. 174. – С. 1664-1678. 31. Soysal M. et al. Modeling a green inventory routing problem for perishable products with horizontal collaboration //Computers & Operations Research. – 2018. – Т. 89. – С. 168-182. 32. Archetti C., Bertazzi L., Laporte G., Speranza M. G. A branch-and-cut algorithm for a vendor-managed inventory-routing problem // Transportation Science. 2007. Vol. 41, No 3. P. 382-391. 33. Desaulniers G., Rakke J. G., Coelho L. C. A branch-price-and-cut algorithm for the inventory-routing problem // Les Cahiers du GERAD G-2014-19, GERAD, Montréal, Canada. 2014. 34. Solving the pla85900 TSP // http://www.math.uwaterloo.ca/tsp/pla85900/compute/compute.htm 35. Concorde Home. Benchmark information // http://www.math.uwaterloo.ca/tsp/concorde/benchmarks/bench.html 36. Coelho L. C., Cordeau J. F., Laporte G. The inventory-routing problem with transshipment //Computers & Operations Research. – 2012. – Т. 39. – №. 11. – С. 2537-2548. 37. Archetti C., Bertazzi L., Hertz A., Speranza M. G. A hybrid heuristic for an inventory routing problem // INFORMS Journal on Computing. 2012. Vol. 24, No 1. P. 101-116. 58 38. Hemmelmayr V. C., Cordeau J. F., Crainic T. G. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics //Computers & operations research. – 2012. – Т. 39. – №. 12. – С. 3215-3228. 39. Беллман Р. Динамическое программирование. М.: Изд-во иностранной литературы, 1960. 400 с. 40. Zakharov V. V., Schegryaev A. N. Multi-period cooperative vehicle routing games // Contributions to Game Theory and Management, 2014. Vol. 7. P. 349-359. 41. Shirokikh V. A., Zakharov V. V. Dynamic adaptive large neighborhood search for inventory routing problem //Modelling, Computation and Optimization in Information Systems and Management Sciences. – Springer, Cham, 2015. – С. 231- 241. 42. Leandro C. Coelho. Problem Instances: Inventory-Routing. // http://www.leandro- coelho.com/instances/inventory-routing 43. PDPTW. Li & Lim benchmark. // https://www.sintef.no/projectweb/top/pdptw/li- lim-benchmark 44. Verdonck L. et al. Collaborative logistics from the perspective of road transportation companies //Transport Reviews. – 2013. – Т. 33. – №. 6. – С. 700- 719. 45. Guajardo M., Rönnqvist M. A review on cost allocation methods in collaborative transportation //International transactions in operational research. – 2016. – Т. 23. – №. 3. – С. 371-392. 46. Krajewska M. A. et al. Horizontal cooperation among freight carriers: request allocation and profit sharing //Journal of the Operational Research Society. – 2008. – Т. 59. – №. 11. – С. 1483-1491. 47. Kimms A., Kozeletskyi I. Core-based cost allocation in the cooperative traveling salesman problem //European Journal of Operational Research. – 2016. – Т. 248. – №. 3. – С. 910-916. 59 48. Shapley L. S. A value for n-person games //Contributions to the Theory of Games. – 1953. – Т. 2. – №. 28. – С. 307-317. 49. Zakharov V. et al. Comparing solutions in joint implementation projects //International Game Theory Review. – 2008. – Т. 10. – №. 01. – С. 119-128. 50. Tijs S. H., Driessen T. S. H. Game theory and cost allocation problems //Management Science. – 1986. – Т. 32. – №. 8. – С. 1015-1028. 51. Frisk M. et al. Cost allocation in collaborative forest transportation //European Journal of Operational Research. – 2010. – Т. 205. – №. 2. – С. 448-458. Приложения Приложение 1: Агрегированные данные выч. экспериментов п.4.5. Размерность примера Примеры IRP в основе Алгоритм Минимум/Среднее/Максимум для ситуации: 1,2,3 1,23 2,13 3,12 123 (3,90, 𝑙𝑜𝑤) abs1n30 abs2n30 abs3n30 ALNS 9223.96 10308.5 13076.3 8203.18 9898.38 12090. 8117.86 10335.6 12763. 8030.97 9937.85 12102.6 7171.8 9284.36 10999.3 DALNS 9223.96 10305.5 12989.8 8203.18 9855.08 12053.7 8117.86 10290.5 12044.8 8030.97 9864.3 11992.6 7058.08 9239.98 10929. (3,90, ℎ𝑖𝑔ℎ) abs1n30 abs2n30 |