求解车辆路径问题的离散蝙蝠算法

《求解车辆路径问题的离散蝙蝠算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、求解车辆路径问题的离散蝙蝠算法　　摘要根据车辆路径问题的数学模型，分析了它的具体特征，从而对BA的操作算子又进行了重新定义，设计了求解VRP问题的离散蝙蝠算法，并通过实例测试将离散蝙蝠算法与其他算法进行比较，验证了该算法求解VRP问题的有效性与可行性.　　关键词车辆路径问题；蝙蝠算法；离散；遗传算法　　中图分类号U492.3文献标识码A　　AbstractBasedonthemathematicalmodelandspecificfeaturesofthevehicleroutingproblem（VR

2、P），thispaperredefinedtheoperatorsforbatalgorithm（BA）anddesignedadiscretebatalgorithm（DBA）forsolvingit.AndnumericalexperimentwasimplementedbyusingDBAtosolveatestingexample，anditssolutionwascomparedwiththeoneobtainedwiththestateoftheartalgorithm.Theresults

3、showthatDBAcaneffectivelyandfeasiblysolveVRP.　　Keywordsvehicleroutingproblem；batalgorithm；discrete；geneticalgorithm　　1引言　　车辆路径问题（VehicleRoutingProblem，6VRP）主要目的是在一定的约束条件下，最大化满足客户需求的同时消耗最少的时间，所行驶的路程最短，成本最小，学者们也通常称它为有能力约束的车辆路径问题（CapacityVehicleRoutingProbl

4、em，CVRP），它最早来源于货物交通运输工程领域[1]，是车辆调度中最基本的问题之一.求解旅行商问题（TravelingSalesmanProblem，TSP）和装箱问题（BinPackingProblem，BPP）分别是求解车辆路径问题（VRP）的两种特殊情况，研究者们通常把VRP问题看作是这两种问题的的混合问题，其已被证明属于NP完全问题.　　车辆路径问题（VRP）首次由美国学者在1959年提出[2]，其逐渐成为运筹学与组合优化领域的研究热点，并引起了广大学者们的高度重视.目前，求解VRP问题的经

5、典算法主要有：网络流算法、列生成算法、和割平面法等等，但是，这些经典的方法仅适用于求解小规模车辆路径问题；面对大规模的VRP问题时，其庞大的计算量导致计算速度缓慢，运行效率低，甚至出现无法求解的情况.随着遗传算法、蚁群算法、遗传算法、禁忌搜索算法、粒子群算法等智能优化算法的提出及其在组合优化问题中的应用，求解大规模VRP问题得到了较好地解决.　　2010年剑桥大学的一名资深研究员杨提出了一种新的群体智能优化算法――6蝙蝠算法[3]，它是根据微型蝙蝠在自然界中通过回声定位来捕捉猎物和躲避障碍物的生物学特性

6、研究出的一种算法，是一种基于种群的随机寻优算法.目前为止很少有学者将蝙蝠算法应用到离散问题中去，还停留在解决求解连续函数优化问题中.学者盛晓华等人[4]在2013年通过分析PFSP调度的问题发现蝙蝠算法能够更加有效地解决这类离散型车辆路径问题；在同一年，李枝勇[5]等人，他们设计出了求解TSP问题的离散蝙蝠算法；在2014年，中国学者马邦雄[6]等人提出了一种蝙蝠退火算法，采用ROV编码的方式实现了蝙蝠算法（BA）的连续编码.　　目前，尚未有文献将蝙蝠算法应用于VRP问题的求解，将蝙蝠算法应用于VRP问

7、题的求解是一个新的研究方向.　　经济数学第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基本蝙蝠

8、算法　　蝙蝠是一种神奇的动物，有很强的回声定位能力.微型蝙蝠使用一种叫做回音定位的声波定位器，主要用来探测食物位置，躲避障碍物，捕捉猎物，找到自己的巢穴等.它们发出的声音脉冲很响亮这样更有助于根据从周围物体反射回来的回声响度和蝙蝠的双耳时间差去建立一个立体的三维环境场景[7].　　蝙蝠算法是将虚拟蝙蝠类比成当前的可行域内所分布的搜索点，将蝙蝠飞行移动来不断探测猎物的过程类比为寻找目标函数最优解的过程[8].　　3.1虚拟蝙蝠的运动　　4.2