1、长江水道集装箱运输航线网络优化摘要: 基于长江水道各航段的适航特征和沿岸港口间 OD 集装箱运输需求，构建整数规划模型，以所有集装箱运输总成本最小为目标，优化长江水道上集装箱航线网络，确定各航线靠港、靠泊顺序及所用船舶的类型与数量。优化时，首先确定适合长江航道的主要船型，其次，结合各段航道适航特征，针对可使用的各种船型，设定各航段的通行阻抗函数； 然后，设计基于 Frank-Wolf 法的遗传算法进行求解。优化得到的集装箱航线网络呈现“大船在中间，小船在两边”的形态，与目前遵循的“ 小船走上游，大船走中下游 ”的船舶配置原则有所不同。1.引言长江是我国内河运输的“黄金通道”，是中西部地区与世界
2、实现经济交流的动脉，同时也是东西部经济互补的桥梁。长江水系集装箱运输自 1976 年以来经历了试验、起步和发展三个阶段，目前航线已由单一的内贸航线发展到国际航线、内支线、国内航线，集装箱箱型由 5t 箱变为 20 英尺和 40 英尺国际标准箱，运输方式由顶推船队为主发展到以自航船为主。2002 年，长江水系集装箱吞吐量为 138 万 TEU，主要港口集装箱吞吐量为 126 万 TEU。集装箱运输已成为长江货物运输的新经济增长点。目前，大约有 20 个航运公司主要从事集装箱内河运输，比如，中远集装箱运输公司，中海集装箱运输公司、中外运集装箱运输公司、上海港口航运和驳船运输公司，上海浦海航运有限公
3、司和民生航运公司。在长江水系有 100 多条集装箱航线，包括长江干线港口间、长江港口至沿海港口的国内航线以及开往邻近国家和地区的近洋航线，及其长江三角洲地区的无锡上海、常州上海、杭州上海、嘉兴上海、湖州上海的集装箱航线。由长江干线航道发展规划可知，上起云南水富港、下至上海长江口的长江航道将得到加深。水富至宜宾河段，将由 1.8m 加深至 2.7m，全年可通航由 1000t 级驳船组成的船队；城陵矶至武汉，加深至 3.7m，可通航由 3500t 驳船组成的万吨级船队; 武汉至铜陵河段，通航由 200050000t 级驳船组成的 24万 t 级船队，可通航 5000t 级海船；铜陵至南京，加深至
4、6m，可通航500010000t 级海轮; 南京以下航道加深至 12m 以上，可通航 5 万 t 级以上海轮；浏河口至长江口河段可通航第五代以上超大型集装箱船。上述长江主要通道如图 1 所示。图 1 长江主要通道众所周知，长江上各港口间适航船舶的差异为沿长江设置多种集装箱航线，构建沿江的集装箱水运网络提供了条件。根据交通需求和水道的条件，运营商可以设置几个集装箱运输方案。运营者可以结合需求和航道情况，用适用性强的小型船舶实施点对点运输；或在中下游用大型船舶，在中上游用小型船舶，实施干支线分离运输。各种航线网络效率和效益随需求和航道变化而异，所以有必要针对长江航道进行集装箱运输航线网络设计。2.
5、文献综述有关水上航线设计的研究很多，但相关研究主要集中在海运领域，早期的代表性研究均为海运船队规划问题。随着班轮业的发展，航线所涉及的港口不断增加，航线结构逐渐成为决定运营成本的关键。因此，研究者在船队规划的同时，开始关注船舶定线问题。ana 等用整数规划模型同时优化船队规模和班轮路线；文献以航线收益最大为目标，用集合划分模型优化船队规划和船舶定线 Agarwal 等总结了班轮船舶调度、航线设计和船队规划等问题，并基于时空网络建立混合整数规划模型。另外，部分学者还研究了班轮航线优化与仓储、空箱调运、时间约束、运输需求季节性波动等的相互影响。Hsu 等从承运人的角度，以最小运输成本和库存成本之和
6、为目标，建立双目标模型优化班轮航线、船队规模、发班频率。Shintani 等建立双层模型，同时处理航线优化和空箱调度问题。 Matthew 等在有时间约束的条件下，设计集装箱轴辐式航线网络。Meng 等研究了单一集装箱班轮公司在运输需求不确定时的短期班轮船队规划问题。只有少数学者针对各自国家的内河集装箱运输进行研究，且多是关于船型选择、船型标准化、内河运输与海港衔接等的研究。刘建峰等针对早期长江水道的航行条件，从经济性上研究上游港口实施江海直达运输时，近洋航线(到日本神户、横滨等港口)的最佳船型。在不考虑航线网络和 OD 运输量的情况下，通过装载率不同所导致的单箱运输成本变化来确定合理的船型。
7、 贾瑞华等研究在长江上游运输集装箱时，水运方式与陆运方式的优劣，基于 AHP 法构建评价体系，在宏观层面上分析运输经济性。该研究不涉及航道和航线等微观层面细节，只研究陆路通道和水路通道的经济性。 罗洪波等详细分析长江通航情况，为重庆至洋山港间运输设置了五种方案：直达、芦潮中转、武汉中转、南京中转、外高桥中转，并用评价标准进行测试。该研究的缺点是没有考虑货流量和沿线其他港口的货物。 与之类似，钟华杰等研究了重庆、武汉、长沙、南京、张家港等地至洋山的集装箱运输方案，预先设定了 18 种可能的航线方案，然后确定各港口到洋山港的最佳运输方案。这些研究的特点是不考虑港口间集装箱流量，假设每种船型对应一个
8、单箱运输成本，然后确定运输方案。上述研究的共同特点是，他们都没有考虑集装箱港口之间的 OD 货流，并认为一种类型的船都有一个特定单位集装箱运输成本，然后评估其他港口到洋山港班轮方案。Taylor 等研究了美国俄亥俄河的驳船与动力船的指派问题，作者给出了一个基于仿真的调度系统，用以辅助决策驳船指派和动力船分配问题。Jonkeren 等研究了气候所导致的莱茵河水位变化对航运成本的影响，以及最终引起的水运份额的变化。他们利用 NODUS 软件分析货物在一个范围广泛的综合运输网络中的路径选择问题，关注低水位对水运分担率的影响，用宏观网络规划软件研究OD 货流在虚拟化的综合运输网络上的路径选择问题，而非
9、设计内河航运的运输网络。总之，内河集装箱运输的相关研究很少涉及航线网络优化与航线配船，仅有的一些研究不适用于各航段通航条件不同、水文状况复杂的内陆河道运输系统。因此，本文针对长江水道提出考虑航道水深限制和货主运输路径选择行为的集装箱运输航线网络优化与船队配置模型(COM)，以航线运营总成本最小为目标，确定各航线的靠泊港口、靠泊顺序、船型与船舶数量。为求解模型，基于 Frank-Wolf 原理设计遗传算法( GA)。本文的组织结构如下：第三节介绍了问题描述和提出了一些建立模型时应该处理的关键问题。第四部分描述了路网规划和航线配船模型(NFDM)。第五节设计了相应算法。第六节举例说明了计算结果。最
10、后, 第七节为研究总结。3.问题描述3.1 航线方案的表述方法为了设置航线配船模型，用数学方法来描述班轮航线计划和由路线方案组成的运输路网应该被创建，该方法应该从各方面来考虑内河上所有班轮航线的结构特点。在海洋运输中，班轮航线可拆分为去程子航线和回程子航线，因此确定海上班轮航线就是确定去程子航线和回程子航线的靠泊港口和靠泊顺序。但是，长江航道结构单一，没有可替代路径，各港口沿水道顺序排列，去程子航线由上游至下游顺序靠泊，回程子航线由下游至上游顺序靠泊。因此优化长江上的班轮航线时，只确定各子航线的靠泊港即可。假设图 2 显示了长江沿岸港口的位置，从上游到下游，第一个港口是港口 1 和最后一个港口
11、是港口 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 变量 xitk 来表述港口在航线中的角色，其中 i 为港口编号，t1，5为港口角色编号，k1，K为航线编号，K 为预
12、先设定的航线数量。若航线k 挂靠 i 港，而 i 港在航线 k 中的角色为 t，则 xitk= 1，否则为 0。另外，用 xi0k表示港口 i 是否被航线 k 挂靠，若是则 xi0k= 1，否则为 0。变量 xitk 与 xi0k 之间的关系为：（1）tikiokx式（1）用于确保若港口 i 是挂靠港时，港口 i 在航线中只扮演一种角色； 而若港口 i 不是挂靠港时，x itk 的取值则为 0。（2）ik1（3）ikx5式（2） 、（3） 表明在一个航线中去程子航线和回程子航线都有且只有一个起始港。（4）Mnxnikk 2,0)(151（5）1,15 Mnikikn式（4） 表明，航线中角色
13、1 的港口的上游不可能有角色 5 的港口。同样，式（5） 表明角色 5 的港口的下游不可能有角色 1 的港口。（6）nxniokk2,01（7）1,105 MMnikikn式（6）表明，航线中角色 1 的港口的上游不可能有挂靠港。而式（7）表明角色 5 的港口的下游不可能有挂靠港。给定一组满足约束条件的 xi1k 与 xi0k 便可确定一个航线方案。例如，若 x20k= x30k=xi0k= x（N-1）0k = xN0k= 1，而其他 xi0k= 0，则航线 k 的靠泊港口为 2、3、l、N 1、N；同时，若 x21k= x32k= xl4k= x（N-1）2k = xN5k= 1，而其他
14、xitk= 0，则港口 1 与港口 N 分别为去程子航线与回程子航线的起始港，港口 2 为去程子航线的中途靠泊港，港口 l 为去程与回程子航线均挂靠的中途港，而港口 N 1 仅是回程子航线的挂靠港。这里设 X =( xitk，t 0，5，i M，k 1，K)，z ijk 表示航线 k 中是否有港口 i 至港口 j 的航段。z ijk 与 X 的关系可表示如下：（8）jixxtkjjtkiiijk ,33（9）jiztkjjtkiiijk ,22（10）jizijk,0式（8）表示航线 k 的去程子航线的航段，式（9）表示回程子航线的航段。如果用 A（X）= ( i，j) k| zijk= 1，
15、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. 集装箱货流分配根据上述描述方法，所有的航线都可以用数学结构来表达。然而，要评价航线的优劣，需要估算集装箱在航线网络上的分布情况。在水路运输网络中，托运人通常会选择综合运输成本(运输时间与费用的加权和)最低的运输
16、路径运输货物，其行为符合 UE 原理，因此可以用 UE 分配模型计算各水路路段的集装箱流量。此时，求解 UE 模型的关键是设定路段的阻抗函数。借鉴 Meng 等的研究给出如下阻抗函数： )(,(),(1),(),(),(), 23100 XAjihfeqjiSjitjicjisjig kkkkkk （11）其中: c0( i ，j) k、t0( i，j) k、s( i，j) k 分别为路段 (i，j) k 的运价、自由流时间与流量; h 1k、feq k 分别为 k 航线上船舶的运力与班期密度；FEQ = feqk| k 1，K ； 为时间价值； 1、 2、 3 为待定参数。基于上述阻抗函数，
17、来计算用户平衡状态下，各路段的集装箱流量 ，可以）（ )(,()XAjisSk用变分不等式：for any 0),(),()(, kkk jiSjiXAjijiSjig）（ )(,(), KjisSXk）（12） 其中，（X）为路段上集装箱流量的集合。4.优化模型4.1.假设条件除前面假设外再增加假设：（1）一个班轮航线仅用一种船型；（2）船舶在各港口的在港时间相同；（3）必要时集装箱可在不同班轮航线之间转运；（4）同一航线的平均航速相同；（5）决策周期为 7 天。4.2.模型结构基于上述分析和假设，构建整数规划模型，其解析表达式如下：（13）kjkgcw)(min式（13）为最小化水运网络的
18、总运输成本。其中：c gk 为航线 k 的运营成本; c fk为航线 k 的燃油成本。约束条件除包括式（1）（12）外，还包括：（14）pitkiiijiji txvDsztg424式（14）用于计算航线 k 的全程航行时间。其中：D isij 为港 i 至港 j 的航行距离；v k 为航线 k 的平均航速；t p 为船舶在港停泊时间。（15）gkktfeqh72（16）23kgkc（17）724kfkhc式（15）用于计算航线 k 所需的船舶数量 h2k，其中，feq k 为航线 k 的班期密度。式（16）用于计算 cgk，其中， h3k 为航线 k 上船舶日租金。式（16）用于计算 cfk
19、，其中， h4k 为航线 k 上船舶的日燃油消耗。（18）jkijSLiz1式（18）为航道水深约束，其中，SL ij 为港口 i 至港口 j 航段水深。（19）Dsorfqpsrs ,（20）)(,(),(),( , XAjijifji kpkrsrspk （21）kkhfeqjiS1),(（22）kf式（19）、（20）给出路段集装箱量与港口间 OD 量间的关系。其中: O 为起运港集合；D 为目的港集合；q rs 为由港 rO 至 sN 的 OD 量；非负实数 frsp表示水路网络中连接 OD 对 r s 的路径 p 上的流量；rs( i，j)k ，p 为 0 1 变量，当 OD 对 r
20、 s 间的路径 p 经过路段( i，j) k 时取 1，否则为 0。式（20）确保所有货运需求均获得充足的运力。式（22） 用于保证各航线班期密度至少为每周 1 班。5.模型的解决方案5.1.算法设计上述模型是一个带有平衡约束的整数规划问题，加之要考虑航线结构、港口选择以及航道水深限制等，因此难以精确求解。为此设计一种嵌入 Frank-Wolf 法的遗传算法( FWGA) 。运行步骤如下:步骤 1 (初始化)令 n = 0，生成初始种群 Pn= ( X，FEQ)v|v = 1， ， ；其中，( X ，FEQ)v表示遗传算法的一个个体，包含两部分：航线结构信息 X 与航线班期频率 FEQ； 为种
21、群规模；步骤 2 (计算个体的适应度值)步骤 2.1 根据已知的(X，FEQ)v 构建水运网络 Gv;步骤 2.2 采用 Frank-Wolf 法计算网络 Gv 的用户平衡状态，获得各路段的集装箱流量：sv=( s( i，j)k，( i，j)k A( X) ) ；步骤 2.3 计算个体 v 的适应度值：1,1,0max,10. kXAji hfeqjiSMkcfit kkfgv其中: f itv 为个体 v 的适应度值；M 为一个足够大的正数；max（.）为取大函数。步骤 3(判断算法是否收敛)检查当前种群的适应度最大值与平均值的差是否小于预设的 ，是则执行步骤 4，否则终止算法；步骤 4(
22、执行选择、交叉和变异操作)令 n = n + 1，实施交叉、变异和选择操作，获得新个体 Pn，然后回到步骤 1。5.2 编码方法编码由若干子编码构成，子编码个数取决于预先设定的航线数 K。图 5 为一个K = 2 时的随机编码，由子编码 k = 1 和子编码 k = 2 组成。其中，每个子编码均由 5 部分构成。如图 6 所示。Part 1 表示靠泊港口，同时确定去 / 回程子航线的起始港。例如，0 1 1 1 1 表示去程子航线的起始港为港 2，回程子航线的起始港为港 5，该航线还挂靠港口 3 与港口 4。基于 Part 1 确定靠泊港口与起始港后，便可根据 Part 2 Part 4 来确
23、定各挂靠港在航线中的角色。具体地: 若港口 i 被选为靠泊港，且不是起始港，则 Part 2 的第 i 号基因的作用便是判断该港是否是仅隶属于去程子航线的港口，若是则 Part 2 的第 i 号基因位的值为 1，否者为 0。例如，在图 6 中靠泊港 3 既不是去程子航线的起始港也不是回程子航线的起始港，且 Part2 的第 3 基因位的值为 1，由此可知港口 3 仅隶属于去程子航线。Part 3 与 Part 4 分别用于确定仅隶属于单程子航线和同时隶属于两个子航程的港口，其判定方法与 Part2 相同。图 5 编码方法图 6 子编码构成Part5 用于确定航线方案 k 的班期频率，是二进制编码，位数等于预先设定的备选班期频率 若备选班期频率为每周 1、2、3、4 班，Part 5 便是一个 2 位的二进制数，Part 5 =(0 0) 对应每周 1 班；Part5 = (0 1) 对应每周 2 班; Part 5 = (1 1) 对应每周 3 班; Part 5 = (1 0) 对应每周 4 班。这种编码方法可方便地表示任何一个航线方案与班期频率的组合( X，FEQ)v 例如，根据子编码 k = 1 可得到图 7a 所示的航线 a，根据子编码 k = 2 可得到图 7b 所示的航线 b，两者组合可表述图 7c 所示的航线网络 c。
