城区公路选址问题

关于区域搜索的转弯点选址问题 摘要 本文研究的是公路转弯点的选址问题 由于题目中计划修建公路的区域内各段的单位建设费用不同 根据单位建 设费用的大小将修路区域分区 将问题转化为一个优化运输费用的公路交通枢 纽的选址问题 建立转弯点的区域搜索模型 分段求出各个区域内的建设费用 即可得到公路建设的总费用 再从中选择最优的布局方案即可确定公路转弯点 的位置 问题一 通过对区域内网格点位置的搜索从而得出使目标函数达到最优的 选址方案 即可确定公路转弯点的位置 为或 此时的建设总费用 6 5 5 6 为 14 7068 百万元 问题二 运用问题一建立的布局模型 将区域内的网格点两两随机组合 再从中筛选出最优的转弯点布局方案 此时的转弯点位置为 公 7 44 7和 路建设总费用为 14 6241 百万元 问题三 根据对计划修路区域的连续性分析 可以初步确定网格线上最佳 的选址区域 再对搜索步长进行限制 即可得出 网格线上最佳的转弯点位置 即当步长为 0 01 时 转弯点位置为和 此时的公路建设总费用为 5 6 7 3 62 14 487 百万元 问题四 以问题三确定的转弯点为搜索中心 将搜索范围由网格线扩大为 区域内任意点 得出当步长为 0 1 时的转弯点位置为 此时 2 4 7 46 1 4 6和 的建设总费用为 14 446 百万元 问题五 在区域内任意选择一点作为转弯点修建公路 则在与转弯点距离 足够小的位置处单位建设费用可以近似看做不变 然后对整段路进行积分便可 得出公路建设的总费用 再利用区域搜索模型找出最佳的转弯点位置为 5 3 5 3 建设总费用为 14 708 百万元 关键词 枢纽选址 区域搜索 布局模型 一 问题重述 某区政府计华在下列区域 见图 1 修建一条从 A 0 9 到 B 9 0 的直 线型公路 由于涉及路面拆迁等因素 各地段建设费用有所不同 图 1 中的数 字代表该区域公路单位建设费用 单位 百万元 未标数字的任何地方单位建 设费用均为 1 图 1 的每个网格长与宽都是 1 个单位 每个网格的边界上建设 费用按该地区最小单位费用计算 请你按建设部门的如下具体要求 从建设费用最省的角度 给出最优的方 案 1 公路至多只能有 1 个转弯点 且转弯点只能建在图 1 所示的网格点上 2 公路至多可以有 2 个转弯点 且转弯点只能建在图 1 所示的网格点上 3 公路至多只能有 2 个转弯点 且转弯点只能建在图 1 所示的网格线上 4 公路至多只能有 2 个转弯点 转弯点可以建在图 1 所示区域的任何位置 5 如果各区域的单位建设费用为 百万元 公路 22 1 5 0 1 4 4 xy 至多只能有 1 个转弯点 转弯点可以建在图 1 所示区域的任何位置 图 1 计划修建公路的区域 二 模型假设 1 不考虑转弯点的设置对公路建设费用的影响 2 在区域内设置转弯点不受地形条件的限制 三 符号说明 区域内任意点的横坐标 i x i v 区域内任意点的纵坐标 i y i v 区域内任意点所在区域的单位建设费用 i h i v 区域中任意两点之间的水平距离 d 单位建设费用为 1 的区域 单位建设费用为 1 1 的区域 单位建设费用为 1 2 的区域 单位建设费用为 1 3 的区域 单位建设费用为 1 4 的区域 各段公路的修建费用 s 修建公路的总费用 S 公路转弯点的个数 P 区域中的所有点组成的集合 V 任意两点之间的距离组成的集合 L 区域中的所有网格点集合 1 V 区域中的所有网格线点集合 2 V 区域中的所有点组成的集合 V 网格点上的转弯点 i C 网格线上的转弯点 i D 区域中的任意位置的转弯点 i E 四 问题分析 题目要求设计公路转弯点的位置 使得从图中 A 0 9 到 B 9 0 修建的 一条直线型公路的费用最少 由于公路经过的区域各段的单位建设费用不同 所以在选择公路转弯点的时候既要考虑到公路的长度对修建费用的影响又要令 公路经过的区域单位建设费用尽可能低 从而使得总的修建费用最少 可以将 问题转化成一个公路交通枢纽的选址问题 要求公路造价最低 即是在 A B 两 点之间选择中转的交通枢纽 使得从 A 到 B 的运费最低 问题一 要求公路至多只有一个转弯点 即为一元交通枢纽布局问题 在 网格点集中任意选取一点作为公路的转弯点建立目标函数 通过限制条件得 1 V 出公路修建费用最低的方案 问题二 要求公路至多可以有两个转弯点 且转弯点均在网格点处 这是 一个二元交通枢纽布局问题 运用问题一建立的布局模型 随机地在网格点集 中任意选取两个点作为公路的转弯点建立目标函数 通过不断地比较优化筛 1 V 选出最优的转弯点布局 使得公路的建设费用达到最低 问题三 要求公路至多可以有两个转弯点 且转弯点均在网格线上 这也 是一个二元交通枢纽布局问题 根据问题一对计划修路区域的分析 各区域内 单位修建费用之间具有连续性 认为整数最优解是最靠近实数最优解的的整数 解 所以可以运用建立的模型在问题二中求得的转弯点附近进行寻找 以较小 的精度转化为离散型问题进行解决 问题四 要求公路至多可以有两个转弯点 且转弯点可为图 1 所示区域中 的任意点 根据问题三的思想 最佳转弯点的位置必然在问题三所得到的位置 附近 同样将其转化为离散型问题 将搜索范围由网格线扩大为任意点 找出 区域内的最佳转弯点位置 问题五 由于各个区域内的单位建设费用与所修建公路的位置有关 且公 路至多只能有 1 个转弯点 在区域内任意选择一点作为转弯点修建公路 则在 与转弯点距离足够小的位置处公路的单位建设费用可以近似看做与转弯点相同 然后通过积分可以得出公路建设的总费用 通过比较就可以得出最优的转弯点 的位置 五 模型建立与求解 5 1 问题一 至多设置一个网格点上的转弯点 5 1 1 对计划修建公路区域的三维模拟 题目要求修建公路的区域内单位建设费用不同 这将对公路转弯点的选址 造成影响 首先我们将各区域的单位建设费用作为一个维度 即对于点集中V 的任意点都具有一个单位建设费用 由于题目给出每个网格的边界上建设 i v i h 费用按该地区最小单位费用计算 则计划修建公路的区域就为G 0 0 1 11 0 1 12 0 1 1 0 0 1 1 11 1 1 12 1 1 1 1 0 2 1 11 2 1 12 2 1 2 2 0 1 2 ii ii ii iiiiiiiii xh xh Gxh y hy hy hx y h 如此便得到了计划修建公路区域的阶梯状三维图 如图 2 所示 0123456789 0 1 2 3 4 5 6 7 8 9 A B 图 2 计划修建公路区域的三维模拟 则在每一个单位修建费用水平上修建公路的费用 iji slh 若公路经过区域交界的点为和 区域交界的点为和 1 v 2 v 3 v 4 v 区域交界的点为和 区域交界的点为和 则任意一段路 5 v 6 v 7 v 8 v 建设费用 ij vv 其中 22 iijiji sxxyyh 1 2 3 i j 在区域内的公路的修建费用为 2222 1122 y y y y AABB sx xx xh 在区域内的公路的修建费用为 2222 31314242 y y y ysx xx xh 在区域内的公路的修建费用为 2222 53536464 y y y ysx xx xh 在区域内的公路的修建费用为 2222 75758686 y y y ysx xx xh 在区域内的公路的修建费用为 22 8787 y ysx xh 修建公路的总费用为各区域内公路修建费用的总和S 即 S sssss 22 11 nn iijiji ii Ssxxyyh 为公路穿过区域交界点的个数 A B 两点只记其中一个 n 根据题目要求 要使修建的直线型公路的费用最少 即是通过对公路转弯 点的位置的选择 来使得各个单位修建费用水平上修建公路的费用之和最小 i s 即最小 S 将计划修建公路的区域记作 则目标为最小化修建公路的总费 GV L 用 min S 123 i i vV stCPi 1 123 ij ij vV vV Xi j 即 ij iji vV vV SXs 123 ij ijiji vV vV SXlhi j 01 ijij XvV vV 决策变量 0 1 ij ij ij vv X vv 与之间有连接 与之间无连接 5 1 2 选取最佳的转弯点 根据题目所给图形 所要修建的公路 AB 穿过矩形区域的对角线 对角线上 半区公路的平均单位修建费用为 1 104 百万元 下半区的平均单位修建费用为 1 193 百万元 如表 1 所示 表 1 对角线上下区建设费用的比较 单位 百万元 单位建设费用 1 01 11 21 31 4 平均建设费用 上半区 1612840 51 104 下半区 1161283 51 193 根据表格所得出的数据 公路修建在对角线的上半区的平均修建费用远远低于 下半区的平均修建费用 所以建设的道路必然经过对角线的上半区 即公路的 转弯点将会从上半区的网点中选取产生 在区域中的所有网格点集合中随机选取上半区中的任意一点作为转G 1 V i C 弯点 连接 沿和修建公路 则修建公路的总费用AB i C A i C B 1 22 i i ijiji vV Ssssss xxyyh 将放入集合中 再选取下一个网格点作为新的转弯点 i S min ii SSC j C 同样的方法求解以为转弯点修建公路的总费用 比较两个费用和的 j C j S i S j S 大小 选择其中较小的一个加入集合中以取代集合中的原有元素 完成min S 对角线上半区所有网格点的选择和比较 得到集合 此时的 00 min SSC 网格点即为题目要求的最佳转弯点 使得公路的建设总费用达到最小值 运 0 C 算的过程如图 3 所示 Y N 开始 选取新的转弯点 j C 计算点建设费用 j s ji ss ji sSs加 m i n 中替换 得到minS 图 3 选取最佳转弯点的流程图 5 1 3 转弯点的设置方案 问题一要求选择的转弯点个数至多为 1 即为 1P 1123 i i v V Ci 运用 MATLAB 编程运算求得 当时 达到最小值 0 6 5 5 6C或S 为 结果如表 2 所示 0 14 7068 S 表 2 至多选取一个转弯点的方案 转弯点坐标公路长度经过的区域边界点的数目建设总费用 6 513 042 814 7068 5 6 13 042 814 7068 建设公路的路径如图 3 所示 0123456789 0 1 2 3 4 5 6 7 8 9 A C0 C0 B 图 3 选取一个转弯点时的路径图 由图可以看出 两种设置方案的转弯点呈对称分布 5 2 问题二 至多设置两个网格点上的转弯点 5 2 1 筛选最佳的转弯点 根据问题一建立的布局模型 在每一个不同的单位修建费用区域内修建公 路的费用 其中 22 iijiji sxxyyh 1 2 3 i j 当设置的公路转弯点的个数少于两个的时候 布局方案见于问题一 在 设置一个转弯点 公路的建设总费用达到最小值 为 0 6 5 5 6C或S 0 14 7068 S 当设置的转弯点的个数为两个时 每个区域内公路经过的边界点的个数至 多为六个 各个区域内修建公路所需要的建设费用为 在区域内的公路的修建费用为 112 AiB slllh 222222 111212 y y y y y y AAiBiB sx xx xx xh 在区域内的公路的修建费用为 1223 ij slllh 22 2222 12122323 y y y y y y ijij sx xx xx xh 在区域内的公路的修建费用为 1223 ij slllh 在区域内的公路的修建费用为 1223 ij slllh 在区域内的公路的修建费用为 1223 ij slllh 修建公路的总费用为各区域内公路修建费用的总和S 即 S sssss 22 11 nn iijiji ii Ssxxyyh 为公路穿过区域边界点的个数 A B 两点只记其中一个 n 优化即为筛选网格点使得建设公路的总费用最小 即 i CS min S 123 i i vV stCPi 1 123 ij ij vV vV Xi j 即 ij iji vV vV SXs 123 ij ijiji vV vV SXlhi j 01 ijij XvV vV 根据问题一的推论结果 公路转弯点的选址必然落在区域的上半区内 G 在区域中的所有网格点集合中随机选取上半区中的任意两点 构成组G 1 V i C j C 合作为公路的转弯点 将其与连接 沿 和 iij HCC AB i C A ij CC 修建公路 则修建公路的总费用 j C B 1 22 i i ijiji vV Ssssss xxyyh 将放入集合中 再选取下一组网格点作为新的两个转弯 i S min ii SSH j H 点 同样的方法求解以组合为转弯点修建公路的总费用 比较两个费用 j H j S 和的大小 选择其中较小的一个加入集合中以取代集合中的原有元 i S j Smin S 素 完成对角线上半区所有网格点的选择和比较 得到集合 00 min SSH 此时的网格点即为题目要求的两个最佳转弯点 使得公路的建 000 HCC 设总费用达到最小值 5 2 2 转弯点的布局方案 问题二要求选择的转弯点个数至多为 2 即为 1 或 2 的情况问题P1P 一已经进行了讨论 下面讨论的情况 2P 2123 i i vV Ci 运用 MATLAB 编程运算求得 当时 即两个转弯点 0 7 4 4 7H 的坐标分别为时 建设公路所需要的总费用达到最小值 为 7 44 7和S 结果如表 3 所示 0 14 6241 S 表 3 至多选取两个转弯点的方案 转弯点个数 012 转弯点坐标 6 5 5 6 7 44 7 cost zeros 10 10 A 0 9 B 9 0 x y for i 0 9 for j 0 9 x i 1 j 1 i y i 1 j 1 j yy j xx i xx half yy half cc s 0 for k i 1 1 0 yy yy j 9 i k 9 xx xx k end for l i 1 9 yy l 9 j i 9 yy xx l xx end for p 0 j 1 xx p i 9 j 9 xx yy yy p end for q j 1 9 xx xx q 9 i j 9 yy yy q end xx sort xx yy sort yy yy yy end 1 1 for g 1 18 xx half xx half xx g xx g 1 2 yy half yy half yy g yy g 1 2 cc cc yy g 1 yy g 2 xx g 1 xx g 2 0 5 if xx half g round xx half g end xx half ceil xx half yy half ceil yy half xx half xx half 0 1 yy half yy half 0 1 s cc g price xx half g yy half g s end cost i 1 j 1 s end end minnist min min cost aa bb find cost minnist cross point aa 1 bb 1 xxx yyy meshgrid 0 9 surf xxx yyy cost 14 问题二 clc clear price xlsread xls cost zeros 10 10 10 10 A 0 9 B 9 0 for i 0 9 for j 0 9 for r 0 9 for t 0 9 xx half yy half cc s 0 xx1 yy1 xx2 yy2 xx3 yy3 if i 0 yy1 9 1 j xx1 zeros 1 9 j 1 else for k i 1 0 yy1 yy1 j 9 i k 9 xx1 xx1 k end end if j 9 xx1 0 i xx1 yy1 9 ones 1 i 1 yy1 else for q j 9 xx1 xx1 q 9 i j 9 yy1 yy1 q end end xx1 sort xx1 yy1 sort yy1 yy1 yy1 end 1 1 2 B if t 0 xx2 r 9 yy2 zeros 1 9 r 1 else for p 0 t xx2 p r 9 t 9 xx2 yy2 yy2 p end end if r 9 yy2 0 t yy2 xx2 9 ones 1 t 1 xx2 else for l r 9 yy2 l 9 t r 9 yy2 xx2 l xx2 end end xx2 sort xx2 yy2 sort yy2 yy2 yy2 end 1 1 1 1 if r i yy3 j t j 0 sign t j t xx3 i ones 1 abs t j 1 else for u i r i 0 sign r i r yy3 t j u r r i t yy3 xx3 u xx3 end end if t j xx3 i r i 0 sign r i r xx3 yy3 j ones 1 abs r i 1 yy3 else for v j t j 0 sign t j t xx3 v t r i t j r xx3 yy3 v yy3 end end xx3 sort xx3 yy3 sort yy3 if sign r i 1 xx3 xx3 end 1 1 end if sign t j 4 end xx half ceil xx half yy half ceil yy half xx half xx half 0 1 yy half yy half 0 1 s cc g price xx half g yy half g s end cost i 1 j 1 r 1 t 1 s end end end end minnist min min min min cost cross point for aa 1 10 for bb 1 10 for cc 1 10 for dd 1 10 if cost aa bb cc dd minnist cross point cross point aa bb cc dd end end end end end cross point cross point 1 问题三 clc clear GGG 0 5 1 1 0 5 0 5 1 0 5 1 1 0 5 1 0 5 1 0 5 0 5 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 01 1 1 0 01 0 01 1 0 01 1 1 0 01 1 0 01 1 0 01 0 01 1 cross points cell 1 min cost cell 1 for qqq 1 3 for ppp 1 4 fff 3 6 6 3 ggg GGG ppp ddd 2 ggg 1 1 2 ggg 2 1 2 ggg 3 1 2 ggg 4 1 price xlsread xls cost inf ones ddd 1 ddd 2 ddd 3 ddd 4 A 0 9 B 9 0 for i 3 ggg 1 5 for j 6 ggg 2 8 for r 6 ggg 3 8 for t 3 ggg 4 5 xx half yy half cc s 0 xx1 yy1 xx2 yy2 xx3 yy3 if i 0 yy1 9 1 j xx1 zeros 1 fix 9 j 1 else for k 0 i yy1 yy1 j 9 i k 9 xx1 xx1 k end end if j 9 xx1 0 i xx1 yy1 9 ones 1 fix i 1 yy1 else for q j 9 xx1 xx1 q 9 i j 9 yy1 yy1 q end end xx1 xx1 i yy1 yy1 j xx1 sort xx1 yy1 sort yy1 yy1 yy1 end 1 1 2 B if t 0 xx2 9 1 r yy2 zeros 1 length xx2 else for p 0 t xx2 p r 9 t 9 xx2 yy2 yy2 p end end if r 9 yy2 0 t yy2 xx2 9 ones 1 fix t 1 xx2 else for l 9 1 r yy2 l 9 t r 9 yy2 xx2 l xx2 end end xx2 xx2 r yy2 yy2 t xx2 sort xx2 yy2 sort yy2 yy2 yy2 end 1 1 1 1 tj sort t j ir sort i r if r i yy3 ceil tj 1 abs sign tj 2 ceil tj 1 0 tj 2 xx3 i ones 1 length yy3 else for u ceil ir 1 abs sign ir 2 ceil ir 1 0 ir 2 yy3 t j u r r i t yy3 xx3 u xx3 end end if t j xx3 ceil ir 1 abs sign ir 2 ceil ir 1 0 ir 2 xx3 yy3 j ones 1 length ceil ir 1 abs sign ir 2 ceil ir 1 0 ir 2 yy3 else for v ceil tj 1 abs sign tj 2 ceil tj 1 0 tj 2 xx3 v t r i t j r xx3 yy3 v yy3 end end xx3 sort xx3 yy3 sort yy3 if sign r i 1 xx3 xx3 end 1 1 end if sign t j 4 end xx half ceil xx half yy half ceil yy half xx half xx half 0 1 yy half yy half 0 1 s cc g price xx half g yy half g s end cost int32 abs i ggg 1 fff 1 ggg 1 int32 abs j ggg 2 fff 2 ggg 2 int32 abs r ggg 3 fff 3 ggg 3 int32 abs t ggg 4 fff 4 ggg 4 s end end end end minnist min min min min cost cross point for aa 1 ddd 1 for bb 1 ddd 2 for cc 1 ddd 3 for dd 1 ddd 4 if cost aa bb cc dd minnist eps cross point cross point aa bb cc dd end end end end end min cost qqq ppp minnist cross points qqq ppp cross point 1 repmat ggg size cross point 1 1 repmat fff size cross point 1 1 end end 问题四 clc clear price xlsread xls cost inf ones 11 11 11 11 A 0 9 B 9 0 for i 3 0 1 4 for j 7 0 1 8 for r 7 0 1 8 for t 3 0 1 4 tic xx half yy half cc s 0 xx1 yy1 xx2 yy2 xx3 yy3 if i 0 yy1 9 1 j xx1 zeros 1 fix 9 j 1 else for k 0 i yy1 yy1 j 9 i k 9 xx1 xx1 k end end if j 9 xx1 0 i xx1 yy1 9 ones 1 fix i 1 yy1 else for q j 9 xx1 xx1 q 9 i j 9 yy1 yy1 q end end xx1 xx1 i yy1 yy1 j xx1 sort xx1 yy1 sort yy1 yy1 yy1 end 1 1 2 B if t 0 xx2 9 1 r yy2 zeros 1 length xx2 else for p 0 t xx2 p r 9 t 9 xx2 yy2 yy2 p end end if r 9 yy2 0 t yy2 xx2 9 ones 1 fix t 1 xx2 else for l 9 1 r yy2 l 9 t r 9 yy2 xx2 l xx2 end end xx2 xx2 r yy2 yy2 t xx2 sort xx2 yy2 sort yy2 yy2 yy2 end 1 1 1 1 tj sort t j ir sort i r if r i yy3 ceil tj 1 abs sign tj 2 ceil tj 1 0 tj 2 xx3 i ones 1 length yy3 else for u ceil ir 1 abs sign ir 2 ceil ir 1 0 ir 2 yy3