轴辐式输运网络中的选址优化问题研究

《轴辐式输运网络中的选址优化问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、＇ｒｔｒ瓣啼Ｊ夺固种遷若东大畫＾Ｕｉ打ｖｅｒｓｉｔｏｆＳｃｉｅ打ｃｅａｎｄ了ｅｃｈｎｏｌｏｏｆＧｈｉ打ａｙｇｙｉ”梦義硕±学位论文隊戀某处■：诗；论文题目抽輪式输运柯絡中的速化化化巧题巧奔‘作者姓名炼晚旅理冷学科专业计算机软钟与导师姓名徐斋教狡完成时间二〇—六年巧月中国科学技术大学硕±学位论文＠轴福式输运网络中的选址优化问题硏究作者姓名：陈晓欣学科专业：计算机软件与理论导师姓名：徐云教授

2、—完成时间：二〇六年四月二十曰ｊＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙｏｆＣｈｉｎａＡ，ＤｉｓｓｅｒｔａｔｉｏｎｆｏｒＭａｓｔｅｒｓＤｅｒｅｅｇ戀ＲｅｓｅａｒｃｈｏｎＬｏｃａｔｉｏｎＯｔｉｍｉｚａｔｉｏｎＰｒｏｂｌｅｍｉｎｐＨｕｂ－ａｎｄ－ＳｐｏｋｅＴｒａｎｓｐｏｒｔａｔｉｏｎＮｅｔｗｏｒｋ’Ａｕ化ｏｒｓＮａｍｅ：ＸｉａｏｘｉｎＣｈｅｎＳｐｅｃｉａｌｉｔｙ：ＣｏｍｐｕｔｅｒＳｏｆｔｗａｒｅａｎｄＴｈｅｏｒｙＳｕｐｅｒｖｉｓ

3、ｏｒ：Ｐｒｏｆ．ＹｕｎＸｕ°＾Ｆｉｎｉｓｈｅｄｔｉｍｅ；Ａｒｉｌ２０２０１６ｐ，中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研光工作所取得的成果。除已特别加Ｗ标注和致谢的地方外，论文中不包含任何他人己经发表或撰写过的研究成果一。与我同工作的Ｈ志对本研究所做的贡献均已化论文中作了明确的说明。：Ｈ期．作者签名：；三替签字感、如中国科学技术大学学位论文授权使用声明一作为申请学位的条件之，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即

4、；学校有权按有关规定向国家有关部口或机构送交论文的复印件和化子版，允许论文被查阅和借阅，可Ｗ将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可Ｗ采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相＾致。保密的学位论文在解密后也遵守此规定。本巧□保密（年）作者签名：导师签名：＾＾签字日期、：：Ｍｆ？．５１０签字日期摘要摘要、随着经济全球化不断发展，Ｗ枢纽为核屯的轴福式输运网络是整合输居资源、提高资源利用率、降低输运成本的有效网

5、络结构，己成为现代输运网络结构发展的主流趋势。具有合并转发功能的枢纽和具有运输流量优势的轴线作为轴福式输运网络的重要组成部分，对整个网络的运营有着重大影响，因此，合理的枢纽及轴线选址极其重要。枢纽选址问题和轴线选址问题是轴福式输运网络设计中研究选址优化的两大热点，其中，建立符合实际的选址模型和设计高效快速的优化算法是关键研究。本文对枢纽选址问题中的多分配枢纽中位选址和轴线选址问题中的变折扣轴线选址进行了深入研究，主要工作包括：（１）多分配－枢纽中位问题的算法优化传统用于求解多分配枢纽中位问题的算法在寻找最优

6、枢纽集的过程中，ＯＤｉ－－需要计算每个ＯｒｉｎＤｅｓｔｉｎａｔｉｏｎ流经过集合中任意枢纽对ｂａｉｒ（ｇ）（Ｈｕｐ）的中转成本一，存在大量重复计算现象。为此，我们提出种巧储及索引的方法，即先通过预处理将每个０Ｄ流经过所有潜在枢纽对的中转成本存储起来，再在需要一时直接进行索引查找，，它将每个潜在枢。对于索引我们设计了个哈希函数纽对映射到唯一的整型数值，建立哈希索引，从而实现快速查找。结合该存储及索引的方法，我们实现了优化的枚举算法和优化的禁忌搜索算法。在ＣＡＢ（ＣｉｖｉｌＡｅｒｏｎａｕｔｉｃｓＢｏａｒｄ）标准数

7、据集上的计算实验表明，对于不同的数据规￣２５％的求解时间模，优化算法均能够得到最优解，且比传统算法节约〇％；当１需要选定的枢纽个数值越大时，优化算法节约的时间越多。（２）变折扣轴线选址问题的建模及求解不同于枢纽选址问题需要碗定网络中最优的枢纽节点，轴线选址问题主要一一确定网络中具有流量优势的路段轴线，对其进行运输费用折扣来实现整个网络的运输成本优化。现有研究大都采用固定折扣的轴线，因而不能有效地针对实际网络中轴线上流量差别较大的情形一。为此，我们提出个变折扣轴线选ｌｅｍｗｉｔｈＵｎｆｉｘｅｄＤｉｓｃｏ

8、ｕｎｔｓ址问题巧ＡＬＰＵＤ：ＨｕｂＡｒｃＬｏｃ地ｏｎＰｒｏｂ，使用分段）线性函数进行变折扣模拟。我们建立了ＨＡＬＰＵＤ的数学模型，探讨了问题的最优解性质，设计了拉格朗日松弛求