基于综合启发式算法的物流配送路径优化研究

齐心

摘 要：物流配送是现代物流的一个核心内容，文章以物流配送的总花费最小构建目标函数，建立了物流配送路径优化模型，并对所建立的模型进行分析，为避免遗传算法在求解该类问题有可能陷入局部最优解的情况，设计了基于遗传算法和模拟退火算法的综合启发式算法，最后通过实例验证了该模型和算法的优势。

关键词：物流配送；路径优化；启发式算法

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

Abstract： Logistics distribution is a core content of modern logistics. In this paper， the mathematical model of logistics distribution path optimization is established by taking the minimum total cost of logistics distribution as the objective function. In order to avoid the possibility that the genetic algorithm will fall into the local optimal solution， a comprehensive heuristic algorithm based on genetic algorithm and simulated annealing algorithm is designed. Finally， an example is given to demonstrate the superiority of the model and algorithm.

Key words： logistics distribution； routing optimization； heuristic algorithm

0 引 言

目前很多物流有限公司存在的问题主要是配送成本过高，随着物流信息的加强，各分店对业务时间的要求越来越高，公司配送系统的不完善性使公司有时无法满足顾客的时间窗要求，车辆的载重量过小，有时为满足分店的时间要求，只能对某些分店进行专车配送，但这样的配送方式往往存在成本过高、运距过远等问题。物流公司迫切的希望优化配送系统，通过整合各分店的配送信息，从整体上分析建立配送系统，尽可能降低配送的成本，提高顾客满意度，增加企业的竞争力。针对物流公司存在的问题，本文以物流配送的总花费最小为目标函数，构建合理的模型，并对所建立的模型进行了分析，通过运用扫描法和遗传算法，对数学模型求解出最优的配送方案，这可以给相关配送路径优化问题作为参考。

1 问题描述及模型的建立

1.1 问题描述

通过对物流公司的调研和数据采集，发现对软时间窗单向配送车辆优化调度问题的研究更符合实际，配送方案由k条简单的回路组成，最终目标是通过合理安排配送车辆的行驶路线，在满足各分店需求的条件下，使总的配送成本最小，说明如下：（1）单配送中心由一个配送中心对多个需求点的货物进行配送。（2）纯送货问题，只从配送中心送货到各分店，而不取货，属于单向配送。（3）带软时间窗，客户对时间的要求越来越高，而由于配送条件限制，很难满足硬时间窗的要求，因此软时间窗的模型更符合实际情况，且其条件相对宽松，容易找到可行解。

1.2 物流配送路径优化模型的建立

为了方便建立模型，先对以下几点进行假设：（1）配送中心无缺货情况；（2）需求点的需求量、地理位置、时间要求等为已知，配送中心的位置已知；（3）配送车辆的数量和容量已知；（4）配送车辆从配送中心发出，在完成配送任务后必须返回；（5）一条回路上的所有客户需求量之和不能超过配送车辆的装载能力；（6）配送车辆一次配送的最大行驶距离要大于每条配送路径的长度；（7）车速为某一固定的平均值；（8）每辆车只有一条行驶路线，且每个需求点的货物只能由一辆配送车辆配送。

模型建立：

（1）参数说明

2.2 算法设计

2.2.1 初始可行解的产生

本文在扫描法的基础上，结合最近插入法的思想来制定一种相应的插入准则，形成一种新的扫描插入法。利用扫描插入法得到初始配送方案，如图1所示：

由图中可得到初始遗传算法种子，即：0-7-6-1-0-5-3-0-8-0-11-4-0

-10-9-0-2-0。

2.2.2 遗传算法求解

（1）使用自然数编码方式。比如染色体0230450670，它包含3条子路径，分别为0-2-3-0， 0-4-5-0， 0-6-7-0，也表示需要车辆为3辆。

（2）适应度函数。本文适应值函数为目标函数的倒数。

（3）选择算子：为避免产生局部收敛的情况，选择混合模拟退火算法的两点变异算子。

（5）终止循环的条件，由迭代的次数决定，本文中进化代数为G=500。

3 实例验证与结果分析

3.1 实例验证

3.2 结果分析

运行遗传算法程序，最终得到如图2所示的结果：

分析结果，可知：最优解配送结果是总配送成本为4 430元，其对应的染色体为：0-6-8-0-5-0-4-0-10-9-0-7-11-3-0

-1-2-0。

可知染色体中安排的车辆数为6，可得6个闭合路径，具体如图3所示。

随机生成初始解后的遗传算法的运行结果，由于初始解的随机性，最终结果也不稳定。经过计算，随机求解，连续运行10次，将得到的结果进行统计，如表5所示。

得到的最优结果如图4所示。

根据上面的结果可知：

由随机生成初始解的遗传算法和扫描插入法形成的初始种群，得出的结果如表6所示。

经计算可知，用扫描插入法生成初始解，违约时间减少了3.5小时，优化了77.35%；在总里程上，节省了60km的运距，优化了3.56%；在总成本费用上，节省了856元，优化了16.19%。

4 结束语

本文通过将具体的配送线路问题和限制条件转变为带时间窗的配送数学模型，然后用扫描法和插入法进行了综合并改进，求出初始可行解，并以它为种子，进行百分百变异，得到新的初始化种群，再通过遗传算法的算法设计，用MATLAB进行求解，最终结果大大改善了遗传算法的效率和寻找满意解的能力。随着现代物流技术的更加成熟，各企业也应该跟随技术的发展，致力于基于电子商务的物流配送，应该充分的利用物流技术及相关理论，因地制宜地寻求更加合理、科学、高效的运营方法。为了提高物流公司的运营效率，第三方物流的研究也是当前的热点，因此在以后的学习和研究中，基于第三方物流研究将是重要的方向。

参考文献：

[1] Y. Dumas， F. Soumis， J. Desrosiers. Optimizing the Schedule for a Fixed Vehicle Path with Convex Inconvenience costs[J]. Transportation， 1990，24（2）：145-152.

[2] T. Sexton &， Y. Choi. Pickup and Delivery of Partial Loads with “Soft” Time Windows[J]. Am. J. Math. Mgmt. Sci， 1986，6（3-4）：369-398.

[3] 夏新海. 物流配送车辆调度优化研究[D]. 武汉：武汉理工大学（硕士学位论文），2004.

[4] 林珊，段复建. 一个物流配送中心选址模型及其算法[J]. 吉首大学学报（自然科学版），2012，33（6）：29-32.

[5] 阳永生. 基于分支定界算法的物流配送网络优化研究[J]. 数学理论与应用，2010（1）：57-61.

[6] 樊蓉. 物流配送中車辆调度算法的比较研究[D]. 南京：南京农业大学（硕士学位论文），2013.

[7] 柳林，朱建荣. 基于遗传算法的物流配送路径优化问题的研究[J]. 计算机工程与应用，2005（27）：227-229.

[8] 许欢. 多目标进化算法在物流配送车辆路径问题中的应用研究[D]. 广州：广东工业大学（硕士学位论文），2013.

[9] 李义华. 基于多智能体的物流配送车辆调度决策方法研究[D]. 长沙：中南大学（博士学位论文），2012.

[10] 马彦东. 配送中心车辆调度模型及遗传算法设计[J]. 物流科技，2008，31（5）：79-82.

[11] 张之富，余静，凌镭，等. 基于改进遗传算法的车辆优化调度研究[J]. 中国水运，2009，9（4）：73-75.