收派业务优化是根据收派需求的时空分布对收派线路进行优化设计，对收派人员、车辆合理配置和调度，实现“快速响应，准时送达”的目的。

图6-12　网点班车线路图

1.收派线路分析

设计一条收派线路，主要考虑三个因素：一是收派的准点率，二是业务量，三是收派的效益。

1）收派准点率分析

收派准点率是指实际准点完成的任务数与对该收派线路分配的收派任务总数的比例。收派准点率不得低于设计该线路时制定的准点率标准，而且越高越好。若低于准点率标准，就必须对该线路不能准点收派快递的原因进行调查分析，并对该线路进行优化。

2）业务量分析

业务量是指该线路在一定时间内完成的收派快递量。在准点率有保障的前提下，业务量越多越好。业务量超过一定限度，可能会出现超负荷运行，导致准点率下降。如果业务量经常低于最低标准，则说明该线路的覆盖范围不合理，必须对该线路进行优化。

3）收派效益分析

收派效益是指该线路一定时间段内完成的收派任务所花费用与总收入之间的比例。费用占总收入的比例越低越好，费用低则说明效益好。如果费用过高，则说明该线路存在问题，需进行优化。

对收派线路进行分析时应综合考虑以上几点，同时也要考虑业务的发展需要以及收派网络的覆盖范围，尽可能客观地反映收派线路的效益，针对存在的问题深入研究，制订有效的解决方案，不断对线路进行优化。

2.收派线路优化原则

进行收派线路优化时需遵守以下原则。

（1）时效第一原则。时效是快递服务的生命，优化收派线路时一定要把时效放在第一位。

（2）路线最短原则。只有最短的线路，才能实现合理的时效和成本。

（3）最佳成本原则。在保障时效的前提下，应尽量降低成本，寻找最低成本路线。

（4）一线多点原则。一线多点原则是指一条收派线路尽可能完成多个收派任务，尽可能将收派任务添加到已有的线路中去，尽可能将收件任务添加到派送线路中去。

（5）交通工具最合理原则。优化收派线路时应充分考虑时效、距离以及业务量，合理地选用交通工具。

3.收派线路优化的方法

在从货物的配送中心输送到货物配送目的地的过程中，由于配送中心数量和客户收货地点的数量不同，配送线路的优化计算也不同。

1）一对一配送

一对一配送是由一个供应点到一个客户的配送，在这种配送运输模式中，要求选择最短的配送路线，实现高效率的配送。在这种情况下，就归结为“最短路问题”。

给出一个图A=（V，E），其中V=｛1，2，…，n｝是图中节点的集合，连接两个节点Vi和Vj的有向线段称为弧，记为（Vi，Vj），E为图中全体弧的集合。图A中的每一段弧（Vi，Vj）都对应一个非负数wij称为弧（Vi，Vj）的权，wij可以是点Vi到点Vj的距离，或者行车时间，或者运费等，记为W=｛（Vi，Vj）∈E｝，G=（V，E，W）被称为网络。

对于给定的网络G=（V，E，W），设P是G中从点Vi到点Vj的一条有向路，它通常由若干条首尾连接的弧组成。我们把这些弧的权的和称为有向路P的权，并记为W（P）。最短路问题就是要在G中所有从Vi到Vj的路中找出一条权最小的路Pij，W（Pij）=min｛W（P）｝。如果找到了这样的一条路Pij，即将W（Pij）记为d（i，j）。如果V1为起点，就将d（1，j）简记为d（j）。

寻求最短路的基本思想是从起点V1出发，逐步向外探寻，按规则对所有节点进行标号。标号分两类，一类是永久标号，表示从V1到该点的最小权，并把这个最小权写在方框中置于节点上方。设将已获得永久标号的节点集合记为Xk，则其余节点为第二类标号节点，即临时标号的节点，它们组成的集合记为Yk（Yk=V—Xk）。现在再从Yk中找出一点Vr，该点的临时标号是Yk中各点的最小者，将其并入Xk组成Xk+1=Xk∪｛Vr｝。反复这样的过程，直至最后一个节点也并入永久标号节点的集合Xn。具体步骤如下。

第一步，令d（1）=0，在起点V1上方标上永久标号。这时X1=｛1｝，Y1=｛2，3，…，7｝。对Y1中的每一点都标上临时标号d（j）（j=2，3，…，7）。注意：d（j）为Vi到Vj的最小权，如果点Vj与V1不相邻，则认为d（j）=+∞（暂不标在点上方）。

第二步，求出Y1中所有临时标号的最小者。不妨设d（2）=min｛d（j）｝j=（2，3，…，n），则将点V2并入X1得到X2=X1∪｛2｝=｛1，2｝，并将标在点V2的上方，与此同时，将Y2中的每一点标上临时标号。

第三步，设已求得Xk和Yk，若还有节点不在Xk中，则继续求点V1到Yk中各点的最小权，并把它标在点上方。求Yk中各点的最小权的方法如下。

设点Vj∈Yk，Xk中与Vj相邻的节点有Vi，Vp，…，Vq，则点Vj的最小权为d（j）=min｛d（m）+wmj｝，其中m∈｛i，p，…，q｝。若Xk中没有节点与Vj相邻，则认为d（j）=+∞。这样，便可以比较出Yk中临时标号的最小者。不妨设d（k+1）为Yk中最小的临时标号，则将点Vk+1并入Xk得到Xk+1。如果Xk+1包含了全部节点，则终止运算，否则继续进行第三步。

例如，有7个节点，节点间的距离及关系如图6-13所示，求从点1到点7的最短路径和最小距离。

图6-13　各点间距离关系及第一次标号后的情况

解：第一步，给点1标上永久标号，这时X1=｛1｝，Y1=｛2，3，4，…，7｝。将Y1中各点标上临时标号。由于点2和点3与点1相邻，它们的临时标号分别为2和4［注意：d（3）是由点1到点3的最小距离，所以d（3）=4］，而其余节点与点1不直接相邻，它们的最小距离d（j）=+∞（j=4，5，6，7），暂时都不标出（见图6-13）。

第二步，Y1中各节点的最小临时标号为d（2）=2，于是将点2并入X1，并在其上标以，则X2=｛1，2｝，Y2=｛3，4，…，7｝。Y2中点3、点4、点5与X2中的节点相邻，它们的临时标号分别为d（3）=d（2）+w23=2+2=4，d（4）=d（2）+w24=2+2=4，d（5）=d（2）+w25=2+6=8，点6和点7的临时标号均为+∞（见图6-14）。

图6-14　第二次标号后

第三步，d（3）=d（4）=4为Y2中的最小临时标号。将点3和点4并入X2，则X3=｛1，2，3，4｝，Y3=｛5，6，7｝。点5、点6的临时标号分别为

d（5）=min｛d（2）+w25，d（4）+w45｝=min｛2+6，4+5｝=8，

d（6）=min｛d（3）+w36，d（4）+w46｝=min｛4+5，4+4｝=8而d（7）=+∞（见图6-15）。

第四步，经第四次、第五次标号后，得到的最后结果如图6-16所示。再用粗箭线标出每一个节点获得永久标记的路径，即可看出，由点1到点7的最短路径为①→②→⑤→⑦，最小距离为11。

图6-15　第三次标号后

图6-16　最后结果

实际上，图6-16还给出了由点1到各节点的最短路径和最小距离，只需沿着图中的粗线行进。例如，到点6的最短路径就是①→②→④→⑥，最小距离就是点6的永久标号8。

2）一对多配送

一对多配送是指由一个供应配送点往多个客户货物接收点的配送，这种配送运输模式要求同一条线路上所有客户的需求量总和不大于一辆车的额定载重量。其基本思路是：由一辆车装载所有客户的货物，沿一条优选的线路，依次逐一将货物送到各个客户的货物接收点，既保证按时送货又节约里程，节省运输费用。

解决这种模式的优化设计问题可以采用节约里程算法（节约算法）。(www.daowen.com)

近年来，由于小批量、多批次的及时配送方式的发展，运输费用正在逐年提升，许多企业的运费已经超过了库存费用，选择有效的配送路线已经成为控制物流成本的主要措施。现代企业已经普遍接受了一种观点，即有效的配送路线实际上是保证货物准时到达客户指定点，并且尽可能减少运输的车次和运输的总里程的路线。在这种指导思想下，节约算法已经成为选择配送路线的主要方法，受到了国内外物流界的青睐。

节约算法的具体步骤如下。

第一步，形成一个初始解。形成初始解时，需要满足所有顾客的需求，而且所有的约束条件，如容量的限制、车辆总数的限制等也得到满足。初始解可以由具体运载限制的最近邻点法求得。形成初始解后，可以得到每个车辆的一个初始的运输方案，Tk=｛0，i，…，j，0｝，其中，k表示车辆的标号；i，j表示顾客的标号；0表示配送中心。

第二步，进行节约度的计算。通常以Δcij表示节约度，也称为节约量。

如图6-17所示，假设P为配送中心，A和B为客户接货点，各点相互的道路距离分别用a、b、c表示。比较两种运输路线方案：一是派两辆车分别为客户往A和B点送货，总的运输里程为2（a+b）；二是将A和B两地的货物装在同一辆车上，采用巡回配送的方式，总的运输里程为a+b+c。若不考虑道路特殊情况等因素的影响，第二种方式与第一种方式的路程差为2（a+b）—（a+b+c），按照三角形原理可以看出，第二种方式比第一种方式节约的里程数为a+b—c。节约算法就是按照以上原理对配送网络的运输路线优化计算的。两种方案相比，按以下公式计算节约度，然后对计算结果进行降序排列。

图6-17　节约算法的基本思想示意图

第三步，进行回路的合并。从降序排列的节约度序列中的最上面的值开始，执行下面的步骤。对于一个已知的Δcij先判断这两个关系到i和j的回路是否存在合并的可能性。如果一个回路以（0，j）开始，一个回路以（i，0）结束，则该回路可以合并，并进行下面的合并操作：删除两个回路中的部分路径（0，j）和（i，0），然后引入新的连接（i，j），得到新的回路（0，…，i；0，…，j）。

［例4］现有一配送网络，如图6-18所示。图中P为配送中心，其余A～I为各客户的接货点，各边上的数字为距离，单位为千米；括号里的数字为需输送到各接货点的货物量，单位为吨。

图6-18　配送网络图

假设该配送中心有最大载重量为2吨和5吨的两种货车，并限制车辆次运行线路距离不超过35千米。

解：第一步，利用前面所述的最短路径法求出网络各节点之间的最短距离，计算结果见表6-3。

表6-3　网络节点的最短路径　（单位：千米）

第二步，根据表6-4，计算各用户之间的节约里程，见表6-4。

表6-4　用户之间的节约里程数　（单位：千米）

第三步，对节约里程按大小顺序进行排列，结果见表6-5。

表6-5　节约里程排序结果　（单位：千米）

初始解：从P向各个接货点配送，共有9条，总的运行距离为136千米，需要2吨货车7辆，5吨货车2辆，如图6-19所示。

图6-19　初始解结果

二次解：按照节约里程的大小顺序，连接F-G、F-H，如图6-20所示。

图6-20　二次解结果

总运行距离=2×（6+5+8+7+5+4）+9+4+7+12=102（千米），总运行距离为102千米，配送线路7条，需要2吨货车5辆，5吨货车2辆，其中，配送线路1的运行距离为32千米，装载量为4.7吨。

三次解：连接B-C、A-B、H-I，但因为H-I加入配送线路Ⅰ后，超过车辆最大载重量5吨，所以不予连接，如图6-21所示。此时，总的配送线路为5条，总运行距离为81千米，需要2吨配送货车2辆，5吨配送货车3辆。其中，配送线路Ⅱ的运行距离为19千米，装载量为3.8吨。

图6-21　三次解结果

四次解：连接A-I到配送路线Ⅱ，如图6-22所示。总的配送路线为4条，总运行距离为73千米，需5吨货车3辆，2吨货车1辆。

图6-22　四次解结果

最终解：由于受配载的限制，配送路线不再添加新的节点，连接D-E。这样就完成了全部的配送路线的设计，总共有3条配送路线，总运行距离为67千米，需要2吨货车0辆，5吨货车3辆。其中，配送线路Ⅰ运行距离为32千米，装载量为4.7吨；配送线路Ⅱ运行距离为23千米，装载量为5吨；配送线路Ⅲ运行距离为12千米，装载量为4.7吨，如图6-23所示。

图6-23　最终解结果

节约法需考虑的因素和注意事项：

（1）适用于顾客需求稳定的配送中心；

（2）各配送路线的负荷要尽量均衡；

（3）要充分考虑道路运输状况；

（4）预测需求的变化及发展趋势；

（5）考虑交通的状况；

（6）可利用计算机软件求解最优解。

3）多对多配送

多对多配送是指多个供应点向多个客户的配送运输，这种配送运输模式根据供与销是否平衡又分为两种。

（1）供销平衡模式。

供销平衡模式可以用数学语言描述。设有m个产地Ai（1，2，…，m）供应同一种物资，产量分别为ai（1，2，…，m）单位；有n个销地Bj（1，2，…，n）消耗同一物资，销量分别为bj（1，2，…，n）单位。总产量与总销量相等。第i个产地运到第j个销地单位物资运价为cij（1，2，…，m；1，2，…，n）。如何调运使运费最小。

用xij（1，2，…，m；1，2，…，n）表示从第i个产地调运给第j个销地的物资单位数量。该问题可归纳为如下的数学模型：

（2）供销不平衡模式。

前面阐述了产销平衡的运输问题，但在实际运输配送的物流活动中，往往是产销不平衡的情况比较多。所谓产大于销是指总产量大于总销量，产大于销可以看成产地有库存，将其假想为一个销地，从产地到假想的销地的单位运价为零，这样不平衡问题就化成了平衡问题。同样，需求大于产量时，可虚设一个产地，其虚产量为总需求与原总产量的差，把问题化为产销平衡问题。

产销平衡和产销不平衡问题是多个供应点向多个接货点供货时遇到的问题，也是配送优化调度的问题，具体算法可参考运筹学的相关内容。