组合优化问题广泛存在于交通运输、网络规划、物流配送、云计算、大数据、生产制造等诸多领域。求解多约束、多目标、复杂组合优化问题的智能搜索方法是提高企业效率、优化资源成本、改善用户体验、节省消耗能源等诸多方面的核心技术。本文考虑了求解组合优化问题的两种搜索方法:简单构造式搜索和迭代构造式搜索,结合不同问题场景,依据具体问题特性,对不同的搜索方法进行了相关研究。论文的主要工作体现在:(1)针对基于位置学习效应的最短路径不满足最优子结构、无法直接使用传统A*系列算法求解的问题,提出了基于学习效应最短路径的启发式精确性搜索AA*算法,保留潜在最优解的子路径,形成搜索图:证明了算法的可采纳性;结合问题具体特性,重新定义了启发函数的单调性和一致性;比较了所提AA*算法中启发函数与A*算法中启发函数单调性/一致性之间的关系;分析并证明了在单调性和一致性满足的前提下启发函数大小对搜索效率影响的相关性质;通过仿真实验验证了所提算法的有效性。(2)针对求出双目标最短路径问题所有非支配解花费时间长(尤其是大规模问题)、非支配解数量随着问题规模增加急剧增加的问题,提出了一种增量式、用户驱动的迭代构造启发式搜索算法UDBA*,通过充分利用之前的搜索信息避免重复搜索,在很短时间内快速得到勾画Pareto前沿面的部分分布均匀的非支配解,以满足用户决策需求;证明了所提算法的可采纳性;分析了启发函数的单调性和一致性对搜索效率的影响;通过仿真实验验证了所提算法的有效性。(3)针对更加一般化的、等待和无等待约束同时存在的混合等待流水调度问题,建立了数学模型;设计了一种最大完工时间的快速计算方法;提出了一种改进迭代贪心算法,通过抽取工件数量动态自适应变化策略以及结合模拟退火思想提高搜索多样性,构造可变邻域搜索增加搜索力度;经过参数和算子修正,将所提算法与五个求解类似问题的算法在修正的Taillard benchmark标准测试例上进行实验比较,结果表明所提算法优于其它算法。