马洪坤，杨　伟，赵　佳，郝海彬

(西华大学交通与汽车工程学院，四川 成都　610039)



基于遗传蚁群算法的带时间窗多车场车辆调度问题

马洪坤，杨伟*，赵佳，郝海彬

(西华大学交通与汽车工程学院，四川 成都610039)

摘要：给出带单边硬时间窗的多车场车辆调度问题的数学模型，并提出一种遗传蚁群融合算法。该算法在遗传算法的基础上加入蚁群路径搜索和自适交叉变异来提高算法搜索能力，并且采用模拟退火个体接受方式接受蚁群路径搜索产生的新个体，从而使算法提高了跳出局部最优点能力。结合算例计算验证了算法的有效性和正确性。

关键词：遗传蚁群算法； 自适应； 多车场； 时间窗； 车辆调度问题

车辆路径优化问题是一个经典NP难题[1]，该问题是指在已知配送中心、客户位置和需求量的前提下，在满足运输容量和送达时间约束的基础上，规划出一条或者若干条运输时间或运输距离最小的路径。该问题具有比较大的现实意义，现实中很多客户对货物的需求时间都比较严格，因而都可以归结为带硬时间窗的多车场车辆调度问题；但是该问题是一个NP难度问题，一般优化算法难以得到问题的最优解。近年来，遗传算法和蚁群算法等启发式算法在该类问题的求解中得到成功应用[2-4]，但算法优化结果还有进一步提高的空间。

遗传蚁群算法结合了遗传算法和蚁群算法的优点，是一种优化能力较好的启发式算法。本文从遗传自适应搜索和模拟退火向后搜索机制两方面改进该算法，较好地提高了算法的搜索效率和搜索结果。……