张晓雨

【摘 要】本文从某生产加工型企业配送中心的实际问题出发，根据已知数据建立VRP问题数学模型，并且采用C-W节约式启发算法对车辆路径问题进行解答，逐步获得最优解。结果为该企业设计出优化的车辆配送路线以及车辆数安排，并且计算出每日车辆配送总费用。

【关键词】路径优化；C-W节约启发式算法

一、引言

物流作为“第三利润的源泉”，一直是企业和社会关注的热点问题。物流配送是物流活动的重要环节，降低配送成本，提高客户服务水平，对于促进企业物流的发展具有重要的意义。物流配送运输调度即是在满足客户需求的条件下，为客户配送合理的数量，派遣最少的车辆数量并为配送车辆指派运输时间和运输费用最省的路线，即车辆路径优化问题。

二、数据获取

配送中心有3辆载重为350kg的车，车辆行驶的固定费用为305元；单位里程运输费用为1元。

各客户需求量：苏果超市汉中门大街店：33迈皋桥苏果平价店 55；苏果超市集庆路店 41；苏果奥体庐山路购物中心 33；华润苏果文靖路平价店 48；苏果超市银都店38；苏果超市银都店46；苏果超市瞻园路店 35；苏果超市（和燕路店）53；苏果社区超市（月苑社区店） 45；苏果社区超市尧林仙居店 61；苏果超市大方巷店 33；苏果锁金东路社区店 56 ；苏果超市（马标店） 36；苏果超市（后宰门店） 29

三、数学模型

公式（3-2）说明配送车辆数不能超出所拥有的车辆数；公式（3-3）该配送车辆的运量不能超过最大载重量；；公式（3-4）每个点有且只有一辆车来进行配送；公式（3-5）若点i由车辆k送货，则车辆k送完该点的货后必到达另一点j；公式（3-6）若点j由车辆k送货，则车辆k必由某点i到达点j。

四、问题求解

1.算法步骤

连接原点和其他各点，得到15条线路；根据配送中心与各客户点的距离计算节约值s（i，j）；将所有s（i，j）按其值由大到小排列；按顺序逐个考察端点i和j，若满足：点i和点j不在一条线路上；点i和点j均与基点相邻，则插入线路中。

2.节约值及结果

求解结果得到两条路径分别是：路线一：0-13-11-10-2-9-12-1-0，长度57.1km；路线二：0-4-7-3-8-14-6-15-5-0，长度62.8km。该配送中心需要2辆载重为350kg的车辆进行配送，日总费用为729.9元。

五、总结

本文对于物流配送路径优化问题进行了描述，建立了VRP车辆路径问题数学模型，并采用C-W节约算法设计某配送中心的配送路径。C -W 节约算法求解速度快、通用性强、限制条件易于加入，优先考虑一些配送中心较远的需求点是一种相当实用的启发式算法。

参考文献：

[1]黄震，罗中良，黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J]. 中山大学学报（自然科学版），2015，01：41-46.

[2]赵春阁，徐群. 基于C-W节约算法的物流配送车辆路径问题的研究[J]. 泰山学院学报，2014，03：61-65.