不定期运输船舶配置、路径选择、货流分配组合问题研究

,不定期运输船舶配置、路径选择、货流分配组合问题研究,第六组,Combinedshipallocation,routingandfreightassignmentintrampshipping,来源期刊:TransportationResearchPartE,Abstract,1.研究问题：已知多个港口对间的货运需求，通过配置不同类型的船舶、进行货流分配、选择合理的运输路径，使船公司利润最大。2.组合优化模型：同时考虑不定期运输中的船舶配置、路径选择、货流分配3.遗传算法求解4.实证分析：证明了本文所提出的方法在求解实际问题中的适用性和有效性。,3,1引言,1.Introduction,1.1研究对象,1.Introduction,1.2研究问题特点,1.Introduction,1.3问题属性鉴定,SRP类似于“车辆路径问题(vehicleroutingproblem-VRP)”。SRPTP类似于“带有时间窗的取送货车辆路径问题”，属于车辆路径问题的变异问题，也是NP-hard组合优化问题。,相关概念解释1,参考文献：1谢秉磊,李军,郭耀煌有时间窗的非满载车辆调度问题的遗传算法J，系统工程学报，2000-3（15）2盛丽俊，周溪召，带有时间窗的车辆路径优化问题，上海海事大学学报J,2007,4（28）,1.Introduction,SRP类似于“车辆路径问题(vehicleroutingproblem-VRP)”。SRPTP类似于“带有时间窗的取送货车辆路径问题”，属于车辆路径问题的变异问题，也是NP-hard组合优化问题。,这类问题的特点：复杂，传统数学规划方法无法在有效时间内求解，目前求解技术主要是“元启发式”法。,1.3问题属性鉴定,相关概念解释2,参考文献：陈萍，黄厚宽，董兴业，求解卸装一体化的车辆路径问题的混合启发式算法J,计算机学报，2008,4（31）,1.Introduction,SRP类似于“车辆路径问题(vehicleroutingproblem-VRP)”。SRPTP类似于“带有时间窗的取送货车辆路径问题”，属于车辆路径问题的变异问题，也是NP-hard组合优化问题。,从而，确定SRPTP的建模思路，以及求解方法：遗传算法。,这类问题的特点：复杂，传统数学规划方法无法在有效时间内求解，目前求解技术主要是“元启发式”法。,1.3问题属性鉴定,1.Introduction,1.4本文组织结构第2部分描述了相关的文献综述；第3部分解释了所构建的组合数学模型；第4部分详细阐述了求解该不定期运输船舶航线设计问题的遗传算法设计；第5部分给出了计算求解结果和相关见解；第6部分总结了全文，并指出了未来研究方向。,2文献综述,2.Literaturereview,2.Literaturereview,TheUniquenessoftheSRPTP:航线的非闭合性,文献综述,针对研究问题,针对求解思路,2.Literaturereview,研究贡献：,1.与已有研究只考虑满载问题不同，本文在不定期运输船舶路径问题中考虑了非满载问题，这使模型更加适用、更加复杂。,2.与传统商业软件包相比，本文提出的求解算法求解速度更快。,3模型建立,3.Model,不定期船运输特点,3.Model,SRPTP问题的特点,3.1船舶子网络,3.Model,3.1船舶子网络,3.Model,3.2货物子网络,3.Model,3.2货物子网络,3.Model,3.Model,目标函数,总收入,货物运输成本,船舶航运成本,装卸费保险费佣金,船舶租金燃油成本停泊费杂费,3.3数学表达式,1票货物的单位收入,取货弧流量,取货弧的单位运输成本,单位航运成本,3.Model,目标函数,总收入,货物运输成本,船舶航运成本,3.3数学表达式,1票货物的单位收入,取货弧流量,取货弧的单位运输成本,单位航运成本,货物m调整弧的单位成本,货物m调整弧的流量,3.Model,SRPTP模型约束,除了网络模型中常用的流量守恒约束以外，SRPTP还需要四种附加约束。3.2.1、船舶子网络和货物子网络之间交互作用约束3.2.2、船舶容量/载重吨约束3.2.3、货物装载/卸载操作时间约束3.2.4、非分割装载和直达运输约束,3.Model,船舶子网络中流量守恒约束,3.3数学表达式,虚拟的汇聚节点,虚拟的源节点,船舶子网络中，弧上的流量,3.Model,货物子网络中流量守恒约束每艘船、每票货,3.3数学表达式,货物网络源节点,货物网络汇聚节点,交货节点,取货节点,3.Model,货物子网络中流量守恒约束,3.3数学表达式,货物网络源节点,货物网络汇聚节点,交货节点,取货节点,货物流子网络中，弧上的流量,3.Model,货物O-D子网络中流量守恒约束,3.3数学表达式,从O点来看,交货弧流量,取货弧流量,调整弧流量,从D点来看,3.Model,SRPTP模型约束,除了网络模型中常用的流量守恒约束以外，SRPTP还需要四种附加约束。3.2.1、船舶子网络和货物子网络之间交互作用约束3.2.2、船舶容量/载重吨约束3.2.3、货物装载/卸载操作时间约束3.2.4、非分割装载和直达运输约束,3.2.1船舶子网络和货物子网络之间交互作用约束,3.Model,货物只能够沿着“船舶子网络中存在的弧线”运输,3.Model,SRPTP模型约束,除了网络模型中常用的流量守恒约束以外，SRPTP还需要四种附加约束。3.2.1、船舶子网络和货物子网络之间交互作用约束3.2.2、船舶容量/载重吨约束3.2.3、货物装载/卸载操作时间约束3.2.4、非分割装载和直达运输约束,3.2.2船舶容量/载重吨约束,3.Model,货物的体积/重量,货物流子网络中的流量,船舶容量/载重吨,船舶子网络中的流量,3.Model,SRPTP模型约束,除了网络模型中常用的流量守恒约束以外，SRPTP还需要四种附加约束。3.2.1、船舶子网络和货物子网络之间交互作用约束3.2.2、船舶容量/载重吨约束3.2.3、货物装载/卸载操作时间约束3.2.4、非分割装载和直达运输约束,3.2.3货物装载/卸载操作时间约束,3.Model,假设：取货2天；交货2天；装/卸1天,3.Model,3.2.3货物装载/卸载操作时间约束,装载操作时间约束,取货弧,装货操作时间,取货弧流量,取货日期离港日期,离港日期-取货日期=装货时间,离港日期=取货日期+装货时间,k=j,i,xl=1,3.Model,3.2.3货物装载/卸载操作时间约束,卸载操作时间约束,卸货弧,卸货操作时间,交货弧流量,到港日期交货日期,交货日期-到港日期=卸货时间,到港日期=交货日期-卸货时间,3.Model,SRPTP模型约束,除了网络模型中常用的流量守恒约束以外，SRPTP还需要四种附加约束。3.2.1、船舶子网络和货物子网络之间交互作用约束3.2.2、船舶容量/载重吨约束3.2.3、货物装载/卸载操作时间约束3.2.4、非分割装载和直达运输约束,3.2.4非分割装载和直达运输约束,3.Model,3.2.4非分割装载和直达运输约束,3.Model,交货弧流量,取货弧流量,3.Model,决策变量,4遗传算法设计,4.GeneticAlgorithm,特点,遗传算法（GA）综述,全局寻找式的启发式算法拥有更高比例良好解（goodsolutions）的区域会被更加频繁地查找,原则,生物进化论适者生存,主要步骤,遗传算法的主要步骤是编码（encoding），选择（selection），交叉互换（crossover），突变（mutation）和功能评价（functionalevaluation）。,原始种群,新的种群,迭代,进化,遗传算法（GA）计算过程,对后续计算要使用的参数进行初始赋值，比如种群大小，遗传代数，最大遗传代数，交叉互换概率，突变概率等。编码，形成一个初始染色体种群。功能评价，每条染色体被解码并计算评估其适应性值（fitnessvalue）。如果还没有达到最大遗传代数，将根据相应的适宜性值，采用循环往复式方法（roulettewheel）筛选出一对染色体。对其进行基因操作（交叉互换和突变）产生两个后代（offspring）。将所形成的后代置于一个新的种群中。持续整个过程，直到新的种群大小和初始种群大小相等。,编码和解码过程,解码过程：所产生的航线是A-C-D-B如果允许有时间窗灵活性，我们可以把装货和交货顺序一一枚举出来，以寻找拥有最大适应性值的船舶航线但是潜在问题之一是，所求导出来的船舶航线可能会由于违反时间约束或违反船舶载运能力约束而变得不可行,解码,举例：,一条航线必须是由分配到该船的货物的装货日期，交货日期，起始点来决定的。,实践可行,引入惩罚（penaltyterm）,4.GeneticAlgorithm,选择过程,1.计算每个染色体的适应性值。,2.根据，对种群内的染色体进行排序。,3.计算每个染色体的选择概率，计算公式为：,其中，是染色体的排名数，代表种群大小。,4.计算累计概率：,5.产生一个随机数r。6.如果，则选择第一个染色体，否则选择第i的染色体，使。,交叉互换过程,两个被选中的染色体，采用单点交叉互换方法产生一个后代。在每次交叉互换中，随机选择一个切点（cut-point），交换两个亲代染色体上正确的部分来产生一个后代。交叉互换阶段一直重复，直到后代染色体的数目达到预定的种群数,交叉互换概率,突变过程,令船舶数量为SN。在本遗传算法中，突变以一定的概率，随机性地将一个基因由原始值改变成0到SN之间的一个随机数。,突变概率,适应性计算,令为在相应航段没有形成有效航行（feasibletrip）的船舶数（由于连通性或违背时间约束）令为分配至该船的货物超过船舶载运能力的船舶数令和为任意的大值数，用来代表惩罚,惩罚项,适应性函数,5实证分析,5.Empiricalstudies,为了评价遗传算法,把此方法用到台湾最大的不定期船承运人网络中。15个货物起运港和目的港分散在东北亚、东南亚以及南亚区域，且任意两个港口的航行时间在1天到15天之间不等。,在计划范围内，承运人有7艘船，32票货，船型是拥有长期租约的大灵便型散货船，每条船有自己的属性，包括航行速度，吃水和航行费用（包括租金、燃油费、靠泊费和杂费），船舶在任意两个港口间的航行时间由其航行速度决定。这次计划测试是从2004年4月24日到2004年6月12日，包括两段时间（5月1日到5月21日，5月22日到6月12日），装货准别过程从4月底开始。这些货物要在15个起运港和目的港间运送，且其中编号1-12的主要货物和编号13-28的现货在规划在第一时间段，编号29-32的4票主要货物要规划在第二时间阶段。,5.Empiricalstudies,5.1遗传算法的参数标定,为了校准在最后实例分析中主要的遗传算法参数（包括交叉率、突变率、种群规模和世代数目），我们用不同的参数组合进行测试，以此来鉴定能产生最好解决方案质量和收敛行为的一组参数。7艘船32票货的实例（命名为732案例）来校准参数。值得注意的是在后面章节随机产生的案例都以案例732作为基准，且与其拥有相同数量的船舶，这些案例的不同只体现在货物数量和是否加了时间窗限制。首先，我们运用下面的参数组合作为基准值：100的种群规模、3000的种群规模、100%的交叉率和10%的突变率。这四个参数组合在表格3里面总结了，校准结果在5.1.1到5.1.4部分。接着，我们改变这些参数值来测试遗传算法的性能，因为计划的遗传算法涉及随机性（比如突变或者交换操作的随机性），每个参数的设定用10次遗传算法来测试，结果产生的性能指数作为该参数设定的最后适应值,5.Empiricalstudies,5.1.1实验1：改变交叉率,将100%、80%、40%、20%的交叉率代入运行得到的最优差距结果分别为0.89%、0.24%、1.98%、1.45%，因此80%的交叉率是最合适的,5.Empiricalstudies,5.1.2实验2：改变突变率,不同突变率的性能是相似的，然而10%的突变率比其他突变率值有着稍好的结果，它展现了一个更大解的空间探索，所以，我们运用10%的突变率进行实例测试。,5.Empiricalstudies,5.1.3实验3：改变种群规模和世代数量,我们用来测试种群规模和世代数的参数组合为：（30，10000），（50，6000），（100，30000）和（200，1500），最后（200，1500）这个组合优于其他组合，因此我们决定运用200的种群规模和1500的世代数量,5.Empiricalstudies,5.1.4实验4：改变处理机的数量,用双处理机运行的速度比单处理机速度快，此外，双处理机连续的组成了单处理机。甚至在6000世代后，由双处理机和单处理机运行的结果分别是176231和174667.性能提高一个可信的理由是双处理机在解决程序的最初阶段探索了一个更大的求解空间，在相同的允许的计算时间内，对于双处理机的最优间距是0.89%，在现实应用中是可接受的，因此，在接下来的实验中，我们运用双处理机来进行运算。,5.Empiricalstudies,从上述的校准过程看出，最优的遗传算法参数最优值是：80%的交叉率，10%的突变率，200的种群规模，1500的世代数量。这些参数值将固定，用在接下来的实例中。,5.Empiricalstudies,5.2遗传算法的运行,在实例中应用了遗传算法和CPLEX后，我们总结了航线结果和相应的时间分配关系，如图所示。图中的用节点（天，港口）表示了船舶的时空位置。,5.Empiricalstudies,5.2遗传算法的运行,7号船舶是（1，4），（2，4），（4，3），（13，2），（16，5），（20，5），（22，6）和（43，6）。节点（1，4）是货物10、27和28被接收，节点（10，2）是这些货物被配送。同样的，货物11和12在分别在节点（10，2）和节点（12，2）被接收，在节点（25，6）和（18，6）被相应的配送。,5.Empiricalstudies,GA算法和CPLEX算法计算结果对比,结论一：与实际的收益（101172美元）相比，遗传算法和CPLEX算法获得更高的收益（176231美元），表明承运人通过简单调整其船舶调度计划就可以获得高出74%的收益。如果托运人进一步考虑时间窗的灵活性，收益可能会更高（达到189622美元）。,5.Empiricalstudies,在实证研究