物流系统优化与仿真课件.ppt

物流系统优化与仿真 彭扬伍蓓 著 内容提要 物流系统优化是实现物流管理目标 体现物流管理效率与效益的必要过程和手段 物流系统优化主要有运筹学方法 智能优化方法和模拟仿真法等三种方法 系统仿真是根据被研究的系统模型 利用计算机进行实验研究的方法 目前仿真技术是分析 研究复杂物流系统的重要工具 也成为物流工程技术人员的一项重要技能 内容提要 本书即强调优化和仿真的方法学和技术 又立足于物流系统的管理决策问题的解决 在知识体系上 横向 方面从传统的运筹规划方法 排队存储论方法 系统动力学方法到现代智能优化方法以及Petri网 多Agent 面向对象等仿真方法的介绍 纵向 方面主要是物流系统的一些应用问题 如物流网络布局问题 车辆路径问题 装卸搬运问题 区域物流宏观规划问题以及供应链系统设计问题等 目录 第1章物流系统优化概述第2章物流系统模型第3章物流系统优化的运筹规划方法第4章物流系统模型的智能优化方法第5章物流系统仿真应用基础第6章物流系统动力学仿真第7章排队模型与存储模型及应用第8章Petri网模型及仿真第9章物流系统仿真方法的发展第10章供应链系统仿真优化第11章博弈论及其在供应链中的应用第12章仿真工具与软件应用 第1章物流系统优化概述 本章概述了物流系统优化的相关概念 并就物流优化的主要方法进行了综合性的介绍 1 1物流系统1 2物流系统优化问题1 3物流系统优化的方法 1 1物流系统1 1 1系统及其特征 1 我国系统科学界对系统的通用定义是 钱学森 系统是由相互作用和相互依赖的若干组成部分结合而成的 具有特定功能的有机整体 而且这个整体又是它从属的更大的系统的组成部分 输入 处理 转换 输出是组成系统的三大要素 图1 1系统的一般模式 整体性相关性目的性环境适应性 2 系统的特征 1 1 2物流系统的概念和要素 1 物流系统的概念 和一般系统一样 具有输入 转换 输出三要素 通过输入和输出使系统与社会环境进行交换 使系统和环境相依存 环境 图1 2物流系统的一般模型 2 物流系统的特点是一个大跨度系统是一个可分系统是一个动态系统 是一个复杂系统物流系统运行对象一 物 遍及全部社会物质资源 资源的大量化和多样化带来了物流的复杂化是一个多目标函数系统3 物流系统的目标将货物按照规定的时间 规定的数量送达到目的地合理配置物流中心 维持适当的库存实现装卸 保管 包装等物流作业的省力化 效率化维持合适的物流成本实现从订货到出货全过程信息的顺畅流动等 4 物流系统的要素一般要素功能要素支撑要素物质基础要素 5 物流系统中的制约关系物流服务和物流成本间的制约关系 如图1 3构成物流服务子系统功能之间的约束关系构成物流成本的各个环节费用之间的关系各子系统的功能和所耗费用的关系 图1 3服务与成本的制约关系 1 1 3物流系统化 1 物流系统化的目标总体目标目标体系服务目标快速 及时目标节约目标规模优化目标库存调节目标 2 系统目标关系的协调原则层次间的目标发生冲突时 通常要以较低层次的目标服从于较高层次目标的要求为前提协商解决 于同一层次上的目标发生冲突时 应该在分析的基础上确定一定的取舍和补偿标准进行协调与决策 3 物流系统设计要素ProductsQuantityRouteServiceTimeCost 1 2物流系统优化问题1 2 1物流系统的效益目标 物流的宏观经济效益是指物流系统的建立对社会经济效益的影响 直接表现为物流对整个社会流通及全部国民经济效益的影响 物流系统的微观经济效益是指该系统本身在运行后所获得的效益 其直接表现形式是物流系统本身所耗与所得之比 1 2 2物流系统优化的必要性 1 要素目标冲突要素之间的目标冲突要素内部的目标冲突物流系统与其它系统的目标冲突2 要素产权冲突物流系统是由不同产权组织共同完成的 产权边界不清晰 必须克服这种产权的分散性与物流系统的统一性之间的矛盾 3 要素运作冲突 1 2 3系统优化设计 1 优化设计的概念实现问题的优化必须具备两个条件 一是存在一个优化目标 另一是具有多个方案可供选择 2 优化设计的数学模型优化设计三要素设计变量目标函数设计约束与可行域3 优化方法的分类有多种类型 有不同的分类方法 4 优化设计步骤设计对象的分析设计变量和设计约束条件的确定目标函数的建立合适的优化算法的选择优化结果分析 1 2 4物流系统优化的原则 美货运计划解决方案供应商Velant公司的总裁和DonRatliff博士在2002年美国物流管理协会 CLM 年会上提出了 物流优化的10项基本原则 并认为通过物流决策和运营过程的优化 企业可以获得降低物流成本10 40 的商业机会 物流优化的10项基本原则目标 Objectives 设定的目标必须是定量的和可测评的 模型 Models 模型必须忠实地反映实际的物流过程 数据 Data 数据必须准确 及时和全面 集成 Integration 系统集成必须全面支持数据的自动传递 表述 Delivery 系统优化方案必须以一种便于执行 管理和控制的形式来表述 算法 Algorithms 算法必须灵活地利用独特的问题结构 计算 Computing 计算平台必须具有足够的容量在可接受的时间段内给出优化方案 人员 People 负责物流系统优化的人员必须具备支持建模 数据收集和优化方案所需的领导和技术专长 过程 Process 商务过程必须支持优化并具有持续的改进能力 回报 ROI 投资回报必须是可以证实的 必须考虑技术 人员和操作的总成本 要证实物流系统优化的投资回报率 必须把握两件事情 诚实地估计全部的优化成本将优化技术给出的解决方案逐条与标杆替代方案进行比较要确定物流优化技术系统的使用效果 必须做三件事在实施优化方案之前根据关键绩效指标 KeyPerformanceIndicators 测定基准状态将实施物流优化技术解决方案以后的结果与基准状态进行比较对物流优化技术系统的绩效进行定期的评审 1 2 5物流系统优化的层次 可以依照以下几个层次决策层中间层执行层 1 3物流系统优化的方法 物流系统优化方法主要有运筹学方法智能优化方法模拟仿真法 1 3 1运筹学方法 1 线性规划一般线性规划模型的表达形式线性规划的求解线性规划可能是非可行的可能只有无界的解在大多数情况下 线性规划至少有一个有限的最优解 有时它还会有多重的最优解 整数规划 非线性规划 线性规划的性质对于现实生活中的问题必须把其中基本部分抽出来构成数学模型研究解的结构和系统化的求解程序产生了所期望的系统的最优解 或者至少是得到了通过对客观需要的评价 经过比较的行动方针 2 网络与图论法3 库存论4 排队论 1 3 2智能优化方法 1 智能优化算法的概念优点与精确算法相比的明显优势在于 能显著的节省时间开支 灵活 在不能用定量表示的约束集合中 用它制订计划 比较简单 常能由缺乏高级训练的实践者来实现 3 几种常用的智能优化技术 1 3 3模拟仿真法 1 仿真模型系统仿真的目的在于利用人为控制的环境条件 改变某些特定的参数 观察模型的反应 研究真实系统的现象或过程 是一种间接的研究方法 优势符合人们的思维习惯 有助于系统分析系统仿真可以是一种非解析的分析方法 对各种复杂的系统具有很好的适应性系统仿真有利于解决随机因素的影响系统仿真可以帮助系统优化 不单纯追求最优解 而寻求改善系统行为的途径和方法 系统仿真方法正是提供了这种环境 利用仿真模型进行系统分析利用仿真模型进行系统的综合 图1 4用仿真进行系统分析 图1 5用仿真进行系统综合 3 系统仿真在物流系统研究中的作用物流系统规划与设计仓储规模与库存管理物料运输调度物流成本估算 1 3 4物流系统优化方法的比较 运筹学方法和智能优化方法可以统称为解析法 1 解析法的优势解析法是建立在数学模型的基础上的 数学模型是定量化的 可以产生更高的精确度 模拟仿真活动有时要耗费大量的时间和物资 花费高昂的代价才能够取得成果 而某些物流系统活动则不能或者很难做仿真实验 2 仿真方法的优势动态的 瞬时的影响随机因素非标准分布随机活动的交互作用 第2章物流系统模型 本章首先概述了几类主要的模型及其特点 并对常用的物流系统建模技术进行讨论 2 1模型概述2 2物流系统模型2 3建模方法与步骤2 4物流系统建模技术 2 1模型概述 2 1 1模型的分类1 实体模型2 图形模型流程图方框图结构图流图 3 数学模型广义 凡是一切数学概念 数学理论体系 各种数学公式 各种方程式以及由公式系列构成的算法系统等都被称为数学模型 狭义 凡是将具体现象 事物的特征和性质给以数学表达的数学结构 如各种等式 不等式 图 表或框图等 也叫数学模型 数学模型 包括原始系统数学模型和仿真系统数学模型 仿真系统数学建模过程称为二次建模过程 模拟模型模拟模型和原系统的物理元素完全不同 但动作相似 2 1 2数学模型的意义 2 1 4系统模型模拟的特殊作用 过程系统流程复杂 投资巨大 生产连续性强 一般不允许在真实系统上进行试验研究 计划中或设计中的过程系统尚不存在 高质量的模拟模型具有预测性 实际过程系统根本不允许作的试验 大大节省原材料 能源消耗和人力资源等 模型的预测性 传递复制极为方便 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 物流模型简单化3 物流研究多方位化4 物流模型构建的规范化 2 3建模方法与步骤2 3 1系统建模方法 U代表目标值 一般希望达到最大值 如利润 效益等 或最小值 如成本 支付 亏损等 加上约束条件就形成一个系统模型 模型思路1 直接分析法例2 1流通加工中的下料问题 试求面积为一定值的矩形中 周长和为最小时的各边长度 2 数据分析法通过分析系统功能的已有数据或新做的试验所获取的数据可以建立系统的模型 3 实验分析法例2 2 4 主观想象法5 人工实现法 2 3 2物流系统模型建立步骤 弄清问题 掌握真实情况搜集资料确定因素之间的关系构造模型求解模型检验模型的正确性 2 3 3系统模拟遵循的总体工作流程 系统定义数学建模模拟建模装载试验结果分析 图2 4系统模拟的工作流程 2 3 4物流系统建模应注意的几个问题 1 对研究对象的了解经常遇到以下情况片面性 偏离了实际无法获得完备的 有关过程系统的数据源数学方法不正确建模效率低2 对于模型构建者提出的要求面向实际具备跨学科多专业的知识及扎实的数学功底意志 善于合作注意外部环境 3 物流系统建模应注意的问题明确目的 确定构成要素模型的简单化和高精度模型没有固定不变的建模方法 2 4物流系统建模技术2 4 1形式化建模与非形式化建模技术 1 形式化建模技术排队网络法 极大代数法 扰动分析法2 非形式化建模技术活动循环图 流程图法 面向对象的建模技术3 Petri网络物流系统模型 图2 5Petri网示意图 4 系统动力学建模技术动力学系统涵义组成部分的子结构及其相互间的关系系统内部的反馈回路结构及其相互作用5 Agent与Multi Agent模型应用Agent与多Agent系统Agent的特征自治智能交互 基于Agent的建模思想无论在现在还是在将来的计算机科学及其应用领域中 由Agent组成的RAS有能力扮演重要的角色 在建立和分析人类社会中的交互模型和理论方面 MAS也可以扮演重要的角色 在物流供应链系统建模中的应用 第3章物流系统优化的运筹规划方法 本章将就物流系统中常见的规划模型形式及求解方法进行研究 并以一个物流网络布局问题的建模与求解作为实例说明该方法的一般应用过程 3 1概述3 2求解方法3 3物流网络布局问题的建模与求解 3 1概述3 1 1物流系统数学模型构建和模拟过程 3 1 2运筹学规划论模型 1 线性规划模型基本结构决策变量约束条件决策目标 标准型的特点目标函数是最大化类型约束条件均由等式组成决策变量均为非负模型隐含的假设比例性假定可加性假定连续性假定确定性假定 图3 2LP问题的解之间的关系图 LP问题的解的概念可行解和最优解基 退化解 最优基 建立线性规划模型的基本步骤明确管理问题 确定决策目标 分析约束因素建立包含一组线性约束条件等式或不等式和最优线性目标函数表达式的数学模型数学模型的求解与检验优化后的分析 整数规划纯整数规划混合整数规划纯0 1整数规划混合0 1整数规划 2 非线性规划模型特征每个问题都可用一组决策变量 x1 x2 xn 表示某一方案存在一组线性等式或不等式的约束条件目标函数 3 1 3几个物流系统数学模型的例子 1 运输问题的数学模型 2 物流配送计划的制定问题 3 集装箱拼箱及装箱问题 4 物流网络布局问题的数学模型 3 2求解方法3 2 1单目标优化问题求解算法 1 无约束优化问题的牛顿法及其修正方法牛顿法 阻尼牛顿法 2 拉格朗日乘子法 拉格朗日乘子法求约束优化问题的计算步骤如下 3 单纯形法基本思想单纯形法是描述可行解从可行域的一个极点沿着可行域的边界移到另一个相邻的极点时 目标函数和基变量随之变化的方法 步骤 图3 3单纯形法的求解过程 4 非线性规划及求解乘子法 3 2 2多目标函数的优化方法 1 统一目标法 极小化 统一目标函数 为了使各个目标函数能均匀一致地趋向各自的最优值 可采用的方法 2 主要目标法 3 2 3整数规划及求解 1 割平面法 2 分枝定界法 3 求解0 1规划的隐枚举法隐枚举法的基本原理与步骤 4 求解指派问题的匈牙利法 3 2 4动态规划法 1 动态规划的基本概念 2 动态规划模型的构成 3 基本原理和基本方程 3 2 5图与网络优化算法 1 求最小生成树的Kruskal算法 2 求最短路径的Dijkstra算法 3 求二部图最大匹配 指派问题 的匈牙利算法 最大流问题就是找出给定流网络的最大流 网络流问题可以归结为一类特殊的线性规划问题 增广链截集 割集 最大流最小截量定理 4 求最大流的方法 Ford Fulkerson标号法 5 贪心法与拟阵贪心法的思想是 从问题的某一个初始解出发逐步逼近给定的目标 以尽可能快的地求得更好的解 当达到某算法中的某一步不能再继续前进时 算法停止 该算法存在问题 不能保证求得的最后解是最佳的 不能用来求最大或最小解问题 只能求满足某些约束条件的可行解的范围 实现该算法的基本思路是 从问题的某一初始解出发 重复判断如果能朝给定总目标前进一步 则求出可行解的一个解元素 直到由所有解元素组合成问题的一个可行解为止 组合算法 提前判断出某些情况不可能取到最优解 3 3物流网络布局问题的建模与求解3 3 1概述 1 物流网络布局问题的意义与主要内容2 物流网络规划的步骤找出物流网络规划的约束条件根据约束条件构造物流网络符合的模型将物流网络符合的模型转化成数学模型求出多组可行解利用可行的评估方法或准则 对以上求出的多组可行解进行评估 将各可行解进行排序 以选取最适合的规划方案 3 选址问题的一个简单实例 3 3 2多元网点布局问题 1 问题描述多元网点布局问题通常有如图3 5所示的系统结构 图中有m个资源点Ai i 1 2 m 各点的资源量为 有个需求点 各点的需求量为 有个可能设置网点的备选地址 需求点可以从设置的网点中转进货 也可以从资源点直接进货 假定各备选地址设置网点的基建投资 仓储费用和运费率均为已知 以总成本最低为目标确定网点布局的最佳方案 图3 5网点布局结构示意图 2 多元单品种物流网点布局的建模方法 3 多元多品种物流网点布局的建模方法 3 3 3设施容量问题 CFLP法 CELP法的基本思想是 首先假定网点布局方案已经确定 即给出一组初始网点设置地址 根据初始方案按运输规划模型求出各初始网点的供货范围 然后在各供货范围内分别移定网点到其他备选地址上 以使各供货范围内的总成本下降 找到各供货范围内总成本最小的新网点设置地址 再将新网点设置地址代替初始方案 重复上述过程直至各供货范围内总成本不能再下降时为止 以图3 6所示的物流网络结构为对象来介绍CFLP方法的处理过程 CFLP法的基本步骤给出网点地址初始方案确定各网点的供货范围寻求网点地址的新方案新旧方案对比 图3 6网络结构图 数例 在某计划区域内 物流网络结构如图3 6所示 其中有12个需求点 中的数字为各点需求量 弧线旁的数字为运价系数 现需要在12个需求点的位置上选取3个点作为网点设置地址 假定网点的最大规模为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人工神经网络4 3禁忌搜索4 4遗传算法4 5模拟退火算法4 6群体智能方法4 7车辆路径问题模型及求解 4 1智能优化方法概述4 1 1优化算法及其分类 目前工程中常用的优化算法经典算法构造型算法邻域搜索算法局部搜索法指导性搜索法基于系统动态演化的方法混合型算法 4 1 2智能优化算法的概念 智能优化算法的基本概念搜索空间 SearchSpace 计算复杂性与NP难题 NP hard 按照计算复杂性理沦研究问题求解的难易程度 可把问题分为P类 NP类和NP完全类 其性质如下 1 这类问题中任何一个问题至今未找到多项式时间算法 2 如果这类问题中存在一个问题有多项式时间算法 那么这类问题都有多项式时间算法 4 2人工神经网络4 2 1人工神经网络概述 神经元及其特性 人工神经网络的基本特性和结构 人工神经网络的简单原理 人工神经网络是根据人的认识过程而开发出的一种算法 假如我们现在只有一些输入和相应的输出 而对如何由输入得到输出的机理并不清楚 那么我们可以把输入与输出之间的未知过程看成是一个 网络 通过不断地给这个网络输入和相应的输出来 训练 这个网络 网络根据输入和输出不断地调节自己的各节点之间的权值来满足输入和输出 当训练结束后 我们给定一个输入 网络便会根据自己已调节好的权值计算出一个输出 4 2 2人工神经网络的数学模型及应用 1 BP神经网络的数学模型 2 BP算法的实现步骤 3 神经网络模型的运行 神经网络的运行包括两个阶段 训练或学习阶段 trainingorlearningphase 预测 应用 阶段 generalizationphase 4 3禁忌搜索4 3 1禁忌搜索算法的主要构成 1 初始解2 邻域移动3 禁忌表和禁忌移动4 选择策略5 破禁策略两个准则 基于适值是准则 若某个禁忌侯选解的适值优于以往搜索最优解 则解禁此候选解为当前解 基于搜索方向的准则 按有效的搜索途径进行 6 禁忌频数 7 停止规则给定最大迭代步数 当总迭代次数达到一个给定的最大迭代步数 或在一个给定的连续迭代步数内当前的最好解没有改善时 则算法终止 禁忌频率数控制原则 达到一定禁忌频数要求时 即当不能使当前最好解改善的循环次数超过了预先设定的阈值时 则算法终止 目标值变化控制原则 当目标值偏离最优值的程度超过了预先设定的阈值时 则算法终止 目标值偏离程度原则 当目标值偏离最优值的程度超过了预先设定的阈值时 则算法终止 4 3 2禁忌搜索算法流程 主要步骤如下 给定算法参数 随机产生初始解 置禁忌表为空 设当前解Xcurrent Xint 当前最好解Xbest Xint 判断算法终止条件是否满足 若是 则结束算法并输出优化结果 否则 继续以下步骤 Xint的邻域内产生Ns个测试解Xi 1 i Ns 求出目标函数f Xi 判断测试解是否在禁忌表中 若不在禁忌表或在禁忌表中但在其目标函数值比Xbest还好 则把它作为新的当前解Xcurrent 并转到 否则 继续测试下一个测试解 若所有的测试解都在禁忌表中 则转到 Xbest Xcurrent 若禁忌表已满 则按先进先出的原则更新禁忌表 把当前解Xcurrent插入禁忌表 记下最优解Xbest 结束算法 4 4遗传算法4 4 1进化计算与遗传算法概述 进化算法 EvolutionaryComputation 是指一类以达尔文进化论为依据来设计 控制和优化人工系统的技术和方法的总称 包括遗传算法 geneticalgorithm 进化策略 evolutionarystrategy 和进化规划 evolutionaryprogramming 遗传算法中处理的是染色体 或者叫基因型个体 一定数量的个体组成丁群体 population 群体中个体的数目称为群体规模 populationsize 而各个体对环境的适应程度叫作适应度 fitness 两个必要的数据转换操作 一个是表现型到基因型的转换 另一个是基因型到表现型的转换 主要特点直接对结构对象进行操作 不存在求导和函数连续性的限定 具有内在的隐并行性和较好的全局寻优能力 采用概率化的寻优方法 4 4 2基本遗传算法 1 染色体编码方法2 适应度函数3 遗传算子选择算子 交叉算子变异算子4 基本遗传算法的运行参数N 群体大小 即群体中所含个体的数量 一般取20 100 T 遗传算法的终止进化代数 一般取为100 500Pc 交叉概率 一般取为0 4 0 99Pm 变异概率 一般取为0 000l 0 1 4 4 3基本遗传算法的一般框架 问题求解的过程编码初始群体的生成适应性值评估检测选择交叉变异 基本遗传算法可定义为一个八元组 SGA C E P0 M T 式中各元素的意义为 C 个体的编码方法 E 个体适应度评价函数 P0 初始群体 M 群体大小 选择算子 交叉算子 变异算子 T 遗传运算终止条件 4 4 4遗传算法的应用 1 遗传算法的应用步骤确定决策变量及其各种约束条件 即确定个体的表现型和问题的解空间 建立优化模型 即确定出目标函数的类型及其数学描述形式或量化方法 确定表示可行解的染色体编码方法 也即确定出个体的基因型及遗传算法的搜索空间 确定解码方法 即确定出由个体基因型到个体表现型的对应关系或转换方法 确定个体适应度的量化评价方法 即确定由目标函数值f X 到个体适应度F X 的转换规则 设计遗传算子 即确定出选择运算 交叉运算 变异运算等遗传算子的具体操作方法 确定遗传算法的有关运行参数 即确定出遗传算法的群体规模popSize 终止进化代数maxGen 交叉概率pc和变异概率pm 2 遗传算法的特点优点遗传算法可以直接根据目标函数值进行搜索 而无需其它信息 如导数信息 遗传算法同时使用多个搜索点的搜索信息 隐含并行搜索特性 遗传算法使用概率搜索特性 其选择 交叉和变异等运算都是以一种概率的方式来进行的 增加了其搜索过程的灵活性 遗传算法具有全局搜索能力 善于搜索复杂问题和非线性问题 遗传算法同求解问题的其它启发式算法有较好的兼容性 可以与其它优化算法进行结合 改进算法性能 如模拟退火遗传算法 缺点编码不规范及编码存在表示的不准确性 单一的遗传算法编码不能全面地将优化问题的约束表示出来 易于陷入局部最优点 导致早熟 4 5模拟退火算法4 5 1模拟退火算法的模型 1 基本思想初始化 初始温度T 充分大 初始解状态S 是算法迭代的起点 每个T值的迭代次数L 对k 1 L做第 3 至第6步 产生新解S 计算增量 t C S C S 其中C S 为评价函数 若 t 0 然后转第2步 2 模拟退火算法新解的产生和接受可分为如下四个步骤由一个产生函数从当前解产生一个位于解空间的新解 计算与新解所对应的目标函数差 断新解是否被接受 判断的依据是一个接受准则 最常用的接受准则是Metropo1is准则 若 t 0则接受S 作为新的当前解S 否则以概率exp t T 接受S 作为新的当前解S 当新解被确定接受时 用新解代替当前解 这只需将当前解中对应于产生新解时的变换部分予以实现 同时修正目标函数值即可 4 5 2模拟退火算法的应用 4 5 3模拟退火算法的参数控制问题 温度T的初始值设置问题 退火速度问题 温度管理问题 常采用如下所示的降温方式 T t 1 k T t 式中k为正的略小于1 00的常数 t为降温的次数 4 6群体智能方法4 6 1蚁群算法 1 引论蚁群算法 ACO 是受自然界中蚂蚁搜索食物行为启发而提出的一种智能优化算法 正反馈机制和通讯机制是蚁群算法的两个重要基础 2 蚁群算法基本原理 3 算法的改进 4 6 2粒子族群优化算法PSO 1 简介 图4 5粒子移动原理图 图4 6平面粒子散布图 粒子起始 图4 7经三次位移后之路径图 2 算法的流程 图4 8PSO流程图 其中present表示粒子当前的位置 pbest表示粒子的个体极值 gbest表示粒子的全局极值 3 粒子群算法和遗传算法的比较 相同 都是随机全局优化算法 都需要随机初始化种群 都是使用适应值来评价 都是根据适应值来进行一定的随机搜索 两种算法都只能不断逼近最优解 不一定能找到最优解 不同 遗传算法需要复制 交叉 变异等遗传操作来产生新个体 在群体中产生新个体是寻优的必须途径 但粒子群优化 PSO 算法没有遗传算法中的复制 交叉 变异等复杂操作 而是根据自己的速度来决定搜索 通过动态跟踪两个极值来更新自己 粒子还有一个重要的特点 就是有记忆 信息共享机制也不同 在遗传算法中 复制 交叉和变异操作都是围绕染色体进行的 染色体 chromosomes 互相共享信息 所以整个种群的移动是比较均匀地向最优区域移动 在粒子群算法中 只有全局极值 gbest 才传递信息给其它粒子 这只是单向的信息流动 整个搜索更新过程总是跟随当前最优解 与遗传算法相比 在大多数的情况下 粒子群算法可能更快的收敛于最优解 4 7车辆路径问题模型及求解4 7 1车辆路径问题的一般描述与问题分类 1 车辆路径问题从配送中心 物流据点 用多辆车向多个需求点 顾客 送货 每个需求点的位置和需求量一定 每辆车的载重量一定 要求合理安排车辆路线 达到一定的目标 如路程最短 费用最少 时间尽量少 使用车辆数尽量少等 此即为VRP问题 并满足以下条件 1 每条配送路径上各需求点的需求量之和不超过车辆载重量 2 每条配送路径的长度不超过车辆一次配送的最大行驶距离 3 每个需求点必须满足 且只能由一辆车送货 4 每辆车均从中心出发 完成任务后又全部回到中心 这就是VRP问题的一般描述 2 VRP问题分类 按照运输任务分为纯装问题 纯卸问题以及装卸混合问题 按照车辆载货状况分为满载问题和非满载问题按照车辆类型分为单车型问题和多车型问题按照车辆是否返回配送中心车场划分为车辆开放问题和车辆封闭问题按照优化的目标可分为单目标优化问题和多目标优化问题按照有无时间要求可分为有时间窗的VRP和无时间窗VRP问题 3 基本VRP的数学模型 4 7 2求解算法综述 精确优化方法 运用线性规划和非线性规划等数学规划技术 来求取最优决策 启发式方法 Heuristic 指通过经验法则来求取运输过程满意解的数学方法 模拟方法 Simulation 交互优化法 图4 8启发式方法求解过程示意图 4 7 3C W算法 4 7 4车辆路径问题的禁忌算法设计 1 算法流程确定D 1 D对应的路线是否满足不大于车辆的最大载重量和最大行驶里程的限制 若满足 则转下一步 把该解中对应的下一个客户2加入到该路线中 此时路线为D 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比较 若m 3 表示该解是一个可行解 若m 3 则表示该解是一个不可行解 2 算法策略解的评价方法邻域操作方法禁忌对象的确定禁忌长度的确定候选集合的确定终止准则的确定 4 7 5神经网络算法 一般按下列步骤进行产生邻接矩阵约束的处理神经网络计算调度方案的形成 4 7 6遗传算法 采用遗传算法求解车辆优化调度问题时 一般按照以下步骤进行确定染色体的编码和初始群体确定适应度函数处理约束遗传算子确定调度方案 第5章物流系统仿真应用基础 本章主要介绍系统仿真的一些基础知识 包括仿真连续与离散系统的基本仿真方法 数据分析与随机数产生等 同时对系统仿真在物流中的应用进行一般性介绍 然后以运输与装卸系统仿真为例介绍仿真应用的一般流程 5 1系统仿真基础5 2仿真方法在物流系统中的应用5 3运输与装卸系统仿真 5 1系统仿真基础 广义的仿真概念是泛指在系统模型上进行试验的技术 也就是说将所研究的对象用某种手段加以模仿的技术 主要有物理模拟技术 称为物理仿真 和数值模拟技术 计算机仿真 计算机仿真的主要特点有时间的伸缩性具有大量逻辑 随机关系复杂的系统运行的可控性便于多方案选优应用的广泛性仿真方法主要是指在计算机上建立仿真模型及进行仿真研究的方法 根据被仿真的系统不同 可分为连续系统仿真方法和离散事件系统仿真方法 5 1 1连续系统仿真方法 1 建立数学模型 2 建立仿真模型 2 离散相似法 图5 2中保持器的作用是使在采样开关断开时 连续系统有一个输入值 否则 如果对原系统的输入输出端只加采样开关 即无图中的保持器 那么离散化之前的输出y t 与离散后的y t 就不会相同 这种离散化方法的近似程度取决于采样频率和保持器的特性 图5 2连续系统离散化 5 1 2离散事件系统仿真方法 1 基本概念实体事件活动进程仿真钟统计计数器2 仿真钟的推进事件调度法固定增量推进方法 3 仿真策略 4 三种仿真策略比较 系统描述建模要点仿真钟的推进执行控制概括地说 事件调度法建模灵活 可应用范围广泛 但一般要求用户采用通用的高级语言编写事件处理子例程 建模工作量大 活动扫描法对于各成分相关性很强的系统来说模型执行效率高 但是 建模时要对各成分的活动进行建模 程序结构比较复杂 流程控制不易 进程交互法是建模最为直观的策略 其模型表示接近实际系统 特别适用于活动可以预测 顺序比较确定的系统 但是其流程控制复杂 建模灵活性不如事件调度法 5 1 3数据输入分析 1 数据收集2 数据收集过程中的注意事项做好仿真计划 详细规划仿真所需要收集的数据在收集数据过程中要注意分析数据数据的均匀组合3 直方图4 直方图分组区间数量的选取 图5 3直方图分组区间示例 5 参数估计 表5 1仿真中常用的一些分布参数建议值 6 拟合度检验 7 相关性分析 8 单变量线性回归的显著性检验 5 1 4随机变量及其生成方法 分布所采用的大多数参数 可分为位置参数 比例参数和形状参数三个基本类型 1 随机数发生器 2 组合发生器 第一种方法是 首先从第一个发生器产生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 优点是大大减少了线性同余发生器带来的自相关 提高了独立性 还可以加长发生器的周期 提高随机数的密度 从而提高了均匀性 而且它一般对构成组合发生器的线性同余发生器的统计特性要求较低 得到的随机数的统计特性却比较好 缺点是速度慢 2 随机变量产生的方法 5 2仿真方法在物流系统中的应用5 2 1应用仿真技术的几个方面 物流系统规划与设计仓储规模与库存管理物料运输调度物流成本估算 5 2 2物流系统仿真的应用意义 物流系统中流 通常应采用动态仿真方法描述流的产生 流动 消失 积累和转换等 才能收到较好的效果 物流系统运行中的仿真 大多采用离散型仿真方法来进行 通过计算机仿真才有可能比较合理地描述由于人的思维模式对真实系统运行的影响和作用 而而也就有可能获得较为优秀的物流系统运行的组织方案 5 2 3物流系统仿真类型 1 连续系统模型2 离散系统模型根据仿真时钟推进的方式下次事件时间推进法固定增量时间推进法主导时钟推进法 5 2 4物流系统仿真的主要步骤 问题的描述设定目标与总体方案 建立仿真模型收集和处理信息确认模型参数仿真模型的程序设计仿真模型的试运行确认模型正确设计试验仿真运行分析仿真结果向决策者提出建议建立文件的数据库 知识库 图5 4物流系统仿真的一般步骤 5 2 5物流系统仿真模型的确认 1 仿真模型确认一般观点建立仿真模型的目的是要用仿真实验代替实际系统的实验 模型应能满足使用要求且费用较低 不管在研究模型上作了多大的努力 模型总是仅仅近似于现实系统 某一模型对某一个目标是有效的 也许对另一个目标是无效的 确认模型时总是相对于一组判断准则而言 应仔细选择这些准则 仿真模型的研究和确认应贯穿于建模的全过程 大多数经典统计分析方法不可直接用于确认模型 2 确认物流系统仿真模型的三步法建立直观看来是正确的仿真模型检验建模假设仿真数据与实际数据的比较3 仿真程序验证首先将仿真主程序和少数关键子程序编好 同时进行详细的检验和验证 确保它们是正确无误 然后逐步扩展和完善 由多位编程人员同时阅读和检查同一程序 程序运行的追踪检查是用于调试离散事件仿真模型的一种最为有用的技术 进行仿真试验前 应用简化考题验证仿真程序 图形显示 5 3运输与装卸系统仿真5 3 1概述 运输与装卸配合关系 可视为一排队系统 以系统总费用最低作为系统优化组合的主导因素 运用离散系统仿真的办法来寻找及恰当的组合与配合关系 5 3 2仿真示例 1 装运问题的提出和系统定义装运过程描述 装车设备在装车场为汽车装载 汽车到达装车场时若装车设备空闲就立即装载 否则汽车加入等待队列 装载完毕的汽车从装车场上坡运行到卸车点称重并卸车 卸车点在任一时刻只允许一辆汽车卸车 其余汽车将排队等待 卸车完毕空车返回装车场 装车设备和汽车每班工作6小时 一上班时全部汽车在装车场等待 要研究的问题是对于不同类型的汽车 每台装车设备和几辆汽车搭配时能得到较高的日产量和较低的装运费用 可将系统范围确定为一个装车场 一台装车设备 数目不同的某种类型汽车 一定距离外的卸车点 约束条件有 6小时一班的断续工作 汽车数目在1到10之间 2 系统的流程图 图5 5系统流程图符号 图5 6系统流程图 3 构造系统模型 某辆汽车到达装车点某辆汽车装完车离开装车点某辆汽车到达卸车点某辆汽车卸完车离开卸车点每一事件发生时系统状态的变化以及与该汽车的下一事件之间的联系构成一个子模型 这四个子模型构成了装运系统的基本模型 4 数据准备 表5 2 表5 3 图5 7满载和空载运行的模型 5 3 3用事件法描述装运系统 1 用事件法描述装运系统建立模拟时钟用变量 CLOCK 用以记录汽车在不同状态下所处的时刻 设定系统状态变量 描述系统状态 设定记录状态变化的时间变量 2 进行系统模拟 1 确定下次发生的事件 图5 8系统模拟过程的粗框图 2020 1 30 167 可编辑 事件子程序 子程序1用来处理某汽车装载完毕进入满载运行的事件 子程序2用来处理某汽车到达卸车点后系统状态变化及累计卸车等待时间和货物装运量 图5 9是子程序2的框图 子程序3用来处理某汽车卸完车进入空载返回状态的事件 子程序4用来处理汽车到达装车场后系统状态的变化及累计等待时间 图5 10是子程序4的框图 图5 10子程序4框图 图5 9子程序2框图 3 控制模拟运行 设置系统初始状态产生随机数的子程序数据块子程序可以方便地用于不同类型的汽车与装车设备配合数的研究以及不同的运输路程的情况 可以使用数据块子程序向公用区中的变量赋初值 从而得到装载时间 卸车时间 每车装载量以及满载运行时间 空载运行时间这些随机变量的均值和方差等有关参数 5 3 4装运系统试验设计 1 确定统计分析形式2 确定样本大小 3 相关抽样4 模拟试验的输出分析 模拟运行结果如表5 4所示 从图中可以看出汽车数目较小时货物装运量随车数增加显著增加 汽车数目较大时 装运量逐渐达到饱和 图5 11货物装运量和汽车数目关系曲线 从设备利用率分析 装车设备空闲时间随汽车数目增加而减少 汽车总等待时间包括装载等到待总时间和卸车等待总时间随汽车数目增加而增加 如图5 12所示 按表5 4可计算出不同汽车数目的装运费用如表5 4 其对应的近似曲线如图5 13 图5 12汽车和装车设备配合曲线 表5 4 图5 13不同汽车数目的装运费用曲线 第6章物流系统动力学仿真 本章介绍系统动力学及与物流系统应用结合而成的所谓 物流系统动力学 旨在以系统动力学为框架 综合其他定性 定量方法 应用于物流系统领域 分析物流的系统结构及动态发展机制 进行物流系统宏观战略上的决策问题的仿真与优化问题研究 6 1系统动力学方法6 2物流系统动力学应用6 3区域物流系统动力学模型设计 6 1系统动力学方法6 1 1什么是系统动力学 系统动力学是研究信息反馈系统动态行为的计算机仿真方法 它有效地把信息反馈的控制原理与因果关系的逻辑分析结合起来 面对复杂的实际问题 从研究系统的内部结构入手 建立系统的仿真模型 并对模型实施各种不同的政策方案 通过计算机仿真展示系统的宏观行为 寻求解决问题的正确途径 6 1 2系统动力学模型特点与建模步骤 1 系统动力学模型特点所建模型要与管理者的思维模型相沟通研究问题注重从因果机制出发从观察系统结构入手内部结构处理非线性性延迟特性能够进行仿真 2 系统动力学理论的特点 系统动力学是一门可用于研究处理社会 经济 生态和生物等一类高度非线性 高阶次 多变量 多重反馈 复杂时变大系统问题的学科 系统动力学的研究对象主要是开放系统 系统动力学研究解决问题的方法是一种定性与定量结合 系统 分析 综合与推理的方法 规范的模型 它是社会经济一类系统的实验室 系统动力学模型被誉为实际系统的实验室 系统动力学的建模过程便于实现建模人员 决策者和专家群众的三结合 便于运用各种数据 资料与人们的经验与知识 也便于汲取 融汇其他系统学科与其他科学理论的精髓 2 系统动力学建模基本步骤 明确仿真目的构成系统因果反馈环绘制系统流图程序设计上机仿真实验仿真结果分祈 6 1 3系统动力学模型结构 1 闭合的边界社会或管理系统应属于开放系统 虽然系统与环境之间具有相互作用的现象 但在构建系统模型时 必须假设系统为完全独立 没有任何东西可以流穿边界进入或离开系统 2 模型的反馈一般地 当A变化时将引起B变化 假定 A 0 B 0 分别表示变量A B的改变量 若满足下列条件之一 A加到B中 A是B的乘积因子 A变到A A 有B变到B B 即A B的变化方向相同 则称A到B具有正因果关系 简称正关系 用 号标在因果链上 若满足下列条件之一 A从B中减去 1 A是B的乘积因子 A变到A A 有B变到B B 即A B的变化方向相反 则称A到B具有负因果关系 简称负关系 用 号标在因果链上 图6 1因果链 当这种关系从某一变量出发经过一个闭合回路的传递 最后导致该变量本身的增加 这样的回路就称为正反馈环 反之则称为负反馈环 实际的复杂社会系统都是由许多相互联系的非线性反馈回路组成 实际的复杂社会系统都是由许多相互联系的非线性反馈回路组成 系统动力学了解系统动态特性的主要方法是回路分析法 即因果关系和反馈思想 反馈分为正反馈与负反馈 一般原则是 若反馈回路包含偶数个负的因果链 则其极性为正 叫正反馈回路 若反馈回路包含奇数个负的因果链 则其极性为负 叫负反馈回路 图6 2因果反馈回路 环 3 流位与流率 每一个反馈环中至少包含着两种基本的变量即流位与流率 流位是系统内流量的积累 它是系统的状态变量 流率从物理概念上将流位变化定量化 根据对流位的关系分成入流率和出流率 可能有多个 它是单位时间内流入或流出流位的流量 4 流程图 图6 3常用流程图符号 6 1 4系统动力学流程 为了进一步明确表示系统各元素之间的数量关系 并建立相应的动力学模型 系统动力学方法通过广义的决策反馈机构来描述上述机制 如图6 4所示 任何决策反馈回路一定要包含两种基本变量 状态变量 或称为流位变量Lever 决策变量 也称变化率 或称流率变量Rate 6 1 5系统动力学模型方程体系 主要方程包括以下五类 水平方程 L方程 速率方程 R方程 辅助方程 A方程 常量方程 C方程 初值方程 N方程 6 2物流系统动力学应用6 2 1概述 物流系统动力学就是系统动力学与物流系统科学相结合形成的一门新的交叉学科 物流系统动力学的基本特点在于它从物流系统复杂的基本构造出发 充分考虑到系统与环境 系统内部各因素间的关系 构造出一种能够比较全面刻画复杂物流系统的模型 这种模型也被誉为 战略与策略的实验室 系统动力学本身亦有其固有的缺陷 需要结合采用多种方法互相补充 互相完善 6 2 2物流系统动力学因果分析 1 由于社会系统的复杂性 以至于无法仅凭借语言和文字对它的行为和结构做准确地描述 2 在研究模型中 不仅要准确地描述现实领域 也是合理地描述控制领域 现实领域经济水平 人口水平 消费水平 物流系统需求 物流系统供给等 控制领域国民收入分配政策 人口控制政策 物流系统政策 经济发展政策等 3 基本因果关系图 6 2 3物流系统动力学结构方程式 表6 1时间标号表 6 2 4DYNAMO仿真计算 图6 6一阶正反馈回路流程图 表6 2仿真表 图6 7仿真结果示意图 图6 8一阶负反馈回路流程图 表6 3仿真表 图6 9仿真结果示图 表6 4仿真表 图6 11仿真结果示意图 图6 10两阶负反馈回路示意图 6 2 5物流系统动力学模型建模步骤 确定系统的边界 画出因果图 选择模型的基本变量 水准 以水准为中心构造各自的子系统 根据因果图 连接各子系统 根据以上的描述 写出方程式 进行仿真运算 并做出真实性检验与政策分析 图6 12DYNAMO仿真程序框图 6 3区域物流系统动力学模型设计 1 物流系统的因果关系图 图6 12地区物流系统基本因果关系图 图6 13基本因果关系环 2 经济增长子构造 图6 14经济增长子构造 3 物流需求子构造 图6 15物流需求