物流系统优化与仿真.ppt

《物流系统优化与仿真.ppt》由会员分享，可在线阅读，更多相关《物流系统优化与仿真.ppt（331页珍藏版）》请在三一办公上搜索。

1、物流系统优化与仿真,内容提要,物流系统优化是实现物流管理目标、体现物流管理效率与效益的必要过程和手段。物流系统优化主要有运筹学方法、智能优化方法和模拟仿真法等三种方法。系统仿真是根据被研究的系统模型，利用计算机进行实验研究的方法.目前仿真技术是分析、研究复杂物流系统的重要工具，也成为物流工程技术人员的一项重要技能。,内容提要,本书即强调优化和仿真的方法学和技术，又立足于物流系统的管理决策问题的解决。在知识体系上，“横向”方面从传统的运筹规划方法、排队存储论方法、系统动力学方法到现代智能优化方法以及Petri网、多Agent、面向对象等仿真方法的介绍；“纵向”方面主要是物流系统的一些应用问题，如

2、物流网络布局问题、车辆路径问题、装卸搬运问题、区域物流宏观规划问题以及供应链系统设计问题等。,目录,第1章 物流系统优化概述 第2章 物流系统模型第3章 物流系统优化的运筹规划方法 第4章 物流系统模型的智能优化方法 第5章 物流系统仿真应用基础第6章 物流系统动力学仿真第7章 排队模型与存储模型及应用第8章 Petri网模型及仿真第9章 物流系统仿真方法的发展第10章 供应链系统仿真优化第11章 博弈论及其在供应链中的应用第12章 仿真工具与软件应用,第1章 物流系统优化概述,本章概述了物流系统优化的相关概念，并就物流优化的主要方法进行了综合性的介绍。1.1 物流系统1.2 物流系统优化问题

3、1.3 物流系统优化的方法,1.1 物流系统 1.1.1 系统及其特征,1我国系统科学界对系统的通用定义是(钱学森):系统是由相互作用和相互依赖的若干组成部分结合而成的、具有特定功能的有机整体，而且这个整体又是它从属的更大的系统的组成部分。输入、处理（转换）、输出是组成系统的三大要素.,图1.1 系统的一般模式,整体性 相关性 目的性 环境适应性,2系统的特征,1.1.2 物流系统的概念和要素,1物流系统的概念:和一般系统一样，具有输入、转换、输出三要素。通过输入和输出使系统与社会环境进行交换，使系统和环境相依存.,环境,图1.2 物流系统的一般模型,2物流系统的特点是一个大跨度系统是一个可分

4、系统是一个动态系统:是一个复杂系统物流系统运行对象一“物”，遍及全部社会物质资源，资源的大量化和多样化带来了物流的复杂化 是一个多目标函数系统3物流系统的目标将货物按照规定的时间、规定的数量送达到目的地 合理配置物流中心，维持适当的库存 实现装卸、保管、包装等物流作业的省力化、效率化 维持合适的物流成本 实现从订货到出货全过程信息的顺畅流动等,4物流系统的要素一般要素 功能要素 支撑要素 物质基础要素,5物流系统中的制约关系 物流服务和物流成本间的制约关系,如图1.3构成物流服务子系统功能之间的约束关系 构成物流成本的各个环节费用之间的关系 各子系统的功能和所耗费用的关系,图1.3 服务与成本

5、的制约关系,1.1.3 物流系统化,1.物流系统化的目标 总体目标 目标体系 服务目标 快速、及时目标 节约目标 规模优化目标 库存调节目标,2系统目标关系的协调原则 层次间的目标发生冲突时，通常要以较低层次的目标服从于较高层次目标的要求为前提协商解决。于同一层次上的目标发生冲突时，应该在分析的基础上确定一定的取舍和补偿标准进行协调与决策。3.物流系统设计要素Products Quantity Route Service Time Cost,1.2 物流系统优化问题 1.2.1 物流系统的效益目标,物流的宏观经济效益是指物流系统的建立对社会经济效益的影响，直接表现为物流对整个社会流通及全部国民

6、经济效益的影响。物流系统的微观经济效益是指该系统本身在运行后所获得的效益。其直接表现形式是物流系统本身所耗与所得之比。,1.2.2 物流系统优化的必要性,1要素目标冲突要素之间的目标冲突 要素内部的目标冲突 物流系统与其它系统的目标冲突 2要素产权冲突物流系统是由不同产权组织共同完成的，产权边界不清晰。必须克服这种产权的分散性与物流系统的统一性之间的矛盾。3要素运作冲突,1.2.3 系统优化设计,1.优化设计的概念实现问题的优化必须具备两个条件：一是存在一个优化目标；另一是具有多个方案可供选择。2优化设计的数学模型优化设计三要素 设计变量 目标函数 设计约束与可行域 3优化方法的分类有多种类型

7、，有不同的分类方法,4优化设计步骤设计对象的分析 设计变量和设计约束条件的确定 目标函数的建立 合适的优化算法的选择 优化结果分析,1.2.4 物流系统优化的原则,美货运计划解决方案供应商Velant公司的总裁和Don Ratliff博士在2002年美国物流管理协会（CLM）年会上提出了“物流优化的10项基本原则，并认为通过物流决策和运营过程的优化，企业可以获得降低物流成本10%-40%的商业机会。物流优化的10项基本原则目标（Objectives）：设定的目标必须是定量的和可测评的。模型（Models）：模型必须忠实地反映实际的物流过程。数据（Data）：数据必须准确、及时和全面。集成（In

8、tegration）：系统集成必须全面支持数据的自动传递。表述（Delivery）：系统优化方案必须以一种便于执行、管理和控制的形式来表述。算法（Algorithms）：算法必须灵活地利用独特的问题结构。计算（Computing）：计算平台必须具有足够的容量在可接受的时间段内给出优化方案。人员（People）：负责物流系统优化的人员必须具备支持建模、数据收集和优化方案所需的领导和技术专长。过程（Process）：商务过程必须支持优化并具有持续的改进能力。回报（ROI）：投资回报必须是可以证实的，必须考虑技术、人员和操作的总成本。,要证实物流系统优化的投资回报率，必须把握两件事情：诚实地估计全部

9、的优化成本 将优化技术给出的解决方案逐条与标杆替代方案进行比较 要确定物流优化技术系统的使用效果，必须做三件事 在实施优化方案之前根据关键绩效指标（Key Performance Indicators）测定基准状态 将实施物流优化技术解决方案以后的结果与基准状态进行比较 对物流优化技术系统的绩效进行定期的评审,1.2.5 物流系统优化的层次,可以依照以下几个层次 决策层 中间层 执行层,1.3 物流系统优化的方法,物流系统优化方法主要有运筹学方法智能优化方法模拟仿真法,1.3.1 运筹学方法,1线性规划一般线性规划模型的表达形式 线性规划的求解 线性规划可能是非可行的 可能只有无界的解 在大多

10、数情况下，线性规划至少有一个有限的最优解，有时它还会有多重的最优解。整数规划,非线性规划,线性规划的性质 对于现实生活中的问题必须把其中基本部分抽出来构成数学模型研究解的结构和系统化的求解程序 产生了所期望的系统的最优解，或者至少是得到了通过对客观需要的评价，经过比较的行动方针,2网络与图论法3库存论4排队论,1.3.2 智能优化方法,1智能优化算法的概念优点 与精确算法相比的明显优势在于:能显著的节省时间开支；灵活，在不能用定量表示的约束集合中，用它制订计划；比较简单，常能由缺乏高级训练的实践者来实现；,3、几种常用的智能优化技术,1.3.3 模拟仿真法,1仿真模型系统仿真的目的在于利用人为

11、控制的环境条件，改变某些特定的参数，观察模型的反应，研究真实系统的现象或过程，是一种间接的研究方法。优势 符合人们的思维习惯，有助于系统分析 系统仿真可以是一种非解析的分析方法，对各种复杂的系统具有很好的适应性系统仿真有利于解决随机因素的影响 系统仿真可以帮助系统优化,不单纯追求最优解，而寻求改善系统行为的途径和方法。系统仿真方法正是提供了这种环境。利用仿真模型进行系统分析 利用仿真模型进行系统的综合,图1.4 用仿真进行系统分析,图1.5 用仿真进行系统综合,3系统仿真在物流系统研究中的作用物流系统规划与设计 仓储规模与库存管理 物料运输调度 物流成本估算,1.3.4 物流系统优化方法的比较

12、,运筹学方法和智能优化方法可以统称为解析法。1解析法的优势解析法是建立在数学模型的基础上的。数学模型是定量化的，可以产生更高的精确度。模拟仿真活动有时要耗费大量的时间和物资，花费高昂的代价才能够取得成果；而某些物流系统活动则不能或者很难做仿真实验。,2仿真方法的优势动态的、瞬时的影响 随机因素 非标准分布 随机活动的交互作用,第2章 物流系统模型,本章首先概述了几类主要的模型及其特点，并对常用的物流系统建模技术进行讨论。2.1 模型概述 2.2 物流系统模型2.3 建模方法与步骤2.4 物流系统建模技术,2.1 模型概述,2.1.1 模型的分类1.实体模型2.图形模型流程图 方框图 结构图 流

13、图,3.数学模型广义：凡是一切数学概念、数学理论体系、各种数学公式、各种方程式以及由公式系列构成的算法系统等都被称为数学模型。狭义：凡是将具体现象、事物的特征和性质给以数学表达的数学结构，如各种等式、不等式、图、表或框图等，也叫数学模型。数学模型，包括原始系统数学模型和仿真系统数学模型。仿真系统数学建模过程称为二次建模过程。模拟模型 模拟模型和原系统的物理元素完全不同，但动作相似。,2.1.2 数学模型的意义,2.1.4 系统模型模拟的特殊作用,过程系统流程复杂、投资巨大、生产连续性强，一般不允许在真实系统上进行试验研究。计划中或设计中的过程系统尚不存在。高质量的模拟模型具有预测性。实际过程系

14、统根本不允许作的试验。大大节省原材料、能源消耗和人力资源等。模型的预测性。传递复制极为方便。,2.2 物流系统模型 2.2.1 物流系统模拟技术的应用,1.物流系统规划与设计2.物料控制3.物料运输调度4.物流成本估算,2.2.2 物流系统模型的特点,1.三个特征：是实体的抽象或模仿 是由与分析问题有关的因素所组成 是用来表明这些因素间的关系 主要参数：周期数、库存量、初始库存、库存价格、库存成本、进(出)货量,2.2.3 物流系统常用的数学模型,1.资源分配型2.存储型3.输送型4.等待服务型5.指配型6.决策型7.其他模型,2.2.4 物流模型构建的原则,1模型构造的系统化2物流模型简单化

15、3物流研究多方位化4物流模型构建的规范化,2.3 建模方法与步骤 2.3.1 系统建模方法,U代表目标值，一般希望达到最大值(如利润、效益等)或最小值(如成本、支付、亏损等)，加上约束条件就形成一个系统模型。模型思路1.直接分析法 例2.1 流通加工中的下料问题。试求面积为一定值的矩形中，周长和为最小时的各边长度。2.数据分析法 通过分析系统功能的已有数据或新做的试验所获取的数据可以建立系统的模型。,3.实验分析法例2.2,4.主观想象法5.人工实现法,2.3.2 物流系统模型建立步骤,弄清问题，掌握真实情况 搜集资料 确定因素之间的关系 构造模型求解模型 检验模型的正确性,2.3.3 系统模

16、拟遵循的总体工作流程,系统定义 数学建模 模拟建模 装载 试验 结果分析,图2.4 系统模拟的工作流程,2.3.4 物流系统建模应注意的几个问题,1.对研究对象的了解 经常遇到以下情况 片面性、偏离了实际 无法获得完备的、有关过程系统的数据源 数学方法不正确 建模效率低 2.对于模型构建者提出的要求面向实际 具备跨学科多专业的知识及扎实的数学功底 意志、善于合作 注意外部环境,3物流系统建模应注意的问题明确目的，确定构成要素 模型的简单化和高精度模型 没有固定不变的建模方法,2.4 物流系统建模技术 2.4.1 形式化建模与非形式化建模技术,1.形式化建模技术排队网络法、极大代数法、扰动分析法

17、 2.非形式化建模技术活动循环图、流程图法、面向对象的建模技术3.Petri网络物流系统模型,图2.5 Petri网示意图,4.系统动力学建模技术动力学系统涵义组成部分的子结构及其相互间的关系 系统内部的反馈回路结构及其相互作用 5.Agent与Multi-Agent模型应用Agent与多Agent系统 Agent的特征自治智能交互,基于Agent的建模思想 无论在现在还是在将来的计算机科学及其应用领域中，由Agent组成的RAS有能力扮演重要的角色。在建立和分析人类社会中的交互模型和理论方面，MAS也可以扮演重要的角色。在物流供应链系统建模中的应用,第3章 物流系统优化的运筹规划方法,本章将

18、就物流系统中常见的规划模型形式及求解方法进行研究，并以一个物流网络布局问题的建模与求解作为实例说明该方法的一般应用过程。3.1 概述3.2 求解方法3.3 物流网络布局问题的建模与求解,3.1 概述 3.1.1 物流系统数学模型构建和模拟过程,3.1.2 运筹学规划论模型,1.线性规划模型基本结构 决策变量 约束条件 决策目标,标准型的特点 目标函数是最大化类型 约束条件均由等式组成 决策变量均为非负 模型隐含的假设 比例性假定 可加性假定 连续性假定 确定性假定,图3.2 LP问题的解之间的关系图,LP问题的解的概念 可行解和最优解基、退化解、最优基,建立线性规划模型的基本步骤 明确管理问题

19、，确定决策目标，分析约束因素 建立包含一组线性约束条件等式或不等式和最优线性目标函数表达式的数学模型 数学模型的求解与检验 优化后的分析,整数规划 纯整数规划 混合整数规划 纯01整数规划 混合01整数规划,2非线性规划模型 特征每个问题都可用一组决策变量(x1，x2，xn)表示某一方案 存在一组线性等式或不等式的约束条件 目标函数,3.1.3 几个物流系统数学模型的例子,1.运输问题的数学模型,2.物流配送计划的制定问题,3.集装箱拼箱及装箱问题,4.物流网络布局问题的数学模型,3.2 求解方法 3.2.1 单目标优化问题求解算法,1无约束优化问题的牛顿法及其修正方法牛顿法,阻尼牛顿法,2拉

20、格朗日乘子法,拉格朗日乘子法求约束优化问题的计算步骤如下,3单纯形法基本思想 单纯形法是描述可行解从可行域的一个极点沿着可行域的边界移到另一个相邻的极点时，目标函数和基变量随之变化的方法。步骤,图3.3 单纯形法的求解过程,4非线性规划及求解乘子法,3.2.2 多目标函数的优化方法,1统一目标法,极小化“统一目标函数”，为了使各个目标函数能均匀一致地趋向各自的最优值，可采用的方法,2主要目标法,3.2.3 整数规划及求解,1割平面法,2分枝定界法,3求解0-1规划的隐枚举法隐枚举法的基本原理与步骤,4求解指派问题的匈牙利法,3.2.4 动态规划法,1动态规划的基本概念,2动态规划模型的构成,3

21、基本原理和基本方程,3.2.5 图与网络优化算法,1、求最小生成树的Kruskal算法,2、求最短路径的Dijkstra算法：,3.求二部图最大匹配（指派问题）的匈牙利算法：,最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。增广链 截集（割集）最大流最小截量定理,4求最大流的方法(Ford-Fulkerson标号法),5.贪心法与拟阵 贪心法的思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：不能保证求得的最后解是最佳的；不能用来求最大或最小解问题；只能求满足某些约

22、束条件的可行解的范围。实现该算法的基本思路是：从问题的某一初始解出发，重复判断如果能朝给定总目标前进一步，则求出可行解的一个解元素，直到由所有解元素组合成问题的一个可行解为止。组合算法：提前判断出某些情况不可能取到最优解。,3.3 物流网络布局问题的建模与求解 3.3.1 概述,1.物流网络布局问题的意义与主要内容 2.物流网络规划的步骤找出物流网络规划的约束条件 根据约束条件构造物流网络符合的模型 将物流网络符合的模型转化成数学模型求出多组可行解 利用可行的评估方法或准则，对以上求出的多组可行解进行评估，将各可行解进行排序，以选取最适合的规划方案,3.选址问题的一个简单实例,3.3.2 多元

23、网点布局问题,1问题描述多元网点布局问题通常有如图3-5所示的系统结构。图中有m个资源点Ai(i=1，2，m)，各点的资源量为；有个需求点，各点的需求量为；有个可能设置网点的备选地址；需求点可以从设置的网点中转进货，也可以从资源点直接进货。假定各备选地址设置网点的基建投资、仓储费用和运费率均为已知，以总成本最低为目标确定网点布局的最佳方案。,图3-5网点布局结构示意图,2多元单品种物流网点布局的建模方法,3多元多品种物流网点布局的建模方法,3.3.3 设施容量问题（CFLP法）,CELP法的基本思想是：首先假定网点布局方案已经确定，即给出一组初始网点设置地址。根据初始方案按运输规划模型求出各初

24、始网点的供货范围，然后在各供货范围内分别移定网点到其他备选地址上，以使各供货范围内的总成本下降，找到各供货范围内总成本最小的新网点设置地址，再将新网点设置地址代替初始方案，重复上述过程直至各供货范围内总成本不能再下降时为止。,以图3-6所示的物流网络结构为对象来介绍CFLP方法的处理过程,CFLP法的基本步骤 给出网点地址初始方案 确定各网点的供货范围 寻求网点地址的新方案 新旧方案对比,图3-6网络结构图,数例：在某计划区域内，物流网络结构如图3-6所示，其中有12个需求点，“”中的数字为各点需求量，弧线旁的数字为运价系数。现需要在12个需求点的位置上选取3个点作为网点设置地址。假定网点的最

25、大规模为13，设定每个网点的固定成本为10。,图3-7物流网络结构图,步骤2 以4，6，9为发货点，各点发货量均为13；以需求点为收货点，需求量为已知；收、发货点之间的费用系数用最短路线法求得构成运输规划模型，如表3-1所示。,表3-1运输模型,步骤3 寻找各子区域内使区域总费用最小的网点位置。,表 3-2初始方案,上面讨论的是网点数目有限的情况，如果网点数目没有限制，则只需对网点数目为1，2，3，12诸情况分别进行讨论，找出使系统总费用最低的网点数目作为最佳方案即可。,第4章 物流系统模型的智能优化方法,本章介绍常见的一些智能优化方法及其在物流系统中的应用。4.1 智能优化方法概述 4.2

26、人工神经网络 4.3 禁忌搜索 4.4 遗传算法 4.5 模拟退火算法 4.6 群体智能方法 4.7 车辆路径问题模型及求解,4.1 智能优化方法概述 4.1.1 优化算法及其分类,目前工程中常用的优化算法 经典算法 构造型算法 邻域搜索算法 局部搜索法 指导性搜索法 基于系统动态演化的方法 混合型算法,4.1.2 智能优化算法的概念,智能优化算法的基本概念搜索空间（Search Space）计算复杂性与NP难题(NP-hard)按照计算复杂性理沦研究问题求解的难易程度，可把问题分为P类、NP类和NP完全类。其性质如下：1、这类问题中任何一个问题至今未找到多项式时间算法。2、如果这类问题中存在

27、一个问题有多项式时间算法，那么这类问题都有多项式时间算法。,4.2 人工神经网络 4.2.1 人工神经网络概述,神经元及其特性,人工神经网络的基本特性和结构,人工神经网络的简单原理,人工神经网络是根据人的认识过程而开发出的一种算法。假如我们现在只有一些输入和相应的输出，而对如何由输入得到输出的机理并不清楚，那么我们可以把输入与输出之间的未知过程看成是一个“网络”，通过不断地给这个网络输入和相应的输出来“训练”这个网络，网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出。当训练结束后，我们给定一个输入，网络便会根据自己已调节好的权值计算出一个输出。,4.2.2 人工神经网络的数学

28、模型及应用,1.BP神经网络的数学模型,2.BP算法的实现步骤,3神经网络模型的运行,神经网络的运行包括两个阶段：训练或学习阶段（training or learning phase）。预测（应用）阶段（generalization phase）。,4.3 禁忌搜索 4.3.1 禁忌搜索算法的主要构成,1、初始解 2、邻域移动 3、禁忌表和禁忌移动 4、选择策略 5、破禁策略 两个准则：基于适值是准则：若某个禁忌侯选解的适值优于以往搜索最优解，则解禁此候选解为当前解；基于搜索方向的准则：按有效的搜索途径进行。6、禁忌频数,7、停止规则 给定最大迭代步数：当总迭代次数达到一个给定的最大迭代步数，

29、或在一个给定的连续迭代步数内当前的最好解没有改善时，则算法终止。禁忌频率数控制原则：达到一定禁忌频数要求时，即当不能使当前最好解改善的循环次数超过了预先设定的阈值时，则算法终止；目标值变化控制原则：当目标值偏离最优值的程度超过了预先设定的阈值时，则算法终止。目标值偏离程度原则：当目标值偏离最优值的程度超过了预先设定的阈值时，则算法终止。,4.3.2 禁忌搜索算法流程,主要步骤如下：给定算法参数，随机产生初始解，置禁忌表为空；设当前解Xcurrent=Xint，当前最好解Xbest=Xint；判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继 续以下步骤。Xint的邻域内产生Ns

30、个测试解Xi，1iNs；求出目标函数f(Xi)；判断测试解是否在禁忌表中，若不在禁忌表或在禁忌表中但在其目标函数值比Xbest还好，则把它作为新的当前解Xcurrent，并转到；否则，继续测试下一个测试解。若所有的测试解都在禁忌表中，则转到；Xbest=Xcurrent；若禁忌表已满，则按先进先出的原则更新禁忌表；把当前解Xcurrent 插入禁忌表；记下最优解Xbest，结束算法。,4.4 遗传算法 4.4.1 进化计算与遗传算法概述,进化算法（Evolutionary Computation）是指一类以达尔文进化论为依据来设计、控制和优化人工系统的技术和方法的总称，包括遗传算法（genet

31、ic algorithm）、进化策略（evolutionary strategy）和进化规划（evolutionary programming）。遗传算法中处理的是染色体，或者叫基因型个体。一定数量的个体组成丁群体(population)。群体中个体的数目称为群体规模(population size)。而各个体对环境的适 应程度叫作适应度(fitness)。两个必要的数据转换操作，一个是表现型到基因型的转换，另一个是基因型到表现型的转换。主要特点 直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和较好的全局寻优能力；采用概率化的寻优方法,4.4.2 基本遗传算法,1.染

32、色体编码方法 2.适应度函数 3.遗传算子 选择算子：交叉算子 变异算子 4.基本遗传算法的运行参数 N：群体大小，即群体中所含个体的数量，一般取20100；T：遗传算法的终止进化代数，一般取为100500 Pc：交叉概率，一般取为0.40.99 Pm：变异概率，一般取为0.000l0.1,4.4.3 基本遗传算法的一般框架,问题求解的过程 编码 初始群体的生成 适应性值评估检测 选择 交叉 变异,基本遗传算法可定义为一个八元组：SGA(C，E，P0，M，T)式中各元素的意义为：C个体的编码方法；E个体适应度评价函数；P0初始群体；M群体大小；选择算子；交叉算子；变异算子；T 遗传运算终止条件

33、。,4.4.4 遗传算法的应用,1.遗传算法的应用步骤 确定决策变量及其各种约束条件，即确定个体的表现型和问题的解空间。建立优化模型，即确定出目标函数的类型及其数学描述形式或量化方法。确定表示可行解的染色体编码方法，也即确定出个体的基因型及遗传算法的搜索空间。确定解码方法，即确定出由个体基因型到个体表现型的对应关系或转换方法。确定个体适应度的量化评价方法，即确定由目标函数值f(X)到个体适应度F(X)的转换规则。设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。确定遗传算法的有关运行参数，即确定出遗传算法的群体规模popSize，终止进化代数maxGen，交叉概率pc

34、和变异概率pm。,2.遗传算法的特点优点遗传算法可以直接根据目标函数值进行搜索，而无需其它信息，如导数信息；遗传算法同时使用多个搜索点的搜索信息，隐含并行搜索特性；遗传算法使用概率搜索特性，其选择、交叉和变异等运算都是以一种概率的方式来进行的，增加了其搜索过程的灵活性；遗传算法具有全局搜索能力，善于搜索复杂问题和非线性问题；遗传算法同求解问题的其它启发式算法有较好的兼容性，可以与其它优化算法进行结合，改进算法性能。如模拟退火遗传算法。缺点 编码不规范及编码存在表示的不准确性。单一的遗传算法编码不能全面地将优化问题的约束表示出来。易于陷入局部最优点，导致早熟。,4.5 模拟退火算法 4.5.1

35、模拟退火算法的模型,1.基本思想 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L。对k=1，L做第(3)至第6步。产生新解S。计算增量t=C(S)-C(S)，其中C(S)为评价函数。若t0，然后转第2步。,2.模拟退火算法新解的产生和接受可分为如下四个步骤 由一个产生函数从当前解产生一个位于解空间的新解。计算与新解所对应的目标函数差。断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则:若t0则接受S作为新的当前解S，否则以概率exp(-t/T)接受S作为新的当前解S。当新解被确定接受时，用新解代替当前解，这只需将当前解中

36、对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。,4.5.2 模拟退火算法的应用,4.5.3 模拟退火算法的参数控制问题,温度T的初始值设置问题。退火速度问题。温度管理问题。常采用如下所示的降温方式：T(t+1)kT(t)式中k为正的略小于1.00的常数，t为降温的次数,4.6 群体智能方法 4.6.1 蚁群算法,1.引论蚁群算法（ACO）是受自然界中蚂蚁搜索食物行为启发而提出的一种智能优化算法。正反馈机制和通讯机制是蚁群算法的两个重要基础。,2蚁群算法基本原理,3.算法的改进,4.6.2 粒子族群优化算法PSO,1简介,图4.5 粒子移动原理图,图4.6平面粒子散布图（粒子起始）

37、,图4.7 经三次位移后之路径图,2.算法的流程,图4.8 PSO流程图,其中present表示粒子当前的位置，pbest表示粒子的个体极值，gbest表示粒子的全局极值。,3.粒子群算法和遗传算法的比较,相同：都是随机全局优化算法，都需要随机初始化种群，都是使用适应值来评价，都是根据适应值来进行一定的随机搜索，两种算法都只能不断逼近最优解，不一定能找到最优解。不同：遗传算法需要复制、交叉、变异等遗传操作来产生新个体，在群体中产生新个体是寻优的必须途径。但粒子群优化(PSO)算法没有遗传算法中的复制、交叉、变异等复杂操作，而是根据自己的速度来决定搜索，通过动态跟踪两个极值来更新自己。粒子还有一

38、个重要的特点，就是有记忆。信息共享机制也不同。在遗传算法中，复制、交叉和变异操作都是围绕染色体进行的，染色体(chromosomes)互相共享信息，所以整个种群的移动是比较均匀地向最优区域移动，在粒子群算法中，只有全局极值(gbest)才传递信息给其它粒子，这只是单向的信息流动，整个搜索更新过程总是跟随当前最优解，与遗传算法相比，在大多数的情况下，粒子群算法可能更快的收敛于最优解。,4.7 车辆路径问题模型及求解 4.7.1 车辆路径问题的一般描述与问题分类,1.车辆路径问题 从配送中心(物流据点)用多辆车向多个需求点(顾客)送货，每个需求点的位置和需求量一定，每辆车的载重量一定，要求合理安排

39、车辆路线，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。此即为VRP问题。并满足以下条件:(1)每条配送路径上各需求点的需求量之和不超过车辆载重量；(2)每条配送路径的长度不超过车辆一次配送的最大行驶距离；(3)每个需求点必须满足，且只能由一辆车送货。(4)每辆车均从中心出发，完成任务后又全部回到中心。这就是VRP问题的一般描述。,2.VRP问题分类,按照运输任务分为纯装问题、纯卸问题以及装卸混合问题。按照车辆载货状况分为满载问题和非满载问题 按照车辆类型分为单车型问题和多车型问题 按照车辆是否返回配送中心车场划分为车辆开放问题和车辆封闭问题 按照优化的目标可分为单目

40、标优化问题和多目标优化问题 按照有无时间要求可分为有时间窗的VRP和无时间窗VRP问题,3.基本VRP的数学模型,4.7.2 求解算法综述,精确优化方法。运用线性规划和非线性规划等数学规划技术，来求取最优决策。启发式方法(Heuristic)。指通过经验法则来求取运输过程满意解的数学方法。模拟方法(Simulation)。交互优化法。,图 4.8 启发式方法求解过程示意图,4.7.3 C-W算法,4.7.4 车辆路径问题的禁忌算法设计,1算法流程确定D-1-D对应的路线是否满足不大于车辆的最大载重量和最大行驶里程的限制。若满足，则转下一步；把该解中对应的下一个客户2加入到该路线中，此时路线为D

41、-1-2-D，再进行判定是否满足约束条件，若仍满足，就把下一个客户5又加入该路线中，此时路线为D-1-2-5-D，若到此时再进行判断时，该路线己经不满足约束条件，则对应的D-1-2-D是一条可行的子回路；继续循环地进行下一步的工作，假设最后的结果是D-1-2-D，D-5-4-6-7-D，D-9-8-3-D，则表示该客户排列对应3条可行路径，即n=3；用3与最大车辆数m比较，若m3，表示该解是一个可行解；若m3，则表示该解是一个不可行解。,2算法策略解的评价方法邻域操作方法 禁忌对象的确定 禁忌长度的确定 候选集合的确定 终止准则的确定,4.7.5 神经网络算法,一般按下列步骤进行 产生邻接矩阵

42、 约束的处理 神经网络计算 调度方案的形成,4.7.6 遗传算法,采用遗传算法求解车辆优化调度问题时，一般按照以下步骤进行确定染色体的编码和初始群体 确定适应度函数 处理约束 遗传算子 确定调度方案,第5章 物流系统仿真应用基础,本章主要介绍系统仿真的一些基础知识，包括仿真连续与离散系统的基本仿真方法，数据分析与随机数产生等，同时对系统仿真在物流中的应用进行一般性介绍，然后以运输与装卸系统仿真为例介绍仿真应用的一般流程。5.1 系统仿真基础 5.2仿真方法在物流系统中的应用 5.3 运输与装卸系统仿真,5.1 系统仿真基础,广义的仿真概念是泛指在系统模型上进行试验的技术，也就是说将所研究的对象

43、用某种手段加以模仿的技术，主要有物理模拟技术(称为物理仿真)和数值模拟技术(计算机仿真)。计算机仿真的主要特点有 时间的伸缩性 具有大量逻辑、随机关系复杂的系统 运行的可控性 便于多方案选优 应用的广泛性 仿真方法主要是指在计算机上建立仿真模型及进行仿真研究的方法。根据被仿真的系统不同，可分为连续系统仿真方法和离散事件系统仿真方法。,5.1.1 连续系统仿真方法,1.建立数学模型,2.建立仿真模型,(2)离散相似法,图5-2中保持器的作用是使在采样开关断开时，连续系统有一个输入值。否则，如果对原系统的输入输出端只加采样开关，即无图中的保持器，那么离散化之前的输出y（t）与离散后的y*（t）就不

44、会相同。这种离散化方法的近似程度取决于采样频率和保持器的特性。,图5-2 连续系统离散化,5.1.2 离散事件系统仿真方法,1基本概念实体 事件 活动 进程 仿真钟 统计计数器 2.仿真钟的推进事件调度法 固定增量推进方法,3.仿真策略,4三种仿真策略比较,系统描述 建模要点 仿真钟的推进 执行控制 概括地说，事件调度法建模灵活，可应用范围广泛，但一般要求用户采用通用的高级语言编写事件处理子例程，建模工作量大。活动扫描法对于各成分相关性很强的系统来说模型执行效率高.但是，建模时要对各成分的活动进行建模，程序结构比较复杂，流程控制不易。进程交互法是建模最为直观的策略，其模型表示接近实际系统，特别

45、适用于活动可以预测、顺序比较确定的系统，但是其流程控制复杂，建模灵活性不如事件调度法。,5.1.3 数据输入分析,1.数据收集2.数据收集过程中的注意事项做好仿真计划，详细规划仿真所需要收集的数据 在收集数据过程中要注意分析数据数据的均匀组合 3直方图4直方图分组区间数量的选取,图5.3 直方图分组区间示例,5参数估计,表5.1 仿真中常用的一些分布参数建议值,6拟合度检验,7相关性分析,8单变量线性回归的显著性检验,5.1.4 随机变量及其生成方法,分布所采用的大多数参数，可分为位置参数、比例参数和形状参数三个基本类型。1.随机数发生器,(2)组合发生器,第一种方法是：首先从第一个发生器产生

46、K个Zi(Ui)，得到数组U=(U1，U2，UK)或Z（Zl，Z2，ZK)；然后用第二个随机数发生器产生在1，K区间上均匀分布的随机整数I；以I作为数组U（或Z）的元素下标，将U1或Z1，作为组合发生器产生的随机数，然后从第一个发生器再产生一个随机数来取代U1或Z1，依次下去。第二种方法：设Zi(1)与Zi(2)分别是由第一个与第二个线性同余发生器产生的随机数，则令Zi(2)的二进制表示的数循环移位Zi(1)次，得到一个新的位于0到m-1间的整数Zi(2)；然后将Zi(1)与Zi(2)的相应二进制位“异或”相加得到组合发生器的随机变量Zi，且Ui=Zi/m。优点是大大减少了线性同余发生器带来的

47、自相关，提高了独立性；还可以加长发生器的周期，提高随机数的密度，从而提高了均匀性。而且它一般对构成组合发生器的线性同余发生器的统计特性要求较低，得到的随机数的统计特性却比较好。缺点是速度慢。,2随机变量产生的方法,5.2仿真方法在物流系统中的应用 应用仿真技术的几个方面,物流系统规划与设计 仓储规模与库存管理 物料运输调度 物流成本估算,5.2.2 物流系统仿真的应用意义,物流系统中流，通常应采用动态仿真方法描述流的产生、流动、消失、积累和转换等，才能收到较好的效果。物流系统运行中的仿真，大多采用离散型仿真方法来进行。通过计算机仿真才有可能比较合理地描述由于人的思维模式对真实系统运行的影响和作

48、用，而而也就有可能获得较为优秀的物流系统运行的组织方案。,5.2.3 物流系统仿真类型,1.连续系统模型2.离散系统模型根据仿真时钟推进的方式 下次事件时间推进法 固定增量时间推进法 主导时钟推进法,5.2.4 物流系统仿真的主要步骤,问题的描述 设定目标与总体方案。建立仿真模型收集和处理信息 确认模型参数 仿真模型的程序设计 仿真模型的试运行 确认模型正确 设计试验 仿真运行 分析仿真结果 向决策者提出建议 建立文件的数据库、知识库,图5.4 物流系统仿真的一般步骤,5.2.5 物流系统仿真模型的确认,1.仿真模型确认 一般观点建立仿真模型的目的是要用仿真实验代替实际系统的实验，模型应能满足

49、使用要求且费用较低。不管在研究模型上作了多大的努力，模型总是仅仅近似于现实系统。某一模型对某一个目标是有效的，也许对另一个目标是无效的。确认模型时总是相对于一组判断准则而言，应仔细选择这些准则。仿真模型的研究和确认应贯穿于建模的全过程。大多数经典统计分析方法不可直接用于确认模型。,2确认物流系统仿真模型的三步法建立直观看来是正确的仿真模型 检验建模假设 仿真数据与实际数据的比较 3仿真程序验证 首先将仿真主程序和少数关键子程序编好，同时进行详细的检验和验证，确保它们是正确无误；然后逐步扩展和完善。由多位编程人员同时阅读和检查同一程序。程序运行的追踪检查是用于调试离散事件仿真模型的一种最为有用的

50、技术。进行仿真试验前，应用简化考题验证仿真程序。图形显示。,5.3 运输与装卸系统仿真 5.3.1 概述,运输与装卸配合关系，可视为一排队系统，以系统总费用最低作为系统优化组合的主导因素，运用离散系统仿真的办法来寻找及恰当的组合与配合关系。,5.3.2 仿真示例,1装运问题的提出和系统定义装运过程描述：装车设备在装车场为汽车装载，汽车到达装车场时若装车设备空闲就立即装载，否则汽车加入等待队列。装载完毕的汽车从装车场上坡运行到卸车点称重并卸车。卸车点在任一时刻只允许一辆汽车卸车，其余汽车将排队等待，卸车完毕空车返回装车场。装车设备和汽车每班工作6小时，一上班时全部汽车在装车场等待。要研究的问题是