典型优化问题的遗传算法求解—8选址分配问题

《典型优化问题的遗传算法求解—8选址分配问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、典型问题选址－分配问题(LocationAllocationProblem)东北大学系统工程研究所2014.09典型优化问题的模型与算法-R03选址－分配问题选址－分配(location-allocation)问题也称作多韦伯(multi-Weber)问题或P中位(P-median)问题。单韦伯(singleWeber)问题在欧几里德空间上典型的单韦伯(singleWeber)问题是寻找一个位置，使从代表顾客位置的一些固定点到它的距离和最小。问题描述：有m个“设施”需要选址，n个已知位置的“顾客”分配给不同的设施，每个顾客的需求为b，j=1,2,…,nj；每个

2、设施具有的能力为a，i=1,2,…,mi我们需要找到设施的位置（选址）顾客对设施的分配使顾客和服务他们的设施间的距离总和最小。典型优化问题的模型与算法-R032图形描述(u,v)nn(u,v)11CC3Cbn11bn(x1,y1)…F1aFmma1(xm,ym)C2m:设施总数a:第i个设施的能力in:顾客总数b:第j个顾客的需求jF:第i个设施,i=1,2,…,mF=(x,y):设备i的未知位置，决策变量iiiiC:第j个顾客,j=1,2,…,nC=(u,v):顾客j的已知位置jjjj典型优化问题的模型与算法-R033数学模型mnminf(F,z)t(Fi

3、,Cj)ziji11j保证不超过每个设施的服务能力ns.t.gi(z)bjzijai,i1,2,,mj1保证每个顾客只m由一个设施服务gmj(z)zij1,j1,2,,ni1z0or1,i1,2,,m,j1,2,,nij变量:C(uj,vj)jzij:0-1决策变量bjz=1,顾客j由设施i服务；否则z=0ijijF=(x,y):设施i的未知位置，决策变量iiiaFii参数：(xi,yi)……t(F,C):由设施i到顾客j的欧几里得距离。ij22t(F,C)(xu)(yv)ijijij典型优化问题的模型与算法-R034

4、特点非线性规划问题既有0-1变量，又有实数变量分配子问题是一个一般的指派问题NP-难的问题Cooper是正式认识并描述多韦伯问题的第一位学者。他证明目标函数既不是凹的也不是凸的，并存在许多局部最优解。典型优化问题的模型与算法-R035分类按能力分类：有能力约束的LAP无能力约束的LAP按阶段分类：单阶段LAP多阶段LAP其它分类：有障碍的LAP平衡的LAP典型优化问题的模型与算法-R036问题的扩展一般的选址-分配模型致力于为这样一些基础设施寻找最佳选址，如：学校、消防站、公园等，此类基础设施对于“最佳选址”理解的共同点在于，使供需点之间

5、的“总距离”或者“平均距离”最小。除此以外，这个基本模型经过扩展还可以有更广泛的应用范围，如：优化城市零售商业网点空间分布(通过最大化惠顾人流量来实现)、优化制造业场所空间分布(通过最小化运输成本实现)、优化公共服务设施空间分布(通过最优化服务质量实现)、……典型优化问题的模型与算法-R037应用物流配送中心选址问题物流网络设计中首先必须要解决的问题物流中心设施；零售商顾客；运费或距离最C3短F1城市医院空间布局优化医院设施；街区顾客；服务质量,距离最小等C1城市邮政局所空间布局邮局设施；建筑物的中心顾客；邮政服务的…平均出行距离最短C

6、城市电网变电站选址问题2变、配电站设施；小区顾客；输电线（距离F）最短m海上溢油应急点选址优化C应急服务点设施；发生溢油较高的区域顾客n；到达发生事故点的距离之和最小公路养护资源的选址和配置问题养护点设施；路段顾客；目标是工作量均衡典型优化问题的模型与算法-R038应用社会考试考场选择问题例如英语等级考试、公务员考试等涉及的人数很多；C3考场设施；生源地顾客；距离最短、最F1便利等C零售商业点的选址问题1商业点设施；小区（街区）顾客；惠顾人流量最大或距离最短…公共设施的最优选址问题C2如公园、学校、图书馆、加油站、污水处理厂、

7、城市垃圾填埋场、消防设施等Fm突发事件的应急资源配置问题C如地震、海啸、流行病、n设备选址如电力、通信、交通系统中相关设备或站址的选取和定位典型优化问题的模型与算法-R039一般求解方法Cooper提出了一种称作选择选址－分配(alternativelocation-allocation)的启发式，这是一种最好的启发方法随着非线性规划技术的发展，通过松弛整数分配约束，同时考虑选址变量和分配变量，产生了一些新的方法。Murtagh和Niwattisyawong提出一种松弛0-1分配约束的方法。允许在[0,1]区间上