零担物流中配送路径优化与接货整数规划—以大达物流宜兴派送中心为例

陈湘州，文思倩，冯鑫海，陈为民

（湖南科技大学　商学院，湖南　湘潭　411201）

零担物流中配送路径优化与接货整数规划—以大达物流宜兴派送中心为例

陈湘州，文思倩，冯鑫海，陈为民

（湖南科技大学商学院，湖南湘潭411201）

以零担物流中遇到最普通也最急需优化的成本来源—配送路径优化和接货整数规划为研究对象，结合江苏百成大达物流有限公司的日常货物运输安排进行分析，利用C-W优化算法和整数规划算法对每天派送中不同的客户地址和条件进行最低成本方案优化，并通过事例推理的方法对这些最低成本方案进行优化组合，建立起了派送与接货一体化考虑的优化系统，并用实例进行了验证。优化结果具有很高的经济价值，能为公司节约不必要的开支，而且节约下的车辆和司机可以配备到其他地区的配送路线中，或者应对一些突发状况，从而提高了公司的资源利用率。

零担物流；派送中心；路径优化；节约算法；0-1整数规划

1　前言

公路货运是国家经济的命脉，它不仅支撑了国民经济的发展，而且调整了经济结构。物流业属于劳动力密集型产业，在一定程度上是体现地区经济的晴雨表。随着经济的不断发展，物流技术的逐步更新，我国内地公路零担物流企业每年以15%左右的速度增长。

零担物流作为道路物流的主要形式，在公路物流中具有重要作用。作为物流的一个重要组成部分，具有集散为整、化整为零、分路运送、转运直达、便捷迅速等特点，很大程度上方便了人们的生产生活，越来越成为推动国家经济发展的重要动力和调整产业结构、增加就业机会的保障。面对电子商务和国际货代的繁荣发展，零担物流公司普遍存在着服务水平不高、经营效益不高、经营水平不高等窘状，因此，寻求科学合理的配送路径，并以此降低成本，减少不必要的油耗等节能行为、提升货物装载率和客户满意度、提高部门经济效益，促进零担物流健康、快速、节约、可持续发展是亟待解决的问题。

王亚晴等指出物流零担配送路线问题是物流配送优化的重要问题，他们提出了扩圈法的求解方法［1］。赵新慧采用了MVC的模式进行建模，并基于Java ME的Java手机软件这一思路，能够成功地服务于零担物流运输，为广大的货主和司机建立一个畅通的交流平台［2］。吕峰等使用Matlab实现对零担物流运输卸载路径优化，当表示路径的换位矩阵通过迭代计算趋于平衡点时，运费目标函数也趋于最小值［3］。张志清等运用树形结构的最小树生成得到多路线方案，最后用层次分析法计算得出最佳路线，但是并未涉及接货整数规划［4］。高超锋等考虑到网络中枢纽点集散平衡和枢纽点间干线对流平衡对网络设计的影响，建立二级轴辐式零担物流网络混合整数规划模型，并进行算例仿真分析，得出了当不考虑平衡时，网络资源有较大的浪费，而随着平衡程度要求不断提高，网络运营总成本有所上升，枢纽集散及干线对流平衡综合度明显增加，网络资源得到均衡利用［5］。

多数零担物流司机只能简单的凭经验和感觉规划派送路径，其油耗和保养也只能靠平时的习惯来估计。基于零担物流派送中心具体情况，本文从成本最小化、利润最大化的角度出发，加上时间约束，提出了派送环节的路径优化和接货环节的0-1整数规划，从部门每日工作流程和实际出发，把送货时的路径最优和接货时的多种限制作为完整的工作流程都考虑在内，让部门调度或司机可以轻松合理地安排车辆。

2　派送中心日常工作及接送货环节概述

零担物流派送中心的工作大同小异。大达物流宜兴派送中心负责整个宜兴市的货物派送任务。部门有三辆4.2m厢式货车和一辆6.5m厢式货车。四辆车各负责一片派送范围，其派送范围主要按照丁蜀、北线、官林、外围四片区域划分，覆盖了宜兴市21个街道和乡镇，派送范围如图1所示。

图1　宜兴派送中心派送区域分布图

派送中心的工作主要包括接送货、开发维护客户、跟踪监督货物、解决客户难题和日常的维护工作。其中派送中心工作中最为重要的接送货也是区别其他部门的标志。

（1）把干线车上的货物按相应的区域卸车，并装车送往客户手中；

（2）大票货物（占一辆车有效容积的70%）优先派送，然后派送其余货物；

（3）当有客户需要发货时，物流专员通知负责派送该区域的司机安排接货，客户数和预计的货量很少时，司机一般原地待命；

（4）当通知客户数和预计货量达到一定程度时接货，并在途中估算时间和容纳货物量；

（5）接收到的货物还要有开单打单、称重量方、简单的包装、粘贴标签、装车封车等工序。公司规定干线车必须要在当天晚上九点前发车，接货司机一般每日的工作时长为11h，在下午7点前车辆就要到达部门并卸下接来的货。

每日接送货流程及条件如图2所示。

2.1送货环节特点及要求

里程最短、时间最短。零担物流的客户绝大部分是工厂企业，货物多是生产原料或产品配件，为了保证生产的连续性，收发货人都十分重视派送的准时率。对于派送中心来说，按时、及时地把货物送到客户手中就是最大的目标。送货时要提前规划好线路，尽量不重复相同的路，缩短里程就是节约时间。这样也为司机节省出更多的时间去接货、去规划路线。

图2　派送中心每日车辆工作流程图

2.2接货环节特点及要求

货量最多、客户数最多。部门的收入是由每天接到货物的运费决定的，在有限的时间内如何尽可能多地经过客户并且尽可能接货量大的货，是每个部门每天都会遇到的问题。这也是本篇论文讨论的核心。在接货环节也有几个限制条件：

（1）车辆的容积和载重是一定的，载重限制为5t，容积为13.5m3。

（2）工作时间是一定的，不能超过11h。

（3）客户的货物可能不能一次装下，需要根据每个客户的货量来决定走什么样的路线。

3　派送环节路径优化方案设计

3.1模型原理及步骤

本文所用的路径优化方法是节约里程法，原理如下：

假设有n个点，把每个要去的地方看成一个点，取其中的一个点为基点，例如以1为基点。首先联接基点和其他所有的点，构成1→j→1（j=2，3，…，n），得到一个含有n-1条路径的图，按此路线访问n个点所走的里程总和为：

其中c1j为由点1到 j（j=2，3，…，n）的里程长度，此处假定c1j=cj1（对所有的 j）。假如联接了点i和 j且走弧这时就不再走弧和节约的里程值可计算如下：

计算步骤如下：

（1）选取基点，例如选取点0为基点。将基点和其他各点相联接，得到n-1条线路1→j→1（j=2，3，…，n）。

（2）如果这些可连接的点不违反限制条件，就可以计算其节约值（i，j不为基点）：

（3）将所有的s（i，j）从大到小排列。

（4）按s（i，j）从大到小的顺序，逐个考查其端点i和j是否满足如下条件，如果满足下列条件，就可将弧插入到线路中。

①点i和j不在一条线路上。

②点i和j均与基点相邻。

3.2C-W节约算法实现路径优化的基本应用

以2015年5月8日派送货物清单为例，见表1。

表1　收货地址列表

根据表1建立各派送点间的距离表，见表2。以派送中心0为基点，构成初始线路图。按照式（2）计算将弧插入到线路中时引起的里程节约值，并按节约值从大到小的顺序将它们填入节约值表3。

对每条弧按照节约值从大到小的顺序检查，看它是否能插入到线路上。如果能插入，就改变线路。

由表3可知：用该方法得到的线路为0→1→7→8→2→9→3→6→4→5→0。

该条路线的总长度为：

表2　派送点距离表（km）

表3　节约值表

3.3随机选取几条送货路径及与最优路径的比较结果

若随机选取几条派送路径计算其路程：

路径1：0→6→1→5→7→8→3→2→4→9→0

路径2：1→6→8→3→9→7→4→1→5→2→0

路径3：0→7→5→3→9→1→8→2→4→6→0

路径4：0→9→6→3→8→5→2→7→4→1→0

路径5：0→7→8→9→4→5→6→1→2→3→0

路径6：0→3→6→9→8→7→4→1→2→5→0

路径7：0→1→5→9→6→3→2→4→7→8→0

这7条路径方案的路程长度见表4。

表4　路径值

由此可见，经过节约里程算法优化后的路径明显比其他七个路径要短。这七条路径的平均长度为44.124 29，这比优化后的路径要长9.054 286km。如果按4.2m厢式货车平均油耗0.9元/km来算，则这台车出车一次大概可以为部门节约8元。而且部门有四台车，每天可以节省32元左右。

4　收货环节0-1整数规划方案设计

4.1收货环节0-1整数规划的基本模型及运算

接货工作的流程如图3所示。

图3　接货流程图

假设各变量：

单票货物带来的利润为a1，a2，a3，...，ai；

单票货物所耗费的时间为b1，b2，b3，...，bi；

单票货物的重量为v1，v2，v3，...，vi；

单票货物的体积为w1，w2，w3，...，wi；

送货环节所用时间为B（一般为5）；

货车最大容积Wi为13m3；

货车最大载重量Vi为5t；

某一区域总客户为n。

目标函数（求最大利润）：

约束条件：

（1）所装货物重量不能超过货车载重的上限，即：

（2）所装货物体积不能超过货车容积的上限，即：

（3）送货环节和接货环节总工作时长不能超过11h。

由于公司上班时间为08:00，21:00干线车准时出发，即下班时间最晚为21:00。但货物不仅需要运到派送中心，还要根据客户和货物进行简单包装、称重量方、粘贴标签等工作，所以货车实际在19:00就需要返回部门，工作时间为11h。

（4）接货的客户数要大于该区域总客户数的80%：

公司对部门的考核不仅在货量上有规定，对客户的数量也有规定。

某天某区域通知接货的客户信息见表5。

表5　客户接货信息表

运用MATLAB软件求解可得：

由此可知：司机可接除3号、14号客户以外的全部客户的货物。

约束内最大收益为1 395元。

4.2按通知顺序接货的模型及运算结果

如果只按照通知接货的顺序去接货的话，即：

目标函数（求最大利润）：

约束条件：

（1）所装货物重量不能超过货车载重的上限，即：

（2）所装货物体积不能超过货车容积的上限，即：

（3）送货环节和接货环节总工作时长不能超过11h。

（4）按照通知从1到15号客户依次接货：

可建立重量、体积、时长、收益的累积表，见表6。

表6　累积表

由此可知当货车装完第12个客户时，总时长快要达到最大限值，即是满足方程限制的最优解。此时，部门可获得的收益为1 190.4元。这明显小于优化后的1 395元。所以，优化还是比较成功的。

［1］王亚晴，覃运梅.物流企业零担配送路线的优化方法［J］.物流工程与管理，2012，（1）:125-126.

［2］赵新慧.零担物流运输信息系统的设计与实现［J］.交通信息与安全，2009，（1）:134-136.

［3］吕峰，赵卫东，邱会鲁，等.连续Hopfield神经网络零担物流运输路径优化研究［J］.软件导刊，2015，（6）:26-27.

［4］张志清，汪世志.制造业零担运输优化—以湖北为例［J］.物流技术，2013，（9）:148-150.

［5］高超锋，林庆福，胡志华.基于枢纽集散和干线对流平衡的二级轴辐式零担物流网络设计［J］.华中师范大学学报（自然科学版），2015，（4）:551-556.

Distribution Route Optimization and Cargo Pick-up Integer Programming in LTL Logistics:In the Case of Yixing Delivery Center of Dada Logistics

Chen Xiangzhou，Wen Siqian，Feng Xinhai，Chen Weimin
（School of Business，Hunan University of Science&Technology，Xiangtan 411201，China）

In this paper，with the distribution route and cargo pick-up integer programming as the object，we analyzed the routine cargo transportation schedule of the Jiangsu Baicheng Dada Logistics Company，used the C-W algorithm and integer programming algorithm to optimize the customer address and condition in its everyday delivery so as to achieve minimum cost，then through the case-based reasoning，combined and optimized the solutions with the minimum cost，established the optimized system that integrated cargo delivery and pick-up，and at the end，verified its validity through an empirical case.

LTL logistics；delivery center；route optimization；saving algorithm；0-1 integer programming

TQ520.62；F224

A

1005-152X（2016）06-0129-05

10.3969/j.issn.1005-152X.2016.06.031

2016-05-03

湖南省研究生科研创新项目（CX2015B512）

陈湘州（1969-），女，湖南娄底人，湖南科技大学商学院副教授，硕士研究生导师，研究方向：企业管理；文思倩（1991-），女，湖南永州人，湖南科技大学商学院硕士研究生，研究方向：企业管理、闭环供应链管理；冯鑫海（1993-），男，湖南长沙人，任职于山西怡园酒庄有限公司，研究方向：物流管理；陈为民（1973-），男，河南渑池人，湖南科技大学商学院副教授，研究方向：数据挖掘、决策支持系统、风险管理。