论文部分内容阅读
定向问题可分为传统定向问题(OP)和团队定向问题(TOP),是一类特殊的NP-hard路径优化问题,在物流领域、旅游领域非常常见同时也具有极大的挑战性。在介绍国内外定向问题研究现状后引出重点研究的带指定点集的TOP问题,在介绍众多元启发式算法求解定向问题后,引出蚁群优化算法,概述了蚁群算法的基本思想、优缺点等,为带指定点集的TOP问题提供了方法指导和理论依据。为传统OP问题和TOP问题建立了数学模型,在基本蚁群算法的基础上改进启发因子和信息素更新策略,给出两组模型数据测试算法的有效性,算例表明了改进的蚁群算法收敛较快且具有稳定性。考虑现实世界配送问题中客户性质不同的特点,提出了在TOP问题中考虑指定点集这个因素的重要性,形成了带指定点集的TOP问题。对于带指定点集的TOP问题,研究了起终点固定和回到起点两种情形。加入时间窗约束形成了有时间窗约束的带指定点集的TOP问题。针对起终点固定和回到起点两种情形,对问题进行描述后建立了在时间限制下,带指定点集的以利润最大为目标的TOP问题模型。针对起终点固定的情形,提出了带2-opt的最大最小蚂蚁系统的蚁群优化算法求解,结合实际改进启发信息和信息素更新策略,采取2-opt对最优解进行优化。针对回到起点的情形,在求解起终点固定情形的带2-opt的最大最小蚂蚁系统的蚁群优化算法基础上调整信息素更新策略。数值算例验证了算法的有效性,对比分析了路径数相同,带指定点集约束和无指定点集约束的求解情况,表明了在TOP问题中考虑指定点集的重要性。针对有时间窗约束的带指定点集的TOP问题,对问题进行描述后建立了在时间限制下,有时间窗约束的带指定点集的以利润最大为目标的TOP问题模型。在求解起终点固定情形的带指定点集的TOP问题算法的基础上,加入等待时间和时间窗跨度对下一点概率的影响,数值算例表明了算法的有效性。对比分析了路径数相同,带指定点集约束和无指定点集约束的求解情况,再一次表明了在TOP问题中考虑指定点集这一因素的重要性。虽然考虑指定点配送时收益往往比不考虑指定点配送时少,但从企业长期利益出发,部分耗时长、收益少的客户必须配送,这可以理解为企业暂时以损失收益为代价寻求长远发展。带指定点集的TOP问题不仅丰富了定向问题的理论,也结合实际为现实中类似问题提供参考与决策支持。