车辆路径问题的三阶段求解方法研究

作者：黄敏芳,胡祥培,王征,Amy Z.Zeng

摘要：针对由车辆路径问题规模的增大带来求解空间组合爆炸这一难点，从缩减解答空间入手，以节省求解时空为突破口，综合运用知识工程、模糊聚类分析、状态空间搜索理论和运筹学整数规划理论，提出一种求解车辆路径问题的三阶段求解方法。第一阶段分析物流配送过程的主要影响因素，根据相关因素对客户进行初步划分，然后采用模糊聚类分析方法将各配送区域中的客户进行细分；第二阶段采用带控制策略的深度优先搜索算法生成备选的车辆路径方案集合；第三阶段建立整数规划求解模型，并根据邻域规则将求得的解映射为实际问题中的行车方案。最后运用算例验证上述方法的有效性。

发文机构：大连理工大学管理学院 华北电力大学工商管理学院 Department of Management

关键词：车辆路径问题模糊聚类分析知识表示状态空间整数规划模型vehicle routing problemfuzzy clusteringknowledge representationstate spaceinteger programming model

分类号： U116[交通运输工程]