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

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

求解推广k-CARD问题的一种变邻域搜索方法

k-CARD问题是在一个无向网络G中寻找一棵k条边的子树,使得这棵树的权和最小。目前有很多启发式算法用来解决这类NP难问题。一般的研究都只考虑点带权或边带权的k-CARD问题。将k-CARD问题进行推广,考虑边和点都带权的情况。该推广模型不仅统一了传统的边或点带权的问题,更重要的是,它在现实中有着一定的应用背景。针对推广模型的特点,提出了一种变邻域搜索(VNS)方法进行求解。数值实验结果表明此VNS方法求解推广k-CARD问题是有效的。

一种推广的UFCLP的变邻域搜索方法

UFCLP问题是在经典p-中位问题上去掉中位点个数的限制,并且在目标函数中加入设施的建设费用。目前有很多启发式算法用来解决这类NP-难问题。本文将UFCLP问题进行推广,加入投资限制,并且考虑距离和费用的权重。针对此推广模型的特点,提出了一种变邻域搜索方法。数值实验结果表明此VNS方法求解此推广UFCLP问题是有效的。