选址问题的算法模型说明系列六
邮政选址模型的简单描述
•目标函数:
以总体的费用最少为目标,包括网点到中心站点的运输费用总和以及全部中心站点的建站费用
•约束条件:
1.容量限制(处理能力限制):中心局满足所有由它服务的网点的日业务量的总和要小于等于他的处理能力
2.邮件配送的时间限制
3.单次配送的容量限制
4.中心局地理位置的限定
5.投资经费的限制……
还有很多其它的约束在具体实现的模型中可以再加入考虑。
模型的输入
•中心局的候选点坐标(由GIS输入)
•所有网点的坐标(由GIS输入)
•候选点的建站费用(与选址的地点以及中心局的大小规模有关,即与日处理量有关)
•所有网点之间以及候选点和网点之间的运输费用(可以由距离决定,也可以单独输入)
•所有网点的日业务量
•中心局的日处理量(在这里认为与中心局的建站费用成正比)
模型的输出
•Location
1.整个网络中中心局的个数
2.中心局的地点(可以通过GIS显示在地图中)
3.中心局的规模,即每个中心局点的建站费用
•Allocation
1.得出网点的归属中心局(即分区的过程)
•Cost
1.总体的费用
2.全部的建站费用
3.每个中心局所属的分区的最大运输费用和时间
选址模型的求解方法1
•运筹学的线性规划和整数规划
优点:精确式算法,能获得全局最优解
缺点:对一些复杂情况很难建立合适的规划模型或者模型太复杂,计算时间长,非常难以得到最优解;还有些时候得出的解虽然是最优 解,但在实际中不可行。
选址模型的求解方法2
•启发式算法
启发式算法是一种逐次逼近最优解的方法。用启发式算法进行选址,首先要定义计算总费用的方法,拟定判别准则,规定改进途径,然后给出初始方案,迭代求解。
优点:求解速度快,相对于传统的精确式算法更简单,更易获得适用于实际工程应用的优化解。
缺点:不是精确式算法,不能保证给出的解决方案是最优的。
常用的求解选址模型的启发式算法:遗传算法,粒子群优化算法,蚁群算法,禁忌搜索算法等
选址模型的求解方法3
•仿真方法
仿真方法是试图通过模型重现某一系统的行为或活动,而不必实地去建设并运转一个系统,因为那样可能会造成巨大的浪费,或根本没有可能实地去进行运转试验。在选址问题中,仿真技术可以使分析者通过反复改变和组合各种参数,多次试行来评价不同的选址方案。这种 方法还可进行动态模拟。
优点:仿真方法可描述多方面的影响因素,因此具有较强的使用价值, 常用来求解较大型的、无法手算的问题。
缺点:仿真方法不能提出初始方案,只能通过对各已存在的备选方案进行评价,从中找出最优方案。