不确定环境下越库调度的模型及算法研究

论文摘要

本文研究面向汽车入厂物流的不确定环境下的越库调度模型及算法。汽车入厂物流是汽车精益生产体系中的重要组成部分,是国际物流界公认的操作最复杂、技术含量最高的物流服务。越库是指在仓库或配送中心只实现收发货功能而消除货物存储与订单获取功能的运作模式。越库在减少或者消除库存、降低搬运成本、减少空间需求,实现集中化低运输成本等方面作用突出。不确定性是导致物流效率降低的主要因素。而运输不确定又是影响汽车零部件入厂物流中的最主要因素,所以本文针对汽车入厂物流中的运输不确定性进行研究。汽车入厂物流的运输模式主要有直运(Direct Delivery)及循环取料(Milk Run)两种。循环取料适合于多频次小批量运输,而直运适合于大批量满载运输。本文将研究这两种运输模式下的入厂物流越库调度策略。根据出入库车辆数目可以将直运越库调度模型简单的划分为基本直运越库调度模型和柔性直运越库调度模型。因此,本文研究主要分为以下三部分:1)不确定直运越库调度基本模型与算法研究。研究不确定环境下出入库车辆均有一辆的情形。首先,建立确定和不确定混合整数规划模型并用ILOG CPLEX优化软件求解小规模问题。然后,根据问题特征提出三种在确定和不确定情形下均适用的启发式算法和一种仅针对不确定情形的启发式算法,并设计数值实验比较以上各种算法的性能。进一步,根据到实际物流企业调研所得的运输时间服从的分布,利用龙贝格积分方法对用于决策的运输时间的期望值进行修正。最后,通过数值实验比较了期望值修正前后的区别。证明确定性柔性越库调度问题的启发式算法的上界。2)不确定柔性越库调度模型与算法研究。由于在现实的物流企业中一般同时有许多出入库车辆,所以对该情形下的不确定越库调度问题研究更有现实意义。首先建立确定和不确定柔性越库调度模型。用CPLEX求解小规模问题。然后提出与第一部分相似的四种启发式算法,并比较了期望值修正前与修正后的区别。另外,还提出随机调度(Random Scheduling)算法用来检验本文所提启发式算法的有效性。3)不确定循环取料越库调度模型与算法研究。该部分假设出入库车辆均只有一辆,其中入库阶段是循环取料运输模式,出库阶段是直运模式,运输时间随机。首先分别建立混合规划模型,得出小规模确定和不确定情形下的最优解。然后根据问题的特征提出了一种启发式算法和禁忌搜索算法,并通过数值实验比较了两种算法的性能。结果表明,禁忌搜索算法在启发式解的基础上,性能提高明显。本文通过到实际的物流企业调研,采集实际数据进行分析并设计数值实验。最后,实验结果解释了许多现实中存在的问题的原因,并给企业提供了一些有用的建议和算法。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究目的和意义
• 1.3 国内外研究现状
• 1.4 研究内容
• 1.5 论文结构
• 1.6 本章小结
• 第二章 不确定直运越库调度基本模型与算法
• 2.1 问题介绍
• 2.2 混合整数规划模型
• 2.2.1 确定性混合整数规划模型
• 2.2.2 不确定性混合整数规划模型
• 2.3 启发式算法
• 2.3.1 JC算法
• 2.3.2 FC算法
• 2.3.3 NFC算法
• 2.3.4 SJC算法
• 2.4 蒙特卡罗模拟方法
• 2.5 用蒙特卡罗模拟方法产生随机值
• 2.6 数值实验
• 2.6.1 基本定义
• 2.6.2 COP解, UCR解与UCOP解的比较分析
• 2.6.3 小规模不确定性情形下启发式算法与最优解比较
• 2.6.4 大规模确定情形下启发式算法间的比较
• 2.6.5 大规模不确定性情形下启发式算法间的比较
• 2.6.6 大规模确定和不确定情形下的JC算法解的比较
• 2.6.7 找到SJC算法
• 2.6.8 SJC算法与JC算法在大规模不确定情形下的比较
• 2.7 期望值修正
• 2.7.1 问题背景
• 2.7.2 龙贝格（Romberg）积分方法
• 2.7.3 用龙贝格方法修正期望值
• 2.8 数值实验
• 2.8.1 基本定义
• 2.8.2 COP, XCOP, UCR, XUCR和UCOP比较分析
• 2.8.3 大规模不确定情形下修正前后的启发式解对比
• 2.8.4 大规模情形下XJC解与UJC解的比较
• 2.8.5 大规模情形下SXJC与XJC之间的比较
• 2.9 启发式算法上界证明
• 2.10 本章小结
• 第三章 不确定柔性越库调度模型与算法
• 3.1 问题介绍
• 3.2 混合整数规划模型
• 3.2.1 确定性混合整数规划模型
• 3.2.2 不确定性混合整数规划模型
• 3.3 启发式算法
• 3.3.1 MJC算法
• 3.3.2 MFC算法
• 3.3.3 MNFC算法
• 3.3.4 SMJC和SMNFC算法
• 3.3.5 RS （Random Scheduling） 算法
• 3.4 数值实验
• 3.4.1 小规模情形下COP, XCOP, UCR, XUCR和UCOP的比较
• 3.4.2 小规模不确定情形下启发式解与最优解的比较
• 3.4.3 大规模不确定情形下启发式算法之间的比较
• 3.4.4 期望值修正对MJC和MNFC算法结果的影响
• 3.4.5 期望值修正前后计划预测精度对比
• 3.4.6 找到SXMJC和 SXMNFC
• 3.4.7 大规模情形下SXMJC与XMJC, SXMNFC与XMNFC的比较
• 3.5 本章小结
• 第四章 不确定循环取料越库调度模型与算法
• 4.1 问题介绍
• 4.1.1 循环取料介绍
• 4.1.2 循环取料的应用
• 4.1.3 国内外研究现状
• 4.2 混合整数规划
• 4.3 启发式算法
• 4.4 禁忌搜索算法（TS算法）
• 4.4.1 禁忌搜索算法简介
• 4.4.2 禁忌搜索参数设计
• 4.5 数值实验
• 4.5.1 小规模情形下COP,UCR和UCOP解的比较
• 4.5.2 小规模情形下BVSL和TS解与UCOP解的比较
• 4.5.3 大规模情形下BVSL和TS解的比较
• 4.6 本章小结
• 第五章 总结与展望
• 参考文献
• 附录
• 致谢
• 攻读硕士学位期间已发表或录用的论文