启运港退税的航线网络鲁棒优化

杨芊+林国龙+信晓雷

【摘 要】 为解决未来启运港退税政策扩围后启运港的选择和运输网络优化问题，基于港口容量限制和未来运输需求的不确定性，通过将启运港的因素考虑到内支线集装箱运输网络的优化中，分析支线间的多式联运问题，建立鲁棒优化模型，并使用情景分析法对不确定性参数进行描述。论证得出：鲁棒优化模型可有效降低支线网络中启运港的选择风险；使用粒子群-蚁群算法对鲁棒优化模型的求解及仿真证明该算法和鲁棒优化模型的有效性。

【关键词】 启运港退税；鲁棒优化；粒子群-蚁群算法

0 引 言

启运港退税政策指的是从启运港发往洋山保税港区中转至境外的出口货物，一经确认离开启运港口即被视同出口并可办理退税。与传统的船舶抵达后再办理退税相比，启运港退税不仅使企业的资金周转效率更高，还能增强洋山港区的集聚辐射作用，助推上海国际航运中心建设。当启运港退税政策惠及到国内其他沿海中转港、内陆港以及无水港时，选择合适的启运港和合理的航线，才能使整个航线运输网络的物流成本降到最低。从这个角度来看，启运港的选择问题与枢纽港的选址有所相似。

网络优化设计模型由确定型、随机型和鲁棒优化型等3种组成。运用确定型和随机型网络优化设计模型都需要能够准确预测网络设计的参数或分布。由于参数值和概率分布很难预测和获取，网络优化多用鲁棒优化理论进行。启运港的确定，不仅要考虑集装箱港口所辐射区域的集装箱出口量，还要考虑多式联运的方便性和成本的节约性。

1 模型的建立

模型建立基础条件有：（1）一个支线港需要出口的集装箱只能通过一种运输方式运到启运港，且只能运到一个启运港；（2）启运港有集装箱最大吞吐量限制；（3）启运港之间和启运港与目的港之间具有一个运输成本折扣d （0

情景s下的鲁棒优化模型为

式中：N为所有的节点集合（支线港、目的港及潜在的启运港）；L为候选路线集合；S为状态情景集合；K为运输需求的港口；€%R€%o为运输方式的集合；c为单位集装箱资金的单位时间占用成本；n为流量资金的占用天数；为在状态情景s下运输需求港口k的集装箱运输量； 为在情景状态s下，支线港建设成启运港的固定成本；为在运输路线（i，j）上每单位流量的运输成本；为在状态情景s下，运输需求港口k在线路（i，j）上的运输成本；为在状态情景s下，在港口节点k处，运输方式由€%o1转为€%o2的中转费用；p为启运港的个数；qs为状态情景s可能出现的概率；为状态情景s的最佳状态；为各港口的吞吐量；Zi为二元决策变量，为“1”则港口i设为启运港，为“0”则不设；Xij为二元决策变量，为“1”则路线（i，j）被选中，为“0”则不选；为二元决策变量，为“1”则运输方式在节点k由€%o1变为€%o2，为“0”则不变；为在状态情景s中，港口k的集装箱经过启运港i和j中转的比例（当i=j时，表示仅经过一个启运港中转；当i≠j时，表示经过了两次中转）；为在状态情景s中，启运港i的集装箱直接运到枢纽港的比例。

式（1）为目标函数，表示运输成本、启运港的设置成本、运输方式的转换成本和资金占用成本的总和最小。式（2）～式（14）为约束条件：式（2）保证从每个支线港运出的集装箱只能有一条路线；式（3）保证在每一个场景状态s中，启运港i的集装箱可以运输到枢纽港或其他启运港；式（4）保证从启运港i运输的集装箱量等于从其他港口运到启运港i的集装箱量与启运港i自有的集装箱量之和；式（5）保证在每个场景状态s中，支线港i的集装箱运输量都必须被完全满足；式（6）保证启运港i的集装箱吞吐量不大于其最大集装箱吞吐量；式（7）限定了启运港的个数；式（8）保证有集装箱运量的运输路线（i，j）必须是开放的；式（9）保证假如支线港i被选为启运港的话，其能够为其他支线港服务；式（10）保证集装箱运输路线为单向，即只能从支线港到启运港或启运港到枢纽港，不能从启运港到支线港或从枢纽港到其他港口；式（11）限定了p-鲁棒的状态，每个场景状态中的相对遗憾值不能大于一个常数值（p>0），即该情景s的解决方案的成本与最优成本之间的相对距离必须在p以内，因此，该模型中的每个场景的目标函数不能大于（1+ p）；式（12）规定了启运港的数量；式（13）和式（14）规定了约束变量的类型。

2 算法设计

本文设计了两级的混合智能启发式优化算法求解鲁棒优化模型。主级使用粒子群优化算法（PSO）求解启运港的选择问题；从级使用蚁群优化算法求解支线港集运路线以及集运方式的选择。

2.1 PSO优化设计

设搜索空间为D维，粒子数为u，第h个粒子的位置向量Xh=（xh1，xh2，xh3，…，xhd），速度向量Vh=（vh1，vh2，vh3，…，vhd），其中：h=1，2，3，…，u；d=1，2，3，…，D。Ph=（ph1，ph2，ph3，…，phd）为适应值最优的位置向量，Pr=（pr1，pr2，pr3，…，prd）为全局最优位置向量。各粒子按下式更新位置

vhd=wvrd + c1r1（phd-xhd） + c2h2（pgd-xgd）（15）

xhd=xhd + vhd（16）

式中：w是惯性因子；c1，c2是学习因子；r1，r2为[0，1]之间的随机数。

粒子的初始位置和初始速度都是随机产生的，然后按式（15）和式（16）的方法进行迭代，直至找到最优解，迭代结束。

根据以上模型的求解特点，按照整个运输网络中总的节点数n构造粒子h为一维向量且包含n个元素，这n个元素分别对应着网络中的n个节点，以此来表示对应的节点在解码时的先后等级。

2.2 蚁群算法优化设计

将m只蚂蚁放在n个港口上（1≤n≤m），设定如下规则：（l）每只蚂蚁可以释放对其他蚂蚁选择路径带来影响的信息素；（2）在与当前节点相连接的多个路径上，每只蚂蚁可以根据其不同的信息素浓度来选择通过哪条路径进入下一个节点；（3）每只蚂蚁选择路径的依据是信息素浓度，浓度越高，选择此条路径的概率越大；（4）蚂蚁通过信息素寻找食物，而且在寻找过程中会同时释放出信息素；（5）根据每条航线的营收收益大小释放与之相应浓度的信息素，且随着时间推移其浓度会变小。

本文利用可行的航线方案表示蚂蚁群体探索并走过的路径，并将每只蚂蚁所走的路线看作一个方案可行解。优化设计如下：

（1）若第k只蚂蚁在第i个港口节点上，按照随机比例的规则，其选择下一个港口节点j的概率为

=（17）

式中：Ak为蚂蚁k下一步允许选择的港口节点的集合；€%mij为航线路径（i，j）上的信息素量轨迹强度的大小；€%`ij为航线（i，j）的可见度，表示从港口节点i到节点j的启发程度。

在路径选择过程中，蚂蚁并不是仅选择概率最大的路径，而是结合赌轮法，以较大的概率选择概率最大的路径，但不排除选其他路径的可能，从而保证搜索的全面。

（2）蚂蚁在构造路径的同时，按式（18）及时更新局部信息素，减少相应的信息素，更符合蚂蚁搜索过程，且可以有效避免蚂蚁收敛到同一路径。

€%m（i，j）=（1-€%l） €%m（i，j） + €%l€HU€%m（i，j）（18）式中： €%l∈（0，1）为信息挥发因子。

（3）每只蚂蚁完成循环后，在加强最优蚂蚁的信息素的同时减弱最差蚂蚁的信息素，通过增大最优与最差路径上信息素的差异，使最优路径的搜索更加快捷。

2.3 粒子群-蚁群算法步骤

步骤1 设置蚁群算法的相关参数，蚂蚁的位置均处于随机状态。

（1）按照式（17）为每只蚂蚁的初始路径进行概率选择；

（2）每只蚂蚁生成自己的航线路径，并按照式（18）进行信息素的局部更新；

（3）循环（1）―（2）两步，直至所有的蚂蚁都形成完整的航线路径；

（4）将蚂蚁的目标函数值进行记录，并根据数值进行评定；

（5）在迭代完成后，将选出的最优蚂蚁（目标函数值最大）的路径按下式进行全局信息素的更新；

€%m（i，j）=（1-€%j） €%m（i，j） + €%j€HU€%m（i，j）（19）

式中： €%j表示路径中信息素持久性的因子；1-€%j表示路径中信息素的衰减度因子； €%j∈（0，1），表示蚂蚁个体之间相互影响的强弱程度。

（6）将最差蚂蚁（目标函数值最小）的路径按下式更新全局信息素；

€%m（i，j）=（1-€%j） €%m（i，j） + €%^ （20）

（7）重复步骤（1）―（6），直到满足结束条件，依据最后各航线网络节点的选择状态得出最佳网络模型。

步骤2 利用蚁群算法得到每个粒子的适应度值，并更新历史最优粒子位置向量和全局最优粒子位置向量Pg。

步骤3 按式（15）、式（16）对粒子的速度向量和位置向量进行更新。

步骤4 重复步骤2―步骤4，直至满足结束条件，利用蚁群算法求解出最优解。

步骤5 计算结束。

3 算例分析

本文采用小规模算例对算法进行分析和验证。选取10个国内港口（包括未来的无水港），分别标号A，B，C，D，E，F，G，H，I，J，其中港口A为出口目的港。现在目标函数和约束条件下，从其他9个港口中选取启运港。10个港口之间的距离见表1。

从表5可以看出，鲁棒优化后的计算时间明显小于鲁棒优化前的计算时间，这也证明了算法的有效性。当p=2，€%Z=0.6或€%Z=0.8时，鲁棒优化前后的启运港是一样的；但当p=3，€%Z=0.8时，启运港的选择有两组。从中可以看出，随着启运港数目的增加，由于折扣因子的增加，意味着支线港到启运港和启运港之间、启运港与目的港之间的运输效益差正在减小，导致了鲁棒最优解的增加。

p=2和p=3时的运输路线和运输方式分别见图1和图2，图3。

4 结 语

本文将启运港退税政策引入集装箱运输网络，不仅考虑了各港口集装箱运输量增加的不确定性，而且将启运港的因素考虑到内支线集装箱运输网络的优化中，并分析了支线间的多式联运问题，建立鲁棒优化模型，利用一组已知概率的离散情景来表示未来支线港口可能的运量。用粒子群-蚁群双层优化算法求解鲁棒优化模型并进行仿真，证明了算法的有效性，也证明了鲁棒优化模型可以降低支线网络中启运港的选择风险。