基于p-中位模型的高速铁路快运网络枢纽节点城市选址

我国快递需求的快速增长和高速铁路规模的发展对高速铁路网络优化、运力合理配置及枢纽节点布局等持续经济运营问题提出了发展要求,也对运输组织和网络运行等提出了规模化的高要求,基于高速铁路客运运力复合利用视角,借助p-中位模型,以最大二次中转的成本最小化函数构建了我国高速铁路快运网络枢纽节点城市的选址模型,并使用禁忌搜索算法求解和利用矩阵表示法合理分配货流量。考虑我国实际高速铁路网络城市分布及城市内站点分布,将高速铁路与枢纽节点城市内中转车辆两种运输方式相结合,以2019年实际的高速铁路旅客列车运行时刻表为实例计算了枢纽站点、城市的枢纽运输成本,形成了高速铁路快运网络节点城市的枢纽成本位序和集散点集。

多阶段粒子群优化算法求解容量约束p-中位问题

容量约束p-中位问题(Capacitated P-Median Problem,CPMP)已被证明是一类计算机难以求解的具有NP-hard特性的组合优化问题.本文提出一种多阶段粒子群优化算法(Multi-Phase Particle Swarm Optimization,MPPSO)及在算法设计中应用模式有关理论和方法.所提MPPSO在标准PSO基础上,考虑CPMP结构特征信息,采用一种以字符编码为基础的结构体编码结构,重新定义粒子速度与位置更新方式.它将CPMP优化求解分为种群粒子初始化阶段及两个优化阶段.在优化求解第一阶段,分析了惯性因子对所求问题编码结构粒子搜索的局限性,设计一种保留粒子最优特征中位点信息的变异算子.以粒子全局搜索算子操作为重点,期望从整个搜索空间搜索到好的模式结构分布特性的粒子.在优化求解第二阶段,对高适应性粒子执行一种改进的迭代局部搜索操作,达成对粒子精度的进一步提升.迭代局部搜索分为基本局部搜索和深层次局部搜索.基本局部搜索侧重对粒子需求点和中位点提炼用于发现候选粒子相邻的局部最优解.在深层次局部搜索中,采用对粒子执行扰动算子操作,使得算子操作在更大邻域范围内搜索粒子新的模式结构,从而发现蕴含高适应性模式结构的潜在更好解.文中提出模式范数及模式结构距离等概念,并将它们用于扰动算子设计.实验测试表明:MPPSO对4大类CPMP用例问题进行求解得到的实验数据,与4种文献对比算法提供的数据相比有一定优势,且能发现3个大数据集用例新的最好解.

带投资约束p-中位问题的混合蚁群算法

将投资限制引入经典约束p-中位问题,提出带投资的约束p-中位问题,该问题更适用于交通、物流等领域的设施选址。在深入分析带投资约束p-中位问题的数学模型的基础上,首先提出了适用于该问题求解的局部搜索策略;其次,将局部搜索策略与拉格朗日启发式算法和蚁群算法相结合,设计了求解该问题的拉格朗日混合蚁群算法。实验结果表明,带投资的约束p-中位问题能够根据投资金额规划不同的投资方案;且提出的混合蚁群算法较大程度上提高了蚁群算法和拉格朗日启发式算法的求解精度,具有较好的收敛性。

带投资约束且p不确定的推广p-中位问题

p-中位问题是设施选址中的一个经典模型,在交通、物流等领域有着广泛应用.在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题,并且加上总投资约束,使得此推广模型更加实用.针对此推广模型,提出三种启发式算法:简单启发式算法、变邻域搜索算法和改进的遗传算法.数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的.

具有水上事故特征的目标P-中位应急救助选址优化及方法

科学地进行应急救助基地选址是提高应急资源利用效率和应急服务水平的关键,以南京海事辖区为例,对事故多发水域应急救助基地的布局规划和覆盖分配进行了优化研究。总结了辖区水域中影响应急救助站点选址的因素,有辖区事故重点水域分布、桥区水域、锚地3个因素,运用DBSCAN算法确定了辖区事故重点水域的分布情况,结合桥区水域、锚地影响因素,引入安全风险权重系数,利用P-中位建立了应急救助站点选址数学模型。构建的选址模型目标函数在满足设置的约束条件下取最小值,即实现了救援用时最少或救援距离最短。最后运用免疫算法求解选址优化数学模型。经过计算,在考虑时效性的基础上,较好地实现了应急救助对辖区水域的全覆盖和重点水域的重点覆盖。

一种新的求解约束P-中位问题的启发式算法

针对约束P-中位问题的特点,提出了一种新的启发式算法。该算法借鉴了蚁群算法的信息素学习机制,同时针对问题的结构设计了合理的对象分配方式。模拟计算表明,该算法具有更好的全局优化性能和计算效率。

一种求解厌恶型p-中位问题的混合进化算法

厌恶型p-中位问题是一个NP-困难问题.提出了一种求解厌恶型p-中位问题的混合进化算法.首先,通过贪心随机自适应搜索方法和随机构造方法产生初始种群.然后,利用搜索过程中收集到的全局信息和局部信息构造新解,期间注意提高搜索的多样性,避免早熟.最后,针对厌恶型p-中位问题的特点,构造基于约束交换邻域的局部搜索算法,提高了算法的局部搜索能力.通过求解72个标准测试例子以检验算法的性能,发现该算法在较短时间内得到了高质量解,优于现有算法.

广义p-中位模型的遗传算法

针对制造业成组技术中采用的广义ｐ－中位模型，设计了适当的遗传算法。实验结果表明，该算法能在较短时间内给出这类ＮＰ完备问题的满意解。

改进p-中位模型在可重构检具设计中的应用

通过对变速箱传动轴本身特征和检具的功能/机构分析,结合企业原来使用的专用检具,将可重构思想运用于检具的设计之中,实现检具的模块化。应用改进p-中位模型将检具的部件进行重组,并运用LINGO软件采取分支界限法进行组合计算,从而减低测量时的调整量。最后通过对变速箱企业的轴类零件检具设计的应用,大大提高了检测效率,证明设计思想的合理性和可行性。

一种基于P-中位的产品单元化形成方法

讨论了单元化设计技术运用在大批量定制中的可行性.基于功能和物理等特性对产品进行分解以建立零件之间的相似矩阵,采用P-中位优化算法对待配置的零件进行了聚合.结合实例对这种方法进行了验证并和其他几种算法的计算结果进行了比较.结果表明:P-中位方法可以较好地解决单元形成问题,为面向大批量定制的单元化敏捷生产模式提供了另外一种数值评价工具.

基于p-中位模型的区域综合能源系统能源站优化规划

综合能源系统能够实现能源的优化利用,有效提高能源使用效率,缓解环境污染问题。以往对于综合能源系统能源站规划的研究主要集中在设备容量的优化配置方面,较少对能源站位置及管网路径的优化规划进行分析。研究了考虑电、热供应的区域综合能源系统能源站选址及能源传输管网路径优化布局问题。首先,根据p-中位模型建立了能源站选址及管网路径布局的优化规划模型。其次,考虑能源站、管网设备初始投资及施工费用,建立了区域综合能源系统投资费用模型。最后,基于枚举法提出了一种改进求解方法对规划模型进行求解,并以某园区为实例进行仿真分析,验证了所提模型及方法的有效性。

应急物资储备库的可靠性P-中位选址模型

应急物资储备库选址属于战略性决策问题,而突发事件的发生可能会造成储备库失灵,因此在选址设计阶段就考虑其失灵风险是十分必要的。本文以应急物资保障的及时性和可靠性为目标,考虑在不同地区建立储备库的不同失灵概率,建立了一种应急物资储备库的可靠性P-中位选址模型。针对该模型的特点,运用线性化技术进行模型转化,并设计了一种拉格朗日松弛(LR)算法。最后通过两组算例分析对模型和算法进行验证,并与CPLEX求解结果进行了比较。结果表明,对于大规模问题,LR算法效率明显高于CPLEX。

基于p-中位模型的单目标物流配送时间点决策

为了确定最佳的配送时间点,利用p-中位模型,研究单配送目标物流配送的时间点决策问题,建立了最少配送次数、最短配送时间和运费有折扣情况下最低运输成本的数学模型,并以航空货物配送为例,利用ILOG优化软件分别计算了3种模型的配送时间点。计算结果表明:实现最少配送次数需要的平均配送时间是最短平均配送时间的1.6倍,在运费有折扣情况下实现最低运输成本所需配送时间比没有折扣情况下的略长;货主或者物流服务商可以根据客户要求选择相应的模型,确定配送时间点,实现最优决策。

基于网络分割的P-中位问题求解方法

针对传统的PMP（P-median problem）算法在单机环境下无法突破大规模地理网络求解时的空间和时间瓶颈,提出了一种基于网络分割的大规模稀疏网络P-中位问题求解方法.采用多层k-路划分算法对网络进行分割,将大规模PMP问题转换为多个小规模的PMP问题;研究了＂子网络求解-归并-调整中位点数＂操作对PMP解质量的优化效果;应用测试数据评价了网络分割对PMP解质量的影响.结果表明：该算法能够在单机环境下解算大规模PMP问题;分割后PMP解的偏差率在0.16%～2.82%之间;随着中位点数的增加,网络分割对PMP解质量的影响呈减弱的趋势.

基于P-中位模型的聚类分析的新的拉格朗日松弛算法

Clusting problem based on P-Median may be formulated a as 0-1 interger programming problem. In this paper we develop a Lagrangean heuristic algorithms based on relaxation of the inequality constraint. The computational performance of the method is analysed for 10 problems. Computational results show that the average duality gap are within 2%.

p-枢纽中位问题与服务设备配置的联合优化模型

传统枢纽网络设计方法忽略了服务设备网络配置对于枢纽网络设计方案的影响。为了提高枢纽网络与服务设备之间的相互适应能力,并降低枢纽网络设计成本,以枢纽选址、各OD对路径及各边上配置的服务设备类型及其数量选择为决策变量,结合各边上预期服务设备最大数量及各类设备服务总时间限制等因素,构建p-枢纽中位问题与服务设备配置的联合优化数学模型。选取2016年国内航空运输业中“9个城市、4种机型、72个OD对”数据进行验证,结果表明:与传统方法相比,该方法的枢纽网络设计成本降低了1.34%,且两者相互适应能力更强。另外,各边上预期配置的服务设备最大数量及各类设备服务总时间限制是影响两者相互适应能力的重要因素。

中心问题与中位问题的研究现状

p-中心问题与p-中位问题是两类基本的选址问题,在选址问题的研究中占有十分重要的地位。本文从问题的性质、算法设计思想与计算复杂性等方面总结了现有的研究成果,并指出了进一步研究的方向。

成组技术中的P－中位模型的遗传算法

采用遗传算法对成组技术中的零件进行近优分蔟，提出了用０、１码分段构造染色体和分段交叉、变异的策略来满足Ｐ－中位模型复杂约束的要求。实验结果表明，当以类内样本距离之和作为评价准则时，该算法明显好于Ｋ－平均算法。

基于图论的区域综合能源服务商交易路径优化

随着电力体制改革的不断推进,区域能源服务商数量不断增加,电网结构日益复杂,购、售电交易双方之间的可选路径增多。在此背景下,提出了区域能源服务商交易路径两步选择法。首先基于p-中位模型的区域能源服务商交易路径第1步优化选择,考虑综合建设运行成本、能源站与负荷中心的最短路径距离、用户负荷需求三方因素,构建多目标优化模型,作用于区域综合能源服务商的站址规划;然后,基于OD矩阵和双约束重力模型提出了区域能源服务商交易路径第2步优化选择,以电能传输量最大和区域能源服务商日运营利润最大为目标函数,作用于多个区域能源服务商之间的能源传输路径选择。采用枚举法和Dijkstra算法对所建模型进行求解并通过算例仿真证明该模型能够有效降低网络损耗成本,减少弃风弃光量,提高区域能源服务商的运营利润。

改进的求解约束P-Median问题的分散搜索算法

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。