环状区域的车辆路径方案生成系统及优化模型  

Scheme generation system and integer programming model for vehicle routing problem with circular-area distribution

作　　者：胡祥培[1] 黄敏芳[1] Zeng Amy Z 

机构地区：[1]大连理工大学管理学院,大连116023 [2]伍斯特理工学院管理系,美国马萨诸塞州016092280

出　　处：《管理科学学报》2008年第6期103-111,共9页Journal of Management Sciences in China

基　　金：国家杰出青年科学基金资助项目(70725004);国家自然科学基金资助项目(70571009;70171040;70031020);教育部重点科研资助项目(03052);高等学校博士点基金资助项目(2006014013);辽宁省科学基金资助项目(2001101074)

摘　　要：针对顾客满足环状区域分布的车辆路径问题(VRP),以大幅度地缩减问题求解的状态空间为突破口,引入人工智能和运筹学理论,提出求解这类特殊车辆路径问题的两阶段方法.第1阶段考虑行车时间和车载容量,提出带有控制策略的深度优先搜索算法自动生成备选的车辆路径方案集合.第2阶段将此备选方案集合归结为整数规划模型.采用 VB6.0编程语言构建了车辆路径方案生成系统,并实现该系统与运筹学求解软件 lindo 的集成.通过案例验证了上述方法及自动求解系统的有效性.该项研究为解决环状配送区域的车辆路径问题这一难题提供了新方法.Applying theories of Artificial Intelligence and Operational Research, this paper tocuses on me great reduction of solution space and presents a two-stage solution procedure to one specific kind of VRP, in which all customers are distributed in ring-like area. In the first stage, we generate alternative routing schemes for each type of vehicle. Specifically, a depth-first search algorithm with control rules is used. In the second stage, an integer programming model is constructed to identify the optimal routing schemes. Based on our proposed two-stage solution procedure, an intelligent solution system is developed by VB 6.0 and integrated with OR solution software of Lindo. Finally, the result of a real case study shows that the procedure and the system are efficient. This research creates a new way to solve VRP.

关 键 词：车辆路径问题(VRP) 方案生成系统 人工智能 整数规划模型 

分 类 号：U116[交通运输工程] O223[理学—运筹学与控制论]