分散搜索算法求解带货物权重的车辆路径问题  

Scatter search algorithm for solving weighted vehicle routing problem

作　　者：张军[1] 唐加福[1] 潘震东[1] 孔媛[1] 

机构地区：[1]东北大学教育部流程工业综合自动化重点实验室,辽宁沈阳110819

出　　处：《系统工程学报》2010年第1期91-97,共7页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(70625001;70721001);国家重点基础研究发展计划资助项目(2009CB320601);高等学校学科创新引智计划资助项目(B08015)

摘　　要：研究了由一个分销中心、多个零售商组成的分销网络中运输单产品考虑货物权重的车辆路径问题(weighted vehicle routing problem,WVRP).问题的目标是设计合理的路线最小化由于行驶距离,运输载重量及使用车辆而产生的总费用.针对问题的特点,设计了求解WVRP问题的分散搜索算法(scatter search algo-rithm,SS),该算法基于客户进行编码,以基于最优划分过程的随机初始化作为多样性产生方法,通过对不同解包括的弧组合来生成新解,并用最近邻法对解进行改进.分别采用了随机数据与标准数据对算法进行测试,并与其他求解该问题的算法进行了比较,说明了算法的有效性.In a distribution network with one warehouse and multiple retailers,a weighted vehicle routing problem(WVRP) for transporting one kind of production is considered.The objective of the WVRP is to arrange a reasonable route so as to minimize the total cost of traveling cost,cost relating to cargo weight and dispatching cost.In the light of the characteristic of the problem,a scatter search(SS) algorithm is designed.The code of the algorithm is based on customers.The random initialization based on optimal spli...

关 键 词：车辆路径问题 货物权重 分散搜索算法 

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