郑明物流公司物流网络系统设计 - 图文

(3.2)

其中：配送费率；为 i 点的配送量或资源量；为 i 点与配送中心的距离；各资源点或配送点的空间坐标为（xi，yi）；( x , y )为配送中心的空间坐标。

对于连续空间单一配送中心的选址问题学术界一般都采用重心法，这种方法是将物流系统的需求点和资源点看成是分布在某一平面范围内的物体系统，各点的需求量和资源量分别看成是物体的重量，物体系统的重心将作为物流网点的最佳设置点，利用确定物体重心的方法来确定物流网点的位置。运用重心法求解配送中心的空间坐标为：

其中：hi配送费率；为 i 点的配送量或资源量；为 i 点与配送中心的距离；各资源点或配送点的空间坐标为（xi，yi）；( x , y )为配送中心的空间坐标。

对于连续空间单一配送中心的选址问题学术界一般都采用重心法，这种方法是将物流系统的需求点和资源点看成是分布在某一平面范围内的物体系统，各点的需求量和资源量分别看成是物体的重量，物体系统的重心将作为物流网点的最佳设置点，利用确定物体重心的方法来确定物流网点的位置。

图3.2重心模型示意图

15

第四章物流配送路径优化模型

4.1物流配送路径优化模型概述

物流配送是指物流公司根据送货单上的送货信息进行分货、配送的过程，并且能够达到及时、安全、经济的配送目的，让收货人能够满意。在配送过程中配送路径的选择非常重要，一条合理的配送路径不仅能够加快配送速度、降低配送成本，而且能够极大的提高配送质量，使客户得到满足。

整个物流配送过程是：配送中心根据每个配送点的配送信息，安排配送货车向多个配送点配送货物的过程，这个配送过程要综合考虑配送路径和配送的成本。此外配送还要求满足以下几个要求：

（1）配送货车要在要求的时间段之内准确及时地将货物送到客户手中； （2）配送结束后，货车能够在较短的时间内返回到配送中心； （3）配送的货车不能超载。

物流配送路径优化问题是一个典型的多项式复杂程度的非确定性问题（NP问题），因此，物流配送路径优化问题解决的关键是找到一种有效的算法。遗传算法（GA）和模拟退火算法（SA）是两种解决这方面问题的两种算法，并体现出了很好的优势

【7】

。

GA算法易出现早熟收敛问题，且进化后期的搜索效率也不高，但是，GA在全局搜索方面有很好的性能。SA在全局搜索方面的能力也很好，但过于依赖参数。以下将会对配送路径优化的数学模型和这两种算法进行介绍。

4.2物流配送路径优化问题的数学模型

用K表示货车的数量，包括配送中心在内的需求点共有N?1个，货车的数量等于路径的数量，每条路径有一辆货车服务，每个需求点只能由一辆车负责送货，货车送货过程中单位距离需要单位费用和单位时间，即dij?tij?cij。

xijk?1表示第k辆送货车从需求点i到需求点j，xijk?0表示从需求点j到需求点i，

ti和wi分别表示货车到达顶点i的时间和货车在顶点i的等待时间，K,N分别表示货车

数量和需求点的数量，dij表示需求点i到需求点j的距离，tij表示货车从需求点i到需

mi为需求点i的需求量，cij表示货车从需求点i到需求点j的费用，求点j的送货时间，

qk为第k辆货车的载重量，fi为需求i的服务时间，ei和li分别为货车到达需求点i的

16

最早时间和最晚时间，rk表示第k辆货车的结束时间。根据以上定义的各个参数建立以下数学模型：

目标函数：min?KNi?0j?0,j?ik?1N??cxijkNKijijk（4-1）

满足以下条件：??xk?1j?1?K?i?0（4-2）

?xj?1KNijk??xijk?1?i?0,k?(1,K)（4-3）

j?1N????NiKNNxijk?1?i{1,???N}（4-4）

k?1j?0,j?ixNijk?1?j{1,???N}（4-5）

k?1i?0,i?j?m?i?1Nxijk?qk?k{1,???K}（4-6）

j?0,j?i??Nxijk(tij?fi?wi)?rk?k{1,???K}（4-7）

i?0j?0,j?it0?w0?f0?0（4-8）

??KNxijk(ti?tij?fi?wi)?tj?j{1,???N}（4-9）

k?0i?0,i?jei?(ti?wi)?li?i{1,???N}（4-10）

其中，（4-1）是目标函数, 方程（4-2）规定了最多的路径数量，（4-3）表示货车的出发点和返回点都是配送中心，（4-4）和（4-5）确保每个需求点只被一辆货车送货一次，（4-6）表示货车运输过程不能超载，（4-7）表示货车的运输结束时间，（4-8）、（4-9）、（4-10）定义了车流路径的时间窗。

4.3模拟退火算法（SA）模型及其实现

SA算法模型的建立是基于物理中的固态物质的退火过程在一般的优化问题方面存在很大的相似性，通过设置初始的状态和初始的温度，随着温度的降低，结合概率理论中的突跳特性在空间中通过邻域函数进行随机的搜索得到最优的解。退火算法模型可以分为三个部分，即初始解、目标函数和解空间。其模拟过程大概分为以下几个方面：

17

（1）初始化设置：设置初始温度T、初始状态S，每个初始温度迭代的次数L； （2）对k?1,2,???L的各个值，重复（3）到（6）步； （3）对当前的状态S的随机的扰动产生一个解S'； （4）计算增加量?t?C(S')?C(S)，C(S)为评价函数；

（5）若?t?0，则以S'为当前解，否则以概率exp(??t/T)接受S'为当前解； （6）判断当前的解是否满足条件，如果满足则输出当前解； （7）当T趋于0时，跳到第（2）步重复执行。 4.4 遗传算法（GA）模型及其实现

遗传算法模型是建立在生物进化理论和遗传学理论基础上的一种算法，这是模仿遗传算子在选择、交叉和变异过程中的原理，应用在集合物的全局搜索上。遗传算法模型的步骤如下【9】：

（1）对求解空间进行初始和编码；

（2）初始化种群，i?1,2,???pop?size,pop(i)?(S1,S2,???,SN)； （3）计算当前种群pop(i)中的染色体Si的适应程度f(Si)； （4）应用遗传算子生成新一代群体pop(i?1)； （5）判断是否产生终止，若终止则返回第（3）步。

GA算法模型通过模仿遗传过程中的进化选择过程原理，最终使求解的状态最优。为了加快算法的收敛速度，选择适应度函数值大的个体。交叉算子通过对两个父代进行基因交换而搜索出更优的个体。变异操使进化群体产生多样性，避免算法陷入局部最优。

4.5遗传退火混合算法（GA-SA）模型及其实现

模拟退火算法和遗传算法两种算法都是全局随机优化算法，它们在传统的基于梯度的优化方法难以解决的复杂优化问题中显示了优良的求解特性，得到广泛研究和应用【8】。虽然遗传算法有较强的全局搜索性能，但它的爬山能力弱，在实际应用中容易产生早熟收敛的问题，且在进化后期搜索效率较低。而模拟退火算法却具有摆脱局部最优点的能力，能抑制遗传算法的早熟现象。因此，考虑将模拟退火的思想引入遗传算法，有效地缓解了遗传算法的选择压力。

4.5.1退火遗传算法的优点

1.优化机制的融合

理论上，GA 和 SA 两种算法均属于基于概率分布机制的优化算法。不同的是，SA 通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部

18