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

周海兵

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

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

近年来，我国快递业发展迅速，企业数量大幅增加，业务规模持续扩大，服务水平不断提升，在降低流通成本、支撑电子商务、服务生产生活、扩大就业渠道等方面发挥了积极作用。国务院也在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），其中把总站点记为v₀，把n个分站点记为v₁，v₂，…，v_n，边e_ij表示从站点v_i到v_j的路径，边权重w_ij表示从站点v_i到v_j的最短距离或者时间。这样最优快递送货策略就转化为求解图G（V，E，W）中从v₀出发回到v₀的最佳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）构造过程如下：

选取总站点v₀，用两个端点s和f代替；V=（V-v₀）∪{s，F}W'_ij=w_ij对所有v_i，v_j？{s，f}的边；w'_sj=w_0j+M，当v_j≠f；w'_if=w_i0+M，当v_i≠s；w'_sf=w'_fs=2M；W'_ii=∞，对所有v_i∈V'。

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

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

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

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

4.3遗传算法

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

算法描述：

（1）编码初始化。设置最大进化代数MaxG，种群规模G，贪心替换算子P_r，变异算子P_m，和交叉算子P_c，并生成初始随机种群。

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

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

（4）交叉操作。采用顺序交叉操作方法。

（5）变异操作。只有当变异后的基因优于原基因时，变异成功。

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

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

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

5、模型的评价

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

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