基于自适应多态蚁群算法的多约束车辆路径问题

作者：陈美军; 张志胜; 史金飞

来源：东南大学学报(自然科学版), 2008, (01): 37-42.

• 车辆路径问题
• 时间窗
• 多约束
• 数学模型
• 自适应多态蚁群算法 vehicle routing problem
• time windows
• multiple constraints
• mathematical model
• adaptive
• polymorphic ant colony algorithm

建立了在有客户优先级、路况影响、多车型、时间窗和容量等多约束条件下车辆路径问题(VRPMC)的数学模型.由于该模型是一个NP-hard问题,目前还没有多项式算法求解,又提出了采用自适应的多态蚁群算法(APACA)来对其进行求解的策略.首先,算法中侦察蚁完成满足约束条件的路径侦察并设置侦察信息素;其次,搜索蚁利用侦察蚁提供的辅助信息进一步搜索可行路径,通过多态蚂蚁间的协作和自适应调整挥发系数,能更快地搜索到问题的优化解;最后通过一个实例与节约算法、遗传算法、禁忌搜索算法和基本蚁群算法进行了对比,结果表明:对VR-PMC问题,APACA算法比前述算法在算法稳定性、运行距离、计算速度方面更具有优势.

• 单位
  东南大学