第13卷 第6期
2004年12月
运 筹 与 管 理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEVol.13,No.6Dec.2004
车辆路径问题的混合优化算法
汪祖柱1,2, 程家兴1, 方宏兵1, 钱付兰1
(1.安徽大学计算智能与信号处理实验室; 2.安徽大学管理学院,安徽合肥)
摘 要:讨论了一类车辆路径调度问题(VRP)及其数学模型,表示和有关遗传操作,然后结合2-optG2问题,试验结果说明了该算法的有效性和可行性。
关键词:运筹学;组合优化;);(GA)
中图分类号: 23221(2004)0620048205
AnAlgorithmSolvingVehicleRoutingProblems
WANGZu2zhu1,2,CHENGJia2xing1,FANGHong2bing1,QIANFu2lan1
(1.MinistryofEducation,KeyLaboratoryofIntelligentComputing&SignalProcessing,
AnhuiUniversity;2.ManagementSchool,AnhuiUniversity,Hefei230039,China)
Abstract:Akindofvehicleroutingproblems(VRP)anditsformulationaredisscused,andwhensolvingVRPusinggeneticalgorithm(GA),thesolutionpresentationandsomeGAoperationsareanalysed.Thenanhybridalgorithmisproposedtosolvethevehicleroutingproblems,someexperimentalresultsprovethatthealgo2rithmisfeasibleandefficient.
Keywords:operationalresearch;combinatorialoptimization;hybridoptimizationalgorithm;vehicleroutingproblems;geneticalgorithm
0 引言
车辆路径问题(VehicleRoutingProblem,VRP)由Dantzig于1959年提出,属于典型的复杂组合优化问题,考虑其特征该问题可以看做是两类经典的组合优化问题的结合—旅行商问题(TSP)和装箱问题(BinPackingProblem,BPP)。该问题的一些具体实例及其变化形式广泛出现于各种商业中的商品配送系统中,如物流快件公司的邮件收发、大型连锁超市的商品配送以及运输公司的旅客输送等。车辆路径问题是NP—Hardness,且有较强的实际应用背景,相关问题的研究者们提出许多求解问题的方法,设法求解该类问题的最优解、近似解或满意解,这些方法大体上归结为三类,即精确算法(exactalgorithms)、经典启发式算法(classicalalgorithms)和现代启发式算法(modernalgorithms,metaheuristics)。有关精确算法如文献
[1]中应用的最小K-树法(minimumK2trees),结合分支定界(branchandbound)的算法技巧来求解问题,这类方法对一些适当规模的问题求解是可行的。经典启发式算法如节约法(savingsalgorithm)[2]和两阶段法(two2phaseheuristic)[3]和扫描法(sweepalgorithm)[4],这类算法能够广泛应用于VRP问题的求解中,最近许多相关文献提出了一类算法—现代启发式算法设法求解VRP问题[5~8],这类算法主要包括遗传
收稿日期:2004203208
基金项目:安徽省青年教师科研基金资助项目(2004JQ108)
作者简介:汪祖柱(19692),男,安徽肥西人,在职博士生,研究方向为调度规划、组合优化问题的演化算法及多目标优化等。
汪祖柱;程家兴;方宏兵 车辆路径问题的混合优化算法[期刊论文]-运筹与管理 2004(6) 8.Augerat P VRP problem instances 2005 9.Augerat P 车辆路径问题例子 2005...
求解组合优化问题的一种方法—分枝定界法 " 汪祖柱...! 算法概述分枝定界算法 </0123 + 014 + <5614...(或者混合整数线性规划) 的问 [!] 题, 也适用于...
其算法不仅可用于求解 纯整数或混合整数线性规划问题 , 也适用于几乎任 何...运筹学与最优化方法 . 北京 : 北京机械工业出版社 , 2003 3 汪祖柱 , 程...
载重飞机总体参数的多目标优化设计方法王和平 , 王正平 , 张亚锋 , 王 旭 (...[4 ] 汪祖柱 ,程家兴. 一种求解多目标优化问题的混和演算算法 [J ]. 安徽...
321 3 实例 设某车 间有一批 长度 为10a 的钢管...表1下料方案 2 3 汪祖柱 , 程家 兴. 求解 ...刚. 混合遗传算法求解 一维优化下料 问题. 中国水...
载重飞机总体参数的多目标优化设计方法王和平 , 王正平 , 张亚锋 , 王 旭 (...[4 ] 汪祖柱 ,程家兴. 一种求解多目标优化问题的混和演算算法 [J ]. 安徽...
热门文档