Abstract:
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.
Key words:
full load rate,
random,
sweep algorithm,
Genetic Algorithm(GA)
摘要: 为保证配送车辆的满载率,提出一种扫描-遗传算法,以任意一个需求不为0的需求点为子路径的起点开始扫描,结合节约法的思想,制定相应插入准则,并依照该准则向路径中插入需求点直至所有需求点都被插入。基于扫描起点的任意性形成多个可行解,将其作为种群并运用遗传算法,使解在整体上向最优解逼近。运用该扫描-遗传算法对郑州煤电物资供销公司的物资配送进行优化求解,并与随机扫描-遗传算法进行比较,结果表明该扫描-遗传算法满载率较高且费用较低。
关键词:
满载率,
随机,
扫描算法,
遗传算法
CLC Number:
YANG Wen-Xia, GUO Hai-Xiang, YANG Juan, WANG Xiang, CHU Ke-Jun. Sweep-Genetic Algorithm with Full Load Rate for VRP Resolution[J]. Computer Engineering, 2010, 36(17): 187-188,191.
杨文霞, 郭海湘, 杨娟, 王祥, 诸克军. VRP求解中保证满载率的扫描-遗传算法[J]. 计算机工程, 2010, 36(17): 187-188,191.