2.1.1 P-中值问题

P-中值问题一直是选址问题研究的热点，在配送中心等服务设施中应用极其广泛。其目标是平均距离或者时间最短，也可称之为优化问题。其属于NP完全问题，当P为变量时，就成为一个典型的NP-Hard问题，需优化高效算法求解。文献^[4]在考虑p-中值问题时，以尽量减少需求点和服务中心之间的平均加权距离或时间，针对具体问题，提出了一种简单的新启发式方法，并分析了其优越性。文献^[5]使用人工蜂群算法模型求解了P-中值问题，其算法是用于解决组合优化问题的元启发式算法之一，并在实验测试中取得了较好的效果。文献^[6]调查了通常使用启发式方法解决P-中值问题并研究了其进展。同样文献^[7]和文献^[8]也是基于启发式方法解决此类优化问题。文献^[9]给定一个包括P个节点(中值节点)的有向图G(V,A)，目标是最小化与图中其他节点的总距离，提出了一个分支和切割算法，算法的关键成分是延迟列和行生成技术，利用公式的特殊结构来解决LP松弛问题，并切割平面以加强公式并限制枚举树的大小。文献^[10]也将一种新的离散粒子群优化算法成功的引入解决P-中值问题。