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

A Three-stage Intelligent Solution Approach to Vehicle Routing Problem

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

机构地区：[1]大连理工大学管理学院,辽宁大连116023 [2]华北电力大学工商管理学院,北京102206 [3]Department of Management, Worcester Polytechnic Institute, MA 01609, USA

出　　处：《管理科学》2009年第3期37-46,共10页Journal of Management Science

基　　金：国家自然科学基金(70725004,70571009,70801008);高等学校博士点基金(20060141013);辽宁省高等学校优秀人才支持计划([2006]124号)~~

摘　　要：针对由车辆路径问题规模的增大带来求解空间组合爆炸这一难点,从缩减解答空间入手,以节省求解时空为突破口,综合运用知识工程、模糊聚类分析、状态空间搜索理论和运筹学整数规划理论,提出一种求解车辆路径问题的三阶段求解方法。第一阶段分析物流配送过程的主要影响因素,根据相关因素对客户进行初步划分,然后采用模糊聚类分析方法将各配送区域中的客户进行细分;第二阶段采用带控制策略的深度优先搜索算法生成备选的车辆路径方案集合;第三阶段建立整数规划求解模型,并根据邻域规则将求得的解映射为实际问题中的行车方案。最后运用算例验证上述方法的有效性。By applying the theories of knowledge management, fuzzy clustering, artificial intelligence and operational research, this paper presents a three-stage solution approach, namely CSGM, to vehicle routing problem that aims to significantly reduce the solution＇s state space. In the first stage, factors influencing the distribution decisions are analyzed, and based on these qualitative factors, the service region is divided into several areas. The customers in each area are then further segmented into groups by fuzzy clustering. Based on these divisions of the customers, the second stage introduces how to generate feasible routing schemes by the depth-first search algorithm with control rules. In the last stage, an integer programming model is constructed to identify the optimal routing schemes, which is then converted to workable routing plans by using the nearest neighbor principle. Finally, a numerical example is used to demonstrate the efficiency of the intelligent solution approach.

关 键 词：车辆路径问题 模糊聚类分析 知识表示 状态空间 整数规划模型 

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