本文主要有如下假设:①不区分货物品类; ②决策阶段内货物运输需求量和运输成本固定不变; ③货物运输需求产生和消失于某点; ④不考虑货物对运输的特殊要求。

D为货流集合, d∈ D; L为综合运输网络中径路集合, L_d∈ L; L_d表示货流d的可行径路集合, l∈ L_d; A为网络中路段集合, a∈ A; N为网络中结点集合; R为某一路段可以采用的扩建或新建方案集合, r∈ R; v_d为货流d的大小; cad表示货流d通过路段a的单位成本; δla表示货流可行径路l和路段a的对应关系; φli表示货流可行径路l和结点i的对应关系; Q_i表示结点i的通过能力; Q_a表示路段a的通过能力; fra表示路段a采用方案r的扩建或新建费用; C_r表示路段采用方案r能新增的通过能力; F_max表示最大扩建或新建投资金额。

决策变量为: xdl表示在综合运输网络中货流d是否通过径路l进行运输, xdl∈ {0, 1}; yar表示路段a是否采用方案r, yar∈ {0, 1}。

MinCost=∑d∈D∑l∈Ld∑a∈Avdxdlδlacad+∑a∈A∑r∈Ryarfra1s.t.∑l∈Ldxdl=1, ∀d∈D2∑d∈D∑l∈Ldxdlvdφli≤Qi, ∀i∈N3∑d∈D∑l∈Ldxdlvdδla≤Qa+∑r∈RyarCr, ∀a∈A4∑a∈A∑r∈Ryarfr≤Fmax5∑r∈Ryar≤1, ∀a∈A6xdl∈{0, 1}, d∈D, l∈Ld7yar∈{0, 1}, a∈A, r∈R8

模型中, 式(1)为目标函数, 包括在综合运输网络中的运输费用和网络中扩建或新建费用; 式(2)表示货流在运输网络中货流分配约束, 表示一支货流只能选择一条径路运输, 同时保证货流的不可拆分; 式(3)表示在综合运输网络中的结点能力约束; 式(4)表示综合运输网络中的路段通过能力约束; 式(5)表示路段扩建或新建总投资金额约束; 式(6)表示路段的扩建或新建方案选择约束; 式(7)和式(8)为决策变量约束。

利用和声算法求解网络设计问题, 用网络中路段的扩建或新建方案决策作为和声编码。编码如图1所示。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 和声编码示意图Fig.1 Design of harmony for model

图1中和声编码决策变量e表示路段的扩建或新建方案, e的取值范围在0到可行的扩建或新建方案之间, e等于0时表示路段不进行扩建, 等于1表示路段采用方案1, 不同路段的扩建或新建方案预先给定。根据编码内容即可确定各个路段的通过能力, 进而获得各条可行径路的最大通过能力。

2.2.1 和声搜索

和声搜索算法(HS)是由Geem等^[9]于2001年提出, 与其他进化算法相比, HS算法机理简单, 解的构造方式新颖, 易于理解, 易于编程计算, 且只有少数参数需要调整, 已广泛应用于TSP问题^[10]、工程优化^[11]、铁路运输组织^[12]等方面。在计算过程中, 较优解能在和声记忆库(Harmony memory, HM)中得以很好地保留, 而每次迭代过程中的较差解不断被排除。算法参数有:和声记忆库的大小HMS, 和声记忆库取值概率HMCR, 音调微调概率PAR, 音调微调带宽bw和创作的次数Tmax。

传统的和声算法由于参数固定, 在算法迭代后期存在收敛速度慢的问题。因此本文结合云模型(Cloud model, CM)改进和声搜索算法, 设计云和声搜索算法(Cloud harmony search, C-HS)来求解混合网络设计问题。

2.2.2 云模型

云模型是李德毅等^[13]提出的一种定性定量转换模型, 有随机性和稳定倾向性等特点, 已经在进化算法、智能控制、模糊评测等领域取得了广泛应用。云模型利用语言值实现定性概念和定量不确定之间的转化, 每一个定性到定量的论域映射称为一个云滴, 众多的云滴组成云。云有期望Ex、熵En和超熵He三个数字特征, 云模型是云的具体实现, 本文采用正态云模型来实现云。图2为3个具有不同数字特征的正态云模型, 对比图2(a)和图2(b)可以发现En越大, 云的分布范围越广; 对比图2(a)和图2(c)可以发现He越大, 相同范围内的云滴越发散。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 3个具有不同数字特征的云Fig.2 Three examples of normal cloud with different characteristics

云发生器是实现云模型的具体方式。本文采用正向云发生器来实现正态云模型。具体操作如下:

Ex=f-9En=(fmax-f-)/c110He=En/c211En'=NORMEn, He212Qcloud=e-(fi-Ex)2/2En')213

式中:c₁、c₂为控制系数; f-表示和声库中和声值的平均值; f_i表示和声库中个体i的和声值; f_max表示和声库中最优和声值。

结合云模型的和声搜索算法既保留了和声库和声多样性的优点, 又较好地平衡了全局搜索及局部搜索能力。根据和声库中种群和声值情况, 算法不同时期生成不同数字特征来控制算法参数, 初期和声库的数字特征较大, 使得种群能以较大概率更新; 在算法后期和声库的数字特征较小, 使得优秀个体能得到保护, 加速全局收敛。

算法的求解过程如下:

Step 1 初始化算法所有参数。

Step 2 随机生成产生HMS个和声编码, 构建初始和声库HM。

Step 3 根据编码情况求解目标值, 评价所有初始解。

Step 4 产生新的和声编码。新和声可通过三种方式产生:①学习和声记忆库; ②音调微调; ③随机选择音调。新和声有HMCR的概率选自HM中的一个和声, 有1-HMCR的概率选自HM外。HM中和声个体的选择概率由云模型Q_cloud产生, 如果新和声来自和声记忆库HM, 则有PAR的概率对其进行微调, 由于解的编码形式为离散型, 所以求解中不需要微调带宽bw。

和声微调操作:在和声编码中随机生成一个位置, 判断该位置编码情况, 并在取值范围内随机修改对应决策值。图1中和声的微调示意图如图3所示。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 云和声搜索微调示意图Fig.3 Adjustment operation of C-HS

Step 5 根据和声编码情况, 获得各路段扩建或新建方案, 确定各路段能力。根据货流OD情况, 调用k短路算法, 求解货流的备选径路集合。

Step 6 根据k短路情况获得各个径路的最大通过能力。调用Cplex程序求解货流分配模型, 并获得和声目标值。若扩建或新建方案能力不能满足配流或投资金额要求, 则在目标值中加入惩罚系数。

Step 7 评价新和声并更新和声库HM。若新和声目标值优于和声库中最差值, 则用新和声替换最差值; 否则不进行更新操作。

Step 8 判断是否满足计算终止条件(迭代次数), 如满足则输出最优和声; 否则转到Step 4。