1、第三章第三章 配送方案的优化配送方案的优化【教学目的及重点难点】l本章试图从物流配送的各个方面（包括物流配送网络布局优化、货物配装优化、物资调运优化、配送路线优化、物流配送系统模拟仿真优化等）介绍物流配送优化的理论和方法。l本章的重点和难点是配送路线的优化问题，即VRP问题。3.1 引导案例 旅行商问题描述如下：给定n个城市及两两城市之间的距离（或时间、费用等），求一条经过各城市一次且仅一次的长度最短（或耗时最小、费用最少）的路线。其图论描述为：给定图D=(V,A,W)，其中V=0,1,n为顶点集，A=(i,j)|i,j=0,1,n;i j为各顶点相互连接组成的弧集。W=dij|(i,j)A为
2、费用矩阵，表示旅行商经过对应弧(i,j)所需的距离（或时间、费用等），要求确定一条总长度最短的遍历所有顶点一次且仅一次的回路。3.2 配送优化的概述 现代物流配送优化是第三利润泉的一个重点。所谓配送优化，是在配送的诸环节，如流通加工、整理、检选、分类、配货、末端运输中，从物流系统的总体目标出发，运用系统理论和系统工程原理和方法，充分利用各种运输方式优点，以运筹学方法、启发式算法、智能优化和模拟仿真等方法建立模型与图表来选择和规划合理的配送路线和配送工具，以最短的路径、最少的环节、最快的速度和最少的费用，组织好物质产品的配送活动，避免不合理配送情况和次优化的出现。3.3 物流配送网络布局优化 3
3、.3.1 配送网络合理布局的概念 概括地讲，配送网络的合理布局，使指以物流配送系统和社会的经济效益为目标，用系统学的理论和系统工程的方法，综合考虑物资的供需状况、运输条件、自然环境等因素，对物流节点的设置位置、规模、供货范围等进行研究和设计、做出恰当的布局。3.3.2 配送网络布局的目标 配送网络布局模型通常是以系统总成本最低为目标函数的。建立模型时主要应考虑以下几项费用：l网点建设投资 l网点内部的固定费用 l网点经营费用 l运杂费 3.3.3 配送网络布局的步骤（1）找出物流配送网络规划的约束条件，其中约束条件可能包括：总采购、配送及仓储成本、最小运送时间、平均顾客服务水平等。（2）根据约
4、束条件构造模型。（3）将模型转化为数学模型求出多组可行解。（4）利用可行的评估方法或准则，对以上求出的多组可行解进行评估，将各可行解进行排序，以选取最适合的规划方案。3.3.4 备选地址的选择原则 l用户满意度原则 l有利于物资运输合理化 l费用最小原则 l动态性原则 l战略性原则 3.3.5 配送网络布局分类 为了对网络布局进行更深入的研究，根据储放货品的多寡，可以将物流网络布局划分为单品种网点和多品种网点两种类型。3.3.6 进行网点布局的常用方法 l解析方法 l模拟方法 l启发式方法 3.3.7 一元网点布局问题 l1.一元网点布局概念 l2.一元网点布局的方法（1）因素评分法（2）重心
5、法（3）微分法 3.3.8 多元网点布局问题 l1.问题描述 l2.多元单品种物流网点布局的数学模型l3.多元多品种物流网点布局的数学模型 l4.精确重心法l5.集合覆盖模型 l6.最大覆盖模型 l7.奎汉-哈姆勃兹模型 l8.鲍摩-瓦尔夫模型 l9.CFLP模型 3.4 货物配装优化 3.4.1 车辆配载问题介绍 l1.车辆配载注意事项研究物流配送中的车辆配载问题，即根据配货要求，同时考虑配送货物的质量和体积的差异，以及车辆的载重和容积的限制，重点研究集装化杂/散货在运输工具中的装载问题的模型及其优化方法。首先分析容积、重量等制约因素，建立装载模型，然后根据该目标来确立目标函数，找出约束条件
6、，建立规划模型，最后对自动装载计划模型进行优化求解。3.4.1 车辆配载问题介绍l2.现有配载方法及数学模型（1）原始手工经验配载 在货物比较零散时，许多装车是采用手工完成的。即装车的工人根据自己的经验和直观判断以及一些简单的手工计算来进行配载。（2）动态规划方法 装货问题 产品混装问题3.4.2 集装箱装载问题介绍 l1.集装箱装载问题的概述所谓集装箱装载问题(Container Loading Problem)，指如何将一些长方体盒子(货物)按某种方式装入集装箱，从而最大限度地提高集装箱的空间能力。CLP是货物运输过程中普遍存在的一个重要的也很典型的环节。在装载的稳定性、容积限制、载重限制
7、等约束条件下，使集装箱的空间利用率最大，是这类问题的主要目标。3.4.2 集装箱装载问题介绍l2.集装箱装载问题的数学模型配装货物时，要在集装箱宽和高所组成的平面上达到最大化的利用率。因为要使得货物重心平衡，所以在这个二维平面上，以集装箱宽为准线一层一层的在高度上堆放，在堆满一个平面后，在集装箱的长度上前进一个位置，继续以宽为准线在高度上堆放，直至装完同种货物为止。不同种的货物不互相堆叠，以免混淆。货物在层面上放不满的位置及不同货物之间要用衬垫加以分隔。（1）模型一：为货物不能倒放情况下所使用的数学模型（2）模型二：为允许倒放情况下的一个线性型的数学模型（3）模型三：为允许倒放情况下的一个非线
8、性型的数学模型 3.5 物资调运优化 3.5.1 运输问题的数学模型 运输问题属于线性规划问题的范畴，但是由于其约束方程式的系数矩阵有其特殊结构，因而可以找到一种比单纯形法更简便的求解方法。运输问题的一般提法是这样：某种物资有上千个产地和销地，若已知各个产地的产量、各个销地的销量以及各产地到各销地的单位运价，问应如何组织调运，才能使总运费最省。3.5.2 表上作业法 表上作业法是求解运输问题的一种简便而有效的方法，是单纯形法在求解运输问题时的一种简化方法，其求解工作在运输表上进行，其实质仍是单纯形法，只是其具体计算过程和使用的有关术语有所不同，它是一种迭代法。l1.初始方案的确定这里介绍常用的
9、最小元素法。这种方法是按运价由小到大的顺序安排运量。3.5.2 表上作业法l2.最优性检验用最小元素法给出的初始调运方案是一个运输问题的基本可行解，然而还需判断这个调运方案是否是最优方案。初始调运方案中的数格对应基变量，空格对应非基变量，因此，要判断一个调运方案是不是最优方案，首先要计算出方案中每一个空格的检验数，这里介绍两种方法。（1）位势法（2）闭回路法 3.5.2 表上作业法l3.方案的调整（1）取寻找该运量表中的闭回路，每个空格的闭回路都是唯一的；（2）沿闭回路路线进行调整，取调整量闭合回路中减顶点运量元素的数值。3.5.3 产销不平衡的运输问题及其求解方法 l1.产量大于销量的运输问
10、题由于总的产量大于销量，就要增加一个虚设的需求地n+1，它的需求量为。新增从各供应地到该需求地的运输路线（1，n+1），（2，n+1），（m，n+1），这些运输路线上的运价全部等于0，这样就将供给大于需求的问题转化为供求平衡的问题。在新的问题中，从供应地i到新设的需求地n+1的运量，实际上就是存储在供应地i没有运出的数量。新得到的供求平衡的运输问题的最优解，实际上就是各供应地存储多少、运出多少、运往何地，使总运价最低。l2.销量大于产量的运输问题（与上面的分析方法相同）3.6 配送路线优化 3.6.1 车辆路径问题概述l1.问题描述VRP问题为：从配送中心（物流据点）用多辆车向多个需求点（顾客
11、）送货，每个需求点的位置和需求量一定，要求合理安排车辆路线，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆数尽量少等）。并满足以下条件：（1）每条配送路径上各需求点的需求量之和不超过车辆载重量；（2）每条配送路径的长度不超过车辆一次配送的最大行驶距离；（3）每个需求点必须满足，且只能由一辆车送货；（4）每辆车均从中心出发，完成任务后又全部回到中心。这就是VRP问题的一般描述。3.6.1 车辆路径问题概述l2.构成要素车辆路径问题主要包括货物、车辆、物流中心、客户、运输网络、约束条件和目标函数等要素。3.6.1 车辆路径问题概述l3.分类 VRP问题的分类可根据不同性质具体分为以下几
12、类：（1）按照运输任务分为纯装问题、纯卸问题以及装卸混合问题。（2）按照车辆载货状况分为满载问题和非满载问题，满载问题是指货运量多于一辆车的容量，完成所有任务需要多辆运输车辆。非满载问题是指车的容量大于货运量，一辆车即可满足货运要求。（3）按照车辆类型分为单车型问题和多车型问题。（4）按照车辆是否返回配送中心车场划分为车辆开放问题和车辆封闭问题，车辆开放问题是指车辆不返回其出发地，车辆封闭问题是指车辆必须返回其发出配送中心车场。（5）按照优化的目标可分为单目标优化问题和多目标优化问题。（6）按照有无时间要求可分为有时间窗VRP问题和无时间窗VRP问题。实际中的车辆路径问题可能是以上分类中一种或
13、几种的综合。3.6.1 车辆路径问题概述l4.数学模型liLTsETkljyxkliyxliykqyglilj kijkxijcziiikijijkkiiijkkkiikii,;,;,.min1101011 3.6.1 车辆路径问题概述l5.车辆路径问题的求解方法综述 车辆路径问题是组合优化领域中著名的NP难题，近20年来，无论在国内还是国外，VRP问题都是一个非常活跃的研究领域。目前研究该问题有以下几类研究方法：（1）运筹学方法（2）启发式算法（3）智能优化算法（4）模拟方法3.6.2 求解车辆路径问题的运筹学方法 l1.整数规划 在线性规划中，一般情况对决策变量只是提出非负的要求，如果进一
14、步要求决策变量是整数（全部变量或部分变量是整数），这样的线性规划是整数规划。整数规划问题一般可以分为以下几类：所有变量都取整数的规划称为纯整数规划，有时，也称为全整数规划；部分变量取整数的规划称为混合整数规划；所有变量都取0、1两个值的规划称为0-1规划，部分变量取0、1两个值的规划称为0-1混合规划。求解整数规划问题常用的方法有分枝定界法和割平面法。3.6.2 求解车辆路径问题的运筹学方法 l2.动态规划 动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种方法，大约产生于20世纪50年代。1951年美国数学家贝尔曼等人根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相
15、联系的单阶段问题，然后逐个加以解决。与此同时，他提出解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新方法动态规划。动态规划方法在工程技术、企业管理、工农业生产及军事部门都有广泛的应用。3.6.2 求解车辆路径问题的运筹学方法 l3.网络与图论法 图论是应用十分广泛的运筹学分支，它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。这里将介绍最短路问题以及最小费用最大流问题。3.6.3 求解车辆路径问题的启发式算法 l1.节约法（1）基本原理（2）实例分析（3）优缺点分析3.6.3 求解车辆路径问题的启发式算法 l2.扫描法Gillett
16、和Miller提出的Sweep算法简单实用，即使问题规模很大，也可以通过手工计算得出结果。然而，此种方法没有考虑运输工具的利用率，只是沿仓库任一方向向外画一条直线，沿顺时针或逆时针方向旋转该直线依次与某些站点相交，并判断是否超过车辆的载荷能力，从而确定所需的车数。这里从贪婪思想的观点出发，利用Sweep算法思路得出几种可行的装载方案，然后在这些方案中选择比较满意的方案。3.6.4 求解车辆路径问题的智能优化算法 l1.智能优化算法概述 智能优化算法具有全局的、并行高效的优化性能，鲁棒性、通用性强等优点。它以广泛用于计算机科学、优化调度、运输问题、组合优化、工程优化设计等领域。主要有：模拟退火算
17、法、遗传算法、禁忌搜索算法、蚁群算法、人工神经网络、DNA计算等。3.6.4 求解车辆路径问题的智能优化算法 l2.遗传算法Holland创建的遗传算法是一种概率搜索算法，他是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的群体的进化过程。遗传算法通过有组织地也是随机地信息交换来重新结合那些适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来代替原来的部分。遗传算法是一种随机算法，但它不是简单的随机走动，它可以有效地利用已有的信息来搜寻那些有希望改善解质量的串。类似于自然进化，遗传算法
18、通过作用于染色体上的基因，寻找好的染色体来解决问题。3.6.4 求解车辆路径问题的智能优化算法 l3.模拟退火算法退火是一种物理过程，一种金属物体在加热至一定的温度后，它的所有分子在其状态空间中自由运动。随着温度的下降，这些分子逐渐停留在不同的状态。在温度最低时，分子重新以一定的结构排列。统计力学的研究表明，在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。当温度相当高时，每个状态的概率基本相同，都接近平均值。当温度趋向0时，分子停留在最低能量状态的概率趋向于1。模拟退火算法是一种基于上述退火原理建立的随机搜索算法。组合优化问题与金属物体的退火过程可进行如下类比：组合优
19、化问题的解类似于金属物体的状态，组合优化问题的最优解类似于金属物体的能量最低的状态，组合优化问题的费用函数类似于金属物体的能量。3.6.4 求解车辆路径问题的智能优化算法 l4.禁忌搜索算法禁忌搜索算法是解决组合优化问题的另一种优化方法。该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的邻域中搜索若干个解，取其中的最好解作为新的当前解。为了避免陷入局部最优解，这种优化方法在一定程度上允许使解的质量
20、变差。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录己搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。3.6.4 求解车辆路径问题的智能优化算法 l5.人工神经网络 人工神经网络是使模仿生物神经网络的一种经验模型。神经网络是由若干神经元连接成网络，其中的一个神经元可以接受多个输入信号，按照一定的规则转换为输出信号。由于神经网络中神经元间复杂的连接关系和各神经元传递信号的非线性方式，输入和输出信号之间可以构建出各种各样的关系，因此可以用来作为黑箱模型，表达那些用机理模型还无法精确描述、但输入和输出之间确实有客观的、确定性的或模糊
21、性的规律。因此，人工神经网络作为经验模型的一种，在生产实践、研究和开发中得到了越来越多的用途。3.7 物流配送系统模拟仿真优化 3.7.1物流配送系统仿真简介 l1 系统仿真的概念及在物流配送系统中 的应用l2 物流配送系统仿真的类型l3 物流配送系统的仿真步骤 3.7.2 常用仿真工具与软件介绍 l1.Matlab/Simulink 软件简介l2.AutoMod 软件简介 3.8 案例 l3.8.1 北京顺鑫首联生鲜配送中心案例介绍l3.8.2 北京顺鑫首联生鲜配送中心案例分析【本章小结】物流配送优化问题是近年来研究的一个热点问题，优化配送方案可以降低企业配送的成本，提升为客户服务的水平以及增加企业的经济效益。本章就详细介绍了该问题，首先介绍了物流配送优化的基本概念；然后重点从物流配送网络布局、货物装载、物资调运、配送路线等方面详细介绍如何进行配送方案的优化；接着简要介绍了物流配送系统的仿真优化，并介绍了几个常用仿真软件；最后用一个案例来说明配送优化在实际中的应用。【思考题】1.配送优化指的是什么？2.如何优化物流配送网络的布局？3.货物配载的方法有哪些？4.运输问题指的是什么？5.如何优化物流配送路线？6.物流配送系统的仿真步骤是怎样的？
