周期性时变网络中粮食物流优化问题

论文摘要

粮食是国家重要的经济和战略物资.粮食调运问题是国家粮食管理部门和粮食企业急需解决的重要问题.随着电子商务和第三方物流的兴起,出现了专业化的粮食物流企业,为粮食物流的专业化运行和成本节约开创了新的模式.在粮食物流决策中,需要同时考虑运行时间、成本和风险等因素,这样,就将传统单目标的运输路径问题转变成了多目标问题.同时,时间因素对粮食运输的诸多因素都会产生一定的影响.因此研究具有时变特性的粮食运输问题具有极强的社会背景和应用前景.目前文献中研究的时变性物流调度往往以城市交通为背景.城市交通状况变化的特点是以一天为一个周期,因而调度也在一天内进行.粮食运输与市内物流不同,由于它是跨城市、跨地区的,运行时间相对比较长,一次运输要经历多个周期.因此,针对粮食运输的特点,有必要研究周期性时变网络中的物流调度问题.本论文从这种特殊时变网络中的最短路问题入手,从数学模型及算法设计方面开展研究.主要研究成果如下:首先建立周期性时变网络中最速路问题的数学模型,其中主要运用整数的模运算,得到动态的状态转移方程.设一个周期分为K个时段k=0,1,…,K-1.已知t（i,j,k）为车辆在时段（状态）k从顶点i出发运行到顶点j的时间长度,则到达顶点j的时段（状态）为k’=[k+t（i,j,k）]（modK）.通过引进车辆在时段k进入边e（i,j）的指示变量x（i,j,k）以及车辆在时刻k经过顶点i的指示变量y（i,k）,可得到最速路的数学模型:其中目标函数（0.0.1）表示所选出边的运行时间之和最小;约束条件（0.0.2）表示在时刻0从起点s出发;（0.0.3）表示可在任意时段到达终点d;条件（0.0.4）表示车流经过的顶点;条件（0.0.5）表示状态转移关系:x（i,j,k）=1（?）y（j,k’）=1;条件（0.0.6）为（0,1）变量约束.这是一个（0,1）整数规划.其次,由于（0,1）整数规划不便求解,我们将其转化为图论模型.其主要思想是将顶点处于的不同状态看做不同顶点,按照状态转移方程来连边.这样便得到一个周期性时变网络.然后在其中运用已知的最短路算法.在假设时段数K为常数的前提下,得到多项式时间算法.在考虑运行时间最小的单目标问题的基础上,进一步研究双目标问题,包括运行时间及运行费用两个目标.主要研究线性加权法模型、主次日标模型及约束化模型.对前两个模型得到多项式时间算法.最后一个模型是NP-困难的,讨论了实用的启发式算法.最后,在结论部分对论文的工作进行了总结,指出了论文的主要创新之处,并对未来研究加以展望.

论文目录

• 摘要
• Abstract
• 第1章 概论
• 1.1 研究背景
• 1.2 时变网络中的物流调度
• 1.3 最短路问题综述
• 第2章 周期性时变网络中单目标粮食物流优化问题
• 2.1 数学模型的建立
• 2.2 图论模型
• 2.3 算法实施方案
• 2.4 算法运行实例
• 第3章 周期性时变网络中多目标粮食物流优化问题
• 3.1 引言
• 3.2 线性加权法
• 3.3 主次目标模型
• 3.4 约束化模型
• 结论
• 参考文献
• 致谢
• 附录