一种基于模糊需求车辆路径问题的改进蚁群算法

唐瑞雪等

摘 要：针对多种车型，多个供应商，具有模糊需求的车辆路径问题的特点，运用模糊可信性理论，建立了以最短行驶距离和最小车辆使用率为目标函数的数学模型，并设计了求解该模型的一种改进蚁群算法。其中基于置信水平构造初始解，提高解的可行性；引入可信性来调整启发因子，以加快启发式搜索的收敛速度；动态地调整挥发系数，降低初始阶段出现局部收敛的可能，提高寻找最优路径的能力。实验结果表明，所提出的模型和算法是可行有效的。

关键词：模糊需求；车辆路径问题；蚁群算法；可信性；置信水平；挥发系数

中图分类号：TP18

车辆路径问题（简称VRP）属于经典的复杂组合优化问题，是由Dantzing于1959年首次提出的。在以往的VRP研究中，客户的地理位置、需求情况等在路径规划前已经确定，提出了确定VRP的算法。但是在实际的应用中，车辆路径问题的某些信息可能是模糊的、不确定的，模糊车辆路径问题（简称FVRP）开始出现。D.Teodorovic和G.Pavkovic在模糊推理算法中引入了决策者偏好的概念进行求解；张建勇等采用Sweeping算法和混合遗传算法求解模糊需求下的车辆路径问题。

1 问题描述及模型

实验结果表明，本文算法所得车辆行驶距离和车辆利用率是小于文献[6]算法所得行驶距离，尤其当实例集较大时，本文算法明显优于文献[6]算法。所以，本文算法用于求解具有模糊需求的车辆路径问题是可行且有效的。

4 结语

针对模糊需求的车辆路径问题，本文建立了具有模糊特征的数学模型，并提出了基于模糊可信性的改进蚁群算法。算法中通过引入可信性、置信水平来提高运行效率，并考虑了初始化阶段仅以需求量来进行路径构造可能出现局部收敛的情况。本文对soloman实例进行了测试，由实验结果可知本文提出的算法可以快速得到车辆行驶距离较短，车辆利用率较低的路径。

参考文献：

[1]GIANPAOLO G，FRANCESCA G.Real-time vehicle routing：Solution concepts，algorithms and parallel computing strategies[J].European Journal of Operational Research，2001，151（1）：1-11.

[2]ALAN L E，JUAN C M，MARTIN S.The vehicle routing problem with stochastic demand and duration constraints[J].Transportation Science，2010，44（4）：474-492.

[3]袁庆达，杜文，周再玲.带软时间窗的混合车队车辆路线问题的模型和算法研究[J].西南交通大学学报，2001，36（4）：401-406.

[4]TEODOROVIC D，PAVKOVIC G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J].Fuzzy Sets and Systems，1996，82（3）：307-317.

[5]张建勇，李军，郭耀煌.具有模糊预约时间的VRP混合遗传算法[J].管理科学学报，2005，8（3）：64-71.

[6]张建勇，李军，郭耀煌.模糊需求信息条件下的实时动态车辆调度问题研究[J].管理工程学报，2004，18（4）：69-72.

作者简介：唐瑞雪（1987-），女，贵州贵阳人，硕士，研究方向：算法分析；秦永彬（1980-），山东烟台人，博士，研究方向：可计算性及计算复杂性。

作者单位：贵州财经大学信息学院，贵阳 550004；贵州大学计算机科学与信息学院，贵阳 550025

基金项目：贵州省科学技术基金（黔科合J字[2012]2125号）。