集装箱调度问题的平行机排序算法研究
发布时间:2020-07-15 02:33
【摘要】: 本文以现代物流业中港口集装箱的装卸调度作业问题为背景,通过抽象和简化将其等价转化为平行机排序理论中的最早完工时间问题,提出了三种近似算法并分析了各近似算法的时间复杂性以及各自的适用条件,对近似算法性能的分析主要采用了学术界常见的最差情形下的“竞争比分析”来衡量各近似算法所求得的近似解和最优解之间的关系,本文的主要研究成果及贡献如下: 1,针对可组合型集装箱装卸调度问题提出了近似算法APA,并证明了近似算法APA的竞争比为4/3-1/3K(K≥2),其时间复杂性为O(n3+nlogn),该算法的局限性在于当K≥t+1时显然可以通过拆分的方法对近似解作进一步的优化。 2,在近似算法APA的基础上,通过拆分优化的方法提出了近似算法APB,其时间复杂性为O(n3+nlogn+K),并证明了在任一情况下近似算法APB的解均不差于近似算法APA的解,即CmaxAPB≤CmaxAPA;特别地当K≥t+1时,近似算法APB能够将解改进至CmaxAPB≤CmaxAPA,且二者近似解的比值下界K/2K-1(K≥2)随着车辆数K的增大而减小;然而由于对任意的K≥2在最差情形下近似算法APB无法作进一步的优化改进,因而对任意的K≥2近似算法APB的竞争比为4/3-1/3K(K≥2)。 3,针对一类特殊情形分析了近似算法APB对竞争比的具体改进,即τ≥1且K≥5时,近似算法APB有效地将竞争比改进至 4,针对可拆分型集装箱调度问题将其转化为Pm |setup splitting|Cmax,通过改进近似算法LSU的拆分规则提出了近似算法APC,其时间复杂性为O((n+K)log(n+K)),并证明了在任意情形下近似算法APC的解均优于近似算法LSU的近似解,具体的将竞争比改进至 本文所提出的各近似算法均能在多项式时间内求得和最优解较为接近的近似算,能够有效响应客户的实时需求,因而具有较好的理论意义和实际应用价值。
【学位授予单位】:复旦大学
【学位级别】:硕士
【学位授予年份】:2010
【分类号】:F552;U695.22
【图文】:
复旦大学硕士学位论文图3一1具有准备时间的可拆分组合问题的原型图3一1中各图例说明:矩形代表处理终端(港口、码头等)以及系统的可用资源K辆车,分别用K,长,K,……,玲表示;实线三角形代表收货工作点一Pick一 uPJob,实线圆形代表送货工作点- DeliveryJob。如图3一1所示,可知在港口集装箱调度问题原型中的单个工作的完工时间有如下特性:总完工时间由两部分组成,即运输时间和装卸时间,其中运输时间取决于每个工作点和港口终端的距离
复旦大学硕士学位论文图4一1原问题等价转换化为t个双向工作圈后的描述图4一1的对应图例说明:矩形代表港口处理终端及K辆车:1,2,3,……,K;实线三角形代表收货工作点一Pick一 uPJob,实线圆形代表送货工作点- DeliveryJob;虚线三角形代表引入的虚拟收货工作点一 D~yPick一 uPJob,虚线圆形代表引入的虚拟送货工作点一D~yDeliveryjob。4.2近似算法ApA的提出及性质分析4.2.1近似算法APA的原理及步骤由本文第4.1节中的引理4.1知,可通过整数规划Al。在O(n,)时间内求得单辆车情况下最早完工时间的解
以C~(oPT)表示可组合型集装箱调度问题的最优解,v表示每辆车的速度(所有车辆均为同速、匀速、恒速机),则由平行机排序问题最优解的性质以及图4一2所示的已知条件可知:cma二(onT)z格。一(2d卜Zd犷干“‘呱‘衅+’d犷+‘”+2d器)/vk……(4一3)Zd,犷+Zd’F+Zd’彗+Zd,梦+……+Zd,F+Zd’犷)/vk其中:t=max{np,nd}又由图4一1可知,可组合型集装箱调度问题转化为t个双向工作圈以后,每个双向工作圈的加工时间为P’,=(d’尸+叮+叮”)/v
本文编号:2755846
【学位授予单位】:复旦大学
【学位级别】:硕士
【学位授予年份】:2010
【分类号】:F552;U695.22
【图文】:
复旦大学硕士学位论文图3一1具有准备时间的可拆分组合问题的原型图3一1中各图例说明:矩形代表处理终端(港口、码头等)以及系统的可用资源K辆车,分别用K,长,K,……,玲表示;实线三角形代表收货工作点一Pick一 uPJob,实线圆形代表送货工作点- DeliveryJob。如图3一1所示,可知在港口集装箱调度问题原型中的单个工作的完工时间有如下特性:总完工时间由两部分组成,即运输时间和装卸时间,其中运输时间取决于每个工作点和港口终端的距离
复旦大学硕士学位论文图4一1原问题等价转换化为t个双向工作圈后的描述图4一1的对应图例说明:矩形代表港口处理终端及K辆车:1,2,3,……,K;实线三角形代表收货工作点一Pick一 uPJob,实线圆形代表送货工作点- DeliveryJob;虚线三角形代表引入的虚拟收货工作点一 D~yPick一 uPJob,虚线圆形代表引入的虚拟送货工作点一D~yDeliveryjob。4.2近似算法ApA的提出及性质分析4.2.1近似算法APA的原理及步骤由本文第4.1节中的引理4.1知,可通过整数规划Al。在O(n,)时间内求得单辆车情况下最早完工时间的解
以C~(oPT)表示可组合型集装箱调度问题的最优解,v表示每辆车的速度(所有车辆均为同速、匀速、恒速机),则由平行机排序问题最优解的性质以及图4一2所示的已知条件可知:cma二(onT)z格。一(2d卜Zd犷干“‘呱‘衅+’d犷+‘”+2d器)/vk……(4一3)Zd,犷+Zd’F+Zd’彗+Zd,梦+……+Zd,F+Zd’犷)/vk其中:t=max{np,nd}又由图4一1可知,可组合型集装箱调度问题转化为t个双向工作圈以后,每个双向工作圈的加工时间为P’,=(d’尸+叮+叮”)/v
【参考文献】
相关期刊论文 前5条
1 张潜,高立群,胡祥培,吴畏;物流配送路径多目标优化的聚类-改进遗传算法[J];控制与决策;2003年04期
2 吴宗彦;王景华;张建军;张利;;基于蚁群算法的智能运输调度问题的研究[J];计算机工程与应用;2006年35期
3 任传祥,张海,范跃祖;混合遗传-模拟退火算法在公交智能调度中的应用[J];系统仿真学报;2005年09期
4 郭耀煌,李军;车辆优化调度问题的研究现状评述[J];西南交通大学学报;1995年04期
5 胡大伟;朱志强;胡勇;;车辆路径问题的模拟退火算法[J];中国公路学报;2006年04期
本文编号:2755846
本文链接:https://www.wllwen.com/jingjilunwen/jtysjj/2755846.html