随机环境下铁路枢纽内集装箱中心站选址分配优化模型及其遗传模拟

1、随机环境下铁路枢纽内集装箱中心站选址分配优化 模型及其遗传模拟退火算法 1王保华,何世伟,宋瑞北京交通大学交通运输学院,北京(100044摘 要 :研究了随机环境下铁路枢纽内集装箱中心站的选址问题。 首先分析了集装箱中心站 的运输组织模式并给出了其选址的若干原则, 然后在运输需求随机变动和有车站作业能力限 制的条件下建立了 0-1整数随机规划模型, 目标为极小化期望总费用。 该模型中含有不可转 化为确定性等价类的机会约束, 因此文章利用随机模拟方法来计算目标函数值并检验机会约 束, 并在此基础上给出了一种嵌入了模拟退火操作的混合遗传算法。 测试结果表明, 与经典 遗传算法相比, 遗传模拟退火算

2、法运行的时间虽然有所增加, 但结果明显更优, 且有较强的 稳定性。关键词 :集装箱中心站;选址分配问题;随机整数规划模型;遗传模拟退火算法中图分类号:TN953 文献标识码:A 文章编号:2008-04871.引言集装箱运输具有安全、 便捷、 便于实现多式联运等特点, 是世界各国货物运输的发展方 向。 在我国铁路现有运输组织模式下, 若干集装箱流量较大且条件允许的铁路枢纽或车站间 通过开行集装箱班列的方式大大提高了货物运达速度, 但由于大部分集装箱办理站技术装备 落后、专夜话程度不高、主要集装箱运输通道能力紧张,影响了班列的开行质量和数量,严 重阻碍了铁路集装箱运输的发展。集装箱中心站也称结点

3、站, 它是指专业办理集装箱班列及枢纽内集装箱小运转列车到发 和整列集装箱列车中转、 装卸的路网性集装箱货运站, 对其所在枢纽内的集装箱运输有较强 的辐射作用 1。集装箱中心站选址包括两个层次,第一个层次为确定集装箱中心站在路网上 的布局, 即将在哪些枢纽和港口城市中建设中心站; 第二个层次为确定集装箱中心站在所建 城市中的具体位置。 2004年初,国务院批准的中长期铁路网规划指出,我国将在北京、 上海、 武汉等枢纽城市内建设 18个集装箱中心站, 截至 2008年, 已经投入运营的集装箱中心 站有上海、昆明两个,除若干正在建设中外,还有一些集装箱中心站还未开工,因此研究城 市内集装箱中心站选址

4、方案仍具有一定实际意义。集装箱中心站选址方案受地理位置、运量组成、箱源性质、作业方式的影响。位于内陆 铁路枢纽的集装箱中心站宜靠近物流基地或主要工业区, 同时兼顾零散客户; 而位于港口的 集装箱中心站则主要承担大量集装箱海铁联运换装作业, 还要承担地方集装箱集散作业。 由 此可见,中心站如果采用单一场站的方案很难兼顾港口、城市、工业区、物流园区的需求; 如果过于分散则不利于组织集装箱班列, 且有可能造成资源浪费。 因此, 铁路枢纽内的集装 箱中心站宜采用 “ 一站多点 ” 的方式, 根据客户的分布和业务量大小合理配置运能资源, 在作 业量较大的地区(如港口、物流园区等等设置主站区,办理集装箱班

5、列整列到发和中转作 业; 另设置集装箱办理点服务于零散客户。 集装箱办理点应尽量组织整列或整组, 然后送至 中心站集结或换装, 组成班列开往其他中心站。 总之, 在确定集装箱中心站选址备选方案过 程中应遵循如下原则:(1与城市总体发展规划、港口规划、物流园区规划相协调;1本课题得到“863”国家高科技资助项目(2007AA11Z208, 高等学校博士学科点专项科研基金资助课题 (20040004012,北京交通大学重点基金资助项目(No.2006XZ004的资助。(2科学预测集装箱运量增长规律,保留未来发展余地;(3中转和始发作业量大的中心站应尽量靠近枢纽内技术站,以充分利用既有运力资 源;(

6、4尽量靠近枢纽内主要公路货运通道,以便于集装箱集疏运;目前与集装箱中心站选址相关的文献多为定性研究,如文献 1提出了港口型中心站选 址及运输组织的原则,并以大连集装箱中心站为例进行了说明;文献 2采用多因素模糊决 策方法对选址方案进行评价, 而本文则应用最优化理论对铁路枢纽内集装箱中心站选址问题 进行定量研究, 在考虑运输需求之随机性以及作业能力限制的条件下建立了铁路枢纽内集装 箱中心站 0-1随机整数规划模型。对于含随机参数的整数规划模型,用传统的经典算法求解 较为困难, 因此本文采用基于随机模拟的遗传模拟退火算法对之进行求解。 最后, 文章给出 了算例以证明算法的有效性。2.铁路枢纽内集装

7、箱中心站选址 0-1整数随机规划模型2.1 符号表示2.1.1 参数I -集装箱中心站主站区备选位置, 1, 2, , I m =L ;J -集装箱办理点备选位置, 1, 2, , J n =L ;K -客户, 1, 2, , K p =L ;i -集装箱中心站主站区设在地址 i 所能具备的能力,以每天能够办理的集装箱数为单位; j -集装箱办理点设在地址 j 所能具备的能力,以每天能够办理的集装箱数为单位; k -客户 k 的需求,以每天产生的集装箱流为单位;ij c -从集装箱中心站主站区备选位置 i 到集装箱办理点备选位置 j 的运输成本,以元 /箱为单 位;ik d -从集装箱中心站主

8、站区备选位置 i 到客户 k 的运输成本,以元 /箱为单位;jk e -从集装箱办理点备选位置 j 到客户 k 的运输成本,以元 /箱为单位;ij h -从集装箱中心站主站区备选位置 i 到集装箱办理点备选位置 j 的新建(或改建线路所 需费用,若不需改建或修建新线路此参数可设为 0;ik g -从集装箱中心站主站区备选位置 i 到客户 k 的新建(或改建线路所需费用,若不需改 建或修建新线路此参数可设为 0;jk s -从集装箱办理点备选位置 j 到客户 k 的新建(或改建线路所需费用,若不需改建或修 建新线路此参数可设为 0;i F -集装箱中心站主站区建在备选位置 i 的固定成本;i W

9、 -集装箱办理点建在备选位置 j 的固定成本;l -集装箱办理点数量;-置信水平;2.1.2 决策变量0,1i x -如果集装箱中心站选择位置 i 为 1,反之为 0;0,1j y -如果集装箱办理点选择位置 j 为 1,反之为 0;0,1ik u -如果客户 k 的业务由集装箱中心站主站区备选位置 i 办理为 1,反之为 0; 0,1jk v -如果客户 k 的业务由集装箱办理点备选位置 j 办理为 1,反之为 0;2.2 模型表述若运输需求为服从某一分布的随机变量,即 (w =,中心站主站区和各办理点的作 业量就有可能超过其能力限制。 如果规定车站作业量可以在一定置信水平的条件下满足能力

10、限制,则与能力限制相关的约束可以写成机会约束的形式,模型表述如下:Min (i i j j i j ij k ik ik i I j J i I j J i I k K k jk jk ik ik ij k jk jk jk j J k K i I k K i I j J k K j J k K x F y W x y h w u d E w v e u g c w v v s + (1s.t.1ikjk i I j J u v +=, k K (2ik i u x , i I , k K (3jk j v y , j J , k K (4(Pr k ik k jk i i k K j J k

11、 K w u w v x +, i I (5(Pr k jk j j k K w v y , j J (6 1i i I x= (7jj J yl = (8 , , , 0,1i j ik jk x y u v , i I , j J , k K (9式 (1为目标函数,表示极小化期望总成本;式 (2为逻辑约束,表示每一客户的业务 或者在集装箱中心站主站区办理,或者在集装箱办理点办理;式 (3、 (4为逻辑约束,表 示客户与站点之间的对应关系; 式 (5表示集装箱中心站主站区作业量不超过其能力限制的 概率达到给定置信水平; 式 (6表示集装箱办理点作业量不超过其能力限制的概率达到给定 置信水平

12、;式 (7、 (8为集装箱主站区和办理点数量约束;式 (9决策变量的逻辑约束。3.求解算法上述模型属于含随机参数的 0-1整数规划模型,其中的机会约束不能根据文献 4给出的 方法转化为确定性等价类, 因此本文以随机模拟来处理该机会约束, 以基于随机模拟的进化 算法对模型进行求解。在常用的几种进化算法中,遗传算法采用并行搜索,搜索速度快,但容易早熟;而模拟退火算法采用串行搜索的方式,虽然有时可以得到比遗传算法更优的解, 但收敛速度慢且经常依赖于初始解。 本文将模拟退火算法嵌入至遗传算法当中, 形成遗传模 拟退火算法,从而将二者的优点结合起来相互取长补短。在遗传模拟退火算法中, 模拟退火操作可以被

13、嵌入至选择过程中, 也可以嵌入至交叉和 变异操作中 5-7。在模拟退火操作中,算法将以一定概率接受劣质解,从而尽量避免算法收 敛于局部最优解。模拟退火算法中的初始温度选择 0t K =的形式,其中 K 可以为 10、 20等值。 max min f f =, max f 为初始种群中最优染色体的目标值, min f 为初始种群中最差染 色体的目标值, 退温函数选择 1k k t t += , 其中 01<<。 遗传模拟退火算法的主要步骤如 下:Step 1 染色体初始化由于模型中决策变量都为 0-1变量,因此染色体显然应采用二进制编码,根据 2.2.1,其长度为 m n m p n

14、 p +×+×,如下图所示: (010,01010,0100000,0001000, ,0000010m n m n m n p+× LL 123144444424444443染色体共分三个部分, 第一部分中每一基因表示中心站主站区备选方案, 其值为 1表示选择 该方案, 为 0则表示不选择该方案。 由于主站区一般只有一个, 因此第一部分中只能有一位 为 1;第二部分中每一基因表示办理点备选方案,其值为 1表示选择该方案,为 0则表示不 选择该方案。根据 2.2中约束 (5,第二部分中值为 1的基因总数应等于办理点个数;第三 部分每一基因表示客户与其服务站点的对应

15、关系,可选服务站点共有 m n +个,因此共有 m n +个备选方案, 根据 2.2中约束 (2, 每一客户对应的 m n +位基因中, 只能有一位为 1。 初始化染色体的步骤如下:步骤 1:随机生成 1到 m 之间的一个整数, 令染色体 1到 m 段中该整数对应的基因为 1, 其 余为 0,作为主站区地址;步骤 2:随机生成 m 到 m n +之间的 l 个整数(不可重复 , 令该染色体 m 到 m n +段中该 l 各 整数对应的基因为 1,其余为 0作为办理点地址;步骤 3:对客户 j ,随机生成 1到 m n +之间的一个随机整数,如果在染色体 1到 m n +段 中该整数对应的基因为

16、 1,则令该染色体 (m n j +×到 (1m n j +×+段中该整数对应的 基因为 1,其余为 0,否则重新生成。Step 2 染色体可行性判断染色体初始化过程已经包含了约束 (2、 (3、 (4、 (7、 (8、 (9的判断,因此此 处只需判断约束 (5、 (6。约束 (5、 (6属于机会约束,因此算法采用随机模拟方法对其 进行判断,对主站区备选位置 i ,判断染色体是否满足约束 (5的步骤如下:步骤 1:定义 10N =;步骤 2:根据各客户需求的分布生成样本(12, , , p L ; 步骤 3:若 (k ik k jki i k K j J k K w u w

17、 v x +,则 111N N =+;步骤 4:重复步骤 2和步骤 3N 次(N 为较大的正整数 ;步骤 5:若 1N N ,则满足约束条件。判断染色体是否满足约束 (6的步骤与上类似,在此不再赘述。Step 3 染色体适应度的计算计算每个染色体对应方案的目标函数值, 然后根据其值对染色体进行排序, 并定义基于 序的评价函数:(11 1, 2, , _i i eval V a a i pop size =L ,式中, _pop size 为染色体中种群中染色体的数量, 1i =表示染色体最好, _i pop size =表 示染色体最差。 由于目标函数中含有随机变量, 因此其值也需用随机模拟进

18、行计算, 步骤如 下:步骤 1:定义 0C =;步骤 2:根据各客户需求的分布生成样本(12, , , p L ; 步骤 3:根据式 (1计算样本 (12, , , p L 条件下的目标函数值 sample C 并令 sample C C C =+; 步骤 4:重复步骤 2和步骤 3N 次(N 为较大的正整数 ;步骤 5:计算 C N ,此即目标函数值的期望值。Step 4 染色体的选择过程在经典遗传算法中, 染色体的选择过程以其适应度为基础, 染色体的适应度越大, 其被 选中的概率就越大,具体过程可参考文献 4。如果将模拟退火操作嵌入至选择过程,则选 择过程可采取 Metropolis 判别

19、准则的复制策略:首先根据初始种群确定模拟退火操作的参 数 :对 每 一 染 色 体 i x , 在 其 邻 域 (i N x 内 随 机 搜 索 新 的 可 行 解 j x , 计 算 (ij j i f f x f x =,若 0ij f ,则 i j x x =;若 (exp /0,1ij k f t random >(表示 0到 1之间的一个均匀随机数,则 i j x x =,然后执行退温操作,即令 1k k t t +=。 Step 5 染色体的交叉操作定义 c P 作为交叉操作的概率,则每次种群中平均有 _c P pop size 个染色体进行交叉操 作。为保证染色体的可行性,

20、只对染色体 1到 m n +位进行交叉操作,步骤如下: 步骤 1:随机选择父代的两个染色体;步骤 2:随机生成 0到 1间的一个实数 ;步骤 3:若 0.5,则交叉染色体中主站区选址部分,反之则交叉办理点部分; 步骤 4:根据交叉后的染色体,重新生成客户和站点之间的对应方案;步骤 5:判断染色体的可行性,如可行则进行模拟退火操作,如不可行,转步骤 2。令 c 表 示 交 叉 后 的 子 代 染 色 体 , p 表 示 父 代 染 色 体 , 则 模 拟 退 火 具 体 过 程 为 :计 算 (f f c f p =,若 0f ,则 c p =;若 (exp /0,1k f t random &

21、gt;(表示 0到 1之间的一个均匀随机数,则 c p =,然后执行退温操作,即令 1k k t t += 。Step 6 染色体的变异操作定义 m P 作为变异操作的概率,则每次种群中平均有 _m P pop size 个染色体进行变异 操作，步骤如下： 步骤 1：随机选择变异的染色体； 步骤 2：随机生成 0 到 1 间的一个实数 ； 步骤 3：若 0.5 ，则染色体中主站区选址部分进行变异，反之则办理点部分变异； 步骤 4：随机生成变异的基因位置，令其为 1，其余为 0； 步骤 5：重新生成客户与站点的对应方案； 步骤 6：判断染色体的可行性，如可行则完成交叉操作，如不可行，转步骤 2。

22、在变异过程 嵌入模拟退火的过程与交叉类似。 Step 7 判断算法停止条件，若满足条件，算法推出，否则转 Step 4。 4算例分析 本文用 C+语言编写了基于随机模拟的遗传模拟退火算法的代码。 由于条件有限， 本文 无法取得实际数据，因此以下将以随机生成的算例验证算法的有效性。该算例中，置信水平 为 0.8，不考虑线路改扩建费用 h 、 g 、 s ，算例中各参数如下表： 表 1 集装箱中心站主站区备选位置改扩建成本和作业能力 备选位置 改扩建成本（元） 作业能力（箱/日） 1 100000 3000 2 120000 4000 3 120000 3000 4 110000 4000 表 2

23、 集装箱办理点备选位置改扩建成本和作业能力 备选位置 改扩建成本（元） 作业能力（箱/日） 1 30000 1000 2 20000 1000 3 30000 700 4 20000 800 5 40000 800 6 30000 700 表 3 集装箱中心站主站区备选位置至各办理点备选位置的运输成本（元/箱） 办理点 1 主站区 1 主站区 2 主站区 3 主站区 4 100 120 125 230 办理点 2 110 230 135 120 办理点 3 135 250 410 240 办理点 4 200 210 140 330 办理点 5 170 80 230 250 办理点 6 200

24、190 210 210 表 4 各客户需求分布函数（箱，服从平均分布） 客户 需求 客户 需求 客户 需求 1 U(100,120 6 U(50,70 11 U(150,170 2 U(60,80 7 U(55,75 12 U(60,80 3 U(50,70 8 U(150,180 13 U(110,120 4 U(70,100 9 U(120,150 14 U(130,150 5 U(75,95 10 U(140,160 15 U(170,180 表 5 各客户至各主站区备选位置的运输成本（元/箱） 客户 1 客户 2 客户 3 客户 4 客户 5 客户 6 客户 7 客户 8 -6- 主站

25、区 1 主站区 2 主站区 3 主站区 4 （续上表） 120 70 125 60 客户 9 50 55 40 70 客户 10 250 155 40 70 60 185 30 265 40 90 50 50 100 180 60 145 客户 12 70 90 50 150 90 75 65 70 客户 13 100 80 60 45 80 70 275 80 客户 14 90 75 65 70 60 90 180 160 客户 15 80 70 75 80 客户 11 80 65 30 65 主站区 1 主站区 2 主站区 3 主站区 4 70 70 195 60 表 6 各客户至各办理点

26、备选位置的运输成本（元/箱） 客户 1 办理点 1 办理点 2 办理点 3 办理点 4 办理点 5 办理点 6 （续上表） 客户 9 办理点 1 办理点 2 办理点 3 办理点 4 办理点 5 办理点 6 170 50 55 45 55 120 70 50 55 80 90 65 客户 2 50 55 40 100 80 90 客户 10 50 55 140 65 85 75 客户 3 60 85 30 65 45 55 客户 4 40 90 50 70 80 100 客户 5 100 80 60 50 40 50 客户 6 90 115 65 80 100 80 客户 7 80 70 95

27、190 85 75 客户 8 60 80 80 55 45 95 客户 15 80 70 75 85 70 120 客户 11 60 165 30 80 70 60 客户 12 40 90 50 95 50 90 客户 13 100 80 60 50 60 100 客户 14 90 75 65 75 85 75 遗传模拟退火算法中各参数如下：种群大小为 30、交叉概率 Pc 为 0.3、变异概率 Pm 为 0.2、随机模拟次数为 5,000，初始温度系数 K = 20 ，退温系数 为 0.8。 当模拟退火嵌入至选择过程时，遗传算法在 1024M 内存的 AMD Turion-64 1.8G 微

28、机上 运行了 15 次， 平均进化 100 代后可得到最优染色体 （1000， 010010， 1000000000， 1000000000， 0000000010， 0000000010， 0000000010， 1000000000， 1000000000， 1000000000， 1000000000， 1000000000，1000000000，0000010000，0000010000，1000000000，1000000000） ，15 个结 果中最优的总成本期望值为 669180 元，各结果之间差距不大，平均运行时间为 3min。根据 最优染色体可知，集装箱中心站主站区应选择第

29、1 个方案，办理点则选择方案 2 和 5，15 个客户中，主站区服务客户 1、2、6、7、8、9、10、11、14、15，办理点 2 服务客户 12、 13，办理点 5 服务客户 3、4、5。 当模拟退火操作嵌入至交叉和变异操作时，遗传算法在同样的微机上运行 15 次，取得 了相似效果：平均需进化 120 代左右得到相同的最优解，15 个结果中最优总成本期望值为 -7- 669095，平均运行时间稍有延长，为 4min。 当遗传算法中不嵌入模拟退火操作时， 算法进化 80 代左右即可收敛， 15 次计算结果 但 中最优总成本期望值为 731935。 以上测试结果表明， 在遗传算法中嵌入模拟退火

30、操作有利于其收敛至更优解， 而模拟退 火操作嵌入方式对结果的影响并不大。15 次测试结果的差距不大，说明算法具有良好的稳 定性。 5结论 本文构建了铁路枢纽内集装箱中心站选址随机规划模型， 并给出了求解该随即优化模型 的启发式算法， 给出的算例证明算法可以在较短时间内得出满意解， 能够解决实际规模的问 题。尽管如此，文中的模型只考虑了客户需求的随机性，在进一步研究中应将站点能力和费 用等因素的不确定性考虑在内。此外，本文只以成本作为评价指标，当指标中包含不可量化 因素时，如何将定量和定性方法结合起来也是需要研究的问题。 参考文献 1 Yan Haifeng.Study on Container

31、s Transport Organization between Railway Network Container Freight Network D,Chengdu:Southwestern Jiaotong University, 2004. 阎海峰. 结点站间铁路集装箱运输组织的理论和方法D. 成都: 西南交通大学,2004. 2 李佳峰. 港口型集装箱中心站选址及运输组织方案J. 铁道工程学报, 2004, 4(84: 6-10. Li Jiafeng. Site Selection of Harbor Type Container Central Station and Traff

32、ic Organization Program J. Journal of Railway Engineering Society, 2004, Vol.4 (84: 6-10. 3 谢辉, 盖宇仙. 多因素模糊决策在集装箱中心站选址中的应用J. 铁道运输与经济, 2006, 1(28: 73-75. Xie Hui, Gai Yuxian. Fuzzy Decision-Making among Multi-Factors for Location-Choosing of Container Center Station J. Railway Transport and Economy, 2

33、006, Vol.1 (28: 73-75. 4 刘宝锭. 不确定规划理论与方法 M. 北京: 清华大学出版社, 2003. Liu Bao-ding, Uncertain Programming with Applications M, Beijing: Tsinghua University Press. 5 刘以安,曹奇英, 刘同明, 高贵明. 基于遗传模拟退火算法的机动多目标数据关联问题研究J. 系统工 程理论与实践, 2001, 21(9: 67-72. Liu Yian, Cao Qiying, Liu Tongming, Gao Guiming. The Research on

34、Maneuvering Multiple Target s Data Association Problem with Genetic Simulated Annealing Algorithms J. System Engineering Theory and Practice, 2001, Vol.21 (9: 67-72. 6 刘志刚, 王建华, 耿英三, 欧阳森. 一种改进的遗传模拟退火算法及其应用J. 系统仿真学报, 2004, 16(5: 1099-1101. Liu Zhigang, Wang Jianhua, Geng Yingsan, Ouyang Sen. A modifi

35、ed Genetic Simulated Annealing Algorithm and Its Application J. Journal of System Simulation, 2004, Vol.16 (5: 1099-1101. 7 任传祥, 张海, 范跃祖. 混合遗传-模拟退火算法在公交智能调度中的应用J. 系统仿真学报, 2005, 17(9: 1099-1101. Ren Chuanxiang, Zhang Hai, Fan Yuezu. Optimizing Dispatching of Public Transit Vehicles Using Genetic Simu

36、lating Annealing Algorithm J. Journal of System Simulation, 2005, Vol.17 (9: 1099-1101. -8- Optimization Model and Genetic Simulated Annealing Algorithm for Location and Allocation Problem of Container Central Station in Railway Hub under Stochastic Environment Wang Baohua, He Shiwei, Song Rui School of Traffic and Transportation, Beijing Jiaotong Uni