传染病医院选址模型
报名参加了2020年美赛，由于病毒问题，美国官方将比赛分为了两个赛段，2月和3月份的赛段。作为比赛前的准备，学校组织我们针对这一次的新型冠状病毒进行建模，没有明确的内容限制，我们队伍主要针对了病毒传播模型和应对病毒的方式进行了建模，将会分3篇文章介绍我们构建的模型和运用的算法。
代码会在🤚Github 实时更新。
选址问题
有关设施选址模式的问题 Owcn&Daskin 则曾针对地区域性公共设施选址模型问题做探讨,大致可归纳为四类[1]：
- p-中值问题：寻求设施与需求点之间总加权距离的最小化
- p-中心问题：寻求设施与最近需求点间的最大距离的最小化
- 集合覆盖性问题：寻找最少设施数的最适合位置，使所有需求点都在设施服务范围内
- 最大覆盖问题：求设施最大化服务范围内的需求数量
由于各种公共设施性质不同,所适合的选址模式也不同：
一般来说,紧急性设施由于需考虑时效性的问题,因此仅能有效地照顾到服务范围之内的需求点,这类问题适合以覆盖问题或P一center问题进行分析,属于这类的公共设施有:消防队、医院、警察局等。
公共设施的投资都相当庞大,在资源有限的情况下,能够设置的数量就会受到限制,为求所设置的设施成本能够最节省,通常要求将设置总成本最小化,这类问题适用非紧急性设施的配置,即在探讨预先设定设施数目最适合的分布,使其与需求点之间的总加权成本旅行距离和最小化,属于这类的公共设施有:公园、学校、邮局、加油站、行政中心、市场、图书馆等。
另外,有些被讨厌或对人们产生不良影响的避邻设施,一般都设置在城市的边缘位置,使得与其它活动空间有较大的阻隔,这类问题适合于以反中值问题或反中心问题等进行分析,属于这类的设施有:垃圾掩埋场、军事设施、火葬场等。
传染病医院选址的问题描述
经过分析，传染病医院的选址具有特殊的内在矛盾属性，一方面传染病医院作为重要的医疗类公共设施，在这个特殊时段，属于紧急性设施，其时效性需要着重考虑，因此我们选取了p-center模型作为基本的模型；另一方面，传染病医院本身含有风险因素，容易对周边产生不良影响，不能设立在人口稠密的区域，需要考虑到人口，感染率，当地医院病床数等进一步构建复杂程度更高更准确的模型。
在此基础上，我们以武汉市政府规定[2]的共61所发热定点诊疗机构和医疗救治定点机构作为需求点，在需求点中选出m所医院作为专门收治确诊新型病毒患者的医院。
P-Center Problem
A p-center is a minimax solution that consists in a set of p points that minimizes the maximum distance between a demand point and a closest point belonging to that set.[3]
问题重述:
给定有权无向图 $G(E,V)$，设施数 $m$，求点的集合$N$, 满足：
\[N\subseteq V,1<|N|=m<|V|\\ {\underset {N}{\operatorname {arg\,min} }} \sum^{}_{p \in V,p \notin N}{max(\ \{d\ |\ d=|E_{pq}|,q\in{N}\}\ )}\] \[{\underset {BS,FS}{\operatorname {arg\,max} } \ Energy(BS,DS,Temperature,Activity,Population)}\]该问题为NP难问题，无法在多项式时间内给出最优解。使用穷举法，在本题的情况下，若 $|V|=62,m=6$，则共有 $C_{62}^6=61474519$种选择方法，消耗时间空间巨大。因此我们选择启发式算法，而解空间为离散的点集，利于遗传算法编码，所以我们选用遗传算法来求解。
Genetic Algorithm
遗传算法代码已上传至🤚Github。 <!– $$ \sigma_{ID=\pi_{ID}(\sigma_{dept_name=”cs”}(student))}(takes)\
\pi_{ID}(\sigma_{course_id={\pi_{course_id}(\sigma_ {ID=\pi_{ID}(\sigma_{name=”Einstein”}(instructor))})}}(takes))\
\pi_{max(salary)}(instructor) \
instructor - \sigma_{salary>40000\ and\ salary<60000}(instructor)\
instructor - \sigma_{dept_name=”Physics”}(instructor)\
\pi_{customer_name,limit-credit_balance}(credit_info)\
\pi_{name}({\pi_{name}(\sigma_{ID=\pi_{ID}(\sigma_{title=’O.S.’}(course))})}\cap {\pi_{name}(\sigma_{ID=\pi_{ID}(\sigma_{title=’D.B.S.’}(course))})})\
n1 = count(\pi_{course_id}(\sigma_{title=’CS’}(course)))
$$ –>
ps: 最近每日新病毒确诊人数激增，希望武汉能挺住，武汉加油！
