APP下载

哈密尔顿图在快递送货中的应用

2017-06-09周海兵

科学与财富 2017年9期
关键词:近似算法遗传算法

周海兵

摘要:本文对生活中快递送货问题,应用哈密尔顿图、最佳推销员回路,建立模型,对完备加权图给出了近似算法、最小生成树算法和遗传算法三种方法,求解最佳圈,即最优快递送货策略。

关键词:哈密尔顿圈;最佳推销员回路;近似算法;最小生成树算法;遗传算法

近年来,我国快递业发展迅速,企业数量大幅增加,业务规模持续扩大,服务水平不断提升,在降低流通成本、支撑电子商务、服务生产生活、扩大就业渠道等方面发挥了积极作用。国务院也在2015年印发了《关于促进快递业发展的若干意见》,快递业已经成为现代服务业的重要组成部分,是推动流通方式转型、促进消费升级的现代化先导性产业。

一般地,所有快件到达某地总部以后,比如武汉总站,会安排车辆尽快送到各个区分站点。各个区分站点再及时把快件送达各个小的投递点。本文应用哈密尔顿图、最佳推销员回路,建模解决最优快递送货策略。

1、定义和符号

(1)G(V,E,W)表示加权图,V表示点集合,E表示边集合,W表示边的权集合。

(2)经过图G的每个顶点正好一次的路,称为图G的哈密尔顿路。经过图G的每个顶点正好一次的圈,称为图G的哈密尔顿圈,简称H圈。包含H圈的图称为哈密尔顿图。

(3)在加权图G(V,E,W)中权最小的哈密尔顿圈称为最佳H圈,经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路。

2、模型的假设

(1)假设路况良好,没有意外交通拥堵。

(2)假设车辆容量足够大,交货时间忽略。

3、模型建立

总站到分站,一般会安排一个车辆负责运送到其中几个分站点,再要带回分站点要投递的快件返回总站(分站到投递点情形类似处理)。那么寻求路程最短,时间最少的投递线路,就是寻求最佳推销员回路问题。最佳推销员回路问题可转化为最佳圈问题。

首先建立一张完备加权图G(V,E,W),其中把总站点记为v0,把n个分站点记为v1,v2,…,vn,边eij表示从站点vi到vj的路径,边权重wij表示从站点vi到vj的最短距离或者时间。这样最优快递送货策略就转化为求解图G(V,E,W)中从v0出发回到v0的最佳H圈问题。因为是完备图,则G(V,E,W)中一定有哈密尔顿圈,所以是哈密尔顿图。

4、模型求解

4.1近似算法

(1)输入图G(V,E,W)中的一个初始H圈;

(2)用对角线完全算法产生一个初始H圈;

(3)随机搜索出G(V,E,W)中若干个H圈;

(4)对前面所有得到的H圈,用二边逐次修正法在进行优化,获得近似最佳H圈;

(5)在上一步求出的所有近似最佳H圈,找出权最小的一个。此方法可以找到最佳H圈的近似解,即局部最优解。

4.2最小生成树算法

(1)将完备加权图G(V,E,W)转化为新图G(V',E,W'),其中两个端点记为s和f。原图中最佳H圈转化为在新图G(V',E',W')中求s到f的最佳哈密尔顿路。

其中新图G(V,E,W)构造过程如下:

选取总站点v0,用两个端点s和f代替;V=(V-v0)∪{s,F}W'ij=wij对所有vi,vj?{s,f}的边;w'sj=w0j+M,当vj≠f;w'if=wi0+M,当vi≠s;w'sf=w'fs=2M;W'ii=∞,对所有vi∈V'。

M选为足够大的数,应用最小生成树算法时与s和f关联的边就不会被选入最优回路,显然在原图中的最佳H圈与新图中s到f的最佳哈密尔顿路是对应一致的。

(2)在G(V',E',W)中求解最小生成树T,由w'sf的取值可知最優解一定不含边esf,当最小生成树的各个顶点度小于等于2时,则得到s到f的最佳哈密尔顿路,将s和f合并为一个点,即为G(V,E,W)的最佳H圈。

(3)若有顶点度大于等于3,则选择其中次数较小的进行分枝。G'=G'1∪G'2∪G'3…,G'1=G\eT1,G'2=G\eT2…,其中G'1,G'2,G'3…为分枝以后的新图,eT1,eT2,…为与分枝顶点关联的边。继续在G'1,G'2,G'3…中应用最小生成树算法,最后得到一个权值最小且各点的度均小于等于2的图,即是G(V',E',W')中的最佳哈密尔顿路。

此方法中分枝定界等一些环节在结点数n较大时,实现难度增大。在这里单一车辆巡回路,涉及到的结点数一般不会很多。

4.3遗传算法

遗传算法包括3个基本操作:选择、交叉和变异。回路长度是度量某个染色体的优良性的标准,长度越小说明染色体越优秀,应该保留,这也是算法中适用度函数的考量点。

算法描述:

(1)编码初始化。设置最大进化代数MaxG,种群规模G,贪心替换算子Pr,变异算子Pm,和交叉算子Pc,并生成初始随机种群。

(2)个体评价。用适应度函数对每个基因进行评价。

(3)选择操作。首先用最优的染色体方案替换占种群规模Pr的最坏个体,再用基本轮转法进行选择。

(4)交叉操作。采用顺序交叉操作方法。

(5)变异操作。只有当变异后的基因优于原基因时,变异成功。

(6)终止条件。当进化代数大于MaxG时,算法结束,否则转向步骤(2)。

在进行选择操作时,将最优值替换和轮转法相结合,使得算法更容易获得全局最优解。顺序交叉操作方法,也更适合于哈密尔顿圈的特性。

对于三种算法得到的最佳圈,分别计算各个对应的权值,比较得到权值最小的,即就是要寻求的最杭快递送货策略。

5、模型的评价

这里哈密尔顿图模型中只考虑单一车辆最优巡回路问题,而且假设是最简单情形,实际情况要复杂的多,要满足货物需求量、发送量、交货时间、车辆容量限制等目的,需要考虑安排多条送货线路,使得总时间尽量短,总里程尽量小。同时由于不同时间段可能出现的出行高峰,要组织调整合适的车辆行驶路径,才能最终使得快递企业运行成本最低。此问题是一个NP-hard问题。

此方法还可应用生活中于灾情巡视、旅游线路安排、交通车最佳巡回路线等。

猜你喜欢

近似算法遗传算法
遗传算法对CMAC与PID并行励磁控制的优化
多材料Terminal Steiner树拼接问题的近似算法研究
巡检线路的排班模型
基于自适应遗传算法的CSAMT一维反演
一种基于遗传算法的聚类分析方法在DNA序列比较中的应用
基于遗传算法和LS-SVM的财务危机预测
应用自适应交叉近似算法快速计算导体RCS
协同进化在遗传算法中的应用研究
求投影深度最深点的近似算法
基于改进的遗传算法的模糊聚类算法