刘春苗　张惠珍　马祥丽

摘要根据车辆路径问题的数学模型，分析了它的具体特征，从而对BA的操作算子又进行了重新定义，设计了求解VRP问题的离散蝙蝠算法，并通过实例测试将离散蝙蝠算法与其他算法进行比较，验证了该算法求解VRP问题的有效性与可行性.

关键词车辆路径问题；蝙蝠算法；离散；遗传算法

中图分类号U492.3文献标识码A

AbstractBased on the mathematical model and specific features of the vehicle routing problem（VRP），this paper redefined the operators for bat algorithm（BA） and designed a discrete bat algorithm （DBA） for solving it. And numerical experiment was implemented by using DBA to solve a testing example， and its solution was compared with the one obtained with the stateoftheart algorithm. The results show that DBA can effectively and feasibly solve VRP.

Keywordsvehicle routing problem； bat algorithm； discrete； genetic algorithm

1引言

车辆路径问题（Vehicle Routing Problem， VRP）主要目的是在一定的约束条件下，最大化满足客户需求的同时消耗最少的时间，所行驶的路程最短，成本最小，学者们也通常称它为有能力约束的车辆路径问题（Capacity Vehicle Routing Problem， CVRP），它最早来源于货物交通运输工程领域[1]，是车辆调度中最基本的问题之一.求解旅行商问题（Traveling Salesman Problem， TSP）和装箱问题（Bin Packing Problem， BPP）分别是求解车辆路径问题（VRP）的两种特殊情况，研究者们通常把VRP问题看作是这两种问题的的混合问题，其已被证明属于NP完全问题.

车辆路径问题（VRP）首次由美国学者在1959年提出[2]，其逐渐成为运筹学与组合优化领域的研究热点，并引起了广大学者们的高度重视.目前，求解VRP问题的经典算法主要有：网络流算法、列生成算法、和割平面法等等，但是，这些经典的方法仅适用于求解小规模车辆路径问题；面对大规模的VRP问题时，其庞大的计算量导致计算速度缓慢，运行效率低，甚至出现无法求解的情况.随着遗传算法、蚁群算法、遗传算法、禁忌搜索算法、粒子群算法等智能优化算法的提出及其在组合优化问题中的应用，求解大规模……