基于最大熵的多式联运终端集运点选址优化

张 博,黄 静,张永辉,彭 勇

（1.中铁长江交通设计集团有限公司,重庆 401121; 2.重庆交通大学 交通运输学院,重庆 400074）

0 引言

随着区域一体化进程加速，内陆—港口的货物数量急剧增长，刺激了中长距离货物运输企业的蓬勃发展。然而，传统的单一运输方式不足以满足大面积、长距离的货物运输需求，为此采用多式联运方式弥补传统单一运输方式的不足，相互衔接完成货物运输。在此背景下，多式联运终端集运有利于提高货物运输效率、解决交通拥堵和环境污染等一系列问题。因此，建设多式联运终端集运点具有较大的理论意义和应用价值。

从承运人角度，考虑货物从多个备选的多式联运终端集运点选择最佳位置中转可归纳为多式联运终端选址 — 分配问题（Inter-modal Terminal Location Problems，IMTLP），这一问题是经典的枢纽设施选址问题（Hub Facility Location Problems，HFLP）的扩展。Arnold 等[1]在枢纽设施选址问题的基础上研究了多式联运终端集运点选址问题，给出了具有固定成本和无限容量的p-hub中值问题的扩展形式。Sorensen等[2]针对多式联运终端选址问题模型，设计了元启发式算法、贪婪随机自适应搜索算法（GRASP）和基于属性的爬山算法（ABHC）进行求解。Lin等[3]通过4个特征将IMTLP和HFLP区分，基于Sorensen的研究思路，提出了一种改进的混合整数规划模型，并研究了两种近似最优解的数学求解方法。Lin等[4]将多式联运终端的选址与货物分配分离开来，改进了混合整数线性规划模型，并采用两阶段规划方法进行求解。针对目前多式联运终端选址问题模型的研究，大多数学者都是基于混合整数线性规划模型（Mixed Integer Linear Programming，MILP）。

通过对已有文献的梳理可知，各位学者针对多式联运终端集运点选址—分配问题从数学模型、求解算法等视角进行了一系列研究，普遍采用的是传统的混合整数规划模型，忽略了模型中可能出现的面对未来需求不确定导致最优解发生偏差等问题。有学者注意到将最大熵原理运用到多式联运终端集运点选址问题中[5]，综合考虑了运输成本和终端固定成本，但未考虑多式联运终端集运点租金成本，未解决集运点多个、运输方式多样、终端离散分布的扩展问题。基于此，该文借鉴最大熵原理，研究了某城市区域内多货源点时，如何选择合适的集运点以及如何分配将货源点的货物给相应的集运点，使运输成本（直达运输成本和转运成本）和租金成本最低的问题。该问题的解决方法既能满足多货源点物流转运系统实际需求，又能弥补传统单一公路运输的不足，并提高物流转运效率，从而增加铁路—水路—公路运输模式的灵活性。

1 多式联运终端集运点选址问题建模

1.1 问题描述

某城市货源点的货物通过公路直接运输到多式联运起运地成本较高，为提高运输效率和降低运输成本，考虑建立多式联运终端集运点来缓解运输压力，从而多个货源点的货可以一部分直接运到目的地。另外一部分先运到集运点，然后以更大运量的铁路系统或水路系统运到多式联运起运地。该问题的网络结构可描述为三层：1个目的地、T个集运点和O个货源点。

1.2 模型假设

（1）货源点、候选集运点和目的地位置已知。

（2）货源点的运输量已知，并且都能运送到目的地。

（3）多式联运中转成本和直达运输成本已知。

（4）总货物运输预算已知。

（5）候选集运点的单位面积租金成本已知。

（6）经过集运点转运的货物量不能超出集运点的最大处理能力。

（7）货源点的货可经过多个集运点中转。

1.3 符号说明

其中，O为货源点集合（i∈O），D为目的地集合（j∈D），T为备选集运点集合（t∈T），J为虚拟集运点集合，表示直达运输（{0}），K为实际选择的集运点集合（K⊆T），M为备选集运点和虚拟集运点集合的并集（J∪T），R为实际选择的集运点和虚拟集运点集合的并集（J∪K），N={(i,t,j)i∈O;t∈M;j∈D}，其中集合N的基数为n。

1.4 数学模型

目标函数为：

式中，citj——从货源点i经集运点t到目的地枢纽j的货物中转运输成本；Xitj——决策变量，从货源点i经集运点t到目的地枢纽j的货物运输量（TEU/月），若t为虚拟集运点，则为直运量；αt——集运点t的单位面积租金成本；st——集运点t的面积；yt——决策变量，在t处选择并使用集运点取值为1，否则为0。

式（1）由两部分组成，第一部分是不经过集运点和经过集运点的运输成本，第二部分是集运点的场地租金成本。

约束条件为：

式中，qij——从货源点i到目的地枢纽j的总货物运输量，式（2）表示对于每个起点—终点对，不经过集运点和经过集运点的货物数量的和等于从货源点—目的地枢纽的总货物运输量。

式中，p0——可允许选择的最大集运点数量，式（3）表示实际建立的集运点数量不超过允许选择的最大集运点数量。

式中，bt——集运点t的最大处理量，式（4）表示通过多式联运集运点的货物运量不超过集运点每月处理的最大数量。

式（5）表示决策变量的取值为0或1；式（6）是非负约束，表示货物运量取正值。

1.5 模型转化

最大熵原理是在满足已知信息的前提下，对未知信息不做任何假设，而是考虑未知信息所有可能发生的状态，即对于未知概率事件，当作等概率事件来处理。

为了将最大熵原理应用于该文的问题，首先必须明确系统可能的状态，在该文中所有可能的状态为：直达运输货运量和使用集运点多式联运货运量。一般地，数学中系统可能存在的状态数量被定义为：

式中，E——系统可能的状态数量；Q——货源区域内货物总量，根据最大熵原理，目标是使E最大限度地满足多式联运集运点服务系统。满足lnE最大化的Xitj的取值同样会使E最大化，考虑到lnE的求解更加容易，所以可将问题转化为将lnE最大化，因此将式（7）重新定义为：

lnE的最大值对应于缺失信息量（或不确定性或熵）在概率分布构造中的应用，因此缺失信息量（H）得到的概率分布为：

其中，lnE*是lnE的最大值，式（9）可由以下命题得证。

命题1 如果多式联运系统中每个货源节点的需求为Qr(r∈N)，则相应的概率定义为：

式中，Pr表示概率，则等式（8）可表示为：

证明1根据定义，式（8）可写为：

运用斯特林公式的近似结果可得：

综合式（10）和（13），可以得出：

命题2 在多式联运系统其他信息未知的情况下，式（14）中的概率分布满足均匀分布：

相应的熵可以表示为：

其中，n为集合N的基数。

命题3 熵或缺失信息量（H）的概率分布与任何已知关于多式联运系统的信息量不能超过式（16）中的熵，即：

综上所述，最大熵的目标函数可以简化为经过与不经过集运点运输成本之和，将斯特林公式的近似值应用于式（8），得到：

将末端物流系统集运总成本添加为约束（18），其中第一部分是经过与不经过集运点运输成本，第二部分是集运点的场地租金成本，其总费用不超过预算总额C：

忽略最大熵函数中的常数项lnQ!，则由基本的熵公式推导出了最大熵设施选址问题（MEFLP）模型为：

式中，Λe表示函数，约束为（2）～（6）和（19）。

2 求解算法

2.1 MEFLP问题分解

MEFLP问题是典型的NP问题，很难寻找到一个最优解。因此，尝试将该问题分成两个子问题分别求解，这通过放松MEFLP问题的约束（4）和（19）实现。

约束为（2）、（3）、（4）、（5）、（6）和（19）。

式（22）中，ψt＞ 0 ,∀t∈M;β＞0分别表示集运点处理能力和预算约束的拉格朗日乘数，目标函数包括两部分成本（运输成本和场地租金成本），并且容量约束（18）是一个强制约束，为了解决宽松约束的MEFLP问题，将其分解为两个子问题，即设施选址子问题（FLP）和模式分配子问题（MCP）。

式（23）为FLP问题目标函数，其约束包括约束（4）和（6）。

式（24）为MCP问题目标函数，其约束包括约束（3）和（7）。

2.2 FLP子问题求解

成本敏感性参数β是集运点变量yt的函数，反之亦然，如果参数ψt,β已知，则假定yt为1的前提下，就可以求解FLP问题。

2.3 MCP子问题求解

命题4 （存在性）。假设集合K是已知的，如果MCP问题的可行解S是由约束（3）（4）（6）（7）和（13）共同决定的，即：

那么在集合S中至少存在MCP问题的一个解。

命题5 （唯一性）。如果集合S中存在MCP问题的解，那么这个解一定是唯一存在的。

命题4和命题5保证了MCP问题解的存在性和唯一性，可以构造一个拉格朗日方程，对于给定的预算C，可以得出与约束（18）相关的拉格朗日参数β（成本敏感性参数）如下：

函数Φ（β）是连续且对于参数β可微，因此，参数β的求解可以采用牛顿拉夫森方法。

2.4 MEFLP问题综合求解

MEFLP问题被分解为子问题，子问题可精确求解，目前存在的求解方法例如分支定界、拉格朗日启发式算法或完全枚举法等可以解决中小型实例问题。

3 算例分析

为了验证模型和算法的有效性和合理性，以重庆市主城区和周边区县的货源点到果园港码头一个月内的物流数据为例构建算例，根据该文提出的模型及方法，可得到图1所示的最佳集运点的分布示意图。

图1 最佳集运点的位置

从计算结果可以看出：

（1）在只允许选择一个集运点考虑或者不考虑租金成本的情况下，最佳为集运点2（即团结村）；在允许选择多个集运点考虑或不考虑租金成本情况下，最佳为集运点2和3（即团结村和珞璜）；可见案例中租金成本对选择最佳集运点的影响不大，这主要是因为5个备选集运点的租金成本相差不大，对总成本的影响甚微；且合理建设多个集运点可以实现更多成本节约，提高转运效率。

（2）在两个集运点情况下，不同货源点通过集运点中转流量均增大，整个货运中转流量由58%增为71%，成本敏感性参数β由 0.002 100 062 降为 0.001 291 056，说明β减小时式中更多货物总量被分配到更大运量的运输模式，即采用铁路或水路中转的方式进行运输，从而整个系统的中转流量增加，而参数ψ2和ψ2,3都为0，主要原因是货运总需求小于其集运点的最大处理能力。

（3）优化结果未出现木耳、南彭与走马的原因分析如下：木耳集运点离果园港较近，从成本角度考虑，与直达运输区别较小；南彭集运点为公路运输，不适宜大运量的货物进行中转；走马集运点也为公路运输，与团结村集运点距离较近。但相比较而言，团结村和珞璜分别为铁路运输和水路运输，更具有选择优势。

4 结论

为解决多货源点多集运点设施选址—模式分配问题，该文构建了以运输成本和集运点租金成本最小为目标的混合整数规划模型，将最大熵方法应用于该文的问题，解决了模型中可能出现的面对未来需求不确定导致最优解发生偏差等问题，并使用拉格朗日松弛方法将问题分解为两个子问题，即设施选址子问题（FLP）和模式分配子问题（MCP），最后采用完全枚举法结合具体算例进行求解。结果表明：选择以铁路运输为主的团结村集运点和以水路为主的珞璜集运点总成本较少，符合实际运输情况。

该文可根据建立的模型有效解决多货源点多集运点设施选址—模式分配问题，但仍存在不足，可在后续的研究中进一步讨论，主要包括：

（1）考虑多货源点多目的地设施选址—模式分配问题，实际问题中往往存在多个货物运输的目的地，从而满足不同的需求和经济效益。

（2）考虑算法的优化，当实际问题规模较大、条件更复杂时，完全枚举法已不能满足求解需要，可尝试采用智能优化算法提高求解效率。