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

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

Vehicle routing problem with multiple constraints using adaptive and polymorphic ant colony algorithm

A novel mathematical model has been developed to address the complicated issue of vehicle routing problem with multiple constraints(VRPMC),which includes the client priority levels,traffic condition influences,multi-type vehicle,time windows and capacity constraints.As an NP-hard problem,this model has no solution based on polynomial algorithm at present.Therefore,an adaptive and polymorphic ant colony algorithm(APACA) has been brought forward to solve the VRPMC.First,spy ants fulfill the reconnaissance to the route that satisfies constraint condition and set reconnoitering pheromones on the route.Then,search ants search the feasible path by the auxiliary information from spy ants.The cooperating among polymorphic ants and adaptively adjusting the volatilizing coefficient can significantly improve the speed to find the optimum solution.Finally,a case study is presented to compare APACA with saving algorithm,genetic algorithm,tabu-search algorithm and ant colony optimum.The test results show that the proposed algorithm is of more advantage than fore mentioned algorithms in computational results stability,transport distance and computational speed for VRPMC.