第８卷第３期 铁道科学与工程学报 ＪＯＵＲＮＡＬ ＯＦ ＲＡＩＬＷＡＹ ＳＣＩＥＮＣＥ ＡＮＤ ＥＮＧＩＮＥＥＲＩＮＧ ＶＯＩ＿８ ＮＯ．３ Ｊｕｎｅ ２０１ｌ ２０１１年６月 铁路集装箱空箱调运问题的遗传算法 段 刚 ，张慧。，陈莉 ，李引珍 ，刘永莉 ，陈志忠 （１．兰州交通大学交通运输学院，甘肃兰州７３００７０；２．兰州铁路局货运处，甘肃兰州７３００７０； ３．兰州城市学院数学学院，甘肃兰州７３００７０） 摘要：根据铁路集装箱运输的特点，对空箱调运问题进行了分析，并设计了遗传算法求解这类问题。采用整数矩阵编码， 通过对父代染色体的线性组合取整运算作为交叉算子，并做适＂３调整以保证解的可行性，同时利用矩形闭合回路调整调运 －量作为变异算子。以兰州铁路局集装箱办理站为例进行了验证，结果表明：该算法不仅效率非常高，而且可以得到问题的 多个最优解。 关键词：集装箱；空箱调运；遗传算法 中图分类号：Ｕ２９２ 文献标志码：Ａ 文章编号：１６７２—７０２９（２０１１）０２—０ｌｌ０—０６ Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒａｉｌｗａｙ ｅｍｐｔｙ ｃｏｎｔａｉｎｅｒ ａｌｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ＤＵＡＮ Ｇａｎｇ ，ＺＨＡＮＧ Ｈｕｉ ，ＣＨＥＮ Ｌｉ ，ＬＩ Ｙｉｎ．ｚｈｅｎ ，ＬＩＵ Ｙｏｎｇ．．．１ｉ，ＣＨＥＮ Ｚｈｉ—ｚｈｏｎｇ （１．Ｓｃｈｏｏｌ ｏｆ Ｔｒａｆｉｆｃ ａｎｄ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ，Ｌａｎｚｈｏｕ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ ７３００７０，Ｃｈｉｎａ ２．Ｃａｒｇｏ Ｔｒａｎｓｐｏｒｔ Ｄｅｐａｒｔｍｅｎｔ。Ｌａｎｚｈｏｕ Ｒａｉｌｗａｙ Ｂｕｒｅａｕ，Ｌａｎｚｈｏｕ ７３００７０，Ｃｈｉｎａ； ３．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｌａｎｚｈｏｕ Ｃｉｔｙ Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ ７３００７０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｅｍｐｔｙ ｃｏｎｔａｉｎｅｒ ａｌｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ｗａｓ ａｎａｌｙｚｅｄ，ａｃｃｏｒｄｉｎｇ ｔｏ ｒａｉｌｗａｙ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃ，，ａｒｉｄ ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｗａｓ ｄｅｓｉｇｎｅｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｋｉｎｄ ｏｆ ｐｒｏｂｌｅｍ ｉｎ ｔｈｅ ｔｈｅｓｉｓ．Ｗｅ ｅｍｐｌｏｙ ｉｎｔｅｇｅｒ ｍａｔｒｉｘ ｅｎｃｏｄｉｎｇ．Ｃｒｏｓｓ— ｏｖｅｒ ｏｐｅｒａｔｉｏｎ ｍａｋｅｓ ｕｓｅ ｏｆ ｉｎｔｅｇｅｒ ａｒｉｔｈｍｅｔｉｃ ｆｏｒ ａ ｌｉｎｅａｒ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ａ ｐａｉｒ ｏｆ ｐａｒｅｎｔｓ．Ｔｈｅ ａｄｊｕｓｔｍｅｎｔ ｗａｓ ａｌｓｏ ｍａｄｅ ｉｎ ｏｒｄｅｒ ｔｏ ｇｅｔ ｆｅａｓｉｂｌｅ ｓｏｌｕｔｉｏｎ．Ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｉｏｎ ａｄｊｕｓｔｓ ｔｒａｎｓｐｏｔａｔｉｏｎ ｑｕａｎｔｉｔｙ ｉｎ ｒｅｃｔａｎｇｌｅ ｃｉｒｃｕｉｔ．Ａｔ ｌａｓｔ ｔｈｅ ｌｇｏｒｉｔｈｍ ｗａｓ ｔａｅｓｔｅｄ ｂｙ ｔｈｅ ｔｒｕｅ ｄａｔａ ｏｆ Ｌａｎｚｈｏｕ Ｒａｉｌｗａｙ Ｂｕｒｅａｕ ｃｏｎｔａｉｎｅｒ ｈａｎｄｌｉｎｇ ｓｔａｔｉｏｎｓ．Ｒｅｓｕｌｔ ｉｎｄｉｃａｔｅｓ ｔｈｅ ｈｉｇｈ ｅｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｆｉｔｈｍ．Ｗｅ ａｌｓｏ ｃｏｕｌｄ ｇｅｔ ｄｉｖｅｒｓｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｔｈｒｏｕｇｈ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｎｔａｉｎｅｒ；ｅｍｐｔｙ ｃｏｎｔａｉｎｅｒ ａｌｌｏｃａｔｉｏｎ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ 由于我国地区经济发展不平衡、各区域货物流 方案并设计出高效的算法，对于减少空箱调运成 本，提高铁路运能和集装箱使用效率，具有卜分现 实的意义。 量不均衡以及集装箱办理站之间集装箱到发量的 不平衡，导致铁路适箱货源和箱源分布也不平衡。 即使在同一地区，也会因季节和时间的变化而出现 某一段时间集装箱空箱积压，另一段时问短缺的现 象，从而导致空箱调运。频繁地进行空箱调运不但 浪费铁路运能，而且空箱在运输途中支出的各种费 １ 研究现状 铁路空箱调运与空车调配『ｎＪ题无论从模 构 用也给铁路运输企业增加了负担。集装箱的日常 管理费用通常可以分为：空箱调运费、堆存费、修理 费、集装箱租赁费、吊装费和其他费用，而集装箱空 箱调运费用占总费用的１／４。因此，优化空箱调运 收稿日期： 造上还是求解方法上都非常相似，【大Ｊ此可以借鉴 熊红云等 和张得志等 采，｝｝ｊ矩阵表示染色体的 遗传算法分别求解铁路空车和空箱调运问题，他ｆ『Ｊ 基金项目：国家自然科学基金资助项目（６０８７０００８）；教育部新世纪优秀人才支持计划资助项目（ＮＣＥＴ 作者简介：段刚（１９７７一），男，吉林省吉林人，讲师，博士研究生，从事交通运输系统分析研究 通讯作者：李引珍，男，教授，博：仁生导师 第３期 段刚，等：铁路集装箱空箱调运问题的遗传算法 设计的交叉算子均对２个染色体的均值运算和取 余运算的结果进行代数和计算，从而得到新的染色 体，变异算子也都是对染色体子矩阵中的元素进行 调整，区别是一个采用整数编码，一个采用十进制 编码。果鹏文等 采用振荡法解决大规模路网上 的空车调配问题，在事先不知道某个区段空车排空 方向的前提下，预先人为指定该区段的空车排空方 向，作为初始方案，使得区段上中间站的空车流，能 够按照一定的原则归并到前方技术站；然后对初始 方案进行计算，对区段空车方向不断进行调整，反 复计算，直到指定的空车方向与计算结果相符合时 为止。雷中林等 针对运输需求等不确定性建立 了空车调配的随机机会约束模型，并设计了遗传算 法求解。林柏梁等 设计了分步优化迭代算法求 解线路能力约束下的铁路空车调配问题。还有应 用神经网络法 Ｊ、物体重心法 和区段中心优化 法 求解问题。在此，作者从铁路运输实际出发， 针对空箱调运模型，设计了一种新的遗传算法，可 以高效求解空箱调运问题。 ２空箱调运问题的数学模型 ２．１参数与变量 为空箱供应站集合，Ｓ＝｛１，２，…，ｍ｝；Ｄ 为空箱需求站集合，Ｄ＝｛１，２，…，ｎ｝；０ 为ｉ站 可供应的空箱数，口 ∈Ｚ ，ｉ∈Ｓ；６ 为 站需求的空 箱数，ｂｊ∈Ｚ ， ∈Ｄ；ｄ 为ｉ站与 站间的距离，ｉ∈ ，Ｊ ＥＤ；ｘ 为ｉ站向 站调运的空箱数，决策变量。 ２．２空箱调运模型 空箱调运模型如下： ｍｉｎｚ＝∑∑ｄｉｊ （１） ｔ ∑ ＝ ｉ∈Ｓ （２） ∑ ＝ｂ ， ∈Ｄ （３） ｘｉｊ∈Ｚ Ｕ｛０｝，ｉ∈Ｓ， ∈Ｄ（４） （１）式为目标函数，表示空箱调运的总距离最 小；（２）式与（３）式为空箱供应与需求的平衡约束； （４）式为变量的非负和整数约束。 实际上，上述模型为供需平衡的运输问题模 型。然而，由于受到铁路集装箱数量的，经常 出现部分空箱需求无法得到满足的情况，即供不应 求，这时需增加一个虚设的空箱供应站１Ｔｔ＋１，且 ｎ ＝∑ 一∑ｎＥＤ ｉ∈ ，ｄ √＝０，无法满足的空箱 需求就由虚设的空箱供应站提供，即将（２）式～ （４）式中的所有 ∈Ｓ改为ｉ∈Ｓ Ｕ｛ｍ＋１｝，这样 就可以将其转化为平衡的运输问题。对供大于求 的情况可作类似处理。 ３空箱调运问题的遗传算法 自从１９７５年Ｈｏｌｌａｎｄ提出遗传算法后，因为其 简单、鲁棒性好和并行计算等特点，从而在工程技 术、自动控制、图像处理、人工智能和管理科学等众 多领域得到了广泛应用。本文提出一种新的遗传 算法，通过交叉与变异操作，在保证解的可行性基 础上，能够快速高效求解空箱调运问题。 ３．１染色体的构成及种群的初始化 采用整数编码，以矩阵’，表示一个染色体， Ｖ： （５） 其中， ∈Ｚ Ｕ｛０｝，ｉ∈Ｓ， ∈Ｄ。显然，基因 表示ｉ站向 站调运的空箱量，这样，染色体的基因 型与其表现型完全一致，无需解码，因此以下对染 色体和解不加区分。但要使得染色体可行，必须满 足供需平衡的条件。以下种群的初始化，交叉算子 和变异算子的操作，均围绕染色体的可行性来 进行。 初始种群的产生采用下面的算法 ］： 步骤１随机产生下标ｉ和 ，其中ｉ∈Ｓ，Ｊ．∈ Ｄ； 步骤２计算 戈 ＝ｒａｉｎ｛０ ，ｂｊ｝； 步骤３更新Ⅱ 和ｂｊ，Ⅱ ＝口 — ¨ｂｊ＝ｂｊ— ｘｉｊ； 步骤４重复步骤１一步骤３，直到所有ｏ 和 ｂ 都为０。 由上述算法产生的染色体必然对应一组可行 解，其分配思想就是随机化的西北角法。 ３．２交叉算子 按交叉概率Ｐ 随机选择染色体’，ｌ和 作为 父个体，其中Ｖ ＝（ ）， ＝（ ）。为了使得交 ｌ１２ 铁道科学与工程学报 叉操作不破坏染色体的可行性，ＱｅＬ采用下面的方法产 生子代染色体Ｉ／３＝（Ｙ ）和Ｖ４＝（ ）。首先，令 Ｙｌ１＝ｌ ｌ１１＋（１一ｏ爪 ｒ．Ｊ＿ １Ｌ， ）２２１ ∑㈦ ．ｌ （６） 一＝｝ ２ ＋（１一 ） ： Ｉ（７） （ １■一 其中０＜ｏ／≤０．５，ｌ ｌ表示取下整，即 ㈦ ㈦ ｌＩ＝ｍａｘ｛Ｙ∈Ｚ Ｕ｛０｝ｌ Ｙ≤ ｝ （８） 一 ２“ ） 一 Ｙ ＝ｍａｘ｛０，卢 ｝ ∑㈦ （１０） Ｉ Ｊ ＝ｍｉｎ｛ｌ∑（似 ＋（１一 ） ）ｊ— ｌ ｉ —ｌ ∑ ｌｆ＝１ ∑（ｋ＝ｌ 《＋（１一 ） 一。 ＝Ｊ ）（１１） ＝ｍａｘ｛０，ｙ ｝ （１２） 其中，ｉ∈Ｓ√Ｅ Ｄ，ｉ和 不同时为ｌ，０＜ ≤０．５。 当ｉ＝１， ≥２时，（９）式和（１１）式的最小值皆取第 １项，而当 ＝１，ｉ≥２时，两式的最小值皆取第２ 项。 为交叉参数，是本遗传算法中最重要的参数。 实际上，文献［１］和［２］中的交叉方法可以看作是 本交叉算子的特例，即Ｏｔ取值为０．５，也就是对２ 个父代染色体的对应基因求均值。而本文中， 取 值更广泛，这样就能够扩大种群的多样性。 （９）式和（１１）式可以保证子代染色体每行的 调运量之和不会超过供应量，每列的调运量之和不 会超过需求量，（１０）式和（１２）式能够保证调运量 都非负，但却不能保证等式成立，故需要对调运量 进行调整以满足平衡条件。 以染色体Ｖ３为例，若∑Ｙ ＜ ，∑Ｙ ＜ Ｊ∈Ｄ Ｅ∈ ｂｊ ，则令 ＝ｍｉｎ｛ａ 一∑ＹｉＪ∈Ｄ ｌｊ， ｂｊ 一∑ＹＩ ＥＳ ）（１３） 更新Ｙ 令Ｙ ｌ＝ ＋Ｙ １；遍历ｉ， ，直至 所有行列都满足平衡。 ３．３变异算子 求解运输问题的表上作业法，其对基变量的调 整采用闭合回路法。该方法虽然能保证解的可行 性，但寻找闭合回路却相当耗时。本文借鉴该思 想，采用基于矩形闭合回路的方法设计变异算子， 可以大大减少计算量。 按变异概率Ｐ 选择染色体Ｖ５＝（埘 ），随机 选择ｉ０，Ｊｏ，ｉｌ， ｌ，其中ｉｏ∈Ｓ，Ｊｏ∈Ｄ，ｉＩ∈Ｓ／｛ｉ（）｝， １∈Ｄ／｛Ｊｏ｝。当Ｗｉｏ，］ｏｗ ，１＞０，即ＷｍＪ０和Ｗ Ｊｌ同 时为正数，取６＝ｍｉｎ｛Ｗ ，Ｗ ．｝。然后在矩形闭 合回路Ｗ ，Ｗ㈨，Ｗ ，Ｗ 中进行调整，令 Ｗｉｄｏ＝Ｗｉｄｏ一６ （１４） ｗｉ ＝ｗ 一６ （１５） ｗｉ￣ｌ＝ｗ ｌ＋６ （１６） ｗｉ￣０＝Ｗ ＋６ （１７） 其余基因 ，取值不变，组成新的染色体 评价函数和选择操作 由于染色体的可行性以及目标函数为线性函 数，所以取目标函数为评价函数，即： Ｅｖａｌ（ ）＝∑∑ｃ∈ ７∈Ｄ （１ ８） 其中，Ｖ＝（ ）。 采用基于轮盘赌的选择策略，详见文献［９］。 ３．５算法步骤 步骤ｌ初始化种群； 步骤２通过交叉操作和变异操作产生子代 染色体； 步骤３计算每个染色体的评价函数，并记录 最优染色体； 步骤４通过轮盘赌选择染色体； 步骤５ 重复步骤２一步骤４，直到满足停止 条件。 其中，停止条件为可以定义为进化的最大代 数，也可以通过比较前后两代最优染色体的变化情 况确定停止条件，本文采用前者。 ４实验仿真 以兰州铁路局为例，对该局内集装箱办理站问 的空箱调运进行优化。图ｌ所示为 州局的１８个 集装箱办理站。这里取２００９年某月的集装箱运输 数据，用以验证算法的有效性。各个集装箱办理站 的空箱需求量、供应量以及两站之间的距离如表１ 所示，其中，距离为两站之间的最短路径长度。 于绿化、中堡、张家祠和鸳鸯镇４个集装箱办理站 到发集装箱数量平衡，故没有出现在表１中。【大】为 总需求量为５５４箱，而总供应量只有３４４箱，所以 增加虚设供应站５ ，其供应量为２１０箱。 第３期 段 刚，等：铁路集装箱空箱调运问题的遗传算法 １１３ 为了寻求交叉概率、变异概率以及交叉参数 的最佳取值，利用ＶＣ６．０编程，在Ｃｏｒｅ ２ Ｄｕｏ＆ ２．２ＧＨｚ、ｌＧ ＤＤＲ２的惠普笔记本上运行通过，在 每组概率组合下都做了１０次测试，其中群体规模 为２Ｏ，遗传代数为６００。首先令Ｏ／＝０．１，Ｐ ＝ ０．１，交叉概率Ｐ 在（０，１）区间每次变化０．０５，评 价函数的平均值和标准差的变化见图２和图３。 显然ｊ Ｐ 的最优取值为０．６５，在此基础上，变异概 率Ｐ 在（０，１）内每次变化０．０５，同样可以得到评 价函数的均值和标准差变化情况，见图４和图５。 图１ 兰州铁路局集装箱办理站示意图 Ｆｉｇ．１ Ｌａｎｚｈｏｕ Ｒａｉｌｗａｙ Ｂｕｒｅａｕ ｃｏｎｔａｉｎｅｒ ｈａｎｄｌｉｎｇ ｓｔａｔｉｏｎｓ 从图中可以看出，当Ｐ 大于０．６５时，评价函数的 均值几乎相同，其标准差也比较接近，且都比较小， 因此，选取Ｐ ＝０．６５。 注：图中带数字编号的车站表示集装箱办理站 表ｌ集装箱办理站间距离及供需表 Ｔａｂｌｅ １ Ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｃｏｎｔａｉｎｅｒ ｈａｎｄｌｉｎｇ ｓｔａｔｉｏｎｓ ａｎｄ ｓｕｐｐｌｙ ａｎｄ ｄｅｍａｎｄ ｑｕａｎｔｉｔｙ 粤１塞．４９×ｌＯｓ １．４８ｘｌ０ｓ １．４７×１０ 蜷 闺 基Ｌ ４６×１０ １．４５ｘ１０ ‘ ‘ ‘ ‘ ‘ ‘ Ｑ ’ 变异概率 交叉概率 图２不同交叉概率下评价函数平均值 Ｆｉｇ．２ Ｔｈｅ ａｖｅｒａｇｅ ｖａｌｕｅ ｏｆ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ ｕｎｄｅｒ ｄｉｆ－ ｆｅｒｅｎｔ ｃｒｏｓｓｏｖｅｒ ｐｒｏｂａｂｉｌｉｔｙ 图５不同变异概率下评价函数标准差 Ｆ．ｇ．５ Ｔｈｅ ｓｔａｎｄａｒｄ ｄｅｖｉａｔｉｏｎ ｖａｌｕｅ ｏｆ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｍｕｔａｔｉｏｎ ｐｒｏｂａｂｉｌｉｔｙ 篓加。。 ｝ Ｖ Ｖ ００ｏ 。２５００ ／＼八 ／ ＼ 在最优交叉概率和变异概率组合下，令 在区 间［０．０５，０．５］内每次变化０．０５，得到评价函数的均 值和标准差，如图６和图７所示。当 取值为０．１， ０．３５和０．５时，评价函数平均值都比较小，标准差也 相差不多，所以可以任选一个，本文取 ＝０．１。 １．４５×Ｉ 露１．４４×１ 籁１．４４ｘ １ 阁１．４４×ｌ ￥１．４３ｘ ｌ 图６ 不同交叉参数值下评价函数均值 Ｆｉｇ．６ Ｔｈｅ ａｖｅｒａｇｅ ｖａｌｕｅ ｏｆ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ ｕｎｄｅｒ ｄｉｆ－ ｆｅｒｅｎｔ ｃｒｏｓｓｏｖｅｒ ｐａｒａｍｅｔｅｒ １１４ 铁道科学与工程学报 ２０１１年６月 ８ｏｏ ｒ 且还能得到另外一组最优解，如表３所示。不难看 出，在表２中由金昌，兰州北，嘉峪关和白银市组成 亡０ Ｌ——— ———。。 ———‘——— ———— ——— ——— ——— —— ０．０５ ０．１５ ０．２５ ０．３５ ０．４５ ｝＼√ ＼／＾＼／＼ 交叉参数值 的闭合回路里，对调运量进行了１个单位的调整， 即得到表３，而这正是本文中的变异操作。所以使 用该遗传算法，不仅能在不同的计算中得到这２组 最优解，还能在一次计算中同时得到这２组最优 解，而这是ＬＩＮＧＯ软件做不到的。 １．６Ｏ 图７ 不同交叉参数值下评价函数标准差 Ｆｉｇ．７ Ｔｈｅ ｓｔａｎｄａｒｄ ｄｅｖｉａｔｉｏｎ ｖａｌｕｅ ｏｆ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｃｒｏｓｓｏｖｅｒ ｐｒｏｂａｂｉｌｉｔｙ 在以上各参数最优取值下，通过本文设计的遗 传算法，当计算到５２０代时达到最优，评价函数为 １４３６８９，收敛过程如图８所示（其中，从３９０代到 阁１．５６ １．５２ １．４８ １．４４ ５１０代，评价函数都为１４３７２０，与最优评价函数只 相差３１，图中显示不明显）。采用ＬＩＮＧＯ ９．０软件 计算得到的最优解如表２所示，计算时间不到１ Ｓ （ＬＩＮＧＯ ９．０最小计时单位为Ｓ）。本遗传算法的 计算时间仅为０．１４ Ｓ，不但能得到上述最优解，而 １．４０ 导晶莹呈量 曼萤萤莩詈莩萤萤誊 代数 图８ 遗传算法收敛图 Ｆｉｇ．８ Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｃｏｎｖｅｒｇｅｎｃｅ ｆｉｇｕｒｅ 表２应用ＬＩＮＧＯ计算得到的最优调运量 Ｔａｂｌｅ ２ Ｔｈｅ ｂｅｓｔ ｓｏｌｕｔｉｏｎ ｓｏｌｖｅｄ ｂｙ ＬＩＮＧＯ ｓｏｆｔｗａｒｅ ｃｏｎｔａｉｎｅｒ 整得到子代染色体，变异操作则采用矩形闭合凹路 ５结论 法。通过对兰州铁路局集装箱办理站的实例计算， 表明该算法不但效率非常高，而且还能得到小同的 最优解。关于交叉参数 的取值问题，本文采用固 定值，通过测试找到其最佳取值。如果在计箅过程 中，对 进行调整，采用变参数法，或者直接对其进 行编码并参与交叉和变异操作进行自适应调整，这 铁路集装箱空箱调运优化模型与空车调运模 型完全相同，因此，设计高效的算法就成为解决这 类问题的关键。本文提出的遗传算法，交叉操作是 对父代染色体进行线性组合并取整后经过适当调 第３期 段刚，等：铁路集装箱空箱调运问题的遗传算法 ｌｌ５ 样会进一步提高该算法的效率，以利于求解更大规 模的问题，这将是我们下一步要研究的内容。 参考文献： ［１］熊红云，鲁五一，温红艳．铁路空车调配问题的遗传 启发算法［Ｊ］．中国铁道科学，２００２，２３（４）：１１８— １２１． ＸＩＯＮＧ Ｈｏｎｇ—ｙｕｎ，ＬＵ Ｗｕ—ｙｉ，ＷＥＮ Ｈｕｎｇ—ｙａｎ．Ｈｅｒｅｄｉ— ｔａｒｙ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｅｍｐｔｙ ｃａｒ ｄｉｓｔｉｒｂｕｔｉｏｎ ｉｎ ｒａｉｌ— ｗａｙ ｔｒａｎｓｐｏｒｔａｔｉｏｎ［Ｊ］．Ｃｈｉｎａ Ｒａｉｌｗａｙ Ｓｃｉｅｎｃｅ，２００２， ２３（４）：１１８—１２１． ［２］张得志，谢如鹤，黄孝章．铁路集装箱空箱调度模型 及求解算法［Ｊ］．中国铁道科学，２００３，２４（３）：１２５— １２９． ＺＨＡＮＧ Ｄｅ—ｚｈｉ，ＸＩＥ Ｒｕ—ｈｅ，ＨＵＡＮＧ Ｘｉａｏ—ｚｈａｎｇ．Ｄｉｓ— ｐａｔｃｈ ｍｏｄｅｌ ａｎｄ ｓｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｒａｉｌｗａｙ ｅｍｐｔｙ ｃｏｎ— ｔｉａｎｅｒ［Ｊ］．Ｃｈｉｎａ Ｒａｉｌｗａｙ Ｓｃｉｅｎｃｅ，２００３，２４（３）：１２５— １２９． ［３］果鹏文，褚江，林柏梁．用振荡法解大规模路网上 的空车调配问题［Ｊ］．中国铁道科学，２００２，２３（４）： ｌ１１一ｌ１７． ＧＵＯ ＰｅＩｌｇ—ｗｃｎ，ＣＨＵ Ｊｉａｎｇ，ＬＩＮ Ｂｏ—ｌｉａｎｇ．Ｒｅｉｔｅｒａｔｉｖｅ ￣ｔｉｎｇ ｍｅｔｈｏｄ ｏｆ ｅｍｐｔｙ ｗａｇｏｎ ｏｎ ｌａｒｇｅ—ｓｃａｌｅ ｒａｉｌｗａｙ ｎｅｔｗｏｒｋ［Ｊ］．Ｃｈｉｎａ Ｒａｉｌｗａｙ Ｓｃｉｅｎｃｅ，２００２，２３（４）：１１１ 一ｌｌ７． ［４］雷中林，何世伟，宋瑞，等．铁路空车调配问题的 随机机会约束模型及遗传算法［Ｊ］．铁道学报，２００５， ２７（５）：１—５． ＬＥ！Ｚｈｏｎｇ－ｌｉｎ，ＨＥ Ｓｈｉ—ｗｅｉ，ＳＯＮＧ Ｒｕｉ，ｅｔ ａ１．Ｓｔｏｃｈａｓｔｉｃ ｃｈａｎｃｅ——ｃｏｎｓｔｒａｉｎｅｄ ｍｏｄｅｌ ａｎｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｅｍｐｔｙ ｅａｒ ｄｉｓｔｉｒｂｕｔｉｏｎ ｉｎ ｒａｉｌｗａｙ ｔｒａｎｓｐｏｒｔａｔｉｏｎ［Ｊ］．Ｊｏｕｒ－ ｎａｌ ｏｆ ｔｈｅ Ｃｈｉｎａ Ｒａｉｌｗａｙ Ｓｏｃｉｅｔｙ，２００５，２７（５）：１—５． ［５］林柏梁，乔国会．基于线路能力约束下的铁路空车调 配迭代算法［Ｊ］．中国铁道科学，２００８，２９（１）：９３— ９６． ＬＩＮ Ｂｏ—ｌｉａｎｇ，ＱＩＡＯ Ｇｕｏ—ｈｕｉ．Ｉｔｅｒａｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｏｆ ｒａｉｌ— ｗａｙ ｎｅｔｗｏｒｋ ｅｍｐｔｙ ｅａｒｓ ｄｉｓｔｉｒｂｕｔｉｏｎ ｂａｓｅｄ ｏｎ ｒｅｓｔｉｒｃｔｉｏｎ ｏｆ ｒｏｕｔｅ ｃａｐａｃｉｔｙ［Ｊ］．Ｃｈｉｎａ Ｒａｉｌｗａｙ Ｓｃｉｅｎｃｅ，２００８，２９ （１）：９３—９６． ［６］党建武．神经网络在铁路空车调度问题中的应用［Ｊ］． 兰州铁道学院学报，１９９９，１８（１）：７７—８５． ＤＡＮＧ Ｊｉａｎ－ＷＨ．Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ ｔｏ ｅｍｐｔｙ ｃａｒｉｒａｇｅ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ｒａｉｌｗａｙ ｔｒａｎｓｐｏｒｔａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｌａｎｚｈｏｎ Ｒａｉｌｗａｙ Ｉｎｓｔｉｔｕｔｅ，１９９９，１８（１）：７７—８５． ［７］纪嘉伦，林柏梁，李福志，等．用重心优化方法求解 铁路网上空车调配问题［Ｊ］．铁道学报，２００１，２３（３）： １０９—１１３． ＪＩ Ｊｉａ・ｌｕｎ，ＬＩＮ Ｂｏ—ｌｉｎａｇ，ＬＩ Ｆｕ—ｚｈｉ，ｅｔ ａ１．Ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｅｍｐｔｙ ｗａｇｏｎｓ ｏｎ ｒａｉｌｗａｙ ｎｅｔｗｏｒｋ ｂｙ ｕｓｉｎｇ ｔｈｅ ｃｅｎｔｅｒ—ｏｆ —ｇｒａｖｉｔｙ—ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ｃｈｉｎａ Ｒａｉｌｗａｙ Ｓｏｃｉｅｔｙ，２００１，２３（３）：１０９—１１３． ［８］果鹏文，林柏梁，余洋．大规模路网上空车调配的 区段中心优化法［Ｊ］．中国铁道科学，２００１，２２（２）： １２２—１２８． ＧＵＯ Ｐｅｎｇ—ｗｅｎ，ＬＩＮ Ｂｏ—ｌｉａｎｇ，ＹＵ Ｙａｎｇ．Ｔｈｅ ｓｅｃｔｉｏｎ ｃｅｎｔｅｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｏｆ ｅｍｐｔｙ ｃａｒ ａｄｊｕｓｔｍｅｎｔ ｏｎ ｌａｒｇｅ—ｓｃａｌｅ ｒａｉｌｗａｙ ｎｅｔｗｏｒｋ［Ｊ］．Ｃｈｉｎａ Ｒａｉｌｗａｙ Ｓｃｉｅｎｃｅ， ２００１，２２（２）：１２２—１２８． ［９］Ｌｉｕ Ｂ．Ｓｔａｃｋｅｌｂｅｒｇ—Ｎａｓｈ ｅｑｕｉｌｉｂｒｉｕｍ ｆｏｒ ｍｕｌｔｉｌｅｖｅｌ ｐｒｏ— ｇｒａｍｍｉｎｇ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ｆｏｌｌｏｗｅｒｓ ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｍａｔｈｅｍａｔｉｃｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ， ｌ９９８，３６（７）：７９—８９．
