论文部分内容阅读
蝙蝠算法（Bat Algorithm,BA）是Yang受自然界中蝙蝠通过回声定位的方式进行搜索、捕食的生物学特性的启发,于2010年提出的一种新型群智能仿生优化算法[1]。截至目前,BA算法用于求解的问题包括连续域函数优化问题,如基准测试函数;组合优化问题,如二值优化问题、背包问题、最小比率TSP问题、可靠性冗余分配问题等。BA因其具有结构简单、参数少、搜索能力强、稳定性强、易于实现等优点,在函数优化、调度问题、模式识别、图像处理、故障诊断等方面表现出极大优势。随着电子商务的繁荣发展,车辆路径问题（Vehicle Routing Problem,VRP问题）作为物流过程中的一项经典组合优化问题,涉及到的客户规模越来越大,所在区域分布也越来越广泛,客户对配送时间和同时取送货的要求也越来越苛刻。由于电商的发展促使物流快递公司增多,使得用户的选择面增多,物流快递业的竞争也随之加剧,使得用户对配送时间、商家对送货成本和有取送货相关的需求更高。结合求解VRP问题的相关文献可以了解到:对基本VRP问题求解较多,单独考虑时间窗或取送货为限制条件的VRP问题也不在少数,但是对结合时间窗惩罚值、车辆载重限制和取送货的VRP问题求解较少。因此,本文设计求解考虑时间窗限制、车载限制和取送货的VRP问题（Capacitated Vehicle Routing Problem with Time Windows,Simultaneous Delivery and Pickup and Vehicle Restraint,CVRPTW-SDP）。由于VRP问题是NP-HARD难题,经典算法不能在有限时间内给出最优解,但是可以使用智能算法在有限时间内给出相对较优解。本文根据CVRPTW-SDP问题的特点以及BA算法的寻优机制,研究并设计求解CVRPTW-SDP问题的离散蝙蝠算法（Discrete Bat Algorithm,DBA）。为了使用用来求解连续优化问题的BA算法求解CVRPTW-SDP问题,定义蝙蝠算法的离散化编码策略和操作算子,需要进行离散化编码的对象包括蝙蝠的所在位置和飞行速度;需要重新定义的操作算子包括加法操作算子、两个解的减法操作算子以及修正操作算子。为了进一步提高DBA算法的稳定性,使用K-means聚类算法对每次迭代的初始解进行聚类分析,K-means算法应用到CVRPTW-SDP问题的求解目标就是把邻近的配送点聚合成一类,因而加入聚类因子的DBA算法有更高的鲁棒性和稳定性,同时在一定程度上提高了DBA算法的求解速度;为了进一步增强BA算法的局部搜索能力,借鉴遗传算法的交叉、变异因子在较优解附近进行局部搜索。为了验证该DBA算法的有效性,首先根据是否带车载限制、时间窗和同时取送货约束把CVRPTW-SDP问题拆分为TSP问题、CVRP问题、VRPTW问题、CVRPTW问题、CVRP-SDP问题、CVRPTW-SDP问题。然后分别设计出求解这6个VRP问题的DBA算法。最后使用DBA算法与PSO、GA算法在相同运行时间内求解所得最优解及解的平均值进行对比的方式验证DBA算法的可行性。