求解车辆路径问题的离散蝙蝠算法
摘要根据车辆路径问题的数学模型，分析了它的具体特征，从而对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问题时，其庞大的计算量导致计算速度缓慢，运行效率低，甚至出现无法求解的情况.随着遗传算法、蚁群算法、遗传算法、禁忌搜索算法、粒子群算法等智能优化算法的提出及其在组合优化问题中的应用，求解大规模VRP问题得到了较好地解决.
2010年剑桥大学的一名资深研究员杨提出了一种新的群体智能优化算法——蝙蝠算法[3]，它是根据微型蝙蝠在自然界中通过回声定位来捕捉猎物和躲避障碍物的生物学特性研究出的一种算法，是一种基于种群的随机寻优算法.目前为止很少有学者将蝙蝠算法应用到离散问题中去，还停留在解决求解连续函数优化问题中.学者盛晓华等人[4]在2013年通过分析PFSP调度的问题发现蝙蝠算法能够更加有效地解决这类离散型车辆路径问题；在同一年，李枝勇[5]等人，他们设计出了求解TSP问题的离散蝙蝠算法；在2014年，中国学者马邦雄[6]等人提出了一种蝙蝠退火算法，采用ROV编码的方式实现了蝙蝠算法（BA）的连续编码.
目前，尚未有文献将蝙蝠算法应用于VRP问题的求解，将蝙蝠算法应用于VRP问题的求解是一个新的研究方向.
经济数学第 33卷第4期刘春苗等：求解车辆路径问题的离散蝙蝠算法
2VRP的数学模型
车辆路径优化问题一般描述为：假设配送中心（这里的配送中心用0来表示）最多可以用K（k=1，2，…K）辆车对L（i=1，2，…L）个客户进行配送运输服务，配送运输车辆的载重量分别为qk（k=1，2，…K），每个客户的需求量分别为gi=（i=1，2，…L），客户i到客户j的运输成本为cij（可以是距离、费用等），要求配送中心用最短的行驶距离或运输费用完成对所有客户的配送任务.
3基本蝙蝠算法
蝙蝠是一种神奇的动物，有很强的回声定位能力.微型蝙蝠使用一种叫做回音定位的声波定位器，主要用来探测食物位置，躲避障碍物，捕捉猎物，找到自己的巢穴等.它们发出的声音脉冲很响亮这样更有助于根据从周围物体反射回来的回声响度和蝙蝠的双耳时间差去建立一个立体的三维环境场景[7].
蝙蝠算法是将虚拟蝙蝠类比成当前的可行域内所分布的搜索点，将蝙蝠飞行移动来不断探测猎物的过程类比为寻找目标函数最优解的过程[8].
3.1虚拟蝙蝠的运动
4.2线路设计
本文采用最近邻算法构造初始配送路线，采用2opt算法对路线进行改进.下面分别给出配送路线构造和改进的方法.
配送线路构造方法最邻近算法（Nearest Neighbor Algorithm，NNA）[10]：首先取配送中心（0）作为线路的起点；然后寻找与当前线路中最后一个结点的距离最近的点，并将其加入配送线路，重复该操作，直到所有的点均已被考虑，就得到一条配送线路.
值得注意的是：利用上述最近邻法得到的是一条包含所有客户点的配送线路.本文所设计的离散蝙蝠算法将会根据线路中客户的排序，车辆载重量和客户需求量进一步求解实际配送车辆数及相应的配送路线.
配送路线的改进方法——2opt算法[10]：2opt算法的基本思想是对给定的初始回路，通过每次交换两边来改进当前解.
例如如图2（a）所示，车辆初始得行驶路径为：由客户i到达客户i+1，再由客户i+1经若干客户后到达客户j，然后再访问客户j+1；采用2opt算法对图2（a）中得路线进行变换，若以（i，j）、（i+1，j+1）替代（i，i+1）、（j，j+1），则可变为如图2（b）所示的配送路线.
由表2可知：本文采用离散蝙蝠算法求解的最短路径（r）897.56km要优于文献[11]中遗传算法求解的最优路径964.48km；并且本文为最优路径安排车辆时只需要安排5辆车即可，而文献[11]需要安排6辆车才能满足需要，这样势必会增加一定的成本.从对比分析可知，蝙蝠算法对于求解CVRP问题是行之有效的，且该算法参数设置简单，易于操作，运行周期短，便于求解大规模VRP问题.
6结论
本文将蝙蝠算法用于求解VRP问题，根据VRP问题的具体特性重新定义了蝙蝠算法的相关操作算子，设计出了求解VRP问题的离散蝙蝠算法.本文的实验结果显示出了离散蝙蝠算法在求解VRP问题上的可行性、有效性和优越性.
蝙蝠算法参数设置简单，在各类VRP问题的求解中拥有广阔的应用前景.为了扩展蝙蝠算法的应用领域，并进一步研究蝙蝠算法求解相关问题的可行性和有效性，利用离散蝙蝠算法求解设施选址问题将是作者下一步的研究工作.
参考文献
[1]吴斌. 物流配送车辆路径问题及其智能优化算法[M]. 北京：经济管理出版社，2013.
[2]G B DANTZIG，J H RAMSER.The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.
[3]X S YANG. A new metaheuristic batinspired algorithm[C]//Nature Inspired Cooperative Strategies for Optimization （NISCO 2010） （Eds. J R Gonzalez et al.），SCI 284，2010： 65-74.
[4]盛晓华，叶春明. 蝙蝠算法在PFSP调度问题中的应用研究[J]. 工业工程，2013，16（1）： 119-124.
[5]李枝勇，马良，张惠珍. 求解最小比率旅行商问题的离散蝙蝠算法[J]. 计算机应用研究，2015，32（12）：356-359.
[6]马邦雄，叶春明. 基于蝙蝠退火算法的无等待流水线调度问题研究[J]. 数学理论与应用，2014，34（1）：92-101.
[7]孙文捷，张惠珍，张健，等. 基于Fuch映射的混沌蝙蝠算法[J]. 上海理工大学学报，2014，36（1）：26-30.
[8]高珊，马良，张惠珍. 函数优化的小生境蝙蝠算法[J]. 数学的实践与认识，2014，44（15）：253-260.
[9]赵玉新，XinShe YANG，刘利强. 新兴元启发式优化方法[M]. 北京：科学出版社，2013.
[10]李军，郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001.
[11]陈湘州，黎志明，刘祖润. 一种改进的整数编码遗传算法在车辆路径优化问题中的应用[J]. 南方冶金学院学报，2004，25（1）：36-41.