基于“分而治之”与列生成的大规模电动车辆路径问题求解方法

佳宁 江(中国矿业大学经济管理学院，中国)

摘要

本文综合运用“分而治之”的策略和列生成算法求解大规模电动车辆路径问题。采用“分治”的求解框架将大规模问题分解成多个小规模问题，并使用列生成方法求解各个小规模问题，最后将求得的解合并成原问题的解。基于京东2018全球优化竞赛的数据集进行了计算验证，说明了“分治”法在求解大规模电动车辆路径问题的优势。

关键词

电动车辆路径问题；分而治之；列生成；大规模组合优化；聚类

参考

Tahir A, Desaulniers G, El Hallaoui I. Integral column generation for set partitioning problems with side constraints[J]. INFORMS Journal on Computing, 2022, 34(4): 2313-2331.

Martin-Iradi B, Ropke S. A column-generation-based matheuristic for periodic and symmetric train timetabling with integrated passenger routing[J]. European Journal of Operational Research, 2022, 297(2): 511-531.

Duman E N, Taş D, Çatay B. Branch-and-price-and-cut methods for the electric vehicle routing problem with time windows[J]. International Journal of Production Research, 2022, 60(17): 5332-5353.

Xia Y, Zeng W, Zhang C, et al. A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones[J]. Transportation Research Part B: Methodological, 2023, 171: 80-110.

DOI: http://dx.doi.org/10.12345/bdai.v6i1.23361