一种基于轮廓系数和AP聚类算法的离散覆盖仓库选址方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110287989A(43)申请公布日2019.09.27(21)申请号201910423583.1(22)申请日2019.05.21(71)申请人武汉大学地址430072湖北省武汉市武昌区珞珈山武汉大学(72)发明人李石君龚红霞杨济海李学礼余伟余放王凯李宇轩(74)专利代理机构武汉科皓知识产权代理事务所(特殊普通合伙)42222代理人罗飞(51)Int.Cl.G06K9/62(2006.01)G06Q10/08(2012.01)权利要求书2页说明书10页附图2页(54)发明名称一种基于轮廓系数和AP聚类算法的离散覆盖仓库选址方法(57)摘要本发明公开了一种基于轮廓系数和AP聚类算法的离散覆盖仓库选址方法，将库存承载力作为衡量偏度的方法，有效反映了仓库容量与辐射范围的正比关系；考虑轮廓系数的定义，根据簇的内聚度和分离度引入新的约束，同时考虑优化中心覆盖面积和等待时间，在信息迭代传播时对偏度进行自适应更新。基于轮廓系数约束和偏度更新的AP聚类算法有助于避免震荡，加快算法收敛速度，获得兼具理想服务范围和合理响应时间的中心组合。本发明的方法可以达到提高选址准确性和改善选址综合性能的技术效果。CN110287989ACN110287989A权利要求书1/2页1.一种基于轮廓系数和AP聚类算法的离散覆盖仓库选址方法，其特征在于，包括：步骤S1：根据需求点间的特征建立相似度矩阵，其中，对角线上的偏度值采用每个潜在中心的条件作为初始值，并根据相似度矩阵创建参与AP聚类的中间量；步骤S2：引入基于轮廓系数的约束规则，其中，约束规则包括原信息更新规则以及基于原信息更新规则和簇的内聚度和分离度的新约束规则；步骤S3：建立新约束规则与节点间的置信网络，采用基于因子图模型的近似计算算法max-product计算非对角线和对角线元素的信息更新公式，迭代更新置信网络中的传播公式和中间量，并根据传播公式和中间量更新信息量，直到网络收敛；步骤S4：根据收敛后节点的信息量计算每个点的备件中心，取使得吸引度和支持度之和最大的需求点作为选址中心，得到中心解及其集群。2.如权利要求1所述的方法，其特征在于，步骤S1具体包括：步骤S1.1：根据备选点间的距离、仓库容量、建设成本建立相似度矩阵{sij}i∈N，j∈N，非对角线上的值采用备选点之间的距离函数表示：其中mind、maxd分别表示备选点间距离的最小值和最大值；对角线上的偏度值pk采用每个备选点的属性加权和作为初始值：pk＝aVk+bCk，其中，Vk和Ck分别表示第k个备选点的仓库容量和建设成本；步骤S1.2：根据相似度矩阵创建参与AP聚类的中间量，包括吸引度变量αij＝0、轮廓系数阈值和偏度互作用其中，med函数表示取中位数，mapping函数表示步骤1中的距离函数，max_dist表示存在运输时间上限时满足该约束的最大距离。3.如权利要求1所述的方法，其特征在于，步骤S2具体包括：步骤S2.1：基于节点和因子图建立原信息更新规则，包含待供应货物点和备件候选点两方面的约束，将约束转为函数形式得：其中，Ej函数规定了需求点作为中心的条件，即当点j被选为备件中心时，其需求必须由其本身满足；Ii函数规定了每个点有且仅有一个中心；步骤S2.2：根据簇的内聚度和分离度定义引入新的约束，新的约束为作为簇中心的点之间的最大相似度应小于任意簇内最小相似度，用函数形式描述，对于所有备件候选点j∈N，有将约束投影到偏度和备件候选点两个方向，改进Ej(ctj，c2j，...，cNj)公式并引入新的Pk(c1t，c22，...，cNN)函数节点和作为迭代更新中间量的变量节点thj，将约束整合到AP聚类模型中：2CN110287989A权利要求书2/2页其中，Pk为新的函数节点,E′j(ctj，c2j，...，cNj)为改进后的约束公式。4.如权利要求1所述的方法，其特征在于，步骤S3具体包括：步骤S3.1：更新置信传播公式，根据max-sum规则及置信网络结构，将约束转为置信网络中相互制约、动态更新的信息量，其中Ej与节点的信息交互采用变量αij和ρij表示，αij表示约束-＞节点，ρij表示节点-＞约束，约束函数Ii采用ηij和βij、Pk采用θij和εij描述，分别得到非对角节点的信息更新规则和对角节点的信息更新规则；步骤S3.2：根据中心点间的约束动态调整偏度参数；步骤S3.3：更新轮廓系数阈值；步骤S3.4：根据更新后的置信传播公式、偏度参数和轮廓系数阈值迭代更新信息量。3CN110287989A说明书1/10页一种基于轮廓系数和AP聚类算法的离散覆盖仓库选址方法技术领域[0001]本发明涉及仓库选址技术领域，具体涉及一种基于轮廓系数和AP聚类算法