基于遗传算法的熟食配送路径优化

摘要 物流对市场经济活动的影响日益明显，物流配送系统越完善，企业的利润就越丰厚。本文提出最优配送熟食线路的求解算法，实现熟食运送的快速和经济合理。针对运送熟食送路径线路的优化问题，建立基于遗传算法的优化模型，并进行模拟实验。实验结果证明，基于遗传算法解决熟食配送路径优化问题，是可行的，有效的，为其他物流配送提供可以借鉴的思路，拓展了遗传算法的应用领域。

关键词 配送熟食；遗传算法；路径优化

中图分类号O29 文献标识码A 文章编号 1674-6708（2014）120-0166-02

0引言

在现代化物流系统中，跟消费者直接相连的是物流配送环节。选取科学可行的配送路径，能够快速配送货物、减少运输成本、从而获得更大的经济效益。遗传算法的应用为优化物流配送路径问题提供了方便，尤其适用于处理传统搜索方法难于解决的复杂和非线性的问题。本文在优化熟食运送路径问题特点分析的基础上，针对该问题建立了数学模型，并利用遗传算法求解，取得了很好的效果。

1熟食配送路径优化问题的数学模型

优化熟食运送路径的思想是：以运送点为中心，通过多个车辆向若干个顾客点运送货物。其中，顾客的需求量和位置是固定的，车的载重是有限制的。为了实现科学合理的运输路径，实现最优运距，降低成本，获得更好的经济效益。整个过程给出如下假设：

1）在每条运送线路上，车载重≥所有顾客点需求和；

2）每条运送线路长度≤车最大的一次运距；

3）只能由一辆车为相应的顾客需求服务。

在上述假设条件的基础上，建立物流配送路径最优化模型。设物流配送中心地有K辆车，Qk为每辆车的载重量（其中），Dk为一次配送时的最大的运行距离，需求送货点L个，其需求量记为qi（i=1，2，…），dij为需求点i到j的运距。设第k辆车配送的需求点数记为nk（若nk=0，则第k辆汽车未被使用），Rk表示第k条路径的集合，集合中的元素rki表示需求点rki在路径k中的顺序为i（但配送中心没包括在内），令rk0=0表示配送中心，基于物流配送路径的最优化数学模型建立如下[3]：

其中，式（1）为目标函数；式（2）保证在每条运送线路上，车载重≥所有顾客点需求和；式（3）保证每条运送线路长度≤车最大的一次运距；式（4）表明每条运送线路上，总顾客点数≥顾客点数；式（5）表明货物都送至每个顾客点；每一条运输线路上顾客点组成式（6）；式（7）只能由一辆车为相应的顾客需求服务；式（8）为设第k辆车配送顾客数大于1，那么这辆车进行r次配送。若第k辆车配送顾客数大于等于l时选择这辆车，sign（nk）=1。若第k辆车配送客户数小于l时选择这辆车，sign（nk）=0。

2熟食配送路径优化问题的遗传算法

1）编码，分析优化运输路径特征，0代表起点，即配送中心，顾客点用表达。因为起点有K辆车，那么有最多K条运输线路、每条线路的起始和终止，都是一点，即配送中心。通过增加K-1个虚构配送中心，用表示；

2）初始化，任意l排列，这个排列是L+K-1个不相重合自然数组成，也就是若干个个体。假设群体规模是N。那么也就是N个初始群体；

3）个体适应度评价，要辨别一个个体所对应的运输方案好坏，即是否符合运输线路约束；统计所有运输线路长度和。若运输方案不满足上述条件，那么此线路不可取。假设个体j相对的运输方案线路不可取为Mj，目标函数值为Zj，则该个体适应度，式中：G是对每条不可取线路惩罚权重，可按照目标函数取值范围，确定一个较大正数；

4）选择操作。按照适应度，遵循从大到小的顺序，排列Ⅳ个个体，最优性能是第一个体，把它的复制体进入下一代，并占据第一的位置；

5）交叉运算，选择组成新群体，第一位个体除外。其他N-1个个体，基于交叉概率Pi来配对交叉，重新组合。

6）变异运算。为了使个体仍然具有多样化的特点，通过连续多次交换方法，使个体有较大的排列变化。变异操作基于概率P。下面给出应用遗传算法解决优化熟食运送线路的实例。

某送货中心利用2辆车分别对8个顾客点送货，假设每辆载重为kg，每次运送最大运距45km，送货中心和所有顾客点之间、以及各顾客点之间的距离及各顾客点的需求量见

表1。

在模拟实验中的参数选取为：群体规模：20；交叉概率：0.95；变异概率：0.05；进化代数：50；基因换位次数（变异时）：5；对不可取线路惩罚权重取100km。针对以上问题，求解10次，得其计算结果，见表2。

通过上表数据证明，在第5次运算中出现了最优解66.5km，其相应运输线路方案是：路径1：0―4―7―6―0；路径2：0―2―8―5―3―1―0。可得，在优化货物输送线路上，基于遗传算法能够得到最优解或是近似最优解。

3 基于遗传算法的熟食配送路径优化问题的研究意义

随着现代经济发展步伐的加快，作为“第三方利润源泉”的物流对市场经济活动的影响日益明显，越来越受到人们的关注。物流配送系统越完善，企业的利润就越丰厚。这就要求优化货物的运送线路。在物流系统中，选取科学可行的配送路径，能够快速配送货物、减少运输成本、从而获得更大的经济效益。遗传算法应用为优化物流配送路径问题提供了方便。用遗传算法解决熟食配送路径优化问题。保证了路径最优，而且符合企业理念，满足了顾客需求，提高了企业的信誉，从而提高了企业的效益，具有很现实的意义。

参考文献

[1]喻小贤.物流运输与配送管理[M].北京：电子工业出版社，2005：2-12

[2]罗勇，陈治亚.基于改进遗传算法的物流配送路径优化[J].系统工程，2012，8：118-122.

[3]姜丈立，扬西龙，杜文.等车辆路径问题的遗传算法研究[J].系统工程理论与实践，1999，19（6）：40-44，7.

[4]陈国良，王煦法，庄镇泉，等.遗传算法及其应用[M].北京：人民邮电出版社，1996.

[5]王韦克，曹泽阳，郭晓宁.基于分类指标优化的聚类分析[J].陕西师范大学学报，2004，6：185-187.