多时间窗车辆路径问题的智能水滴算法  

Intelligent Water Drops Algorithm for Vehicle Routing Problem with Multiple Time Windows

作　　者：李珍萍[1] 赵菲[1] 刘洪伟[1] 

机构地区：[1]北京物资学院信息学院,北京101149

出　　处：《运筹与管理》2015年第6期1-10,共10页Operations Research and Management Science

基　　金：国家自然科学资助项目(11131009;71540028);北京市属高等学校长城学者培养计划项目(CIT&TCD20130327);北京市科委项目<用于电子商务物流的搬运机器人与多机器人现场控制系统研制及应用验证>;北京物资学院重大科研项目<基于可移动货架的订单拣选优化问题研究>

摘　　要：研究了多时间窗车辆路径问题,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型。根据智能水滴算法的基本原理,设计了求解多时间窗车辆路径问题的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示,利用智能水滴算法求解多时间窗车辆路径问题,能够以很高的概率得到全局最优解,是求解多时间窗车辆路径问题的有效算法。The vehicle routing problem with multiple time windows is investigated in this paper. The constraints of vehicle＇s capacity and the multiple hard time windows are considered. An integer linear programming model of VRPMTW is proposed, and the objective function is to minimize the total costs including the fixed costs of vehicles and the transportation costs of vehicles. Based on the principles of the intelligent water drops, an Intelligent Water Drops（IDW）algorithm for solving the VRPMTW is designed. We further do simulation on an example, and compare the results obtained by IDW algorithm and GA（genetic algorithm）algorithm. The results show that we can find the global optimal solution of VRPMTW with higher probability using Intelligent Water Drops algorithm than Genetic Algorithm. IDW algorithm is an efficient algorithm for solving VRPMTW.

关 键 词：车辆路径问题 多时间窗 数学模型 智能水滴算法 

分 类 号：O226[理学—运筹学与控制论]