P5?P6?P85?0.79691776 ?0.14680064?0.9437184 P4?P5?P84?0.9437184 ?0.0458752?0.9895936 P3?P4?P83?0.9895936 ?0.00917504?0.99876864 P2?P3?P82?0.99876864 ?0.00114688?0.999915521 P1?P2?P8 ?0.99991552?0.00008192?0.99999744 P0?P1?P80?0.99999744?0.00000256?1 又因为Bm?mPm，所以： B0?0?P0?0

B1?1?P1?0.99999 74 B2?2?P2?2?0.999915?15.929983 10 B3?3?P3?3?0.998768?26.949630 59 B4?4?P4?4?0.98959?3 43.695837 B5?5?P5?5?0.94371?84.47185 9 B6?6?P6?6?0.79691776?4.78150656 B7?7?P7?7?0.50331648?3.52321536 B8?8?P8?8?0.167772?11.364217 72综上所述，当m=6时，作业能力值B达到最大值，表明拥有的机械设备在需用m台时发挥出了最大潜能,此时的选择台数为最佳。

利用二项分布方法计算机械设备合理拥有量,仅仅是从技术角度出发,保证生产的需用数量和完好率,完全忽略了机械设备的经济分析。完好率指标一定程度上反映了机械的技术状况,而在配送中心实际生产中,仅仅通过完好率指标无法全面描述设备管理中的技术与经济问题,所以这种方法具有一定的局限性。

41

第五章 配送线路选择与优化

5.1配送线路优化方法概述

配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速度、成本、效益影响很大。设计合理、高效的配送路线方案，不仅可以减少配送时间，降低作业成本，提高企业的效益，而且可以更好地为客户服务，提高客户的满意度，维护企业良好的形象。 配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使用车辆尽可能少）。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要启发算法去求得近似最优解。

（一）多车辆路径问题—VRP模型

多回路运输问题是现实中很普遍的一种调配问题，特别对于有大量服务对象的实体，例如拥有一个上千客户的企业。此类调配的核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型。 该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程最短，费用最小，时间尽量少等）。它涉及了多辆交通工具的服务对象的选择和路径确定两方面问题。 一个典型的VRP模型可以如下表述： 1. 单一的物流中心，多部车辆配送

2. 每个需求点由一辆车服务，每个客户点货物需求量不超过车辆的载重容量 3. 车辆为单一车种，即视为相同的载重量，且有容量限制 4. 无时窗限制的配送问题 5. 客户的位置和需求量均为已知

6. 配送的货物视为同一种商品

42

（二）多车辆路径问题的求解方法

多路径车辆问题的求解方法主要有精确优化方法、人工智能方法、模拟方法、启发式方法等，其中最为常用的就是启发式方法中的节约法和扫描法，下面主要介绍这两种方法。 节约法

节约算法（Saving Algorithm）是用来解决运输车辆数目不确定的VRP问题，

它是目前用来解决VRP模型最有名的启发式算法。节约算法能灵活处理许多现实的约束条件。

节约法的目标是使所有车辆行驶的总里程最短，使提供服务的车辆总数最少。算法的基本思想就是：如果将运输问题中的两个回路合并成一个回路，就可以缩短线路总路程（即节约了距离），并减少了一卡车。 节约算法的主要步骤如下： 1. 确定距离方阵。

这里的距离是指一个广义的距离，可以是两点间的实际空间距离，也可以是两点之间的运输成本。可以用两点间的坐标来计算两点间的距离CAB。 2. 计算节约矩阵。

节约矩阵是指将任两个客户的订货合并放在一辆卡车中运输时节约的累积。例如可以将线路“配送中心--客户A--配送中心”与线路“配送中心--客户B--配送中心”合并为一条线路“配送中心--客户A--客户B--配送中心”，节约的距离为??A,B?。 3. 将客户划归到不同的运输线路

将客户划归到不同的运输线路，有不同的卡车提供送货服务，同一线路上的客户由同一辆车辆提供送货。客户合并的宗旨是使节约的距离最大化。这是一个重复进行的过程。

这里要遵循两个原则：一是保证两条线路的合并睇可行的。如果两条运输线路上的运输总量不超过卡车的最大载重量，那么二者的合并就是可行的。二是试图使节约最大的两条线路合并成一条新的可行路线。这一过程一直持续到不能再有新的合并方案才算结束。

4. 确定每辆车的送货顺序

这是指确定每辆车的行驶路径，使所有车辆的总行程距离最短。这是一个单回路的

43

车辆路径问题， 可以使用Hopfield神经网络方法、遗传算法、启发式算法等求解，对于节点较少的问题，可以用简单贪婪算法求解最佳路线。其步骤如下： 1．选择距出发点最近的顾客位置。

2．再从剩下的位置中选择距离当前已选择的位置最近的顾客位置。 3．如果所有位置都被选择了，则停止；否则返回到第二步. 扫描法

扫描算法（Sweep Algorithm）也是用于求解车辆数目不限制的VRP问题，与节约算法不同的是，它属于亚启发式算法，而节约算法属于构造算法。在VRP求解方法中是一种先分群在寻找最佳线路的算法。

扫描法的基本原理是，先以物流中心为原点，将所有客户需求点的极坐标计算出来，然后依照角度大小以逆时针或顺时针方向扫描，若满足车辆装载容量即划为一群，将所有点扫描完毕后在每个群内部用最短路径算法求出车辆行驶路径。

扫描法的步骤：

1. 以物流中心为原点，将所有客户需求点用极坐标计算出来。

2. 以零角度为极坐标轴，按顺时针或逆时针方向，依角度大小开始扫描。 3. 讲扫描经过的客户点需求量进行累加，当客户需求总量达到一辆车的载重量限

制且不超过载重量极限时，就将这些客户划分为一群，接着按同样的办法对其与客户划分为新的客户群，指派新的车辆。 4. 重复步骤3，直到所有客户都被划分到一个群里。 5. 在每个群内用TSP算法求出车辆行驶的最短路径。

5.2建立最优配送路线 1、配送中心配送问题的描述

配送中心主要配送三种类型的商品，分别是家电、食品、药品，其中家电要求常温配送，食品更药品需要冷链配送，配送中心有两种类型的货车，分别是5吨的和2吨的，其中5吨的车没有温控，2吨的车有温控。所以我们使用5吨的车对家电进行配送，使用2吨的车配送食品跟药品。

各个需求点不同货物的需求量如下表：

44