蝙蝠算法在物流配送车辆路径优化问题中的应用

车辆路径问题(Vehicle Routing Problem,VRP)是组合优化问题中一个典型的NP难题.蝙蝠算法(Bat Algorithm,BA)是一种新型的智能优化算法,尚未被应用到求解VRP问题中去.根据物流配送中VRP问题的数学模型及其具体特征,设计了求解VRP问题的蝙蝠算法,并通过仿真实例和与其他算法进行比较的方式验证了蝙蝠算法求解VRP问题的有效性与可行性.     

贪婪随机自适应蝙蝠算法在车辆路径问题中的应用

车辆路径问题(Vehicle Routing Problem,VRP)在物流与供应链领域是一个非常有研究价值的NP-Hard问题.蝙蝠算法(Bat Algorithm,BA)是一种新兴的智能优化算法,有着广阔的应用前景.然而它不能直接用于求解离散问题,并且如同大多数智能优化算法一样,容易陷入局部最优,后期收敛速度慢.本文针对VRP问题的具体特性,重新定义了蝙蝠的编码方式并利用GRASP启发式算法生成蝙蝠算法初始种群来改进算法,然后应用于求解VRP问题.     

求解无容量设施选址问题的拉格朗日蝙蝠算法

无容量设施选址问题(Uncapacitated Facility Location Problem,UFLP)是一类经典的组合优化问题,被证明是一种NP-hard问题,易于描述却难于求解.首先根据UFLP的数学模型及其具体特征,重新设计了蝙蝠算法的操作算子,给出了求解UFLP的蝙蝠算法.其次构建出三种可行化方法,并将其与求解UFLP的蝙蝠算法和拉格朗日松弛算法相结合,设计了求解该问题的拉格朗日蝙蝠算法.最后通过仿真实例和与其他算法进行比较的方式,验证了该混合算法用来求解UFLP的可行性,是解决离散型问题的一种有效方式.     

基于蝙蝠退火算法的无等待流水线调度问题研究

无等待流水线调度问题(no-wait flow shop scheduling problem,NWFSP)是一类比较重要的复杂生产调度问题,并已经被证明是典型的NP问题.蝙蝠算法(Bat algorithm,BA)是一种较新颖的群体智能算法.本文针对蝙蝠算法在求解无等待流水线调度问题上的不足,提出一种蝙蝠退火算法,它通过采用ROV的编码方式以实现离散问题的连续编码,同时为了避免算法早熟现象引入了模拟退火算法.算法采用基于NEH的局部搜索规则,在很大程度上提高了算法的性能.利用标准Car问题和Rec问题算例进行仿真实验,结果表明了改进算法的可行性和有效性.     

车辆路径问题的混合优化算法

讨论了一类车辆路径调度问题(VRP)及其数学模型，并且分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，然后结合2-opt局部优化算法提出了GA with2-opt算法来求解VRP问题，试验结果说明了该算法的有效性和可行性。     

改进蚁群算法优化周期性车辆路径问题

周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T＞1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。     

求解一般整数规划问题的改进蝙蝠算法

蝙蝠算法是一种新型的智能优化算法,本文针对基本蝙蝠算法易陷入局部最优、过早处于停滞阶段等不足之处,在蝙蝠速度更新公式中引入了惯性权重,并采用权值动态递减的方式变换权重,更好地平衡了算法的全局搜索能力和局部搜索能力.通过求解一系列经典整数规划问题,并与已有算法进行比较,结果表明:改进的蝙蝠算法在一般整数规划问题的求解中具有较高的计算效率和精度,以及较强的全局搜索能力.     

求解零等待流水车间调度问题的改进蝙蝠算法

针对零等待流水车间调度问题特性,设计了一种蝙蝠算法进行求解.算法模拟蝙蝠捕食搜索行为进行寻优,利用基于最小位置值规则的随机键编码方式来表示问题解,采用基于NEH方法的局部搜索策略和随机交换、插入、逆序操作的变邻域搜索策略来提高局部优化性能,进一步根据Metropolis概率准则接受劣解来避免早熟.通过典型算例对所提算法进行仿真测试并与粒子群算法和RAJ启发式算法进行对比,结果表明所设计算法求解零等待流水车间调度问题的有效性和优越性,是求解流水车间生产调度问题的一种有效工具.     

函数优化的小生境蝙蝠算法

针对蝙蝠算法易陷入局部最优解的缺点,利用小生境技术对蝙蝠算法进行了改进,提出一种小生境蝙蝠优化算法.算法基于小生境技术的适应度共享来分隔种群,引入了小生境排挤机制来保持种群多样性,在延续蝙蝠算法原有并行搜索等优势的基础上,提高了算法的金局搜索能力和局部收敛速度,具有可在不同邻域内发现多个解的特点.通过对一系列经典函数测试,并与已有算法进行比较,结果表明该算法在函数优化问题的求解中具有较高的计算效率和精度,以及较好的全局寻优能力.     

基于精英单亲遗传算法的冷链物流VRP模型优化研究

针对冷链物流配送的特殊性,探索冷链物流车辆路径问题(VRP)优化方案.首先,在保证货物不超载的条件下,建立基于时间和品质因素的顾客满意度约束的多配送中心VRP(MDVRP)模型;其次,采用重心分区法和改进的精英单亲遗传算法,求解顾客在配送中心的分配,确定配送车辆数以及顾客服务次序;最后,用Matlab工具编程对模型进行求解分析.结果表明构建基于满意度的冷链物流MDVRP模型更适合冷链物流配送最优路径选择,并且改进单亲遗传算法能够有效求解这类问题.     

An exact solution framework for a broad class of vehicle routing problems

This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.     

A reactive tabu search for the vehicle routing problem

The classical vehicle routing problem (VRP) involves determining a fleet of homogeneous size vehicles and designing an associated set of routes that minimizes the total cost. Our tabu search (TS) algorithm to solve the VRP is based on reactive tabu search (RTS) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. We compare our algorithm with the best methods in the literature using different data sets and report results including new best known solutions for several well-known benchmark problems.     

随机需求的车辆路线问题的新模型

本主要研究随机需求的VRP问题,其中服务需求量满足二项式分布,根据期望值的大小我们提出了在一条路线上理想最大服务点数的新概念,并在此基础上建立了三种VRP问题的新模型,由于允许服务失败两次和部分服务使得模糊能适应多种实际问题,以模拟退火思想为基础的两阶段方法经修正后用于解新模型并取得较好的数值结果,理论分析和数值结果表明,新模型较好地描述随机需求的VRP问题,并且容易求解。     

Exact algorithms for the chance-constrained vehicle routing problem

We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of vehicles required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the VRP with stochastic demands. In contrast to the deterministic VRP, we find that the pricing problem for the CCVRP problem is strongly \(\mathcal {NP}\)-hard, even when the routes being priced are allowed to have cycles. We therefore propose a further relaxation of the routes that enables pricing via dynamic programming. We also demonstrate how our proposed methodologies can be adapted to solve a distributionally robust CCVRP problem. Numerical results indicate that the proposed methods can solve instances of CCVRP having up to 55 vertices.     

Disruption management of the vehicle routing problem with vehicle breakdown

This paper introduces a new class of problem, the disrupted vehicle routing problem (VRP), which deals with the disruptions that occur at the execution stage of a VRP plan. The paper then focuses on one type of such problem, in which a vehicle breaks down during the delivery and a new routing solution needs to be quickly generated to minimise the costs. Two Tabu Search algorithms are developed to solve the problem and are assessed in relation to an exact algorithm. A set of test problems has been generated and computational results from experiments using the heuristic algorithms are presented.     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。