多配送中心路径优化研究

韩茜 苗倩

摘 要针对冷链物流配送客户分布不均匀，导致单一配送中心压力过大、配送中心之间车辆调度不协调的问题，提出了一种改进的遗传算法求解多配送中心路径优化问题的方法。建立了基于K-means聚类算法与遗传算法相结合的冷链物流车辆路径优化模型。给出基于全局最优的区域划分与车辆路径协调优化策略，以实现多配送中心协同配送。最后，通过实例分析证明了该算法及优化策略可以有效地减少运输成本，提高多配送中心整体的工作效率。

关键词冷链物流;多配送中心;区域划分

中图分类号： U12 文献标识码： A

AbstractAiming at the problem of uneven distribution of cold chain logistics distribution customers，resulting in excessive pressure in a single distribution center and uncoordinated vehicle scheduling between distribution centers，an improved genetic algorithm for solving multi-distribution center path optimization problems is proposed.A cold chain logistics vehicle routing optimization model based on K-means clustering algorithm and genetic algorithm is established.A global optimization based region division and vehicle path coordination optimization strategy is proposed to achieve coordinated distribution of multiple distribution centers. Finally，an example analysis shows that the algorithm and optimization strategy can effectively reduce transportation costs and improve the overall efficiency of multi-distribution centers.

Key WordsCold chain;Multi-distribution center;Regional division

0 引言

随着现代社会城市规模不断扩大，电子商务发展迅速，从下单到送货再到收货，其中最重要的就是物流配送这一环节[1]。生鲜产品本身所具有的易腐性使得配送成本本身就高于常温产品，同时也给它的配送质量提出了更高的要求。冷链物流配送受到越来越多学者的关注，文献[2]根据生鲜产品的时效性强的特点，将顾客满意度用模糊隶属度函数表示，验证了模型及算法的有效性。文献[3]针对顾客的随机需求，建立了多温共配路径优化模型。本文针对冷链品的配送问题，考虑企业有多个配送中心，多辆配送车，将K-means算法与改进的遗传算法相结合，从全局上合理划分配送区域和配送路径，以达到降低成本、提高冷链品配送质量的目的。

1 问题描述与数学模型

设某城市中有一个总调度中心安排订单配送，H个配送中心，每个配送中心服务的顾客区域构成一个配送分区，负责给n个客户点完成配送任务，配送中心拥有的车辆数为Kh，且每个配送中心车辆数相等，车型统一，每辆车的最大载装为Q。已知客户i到客户j的运输距离为dij以及客户i的需求qi，要求设计一套合理的调度方案，使所有客户点的货物需求都得到满足，并使总成本最小且满足以下约束条件：式中gkh表示第h个配送中心的第k辆冷藏车所产生的固定成本;φ为单位行驶里程成本;p为冷链产品的单位价值;β1、β2为运输过程中的产品腐败率和装卸过程中的产品腐败率;Q■■是第h个配送中心的车辆k到达客户i时车上所运载的剩余货量。

2 算法设计

遗传算法的启发来自达尔文的进化论，它是依照自然选择和自然进化的原理，模拟生物在自然界中的进化过程所得到的一种优化求解方法[4]。本文利用K-means算法对客户点进行聚类，将聚类的结果作为遗传算法中的初始种群，并且使每个个体满足约束条件，然后利用遗传算法对路径进行优化，之后再随机选择聚类方案再次进行K-means区域划分，直到找到最優解。算法流程如下：

步骤1：将配送中心作为起始点，顾客用自然数进行编号，作为遗传算法的染色体。

步骤2：将自然数列随机排列形成一条染色体，通过循环随机生成N条染色体，作为一个初始种群。

步骤3：把初始种群中的每一个个体带入适应度函数中，求出每个个体的适应度。

步骤4：进行选择、交叉、变异操作。

步骤5：如果满足终止条件，则输出解，否则返回步骤2。

3 算法实验及结果分析

假设某配送站有3个配送中心，每个配送中心有3辆配送车辆，共有60个客户分布点，已知客户需求量且配送车辆的车型规格统一。

对于多配送中心路径优化问题，如果采用传统的固定区域划分方法，就只能求出每个区域的最优解，而不利于求整体最优解。本文在解决问题时采用动态区域划分的方法，这样做能够根据不同顾客点的位置灵活分配配送任务，使结果更加接近于整个配送区域的全局最优解。根据实验结果分析比较可知：在进行区域动态划分后，顾客订单所在的配送区域发生了改变，配送路径也和原来有很大区别，辆配送的顾客数目也能相对更加均匀一些。从距离上看，基于固定区域划分的配送距离为989.53km，基于动态区域划分的配送距离为905.5km，相比原来减少了8.5%，这在一定程度上能降低配送成本。

4 结束语

本文研究中采用动态划分配送区域的方法，将多个配送中心问题转化为多个单一配送中心问题，在一定程度上减少了原算法的复杂程度。通过这种方式，根据顾客点所在位置的不同，随时调整车辆配送区域，为现实应用提供了可行依据。算法实验结果表明：在动态区域划分下，车辆的配送距离有所缩短，能够在一定程度上减少企业的生产成本。将来在研究过程中可以还考虑顾客需求量对路径规划的影响，或是还可以把时间窗作为限制条件一并进行优化。

参考文献

[1]殷脂，叶春明.多配送中心物流配送车辆调度问题的分层算法模型[J].系统管理学报，2014，23（04）：602-606.

[2]邵举平，曹倩，沈敏燕，孙延安.生鲜农产品配送中带时窗的VRP模型与算法[J].工业工程与管理，2015，20（01）：122-127，134.

[3]王淑云，孙虹.随机需求下冷链品多温共配路径优化研究[J].工业工程与管理，2016，21（02）：49-58.

[4]蓝永联.广交长运冷链物流配送路径优化研究[D].华南理工大学，2017.