在求解组合优化问题的启发式算法相关研究中,一直以来存在两种不同的观点：一类认为,算法设计应当从问题出发,针对问题特征设计高度特化的启发式算法；另一类认为,算法设计应当从算法本身出发,设计通用的、高适应性的算法。针对启发式算法的研究现状,我们尝试以组合优化领域经典的p-median问题为案例,分别从两种角度分别对启发式算法求解问题机制做出改进和扩展。一方面,我们以骨架为切入点,关注基于问题特征的求解模式,尤其是大规模实例求解困难的问题。另一方面,我们旨在探讨异构实例求解场景下如何获得健壮结果这一难题。具体的,我们的主要工作可以概括为：1、针对p-median问题大规模实例求解效果不理想的现状,我们关注基于骨架的高效启发式算法设计和问题求解。骨架指的是一个NP-难解问题的实例的所有全局最优解的公共部分,骨架的获取或高效近似对于启发式算法设计和问题求解具有重要意义。我们详细探讨了如何设计骨架导向的高效启发式算法。我们提出了基于限界交叉方法的骨架获取方法,其显著特征在于能够使用启发式方法获得问题全局最优解的部分精确信息。同时,为了解决限界交叉方法高复杂度以及参数敏感的问题,我们提出了基于限界交叉的多级归约算法。实验证明,我们提出的算法能够在一系列标准实例集上获得高质量的结果。在171个实例上,我们获得了52个更好的上界,并达到92个已知最优上界。更进一步的,通过适应度地貌分析,我们验证了算法有效和失效的原因。2、在我们将限界交叉方法首次应用在半监督聚类中,用来自动化提取部分监督信息。与传统半监督聚类方法中监督信息由领域专家提供不同,限界交叉方法方法能够将这一耗时,易出错的手工任务部分自动化。并且,在部分标准与人工数据集上,我们的监督信息自动抽取方法能够提升半监督聚类算法的性能。3、从算法出发,我们主要关注超启发式算法。通过使用高层启发式策略管理和操纵一系列低层启发式算子,超启发式算法意在提升算法抽象层次,跨领域与异构实例求解,以及算法构造自动化。然而,在传统超启发式算法中存在低层参数设置问题。通过引入基于搜索的动态参数控制,我们在一定程度上减少了领域专家在的人工干预需求。同时,为了避免引入额外搜索变量导致的问题,我们提出了一种启发式空间归约机制,有效的避免了搜索空间膨胀的问题,同时能够较好的平衡多样性和强化性。我们发现,低层参数控制与启发式空间规约的有机结合能够很好的维护算法搜索过程中强化性和多样性的平衡。实验证明,算法在多个异构实例集上获得了更为健壮的结果。