Abstract: Aiming at the Multi-Deport Open Vehicle Routing Problem (MDOVRP) influenced by time window,customers'satisfaction level and the corresponding time punishment cost function were described with fuzzy theory,which assumed time window was a trapezoidal fuzzy number,and a robust optimization model was developed.Based on overall method,the virtual distribution center was supposed,and the improved ant colony algorithm was proposed.Numerical experiments were carried out and the results indicated that the proposed algorithm could find high quality solutions with good performance;the developed model was effective and could obtain solutions meeting the characteristics of multi-center,multi-customers and open routing;compared with soft time windows or hard time window,fuzzy time window was more reasonable,and the influences of customer satisfaction level on the solution were illustrated.

Key words: vehicle routing problem, multi-deport vehicle routing problem, open vehicle routing problem, fuzzy time window, ant colony algorithm

摘要： 针对受时间窗影响的多中心开放式车辆路径问题,采用时间窗模糊化处理方法,假设时间窗是一个梯形模糊数,定义客户满意度函数和时间惩罚费用函数,建立有鲁棒优化模型。基于整体法假设虚拟配送中心,设计改进的蚁群算法求解,选取合适的测试算例实验。实验结果表明,所提算法能获得较好的解,是求解该类问题的有效方法;所建模型满足问题的多中心、多需求点和开放式特征,模型合理有效;与软时间窗和硬时间窗设置相比,模糊时间窗设置合理有效,同时展示了模糊时间窗设置下客户满意度对模型求解结果的影响。

关键词: 车辆路径问题, 多中心车辆路径问题, 开放式车辆路径问题, 模糊时间窗, 蚁群算法