喻　伟　何其超　张增棨

摘要：文章针对配送路线问题进行研究，首先提出配送路线优化的原则，在此基础上提出了解决配送路线问题的遗传节约综合算法的流程和步骤，最后通过一个算例实现了本文提出的算法，并与其它方法的计算结果进行了比较，从而证实了遗传节约综合算法的优越性。

关键词：物流；配送路线；遗传算法；节约算法

中图分类号：U116.2文献标识码：A

Abstract: In studying the distribution routes, the paper first introduces the principle of distribution route optimization, and then presents the process and steps of saving hybrid genetic algorithm solving the distribution issue, and last realizes the algorithm raised in this paper by an algorithm example. Compared to the calculated results of other methods, it proves the superiority of saving hybrid genetic algorithm.

Key words: logistics; distribution route; genetic algorithm; saving algorithm

0 引言

配送是近距离、小批量、多品种的物资，根据用户需要，把货物从配送中心送到所需的各个用户手中的物流过程。配送路线优化问题主要是指在保证商品准时到达客户指定点的前提下，如何尽可能地减少运输的车次和运输的总路程[1]。目前解决此问题主要采用节约启发式算法(通常称为节约法)、遗传算法、禁忌搜索算法等单一算法，各种算法均存在一定的缺陷[2]。本文主要通过将遗传算法和节约法两种算法进行结合产生的遗传节约综合算法来解决配送路线优化问题。

1 配送路线优化原则

进行配送路线优化时，必须有明确的目标，遵循基本的原则。配送路线方案目标的选择可以从以下几个方面来考虑：

(1)配送效益最高或配送成本最低；

(2)配送里程最短；

(3)配送服务水准最优。

在满足客户需求的前提下，配送车辆行驶的路程越短，配送的成本越低、效益越高，因此配送成本最低和配送里程最短两个目标选择其中一个即可，本文以配送里程最短为优化目标。

2 配送路线优化的遗传节约综合算法

采用遗传节约综合算法解决以上模型，即在进程层次上，依次进行全局的遗传搜索和局部的节约搜索，是一种两层串行结构。其中，节约操作的个体对象来自遗传的进化结果，而经过节约操作得到的解群又成为新遗传操作的进一步进化的种群对象，这个过程反复迭代，直到满足终止条件为止，终止条件作为基本参数，在运行前输入，可以包括：目标函数满意值、一定的遗传代数、连续多次运算结果均一致不再出现优化值等。遗传节约综合算法主要步骤如下。以下步骤可通过VB等软件编程实现。

step2：设置参数。遗传参数包括群体规模n，适当大的数M，遗传操作的类型(确定型和自适应型选一)，并设置控制参数；

以下首先进行遗传操作过程：

step3：令t=0，随机产生初始群体p0，群体中包括n条染色体，每个染色体表示一条可行的配送线路；

step4：将群体pt中n条染色体解码为线路，计算其目标函数，即运输成本；

step5：寻找群体pt中最优染色体bestt，即目标函数最小的线路；

step6：计算pt中n条染色体的适应度；

step7：若满足终止条件之一，则停止运算，结束程序，输出pt中的最优染色体bestt作为满意解；否则，继续；

step13：根据各辆车所承担的货运任务总量，进行从大到小的排序，并将相应的车辆重新编号为L-m；

stepl4：令当前车辆号mo=1，待选池A1=空集；

step15：针对第mo辆车所承担的各个任务节点，计算费用节约值，并进行从大到小的排序；

step16：进行第mo辆车的原始子路径Ra安排。按照费用节约值从大到小的顺序，将各个货运节点插入，产生原始子路径Ro；

step17：第mo辆车的原始子路径Ro安排中，若有不满足容量约束的节点，则将此节点放入待选池A1；

step18：计算待选池A0中的各个待选节点与原始子路径Ro的起点、终点之间的费用节约值（不包括待选节点相互之间），并进行从大到小的排序；

step19：按照step18中费用节约值从大到小的顺序，将各个待选节点尝试接入原始子路径Ro。若满足容量和时间约束，则插入，并从A0中删除该节点；否则继续，直至A0所有待选节点考察完毕，得到第mo辆车的子路径R；

step20：令A0=A0+A1，A1=空集，即将A0和A1合并为A0，同时清空A1；

step2l：令mo=mo+1，若mo≤m(车辆总数)，则转step15；否则，将m辆车的子路径合并到一起。形成第j条完整的配送线路，并继续；

step22：令j＝j+1，若j≤n(群体规模)，则转step12，否则继续；

step23：将n条配送线路编码为n条染色体，形成新的群体pt+1，令t=t+l转step4。

3 算法的实现

某配送中心使用载重量为4吨的厢式货车向其13个客户(C1—C13)配送物资，各点间单位运费均一样，配送中心（C0）和各客户间距离如表1所示，各客户配送量如表2所示。

根据以上数据，采用节约法优化配送路线，其结果如表3。

采用遗传节约综合算法求解基本过程如下，最终结果如表4。

4 结论

将节约法和遗传节约综合算法的计算结果进行对比，派车数二者均为4辆，总行驶距离综合遗传算法的结果较节约法少29公里，且车辆实载率有三车达到97.5％，较节约法结果也更优。

通过以上分析，遗传节约综合算法将遗传算法和节约算法相结合，相互补充，较好地解决了配送路线优化的问题。但由于该算法需要进行一定数量的迭代计算，因此需要通过计算机编程实现，存在不适合于手工计算的情况。

参考文献：

[1] 李永生，郑文岭． 仓储与配送管理[M]． 北京：机械工业出版社，2005．

[2] 徐天亮． 运输与配送[M]． 北京：中国物资出版社，2002．

[3] 李军，郭耀煌． 物流配送车辆调度优化理论与方法[M]． 北京：中国物资出版社，2001．

[4] 赵家俊，于宝琴． 现在物流配送管理[M]． 北京：北京大学出版社，2004．

[5] 朱德通． 最优化模型与实验[M]． 上海：同济大学出版社，2003．

[6] 《运筹学》教材编写组． 运筹学[M]． 北京：清华大学出版社，2008.

[7] 龚沛曾，陆慰民，杨志强． Visual Basic程序设计教程[M]． 北京：高等教育出版社，2003．

“注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”。