基于遗传算法的带时间窗物流配送研究

尹作海，朱海，卢新宇，崔明

（1山东大学财务部，山东济南 250100；2济南历城黄河河务局，山东济南 250108；3山东省冶金科学研究院，山东济南 250014）

信息化建设

基于遗传算法的带时间窗物流配送研究

尹作海1，朱海2，卢新宇3，崔明3

（1山东大学财务部，山东济南 250100；2济南历城黄河河务局，山东济南 250108；3山东省冶金科学研究院，山东济南 250014）

针对带时间窗的物流配送的特性，设计了基于遗传算法的配送模型，以实际的配送任务作为实例，验证了配送路径设计方案，证实了遗传算法模型和优化方案的可行性。

物流配送；遗传算法；软时间窗

1 物流配送的定义

物流配送是现代化物流系统的一个重要环节，它是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人。物流配送按客户对送货时间的要求分类，可分为带时间窗和不带时间窗两种。所谓带时间窗的物流配送，是指在制定配送路线时，不仅考虑客户的货物需求数量约束和配送车辆一次配送的最大行驶距离约束，而且要考虑客户对货物送到时间的要求。随着企业的发展，零库存成为许多企业追求的目标，于是客户对货物的送到时间提出了更高要求。可见研究带时间窗物流配送问题具有十分重要的现实意义［1］。

在带时间窗物流的配送中，由于交通等方面的原因，可能无法在约定的时间窗内将货物送到目的地，所以硬时窗实用性不高，代之以软时间窗限制。软时窗限制允许配送车辆的到达时间在时间窗之外，但是必须受到惩罚，惩罚点随着超出时间窗范围的增大而增大。

工业生产的快速发展，对高效物流的需求量越来越大，带时间窗的物流优化问题是当前物流配送系统研究中的热点问题，被广泛应用于包括工业生产、商品配送等生产、流通经济活动中。但是该问题具有NP-hard性质，难以求得最优解或满意解。

2 带时间窗物流配送模型的建立

根据带时间窗物流配送过程中对时间等限制条件的特殊要求，以车辆路径问题为方法和手段，将传统物流中普遍使用的配送模型进行适当改进，使其适用于带时间窗的物流配送，即将传统物流配送模型加上时间和载重量限制等约束条件。

2.1 配送问题假设

带时间窗物流配送的模型假设为一个配送中心为多个客户派送货品，配送的货品类型单一，同时满足以下条件：

1）物品流向为单向，即纯送货；2）运输工具为m辆汽车，每辆车都有一定的装载能力限制，满足单车的容量大于运输路线上客户的总需求量；3）每个客户的需求量是已知的，所需货物只能由一辆汽车完成，且所有客户都应该得到服务；4）每条线路的开始和结束位置都在配送中心，所有车辆必须在规定的时间内返回配送中心；5）每个客户都有一个指定的服务时间窗，送货必须在此时间范围内进行；6）目标为多目标：车辆运输费用最小、车辆运输时间及全部客户的等待时间最短；7）配送中心与客户之间，以及两两客户之间的最优配送线路已知。

2.2 参数定义

假设共有m辆车（k=1，2，…，m），n个客户（i=1，2，…，n），第i个客户的需求量为wi，并且己知各个客户互相间的相对距离矩阵以及客户位置分布图。给所有参与配送的车辆下达配送任务，在时间窗限制以及车载重量限制内，产生考虑时间窗限制以及车载重量限制的最短配送时间目标数学模型，这样的任务安排能完成所有配送任务并且总惩罚点数最少。

设N={1，2，…，n}，K={1，2，…，m}，Sij为从客户i到客户j的最短配送时间；Xijk=（0，1）为由客户i由车辆k行驶至客户j之二元变量；Yki=客户i由第k辆车服务，∀i∈N，k∈K；wi：第i个客户的配送重量，∀i∈N；WL=车辆载重上限；ETi：任务i的最早开始时刻，i∈N；LTi：任务i的最迟开始时刻，i∈N；ui：i的服务时间，i∈N；Xijk=1时车辆k从任务i行驶到任务j，或Xijk= 0时车辆k不从任务i行驶到任务j，i，j∈N，k∈K；Yijk=1时任务i由车辆k完成，或Yijk=0时任务i不由车辆k完成，j∈N，k∈K。

配送车辆时间计算函数C1：

配送车辆载重惩罚函数C2：

时间惩罚函数C3：

其中：M1、M2、M3分别为早到惩罚系数、迟到惩罚系数和超过T的惩罚系数。

限制条件：某一配送车辆的总载重量不大于配送车辆载重量上限

总配送时间为每辆车程的总和

目标函数Minimize:

3 遗传算法优化方案设计

物流配送是中国整个物流系统中的薄弱环节，由于现有的配送方案不合理，造成了配送过程中效率低，耗损率过高等现象。因此只有对物流配送方案进行合理的优化设计，才能有效弥补物流系统中存在的上述不足。然而由于带时间窗的物流配送模型求解是一个NP-hard问题，使得传统的精确求解方式并不适用。而遗传算法做为一种启发式算法，是通过模仿自然界的生物进化机制，发展起来的一种全局随机搜索和优化方法，具有更好的全局搜索特性。

本研究针对带时间窗的物流配送的特性，站在实际需求的角度，对带有时间窗的配送模式进行分析，以一个配送中心和63个客户的每日配送任务为实例，使用改进的配送模型和遗传算法对配送方案进行优化设计。采用Matlab7.1，对物流配送模型进行求解［2］。物流分配的遗传算法设计流程见图1。

3.1 参数选择

前提条件：1）相同车型；2）同一时间配送；3）相同客户服务时间；4）相同配送车辆载重上限。设定遗传算法内部参数，分别计算5个种群，每种群体规模均运算10次，寻找最优解。

1）g_max（最大遗传代数）=6 000；2）Size（种群规模）=100，200，…，500；3）变异概率=0.1；4）载重限制=5 t；5）车辆设置辆数=16；6）M1（早到惩罚点数）=3；7）M2（迟到惩罚点数）=10；8）M3（每条路线超过180 min惩罚数）=10；9）D（超重惩罚点数）=10；10）fwsj（服务时间）=10。

图1 遗传算法流程

3.2 求解质量及稳定性评价

实验中，每一代的每个体都被评估，并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，最好的个体有更多机率被选择去产生下一代，适应度低的个体逐渐被淘汰掉。

由于遗传算法是基于全局搜索的启发式解法，也就是在操作过程中会运算所有种群，所以造成运算前期会剧烈波动，但是随着代数的增加而逐渐稳定，并最终下降收敛。

最后，分别绘制不同种群规模下最短配送时间见图2，计算时间见图3，并进行比较。得知Size= 100，群体规模较小时，父代进入选择、交叉、变异过程的种群少，因此求解的速度较快，达到收敛状态；也因为较低的群体多样性，求解过程容易出现“早熟”现象，求解质量不高。而随着种群规模的不断扩大，运行时间明显增加，算法的运行效率大大降低。综合考虑，种群为300时，具有较佳的求解品质与最有效率的运行时间。

图2 不同种群规模下最短配送时间

图3 不同种群规模下各种群计算时间

由图4可知，种群为300时，5 800代后产生最高适应度值，曲线趋于平稳，显示5 800代后运算过程趋于稳定且收敛。

4 结语

研究了带软时间窗的物流配送方案的优化设计问题，考虑了带时间窗配送的时间要求和载重量限制这两方面的因素。在常温条件下物流配送模型的基础上，加入了带时间窗物流配送的时间窗限制和载重量限制，并以实际的配送任务做为实例，验证了文中提出的配送路径设计方案，证实了遗传算法模型和优化方案的可行性。

图4 种群=300适应度与收敛性

［1］国家发展和改革委员会经济运行局，南开大学现代物流研究中心.中国现代物流发展报告［M］.北京：电子工业出版社，2008.

［2］曹阳，方强，王国仁，等.基于遗传算法的多连接表达式并行查询优化［J］.软件学报，2002，13（2）：250-257.

Research on Logistics Distribution with Time Window Based on Genetic Algorithm

YIN Zuohai1,ZHU Hai2,LU Xinyu3,CUI Ming3

（1 Finance Department，Shandong University,Jinan 250100,China;2 Yellow River Jinan Licheng Bureau,Jinan 250108,China; 3 Shandong Metallurgical Research Institute,Jinan 250014,China）

According to the feature of logistics distribution with time window,the thesis designs distribution model based on genetic algorithm.Taking the actual distribution task for example,the thesis verifies the distribution path design plan and confirms the feasibility of genetic algorithm model and optimization plan.

logistics distribution;genetic algorithm;soft time window

F253.9

A

1004-4620（2015）03-0054-03

2015-05-15

尹作海，男，1980年生，2009年毕业于山东大学计算机科学与技术学院。现为山东大学财务部信息科副科长，工程师，从事财务信息化工作。