城区公路选址问题.doc

《城区公路选址问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于区域搜索的转弯点选址问题摘要本文研究的是公路转弯点的选址问题。由于题目中计划修建公路的区域内各段的单位建设费用不同，根据单位建设费用的大小将修路区域分区，将问题转化为一个优化运输费用的公路交通枢纽的选址问题。建立转弯点的区域搜索模型，分段求出各个区域内的建设费用即可得到公路建设的总费用，再从中选择最优的布局方案即可确定公路转弯点的位置。问题一：通过对区域内网格点位置的搜索从而得出使目标函数达到最优的选址方案，即可确定公路转弯点的位置，为或，此时的建设总费用为14.7068百万元。问题二：运用问题一建立的布局模型，将区域内的网

2、格点两两随机组合，再从中筛选出最优的转弯点布局方案，此时的转弯点位置为，公路建设总费用为14.6241百万元。问题三：根据对计划修路区域的连续性分析，可以初步确定网格线上最佳的选址区域，再对搜索步长进行限制，即可得出，网格线上最佳的转弯点位置，即当步长为0.01时，转弯点位置为和，此时的公路建设总费用为14.487百万元。问题四：以问题三确定的转弯点为搜索中心，将搜索范围由网格线扩大为区域内任意点，得出当步长为0.1时的转弯点位置为，此时的建设总费用为14.446百万元。问题五：在区域内任意选择一点作为转弯点修建公路，则在与转弯

3、点距离足够小的位置处单位建设费用可以近似看做不变，然后对整段路进行积分便可得出公路建设的总费用，再利用区域搜索模型找出最佳的转弯点位置为，建设总费用为14.708百万元。关键词：枢纽选址，区域搜索，布局模型一、问题重述某区政府计华在下列区域（见图1）修建一条从A（0,9）到B（9,0）的直线型公路，由于涉及路面拆迁等因素，各地段建设费用有所不同，图1中的数字代表该区域公路单位建设费用（单位：百万元）。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网格的边界上建设费用按该地区最小单位费用计算。请你按建

4、设部门的如下具体要求，从建设费用最省的角度，给出最优的方案。（1）公路至多只能有1个转弯点，且转弯点只能建在图1所示的网格点上。（2）公路至多可以有2个转弯点，且转弯点只能建在图1所示的网格点上。（3）公路至多只能有2个转弯点，且转弯点只能建在图1所示的网格线上。（4）公路至多只能有2个转弯点，转弯点可以建在图1所示区域的任何位置。（5）如果各区域的单位建设费用为（百万元），公路至多只能有1个转弯点，转弯点可以建在图1所示区域的任何位置。图1计划修建公路的区域一、模型假设1.不考虑转弯点的设置对公路建设费用的影响。2.在区域内设

5、置转弯点不受地形条件的限制。二、符号说明：区域内任意点的横坐标；：区域内任意点的纵坐标；：区域内任意点所在区域的单位建设费用；：区域中任意两点之间的水平距离；：单位建设费用为1的区域；：单位建设费用为1.1的区域；：单位建设费用为1.2的区域；：单位建设费用为1.3的区域；：单位建设费用为1.4的区域；：各段公路的修建费用；：修建公路的总费用；：公路转弯点的个数；：区域中的所有点组成的集合；：任意两点之间的距离组成的集合；：区域中的所有网格点集合；：区域中的所有网格线点集合；：区域中的所有点组成的集合；：网格点上的转弯点；：网格

6、线上的转弯点；：区域中的任意位置的转弯点；三、问题分析题目要求设计公路转弯点的位置，使得从图中A（0,9）到B（9,0）修建的一条直线型公路的费用最少。由于公路经过的区域各段的单位建设费用不同，所以在选择公路转弯点的时候既要考虑到公路的长度对修建费用的影响又要令公路经过的区域单位建设费用尽可能低，从而使得总的修建费用最少。可以将问题转化成一个公路交通枢纽的选址问题，要求公路造价最低，即是在A、B两点之间选择中转的交通枢纽，使得从A到B的运费最低。问题一：要求公路至多只有一个转弯点，即为一元交通枢纽布局问题，在网格点集中任意选取一

7、点作为公路的转弯点建立目标函数，通过限制条件得出公路修建费用最低的方案。问题二：要求公路至多可以有两个转弯点，且转弯点均在网格点处，这是一个二元交通枢纽布局问题。运用问题一建立的布局模型，随机地在网格点集中任意选取两个点作为公路的转弯点建立目标函数，通过不断地比较优化筛选出最优的转弯点布局，使得公路的建设费用达到最低。问题三：要求公路至多可以有两个转弯点，且转弯点均在网格线上，这也是一个二元交通枢纽布局问题。根据问题一对计划修路区域的分析，各区域内单位修建费用之间具有连续性，认为整数最优解是最靠近实数最优解的的整数解，所以可以运

8、用建立的模型在问题二中求得的转弯点附近进行寻找，以较小的精度转化为离散型问题进行解决。问题四：要求公路至多可以有两个转弯点，且转弯点可为图1所示区域中的任意点，根据问题三的思想，最佳转弯点的位置必然在问题三所得到的位置附近，同样将其转化为离散型问题，将搜索范围由