面向远海岛礁群的双向物流网络规划

王 诺， 丁 凯， 吴 迪， 吴 暖

(大连海事大学 交通运输工程学院，辽宁 大连 116026)

0 引言

远海岛礁地处海洋深处，岛礁上人类所需的生活物资基本上需要通过大陆进行补给；同时，在各岛礁建设和生产的发展过程中，又会有大量的物资需运回大陆，各岛礁之间水路相连，水上航线纵横交错，将形成复杂的双向物流网络系统。随着我国远海岛礁人工填海建设的陆续完成，为确保岛礁上人类生活及生产物资运输的畅通，亟需规划建立一种集中转岛礁选址、运输航线、库存控制等各项因素的多级双向物流运输网络系统。

有关往返双向物流运输系统的规划，胡天军等[1]研究了逆向物流车辆路径规划问题，采用蚁群算法进行求解带有回程取货的逆向物流车辆路径模型；Fattahi等[2]利用两阶段随机规划方法，通过混合整数线性规划模型求解带有逆向网络物流规划问题；Guo等[3]针对生鲜食品实现低碳运输的目标，采用启发式算法验证了逆向物流网络与路径规划模型的有效性；李锐等[4]综合考虑带有正逆向物流网络中的各因素，采用改进的蚁群算法求解弹性约束条件下成本最小化模型。关于港口和航线配船的规划研究，靳志宏等[5]针对航运的周期性特征，研究了多航线多船型的联合优化问题；陈康等[6]基于混合航线结构研究了班轮航线运力配置和支线运输航线调度的优化；陈超等[7]为解决船舶资源的优化配置，将短期与长期运输统筹起来进行规划。关于“选址-库存-路径”(location inventory routing problem, LIRP)的优化，Mjirda等[8]提出一个两阶段变邻域搜索(VNS)算法来解决多产品库存-路径问题；郑斌等[9]在混合整数线性规划模型中使用拉格朗日方法确定补货计划；Cordeau等[10]研究了震后应急物流动态选址联运问题，并用混合遗传算法进行求解；王海军等[11]针对应急物资配送选址-路径问题，建立了双目标随机规划模型，通过启发式算法来求解；Liu等[12,13]通过建立带有库存控制策略的多节点选址-路径优化模型，采用两阶段启发式算法对模型进行了测试和评价；吴迪等[14]建立了单一群岛的单向物流运行的群岛物流体系的优化模型进行优化。另有部分学者针对“选址-库存-路径”联合优化问题构造了多目标混合整数非线性规划模型，采用启发式算法来求解等等[15～18]。

分析发现，以上成果可为本文研究提供部分思路和借鉴，但在规划模型构建和求解方法上仍需进一步深化。本文规划的远海岛礁群多级双向物流体系是以海上运输为背景的“选址-库存-路径”问题(maritime location inventory routing problem, MLIRP)，此类系统与以往LIRP的区别在于：①海上运输受台风等恶劣天气影响较大，因此需要设定安全库存以避免因突发事件导致物资断供现象发生；②各岛礁根据适宜船型确定泊位建设规模，泊位建设规模将直接影响整个运输系统中基础设施的建设成本；③船舶运行航线交错复杂，存在往返运输与循环运输两种并行方式，需进行协同组合。总之，由于背景的特殊性，已有成果将难以解决MLIRP问题，因而需要另辟蹊径，重新建立新的规划模型和求解方法。

针对远海岛礁群的地理分布及海上运输特点，文中建立了结合多船型、多种运输方式、多级双向的运输网络规划模型，提出了求解模型的双层并行搜索遗传算法。最后，以我国南海群岛为例进行建模并求解，并采用不同算法通过多组不同规模的算例进行演算比较，验证了文中所建规划模型和求解方法的合理性与有效性，从而为远海群岛物流封闭性体系的建设和发展提供理论和方法，对我国南海开发和建设具有重要的理论意义和实用价值。

1 模型构建

1.1 问题描述

不失为一般性，远海岛礁物流网络由大陆港口、各群岛的中心岛礁以及围绕中心岛礁的若干卫星岛礁所组成。其中，大陆港口是补给物资运输的始点和返程产品运输的终点， 承担整个岛礁物流网络的物资集散任务。各岛礁群的中心岛礁是物流网络的枢纽，除了完成与大陆港口的往返运输以外，还要分别联系周边的卫星岛礁，具有物资集散和仓储功能；各卫星岛礁是接受中心岛礁补给物资运输的终点和返程产品运输的始点。因此，每个岛礁群形成1个由中心岛礁为枢纽节点的子网络，整个物流体系即为由多个子网络组成的多级网络。上述物流网络的特殊性在于：①物流网络由多个中心岛礁所构成的多级网络组成；②物流形态同时包含正向和逆向物流，在运输过程中同时进行，其控制因素可能由正向物流量决定，也可能由逆向物流量决定，所以其控制方向上存在一定的不确定性。

在规划内容上，运输成本与仓库成本之间存在效益悖反效应，即以船型、航线、班期为基本元素的运输成本，与以仓库容量、最低风险存储量为基本元素的仓库成本相互矛盾、相互制约。例如，如果选择吨位较大的船型尽可能地满载运输，则可以缩减运输班期以降低运输成本，但同时却会增加仓储量而导致仓库建设成本和仓库储存成本的增加，将两者综合考虑后，有可能使整个物流系统的总成本增加，因而需要寻找相互协调、统筹规划的较佳策略。上述优化目标的复杂性在于：①“选址-库存-路径”各相关成本的变化相互缠绕，构成了复杂的多维问题；②面对多级网络的路径选择，使得上述因素在各级子网络之间相互交叉，求解难度增加。

综上，本文研究的是“选址-库存-路径”问题，需要解决的目标是：①确定各中心岛礁的选址；②为航线配置适用船型；③确定各航线的运行方式(即往返运输或循环运输)；④确定各航线运输班期、船舶运量；⑤确定各岛礁仓储容量及泊位大小和数量。综合以上各因素后，在确保补给物资供应连续不中断且能将返程产品及时运回大陆港口的前提下，确定物流运输系统总成本最小的规划方案。

1.2 规划模型

实际中，航线设置又可分为两种：①大陆港口与中心岛礁之间以及中心岛礁与卫星岛礁之间运输的往返航线；②依次沿各岛礁运输的循环航线。当同1条船舶同时承担2条以上往返航线时，则该类型航线定义为“往返航线组”。由于作为交通枢纽的中心岛礁上承大陆港口，下接周边的卫星岛礁，因而将由大陆港口向多个岛礁群的中心岛礁提供补给物资并接受其返程产品的航线组合称为上层网络，将各中心岛礁向其卫星岛礁分拨物资并接受返程产品的航线组合称为下层网络。

1.2.1 船舶运输成本模型

假定各船型航行成本与航行距离成正比，每次船舶靠泊装卸时间不超过24小时，建立船舶运输成本模型如下：

(1)

(2)

(3)

(4)

船舶购置成本及运营核算期内运营成本的模型为：

(5)

1.2.2 码头建设成本模型

码头建设成本模型为:

(6)

1.2.3 仓储系统成本模型

由于远海地区受台风等不确定因素影响较大，当台风到来时则终止所有海上运输任务，此时各岛礁日常物资的供应及为运出的产品需要靠仓储系统来维持，因此，需设定各岛礁抗风险最低仓储量、单个运输周期内岛礁物资补给量及单个运输周期内岛礁返程产品运回量，其计算公式为：

Qrisk=Δt×q

(7)

Q=t×q

(8)

Q′=t×q′

(9)

式中，Qrisk表示岛礁抗风险最低仓储量，Q表示单个运输周期内岛礁物资补给量，Q′表示单个运输周期内返程产品运回量，Δt为仓储系统最小可维持天数，t为某航线班轮运输周期(即岛礁物资运输周期)，q为岛礁补给物资日均补给量，q′为岛礁的返程产品日均运回量。

为简化计算，假设：①各岛礁物资日常补给量及产品日常运回量连续且稳定；②物资在每一周期t的初始时刻进行补给与运回，每周期补给量、每周期运回量均为定值，且能够全部顺利出入库。

根据上述假设，可得到存储状态函数Q(τ)=Qall+(q′-q)×τ，其中，τ∈[0,t]；Qall为每一个运输周期内仓库初始存储状态，且有Qall=Qrisk+Q，Q(τ)为动态时刻条件下的仓库存储状态，Q*(τ)为每一个运输周期内仓库最终存储状态。当岛礁日常补给量大于日常运回量时，仓储系统存储状态如图1(a)所示，当岛礁日常补给量小于日常运回量时，仓储系统存储状态如图1(b)所示。

由图1可知，在[0,t]时段内仓库的存储量为：

(10)

由以上分析可得到仓库储存成本模型及仓库建设成本模型如下：

(11)

(12)

1.3 规划模型的合成

综合式(1)～(12)，建立群岛物流系统的规划模型如下：

minCtotal=Cdr+Ccy+Cmdr+Cmcy+Cship+Cport+Cstf+Cstb

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

以上各式中，式(13)为经营核算期内物流运输系统的最小总成本；式(14)、(15)分别表示在上层网络中各往返航线的船舶最大载重量不小于各相关中心岛礁的航班物资补给量的总和且不小于产品运回量的总和；式(16)和(17)分别表示上层网络中各循环航线的船舶最大载重量不小于各相关中心岛礁的航班物资补给量的总和且不小于产品运回量的总和；式(18)表示在下层网络中各往返航线的船舶最大载重量不小于各相关卫星岛礁的航班物资补给量及产品运回量；式(19)和(20)分别表示下层网络中各循环航线船舶最大载重量不小于各相关卫星岛礁的航班物资补给量的总和且不小于产品运回量的总和；式(21)、(22)表示在选择中心岛礁时往返航线运输情况下允许建设的仓库容量应大于中心岛礁所需仓储容量；式(23)、(24)表示在选择中心岛礁时循环航线运输情况下允许建设的仓库容量应大于中心岛礁所需仓储容量。

2 算法设计

由以上分析可知，远海多级岛礁群双向物流网络的优化实际上是集“选址-库存-路径”为一体的完全混合整数规划问题。关于此类问题研究，潘震东等[19]提出了基于划分的遗传算法(partition based on autonomous genetic algorithm, PB-GA)，该算法引入仿真软件，按照染色体上的基因顺序依次在满足车辆载重量约束条件下求得各节点费用最小的划分，并对后继节点的划分进行改进，直到获得整个染色体的可行解；周根贵等[20]通过构建逆向物流网络的中心选址模型，采用遗传算法进行求解。以上计算方法为仓储与配送的联合优化提供了思路，但本文模型的计算需要考虑如何将不同岛礁群的中心岛礁选址与上、下两层网络的航线划分以及各航线连接岛礁的顺序等决策变量用染色体表达出来，以达到为不同航线配置船型、设置相应的运行方式和班期，以及为各岛礁规划仓储规模的目的，因而已有算法对本文问题效率较低。比较诸多算法的优劣并结合前述模型特点，本文提出了1种适合求解所述问题的双层并行搜索遗传算法(double gradation parallel search genetic algorithm, DGPS-GA)。

DGPS-GA算法的核心是建立双层并行搜索(double gradation parallel search, DGPS)模块，其基本思想是：通过染色体获得各中心岛礁的选址、上下两层网络航线划分及运行顺序；再依据上述信息对上下两层网络分别以并行搜索(parallel search, PS)的方式配置各岛礁的航班补给量和回运量以及航线、船型、班期、运行方式和仓储系统，得到该染色体对应的可行解，然后再按照规划物流运输系统最小总成本的计算公式进行求解。DGPS-GA算法可同时对搜索空间的多个解进行计算评估，具有明确的搜索方向以及并行搜索机制，可将上下两层网络分离单独并行搜索和比较，有效避免了在下层网络搜索的过程中影响上层网络搜索的弊端，避免出现其他算法中存在的收敛速度慢和未成熟收敛等问题，全局优化性能更为优异。

2.1 染色体

为表达各群岛中心岛礁选址以及上下两层网络航线划分及各航线运输岛礁顺序等信息，满足染色体序列能够完整表达全部解空间(极限情况下可能所有航线均为单船往返航线)的要求，需分别对上层及下层网络以饱和划分的方式设计染色体，即某1个染色体是由大陆至中心岛礁海运网络基因段(简称中心岛礁基因段)和各群岛中心岛礁至卫星岛礁网络基因段(简称岛礁群基因段)联合组成，利用n-1个(设某段基因岛礁数量为n)分隔符，将该段基因分成n段，两个分隔符之间的连续基因即表示1条航线依次运输的岛礁，图2表示1条可能出现的染色体。

图2 染色体表达方式

图2中，将0作为间隔符，两个0之间的岛礁代表由同1条船进行运输且岛礁序号表示运输顺序。例如，中心岛礁基因段的含义为：对于编号为1、2、3的3个群岛，分别以3#、12#、17#岛礁为中心岛礁，上层网络配置3条航线，依次对3#、12#、17#岛礁进行运输；岛礁群1基因段的含义为：在下层网络岛礁群1设置3条航线，依次对5#、9#岛礁(由同1条船)、10#、8#、7#岛礁(由同1条船)和1#、4#、2#、6#岛礁(由同1条船)依次进行运输，岛礁群2、岛礁群3基因段含义以此类推。上述染色体编码中所表达的有关中心岛礁选址及各岛礁航线划分等信息将为DGPS模块提供理论支持。

2.2 DGPS模块

DGPS模块的运行过程为：

(1)下层网络优化过程

Step1先对下层网络中(从中心岛礁至卫星岛礁)某条航线往返运输和循环运输两种运行方式的自变量(即航线运行班期)以并行搜索机制进行邻域搜索；

Step2找出该航线两种运行方式的最低成本并进行比较，选择其中成本较低的运行方式及所对应的各岛礁(从中心岛礁至卫星岛礁)航班物资补给量与产品回运量、航线船型、运行班期等为该航线的配置解，直至遍历搜索所有下层网络中的航线且达到算法限定的迭代次数为止，否则转至Step1，重新设置参数；

Step3以各岛礁群每日补给物资总量与回运产品总量分别作为对应中心岛礁的日均补给量与日均运回量，将合适的运输方式及配置解传递至上层网络(从大陆港口至中心岛礁)。

(2)上层网络优化过程

Step4先对上层网络中(从大陆港口至中心岛礁)某条航线往返运输和循环运输两种运行方式的自变量(即航线运行班期r)以并行搜索机制进行邻域搜索；

Step5以各岛礁群每日补给物资总量与回运产品总量分别作为对应中心岛礁的日均补给量与日均运回量，对上层网络(从大陆港口至中心岛礁)航班物资补给量与产品回运量、航线船型、运行班期等为该航线的配置解，直至遍历搜索所有上层网络(从大陆港口至中心岛礁)中的航线且达到算法限定的迭代次数为止；否则转至Step4，重新设置参数；

图3 DGSP模块流程图

Step5输出整个上下层运输网络中各航线的各项配置解；

Step7算法结束。

具体流程如图3所示。

2.3 交叉

根据染色体编码的特点，DGPS-GA以分隔符及岛礁编号分别交叉的方式进行运算，即子代分别遗传了父代1中的分隔符位置及父代2中的岛礁顺序，具体操作如图4所示。

图4 交叉算子

2.4 变异

由于染色体较为复杂，因此需将变异算子分为3种情况：①为各基因段内部岛礁之间的变异；②为岛礁基因与间隔符之间的变异；③为中心岛礁基因段与各卫星岛礁基因段之间岛礁的变异，具体操作如图5所示。

图5 变异算子演绎方式

2.5 适应度计算

对于DGPS-GA得到的每条染色体，将其适应度函数F(x)定义为由染色体通过DGPS模块得到的总成本。显然，在非负的前提下，适应度函数F(x)的值越低，得到的染色体效果就越好，越接近理想的目标结果。

3 算例

3.1 基本数据

现以我国南海西沙、东沙和南沙群岛为例，假设3个群岛分别由10、5和7个岛礁组成，共计22个，其坐标位置见表1。各岛礁所需的日均物资补给量、产品回运量见表2。备选船型分别为100、500、1000及5000吨级，各有关成本见表3，设定经营核算期为10年，为抵抗台风所导致航线未能及时运输货物的风险，设定物资存储最少维持时间为5天。

表1 各岛礁坐标

注：O#为大陆港口。

表2 各岛礁物资日均物资补给量及日均产品运回量

表3 成本估算表

图6 算法收敛过程图

3.2 计算结果

将有关数据代入物流成本模型，采用MATLAB 7.0运行DGPS-GA算法，在系统为windows7，AMD Athlon(tm) X2 240 Processor 2.81Ghz，2GB内存的计算机环境下进行计算，设定种群为30，交叉概率为0.65，变异概率为0.0055，总的迭代次数为400。在经过312次遗传迭代运算后得到较好结果，计算收敛过程如图6所示。其中，5#、14#及18#岛礁分别被选定为3个岛礁群的中心岛礁；共需配备船舶14条，其中5000吨级1条，1000吨级4条，500吨级4条，100吨级5条；设置泊位27个，其中3#中心岛礁设定5000、1000和500吨级泊位各1个，14#中心岛礁设定1000和100吨级泊位各1个，18#中心岛礁设定5000、1000和500吨级泊位各1个，其他所有卫星岛礁均设定100～1000吨级不等的泊位各1个。优化后的航线设置见表4和表5，各岛礁码头、仓储设施配备和物资补给量、产品回运量见表6，群岛海运物流体系如图7所示。

表5 中心岛礁至各卫星岛礁航线设置表

表6 岛礁泊位数量与规模、仓储设施配备及航班补给量、回运量

图7 岛礁群海运物流网络示意图

3.3 算法比较

为验证本文算法(DGPS-GA)的有效性及合理性，分别采用基于划分的遗传算法、Lingo算法进行对比，每种算法分别单独运行20次。为验证不同规模下的计算效果，同时分别选取2、3、4个中心岛礁进行计算，结果显示：对于2个中心岛礁的规模，DGPS-GA算法比基于划分的遗传算法和Lingo算法在总成本方面分别降低了10.62%和8.97%，计算时间分别减少了7.10%和12.73%，内存占用分别减少了6.55%和2.07%；对于3个中心岛礁的规模，比基于划分的遗传算法和Lingo算法在总成本方面分别降低了12.40%和10.33%，计算时间分别减少了7.51%和2.22%，内存占用分别减少了8.12%和1.32%；对于4个中心岛礁的规模，总成本分别降低了13.52%和9.55%，计算时间分别减少了4.02%和10.50%，内存占用分别减少了8.45%和4.98%，具体见表7。结果表明对于不同规模问题，本文提出的DGPS-GA算法在总成本、计算时间、内存占用等指标均优于基于划分的遗传算法和Lingo算法。

表7 不同规模问题在不同算法下的性能对比

3.4 灵敏度分析

由上文可知，各岛礁群物流运输系统总成本由运输系统成本与仓库系统成本组成，且两者之间存在效益悖反效应。为了便于分析两者的变化对运输系统总成本的影响，现设运输系统成本权重为α，仓储系统成本权重为β，则岛礁群物流系统总成本模型(13)可转化为带有权重的优化模型：

minCtotal=α(Cdr+Ccy+Cmdr+Cmcy+

Cship+Cport)+β(Cstore+Cbuild)

(25)

式中，α、β∈[0，1]。

设α、β的变化幅度为0.1，运行的结果见表8。分别以α、β为自变量，以航线运输、船舶购置、码头建设等运输系统成本，仓库储存、仓库建设等仓储系统成本为因变量进行线性回归分析，其结果见表9。经比较可知，运输系统成本比仓储系统成本对最优解的影响更大，因而对系统总成本更为敏感，因此决策时应更应关注对运输系统的优化。

表8 各项成本计算结果(万元)

表9 回归系数分析

4 结语

远海多级岛礁群双向物流体系规划属于以海上运输为背景的MLIRP问题，该类问题与以往LIRP问题相比，其复杂性不仅体现在海上运输的风险和不确定性需要考虑足够的安全库存，泊位规模与船舶吨位密切相关以及存在往返与循环航线多种运输方式的选择，还体现在由多个中心岛形成诸多子网络的网络多级性以及需同时考虑返程运输的双向性。上述各因素相互关联缠绕，需要对现有算法进行改进才能求解。

根据远海岛礁群运输体系的规划与“选址-库存-路径”紧密相关的特点，在确保补给物资供应连续不中断且能将返程产品及时运回大陆港口的前提下，需综合考虑中心岛礁选址、分别为上下层运输网络配置不同船型并制定班期、设置航线数量及运输方式、设定各岛礁最低仓储容量等各项因素，建立了多级双向物流网络系统总成本最小的规划模型，并提出一种适用于所建模型的双层并行搜索遗传算法(DGPS-GA)。文中以我国南海群岛海事运输系统的规划为例建模和求解，并与其他算法根据不同规模问题就运算结果、计算时间、计算占用内存等指标进行比较，验证了所建模型及算法的可行性与合理性，从而为远海岛礁群海运物流体系的规划研究奠定了基础。

本文以总成本最小为目标构建的物流网络运输系统是基于理想性假设，实际中的问题会更复杂，如船东的利益分配，以海空协同方式增强岛礁物流体系的物资供应保障能力等。对于以上有关内容的规划问题，是下一步研究的方向。