长江水道集装箱运输航线网络优化

-.z长江水道集装箱运输航线网络优化摘要:基于长江水道各航段的适航特征和沿岸港口间OD集装箱运输需求，构建整数规划模型，以所有集装箱运输总本钱最小为目标，优化长江水道上集装箱航线网络，确定各航线靠港、靠泊顺序及所用船舶的类型与数量。优化时，首先确定适合长江航道的主要船型，其次，结合各段航道适航特征，针对可使用的各种船型，设定各航段的通行阻抗函数；然后，设计基于Frank-Wolf法的遗传算法进展求解。优化得到的集装箱航线网络呈现“大船在中间，小船在两边〞的形态，与目前遵循的“小船走上游，大船走中下游〞的船舶配置原则有所不同。1.引言长江是我国内河运输的“黄金通道〞，是中西部地区与世界实现经济交流的动脉，同时也是东西部经济互补的桥梁。长江水系集装箱运输自1976年以来经历了试验、起步和开展三个阶段，目前航线已由单一的内贸航线开展到国际航线、内支线、国内航线，集装箱箱型由5t箱变为20英尺和40英尺国际标准箱，运输方式由顶推船队为主开展到以自航船为主。2002年，长江水系集装箱吞吐量为138万TEU，主要港口集装箱吞吐量为126万TEU。集装箱运输已成为长江货物运输的新经济增长点。目前，大约有20个航运公司主要从事集装箱内河运输，比方，中远集装箱运输公司，中海集装箱运输公司、中外运集装箱运输公司、**港口航运和驳船运输公司，**浦海航运**和民生航运公司。在长江水系有100多条集装箱航线，包括长江干线港口间、长江港口至沿海港口的国内航线以及开往邻近国家和地区的近洋航线，及其长江三角洲地区的**—**、**—**、**—**、**—**、**—**的集装箱航线。由?长江干线航道开展规划?可知，上起**水富港、下至**长江口的长江航道将得到加深。水富至**河段，将由1.8m加深至2.7m，全年可通航由1000t级驳船组成的船队；城陵矶至**，加深至3.7m，可通航由3500t驳船组成的万吨级船队;**至**河段，通航由2000～50000t级驳船组成的2～4万t级船队，可通航5000t级海船；**至**，加深至6m，可通航5000～10000t级海轮;**以下航道加深至12m以上，可通航5万t级以**轮；浏河口至长江口河段可通航第五代以上超大型集装箱船。上述长江主要通道如图1所示。图1长江主要通道众所周知，长江上各港口间适航船舶的差异为沿长江设置多种集装箱航线，构建沿江的集装箱水运网络提供了条件。根据交通需求和水道的条件，运营商可以设置几个集装箱运输方案。运营者可以结合需求和航道情况，用适用性强的小型船舶实施点对点运输；或在中下游用大型船舶，在中上游用小型船舶，实施干支线别离运输。各种航线网络效率和效益随需求和航道变化而异，所以有必要针对长江航道进展集装箱运输航线网络设计。2.文献综述有关水上航线设计的研究很多，但相关研究主要集中在海运领域，早期的代表性研究均为海运船队规划问题。随着班轮业的开展，航线所涉及的港口不断增加，航线构造逐渐成为决定运营本钱的关键。因此，研究者在船队规划的同时，开场关注船舶定线问题。Ｒana等用整数规划模型同时优化船队规模和班轮路线；文献以航线收益最大为目标，用集合划分模型优化船队规划和船舶定线Agarwal等总结了班轮船舶调度、航线设计和船队规划等问题，并基于时空网络建立混合整数规划模型。另外，局部学者还研究了班轮航线优化与仓储、空箱调运、时间约束、运输需求季节性波动等的相互影响。Hsu等从承运人的角度，以最小运输本钱和库存本钱之和为目标，建立双目标模型优化班轮航线、船队规模、发班频率。Shintani等建立双层模型，同时处理航线优化和空箱调度问题。Matthew等在有时间约束的条件下，设计集装箱轴辐式航线网络。Meng等研究了单一集装箱班轮公司在运输需求不确定时的短期班轮船队规划问题。只有少数学者针对各自国家的内河集装箱运输进展研究，且多是关于船型选择、船型标准化、内河运输与海港衔接等的研究。*建峰等针对早期长江水道的航行条件，从经济性上研究上游港口实施江海直达运输时，近洋航线(到日本神户、横滨等港口)的最正确船型。在不考虑航线网络和OD运输量的情况下，通过装载率不同所导致的单箱运输本钱变化来确定合理的船型。贾瑞华等研究在长江上游运输集装箱时，水运方式与陆运方式的优劣，基于AHP法构建评价体系，在宏观层面上分析运输经济性。该研究不涉及航道和航线等微观层面细节，只研究陆路通道和水路通道的经济性。罗洪波等详细分析长江通航情况，为**至洋山港间运输设置了五种方案：直达、芦潮中转、**中转、**中转、外高桥中转，并用评价标准进展测试。该研究的缺点是没有考虑货流量和沿线其他港口的货物。与之类似，钟华杰等研究了**、**、**、**、*家港等地至洋山的集装箱运输方案，预先设定了18种可能的航线方案，然后确定各港口到洋山港的最正确运输方案。这些研究的特点是不考虑港口间集装箱流量，假设每种船型对应一个单箱运输本钱，然后确定运输方案。上述研究的共同特点是，他们都没有考虑集装箱港口之间的OD货流，并认为一种类型的船都有一个特定单位集装箱运输本钱，然后评估其他港口到洋山港班轮方案。Taylor等研究了美国俄亥俄河的驳船与动力船的指派问题，作者给出了一个基于仿真的调度系统，用以辅助决策驳船指派和动力船分配问题。Jonkeren等研究了气候所导致的莱茵河水位变化对航运本钱的影响，以及最终引起的水运份额的变化。他们利用NODUS软件分析货物在一个*围广泛的综合运输网络中的路径选择问题，关注低水位对水运分担率的影响，用宏观网络规划软件研究OD货流在虚拟化的综合运输网络上的路径选择问题，而非设计内河航运的运输网络。总之，内河集装箱运输的相关研究很少涉及航线网络优化与航线配船，仅有的一些研究不适用于各航段通航条件不同、水文状况复杂的内陆河道运输系统。因此，本文针对长江水道提出考虑航道水深限制和货主运输路径选择行为的集装箱运输航线网络优化与船队配置模型()，以航线运营总本钱最小为目标，确定各航线的靠泊港口、靠泊顺序、船型与船舶数量。为求解模型，基于Frank-Wolf原理设计遗传算法(GA)。本文的组织构造如下：第三节介绍了问题描述和提出了一些建立模型时应该处理的关键问题。第四局部描述了路网规划和航线配船模型(NFDM)。第五节设计了相应算法。第六节举例说明了计算结果。最后,第七节为研究总结。3.问题描述3.1航线方案的表述方法为了设置航线配船模型，用数学方法来描述班轮航线方案和由路线方案组成的运输路网应该被创立，该方法应该从各方面来考虑内河上所有班轮航线的构造特点。在海洋运输中，班轮航线可拆分为去程子航线和回程子航线，因此确定海上班轮航线就是确定去程子航线和回程子航线的靠泊港口和靠泊顺序。但是，长江航道构造单一，没有可替代路径，各港口沿水道顺序排列，去程子航线由上游至下游顺序靠泊，回程子航线由下游至上游顺序靠泊。因此优化长江上的班轮航线时，只确定各子航线的靠泊港即可。假设图2显示了长江沿岸港口的位置，从上游到下游，第一个港口是港口1和最后一个港口是港口N。设*航线的去程子航线为：港2—港3—港l—港N，回程航线为：港N—港N－1—港l—港2，由此可确定一个如图3所示的航线。图2港口分布示意图图3航线组成由图3可知，假设*港为挂靠港，则其在航线中的角色可能是：〔1〕去程子航线的起始港〔如港2〕；或〔2〕去程子航线的中途靠泊港〔如港3〕；或〔3〕回程子航线的中途靠泊港〔如港N－1〕；或〔4〕去程和回程子航线均挂靠的中途港〔如港l〕；或〔5〕回程子航线的起始港〔如港N〕。因此，可以用0－1变量*itk来表述港口在航线中的角色，其中i为港口编号，t∈［1，5］为港口角色编号，k∈［1，K］为航线编号，K为预先设定的航线数量。假设航线k挂靠i港，而i港在航线k中的角色为t，则*itk=1，否则为0。另外，用*i0k表示港口i是否被航线k挂靠，假设是则*i0k=1，否则为0。变量*itk与*i0k之间的关系为：〔1〕式〔1〕用于确保假设港口i是挂靠港时，港口i在航线中只扮演一种角色；而假设港口i不是挂靠港时，*itk的取值则为0。〔2〕〔3〕式〔2〕、〔3〕说明在一个航线中去程子航线和回程子航线都有且只有一个起始港。〔4〕〔5〕式〔4〕说明，航线中角色1的港口的上游不可能有角色5的港口。同样，式〔5〕说明角色5的港口的下游不可能有角色1的港口。〔6〕〔7〕式〔6〕说明，航线中角色1的港口的上游不可能有挂靠港。而式〔7〕说明角色5的港口的下游不可能有挂靠港。给定一组满足约束条件的*i1k与*i0k便可确定一个航线方案。例如，假设*20k=*30k=*i'0k=*〔N-1〕0k=*N0k=1，而其他*i0k=0，则航线k的靠泊港口为2、3、l、N－1、N；同时，假设*21k=*32k=*l4k=*〔N-1〕2k=*N5k=1，而其他*itk=0，则港口1与港口N分别为去程子航线与回程子航线的起始港，港口2为去程子航线的中途靠泊港，港口l为去程与回程子航线均挂靠的中途港，而港口N－1仅是回程子航线的挂靠港。这里设*=(*itk，t∈［0，5］，i∈M，k∈［1，K］)，zijk表示航线k中是否有港口i至港口j的航段。zijk与*的关系可表示如下：〔8〕〔9〕〔10〕式〔8〕表示航线k的去程子航线的航段，式〔9〕表示回程子航线的航段。如果用A〔*〕={(i，j)k|zijk=1，i，j∈［1，K］}，其中(i，j)k为网络中航线k的港口i至港口j的有向航段。例如，在图3所示的由两条航线构成的网络中，(1，3)1表示航线k=1由港口1至港口3的有向航段，(2，3)2表示航线k=2由港口2至港口3的有向航段。至此，得到表示靠泊港口选择、靠泊顺序等航线构造的数学表述方法。图4航线网络的描述方法3.2.集装箱货流分配根据上述描述方法，所有的航线都可以用数学构造来表达。然而，要评价航线的优劣，需要估算集装箱在航线网络上的分布情况。在水路运输网络中，托运人通常会选择综合运输本钱(运输时间与费用的加权和)最低的运输路径运输货物，其行为符合UE原理，因此可以用UE分配模型计算各水路路段的集装箱流量。此时，求解UE模型的关键是设定路段的阻抗函数。借鉴Meng等的研究给出如下阻抗函数：〔11〕其中:c0(i，j)k、t0(i，j)k、s(i，j)k分别为路段(i，j)k的运价、自由流时间与流量;h1k、feqk分别为k航线上船舶的运力与班期密度；FEQ={feqk|k∈［1，K］}；为时间价值；α1、α2、α3为待定参数。基于上述阻抗函数，来计算用户平衡状态下，各路段的集装箱流量，可以用变分不等式：forany〔12〕其中，Ω〔*〕为路段上集装箱流量的集合。4.优化模型4.1.假设条件除前面假设外再增加假设：〔1〕一个班轮航线仅用一种船型；〔2〕船舶在各港口的在港时间一样；〔3〕必要时集装箱可在不同班轮航线之间转运；〔4〕同一航线的平均航速一样；〔5〕决策周期为7天。4.2.模型构造基于上述分析和假设，构建整数规划模型，其解析表达式如下：〔13〕式〔13〕为最小化水运网络的总运输本钱。其中：cgk为航线k的运营本钱;cfk为航线k的燃油本钱。约束条件除包括式〔1〕～〔12〕外，还包括：〔14〕式〔14〕用于计算航线k的全程航行时间。其中：Disij为港i至港j的航行距离；vk为航线k的平均航速；tp为船舶在港停泊时间。〔15〕〔16〕〔17〕式〔15〕用于计算航线k所需的船舶数量h2k，其中，feqk为航线k的班期密度。式〔16〕用于计算cgk，其中，h3k为航线k上船舶日租金。式〔16〕用于计算cfk，其中，h4k为航线k上船舶的日燃油消耗。〔18〕式〔18〕为航道水深约束，其中，SLij为港口i至港口j航段水深。〔19〕〔20〕〔21〕〔22〕式〔19〕、〔20〕给出路段集装箱量与港口间OD量间的关系。其中:O为起运港集合；D为目的港集合；qrs为由港r∈O至s∈N的OD量；非负实数frsp表示水路网络中连接OD对r－s的路径p上的流量；σrs(i，j)k，p为0－1变量，当OD对r－s间的路径p经过路段(i，j)k时取1，否则为0。式〔20〕确保所有货运需求均获得充足的运力。式〔22〕用于保证各航线班期密度至少为每周1班。5.模型的解决方案5.1.算法设计上述模型是一个带有平衡约束的整数规划问题，加之要考虑航线构造、港口选择以及航道水深限制等，因此难以准确求解。为此设计一种嵌入Frank-Wolf法的遗传算法(FWGA)。运行步骤如下:步骤1(初始化)令n=0，生成初始种群Pn={(*，FEQ)v|v=1，…，λ}；其中，(*，FEQ)v表示遗传算法的一个个体，包含两局部：航线构造信息*与航线班期频率FEQ；λ为种群规模；步骤2(计算个体的适应度值)步骤2.1根据的(*，FEQ)v构建水运网络Gv;步骤2.2采用Frank-Wolf法计算网络Gv的用户平衡状态，获得各路段的集装箱流量：sv=(s(i，j)k，(i，j)k∈A(*))；步骤2.3计算个体v的适应度值：其中:fitv为个体v的适应度值；M为一个足够大的正数；ma*〔.〕为取大函数。步骤3(判断算法是否收敛)检查当前种群的适应度最大值与平均值的差是否小于预设的μ，是则执行步骤4，否则终止算法；步骤4(执行选择、穿插和变异操作)令n=n+1，实施穿插、变异和选择操作，获得新个体Pn，然后回到步骤1。5.2编码方法编码由假设干子编码构成，子编码个数取决于预先设定的航线数K。图5为一个K=2时的随机编码，由子编码k=1和子编码k=2组成。其中，每个子编码均由5局部构成。如图6所示。Part1表示靠泊港口，同时确定去/回程子航线的起始港。例如，01111表示去程子航线的起始港为港2，回程子航线的起始港为港5，该航线还挂靠港口3与港口4。基于Part1确定靠泊港口与起始港后，便可根据Part2—Part4来确定各挂靠港在航线中的角色。具体地:假设港口i被选为靠泊港，且不是起始港，则Part2的第i号基因的作用便是判断该港是否是仅隶属于去程子航线的港口，假设是则Part2的第i号基因位的值为1，否者为0。例如，在图6中靠泊港3既不是去程子航线的起始港也不是回程子航线的起始港，且Part2的第3基因位的值为1，由此可知港口3仅隶属于去程子航线。Part3与Part4分别用于确定仅隶属于单程子航线和同时隶属于两个子航程的港口，其判定方法与Part2一样。图5编码方法图6子编码构成Part5用于确定航线方案k的班期频率，是二进制编码，位数等于预先设定的备选班期频率．假设备选班期频率为每周1、2、3、4班，Part5便是一个2位的二进制数，Part5=(00)对应每周1班；Part5=(01)对应每周2班;Part5=(11)对应每周3班;Part5=(10)对应每周4班。这种编码方法可方便地表示任何一个航线方案与班期频率的组合(*，FEQ)v．例如，根据子编码k=1可得到图7a所示的航线a，根据子编码k=2可得到图7b所示的航线b，两者组合可表述图7c所示的航线网络c。图7子航线的组合图8长江流域港口位置6.数值分析6．1数据收集选择长江沿线港口中集装箱OD量较大的10个港口，从上游至下游依次为:**(LZ)、**(CQ)、荆州(JZ)、城陵矶(CLJ)、**(WH)、**(JJ)、**(NJ)、*家港(ZKG)、**(NT)、**(SH)．图8显示了长江流域港口间的位置。表1为港口间OD集装箱流量，各港间运价取自实际公布的运价表。各港口间在枯水期和丰水期可通行的最大船舶吨位如表2所示。考虑到长江上、中、下游航段差异，这里选取最具代表性的三种船型:1000MT、3000MT和5000MT。表3为三种船舶的燃油消耗量、运行速度、满载吃水、日租金和燃油本钱。参考长江集装箱班轮航线的现状特征，假定优化的航线网络由三条航线构成，其中每条航线上只使用一种船型。另外假设班轮频率为每周1班～每周8班。6.2计算方法设初始种群由100个个体构成，个体编码包括3个子编码，其中子编码的Part1～Part4拥有10个基因位(备选港口有10个)，Part5拥有3个基因位(航班频率有8种可能)。最大迭代次数为200，穿插率设定为0.92，变异率为0.01。算法终止条件为最大适应度与平均适应度间的差≤0.002。表1集装箱港口之间的OD流(TEU/周)表2港口集装箱吞吐量的运输价格(20TUE/人民币)表3船舶相关数据表4枯水期港口之间航道的通航船舶(ton)表5丰水期港口之间航道的通航船舶(ton)图9枯水期收敛情况采用C++语言编写求解程序，并在DuoCore2．53计算机上运行，分别就枯水期和丰水期，针对不同船型进展计算。数据在表3-5用于不同的船舶类型。图9和图10为计算收敛情况。6.3结果分析表6和表7分别为枯水期与丰水期的航线网络。图11、12分别为枯水期、丰水期航线覆盖区域。枯水期航线网络的最低运营本钱为5658346元/周，丰水期最低运营本钱为3833551元/周。实际上，目前班轮公司一直遵循着“小船走上游，大船走中下游〞的原则。但是，实验结果说明，不管是枯水期还是丰水期，航线网络均呈现“大船在中间，小船在两边〞的形态。这是因为下游水道的航程长，如果在中下游同时用大型船舶，为保班期(每周至少1班)就必须增加大型船舶的数量，结果导致运营本钱增加和运力浪费。图10汛期收敛情况表6旱期班轮航线网络构造表7汛期班轮航线网络构造因此，合理的方案是在下游航段使用中型船舶，而非大型船舶。这样做既能满足运输的要求，又能提高船舶利用率，降低航线的运营本钱。因此,在这种情况下，当与陆路运输相比航道可能比较强。因为水运输本钱减少，同时由于在一样的码头边船只之间转船运输时间可能很难改变。此外，计算结果进一步说明,该运作模式为“大船在中间，小船在两边〞，并非严格按照上游、中游和下游的边界。如图11和图12所示，由于在枯水期5000MT型船只在中游航行的路线会变短。而且，1000MT型船舶的运营区域相应减小。结果说明，在枯水期，使用14艘小型船只，而在丰水期只使用8艘小型船只。因此，在枯水期的运输本钱更大。图11在枯水期的运输路线图12在丰水期的运输路线7.结论本文探讨了长江水道集装箱班轮航线网络设计与船队配置问题，开发了基于UE原理的优化模型，并设计启发算法。与传统的在通航能力大的流域使用大型船的做法不同，本文计算结果显示，应该在长江中游使用大型船，在下游使用中型船，在上游使用小型船。通过这样做，可以满足集装箱运输的需求以及操作总本钱最小化。在沿河的港口之间基于完整的OD矩阵得到上述结果。它说明,当一个操作员根据方案做运输业务，运输本钱可以大大降低。同时，操作员可以优化船舶的航行时间，减少转运时间。随着所节约本钱的增大和时间增量的减少，航道的竞争力变得更强壮从陆运模式去吸引更多的集装箱。结果，长江沿岸地区的交通可能变得更加环保。参考文献[1]Agarwal,R.,andÖ.Ergun.2021.“ShipSchedulingandNetworkDesignforCargoRoutinginLinerShipping.〞TransportationScience42(2):175–196.[2]Cho,S.-C.,andA.N.Perakis.1996.“OptimalLinerFleetRouteingStrategies.〞MaritimePolicyandManagement23(3):249–259.[3]Claessens,E.M.1987.“OptimizationProceduresinMaritimeFleetManagement.〞MaritimePolicyandManagement14(1):27–48.[5]Fagerholt,K.1999.“OptimalFleetDesigninaShipRoutingProblem.〞InternationalTransactionsinOperationalResearch6(5):453–464.[6]Hsu,C.,andY.Hsieh.2007.“Routing,ShipSize,andSailingFrequencyDecision-MakingforaMaritimeHub-and-SpokeContainerNetwork.〞MathematicalandputerModelling45(7):899–916.[7]Jaramillo,D.I.,andA.N.Perakis.1991.“FleetDeploymentOptimizationforLinerShippingPart2.ImplementationandResults.〞MaritimePolicyandManagement18(4):235–262.[8]Jia,R.H.,Y.Zhang,andB.Yang.2006.“ProjectOptimizationofContainerTransportfortheUpperReachoftheYangtzeRiver.〞JournalofWaterwayandHarbor27(2):127–130.[9]Jonkeren,O.,B.Jourquin,andP.Rietveld.2021.“Modal-SplitEffectsofClimateChange:TheEffectofLowWaterLevelsonthepetitivePositionofInlandWaterwayTransportintheRiverRhineArea.〞TransportationResearchPartA:PolicyandPractice45(10):1007–1019.[10]Karlaftis,M.G.,K.Kepaptsoglou,andE.Sambracos.2021.“ContainershipRoutingwithTimeDeadlinesandSimultaneousDeliveriesandPick-Ups.〞TransportationResearchPartE:LogisticsandTransportationReview45(1):210–221.[11]Lane,D.E.,T.D.Heaver,andD.Uyeno.1987.“PlanningandSchedulingforEfficiencyinLinerShipping.〞MaritimePolicyandManagement14(2):109–125.[12]Liu,J.,andS.Qin.1994.“AnalysisofContainerShipTypesandTransportationfromtheYangtzeRivertoAbroad.〞JournalofEastChinaShipbuildingInstitute8(4):21–29.[13]Luo,H.B.,andJ.Y.Sun.2006.“StudyonContainerTransportationModesfromChongqingtoShanghai.〞ResearchonWaterborneTransportation2:18–22.[14]Meng,Q.,andS.Wang.2021a.“LinerShippingServiceNetworkDesignwithEmptyContainerRepositioning.〞TransportationResearchPartE:LogisticsandTransportationReview47(5):695–708.[15]Meng,Q.,and*.Wang.2021b.“IntermodalHub-and-SpokeNetworkDesign:IncorporatingMultipleStakeholdersandMulti-TypeContainers.〞TransportationResearchPartB:

Methodological45(4):724–742.[16]Perakis,A.N.,andD.I.Jaramillo.1991.“FleetDeploymentOptimizationforLinerShippingPart1.Background,ProblemFormulationandSolutionApproaches.〞MaritimePolicyandManagement18(3):183–200.[17]Powell,B.J.,andA.N.Perkins.1997.“FleetDeploymentOptimizationforLinerShipping:AnIntegerProgrammingModel.〞MaritimePolicyandManagement24(2):183–192.[18]Rana,K.,andR.G.Vickson.1988.“AModelandSolutionAlgorithmforOptimalRoutingofaTime-CharteredContainership.〞TransportationScience22(2):83–95.[19]Rana,K.,andR.G.Vickson.1991.“R