近日，公司管理科学系赖晓凡副教授的学术论文“An Approximation Algorithm for k-Depot Split Delivery Vehicle Routing Problem”被国际顶级期刊 INFORMS Journal on Computing（IJOC）录用并在线发表。该期刊是美国运筹学与管理科学协会（INFORMS）的会刊之一，也是美国德克萨斯大学达拉斯分校（University of Texas, Dallas）选出的用于评估美国商学院前100名研究能力的24本学术期刊（简称UTD24）之一。该研究成果以3044am永利集团官网为第一署名单位，是公司高质量科研成果的重要体现。一直以来，学院及管理科学与工程学科点重视科研发展，鼓励从事前沿科学研究，以高质量产出推进学科的建设。

该论文考虑了一个多仓库有容量的车辆路径问题的变种——需求可拆分情形下的k个车场车辆路径问题，其中，k为一个大于等于2的常数。该问题在物流运输领域具有广泛的应用，但却属于一类强NP难问题（Strongly NP-hard），因此理论上无法在多项式时间内求得最优解。为了高效地求解此问题，基于新提出的松弛问题、圈切分算法以及车辆分配算法，该论文提出了一套可用于求解该问题及其变种的全新求解框架。基于该框架所得到的近似算法不仅具有多项式的求解时间，而且能在理论上保证所求解的质量。此外，该近似算法还被进一步用于设计高效快速的启发式算法，进而可更好地被应用于企业实践中。

论文的引用信息：Xiaofan Lai, Liang Xu, Zhou Xu, Yang Du (2023) An Approximation Algorithm for k-Depot Split Delivery Vehicle Routing Problem. INFORMS Journal on Computing, forthcoming.

论文的链接如下：https://pubsonline.informs.org/doi/10.1287/ijoc.2021.0193.