VRP求解中保证满载率的扫描-遗传算法  

Sweep-Genetic Algorithm with Full Load Rate for VRP Resolution

作　　者：杨文霞[1] 郭海湘[1,2] 杨娟[1] 王祥[1] 诸克军[1] 

机构地区：[1]中国地质大学经济管理学院,武汉430074 [2]西安交通大学管理学院,西安710049

出　　处：《计算机工程》2010年第17期187-188,191,共3页Computer Engineering

基　　金：国家自然科学基金项目资助项目(70573101);中国博士后基金资助项目(20090461293);中央高校基本科研业务费用专项资金资助项目(CUG09013);中国地质大学(武汉)资源环境经济研究中心开放基金资助项目(2009B012)

摘　　要：为保证配送车辆的满载率,提出一种扫描-遗传算法,以任意一个需求不为0的需求点为子路径的起点开始扫描,结合节约法的思想,制定相应插入准则,并依照该准则向路径中插入需求点直至所有需求点都被插入。基于扫描起点的任意性形成多个可行解,将其作为种群并运用遗传算法,使解在整体上向最优解逼近。运用该扫描-遗传算法对郑州煤电物资供销公司的物资配送进行优化求解,并与随机扫描-遗传算法进行比较,结果表明该扫描-遗传算法满载率较高且费用较低。To ensure the full load rate of delivering vehicle, this paper proposes a Sweep-Genetic Algorithm（S-GA）. It starts to sweep with an arbitrary demand point which the demand is not zero as the starting point for sub path. Combining with the idea of saving algorithm, corresponding norm for inserting demand point is formulated. It follows the norm and inserts the demand point until all the demand points are in the route. As the arbitrary of starting point, it can form a number of possible solutions and obtain optimal solution by using Genetic Algorithm（GA）. It uses the S-GA to solve the optimization problem of goods delivering of Zhengzhou coal electricity material supply and marketing limited company. Compared with the random S-GA, this S-GA can guarantee the full load rate of delivering vehicle and minimize the delivering cost.

关 键 词：满载率 随机 扫描算法 遗传算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]