基于改进蝙蝠算法的带模糊需求的车辆路径问题

Vehicle Routing Problem with Fuzzy Demands Based on An Improved Bat Algorithm

摘要:

蝙蝠算法作为一种新的元启发式算法,尚未被应用到模糊车辆路径问题中；针对带模糊需求的车辆路径问题,以极小化总运输距离为目标,建立基于可信性理论的模糊规划模型,提出一种改进的蝙蝠算法；算法采用基于客户编号的编码方式,利用随机模拟算法计算额外行驶距离；在蝙蝠位置更新时,引入基于非线性调整的惯性权重和基于子路径的局部搜索；为提高全局搜索能力,避免算法早熟,对处于较差位置的蝙蝠进行交叉操作；最后,利用随机实验数据进行仿真,分析了决策者主观偏好值对目标值的影响,并与其它算法的寻优结果进行对比分析,结果表明,算法具有一定的可行性和有效性。

Abstract:

As a new meta-heuristic, bat algorithm has not yet been applied to solve fuzzy vehicle routing problem until now. In this paper, the vehicle routing problem with fuzzy demands is considered at first, in which the final objective is to minimize the total distance, and then a fuzzy programming model based on fuzzy credibility theory is presented, in order to solve this problem, an improved bat algorithm with the coding method of customer number is introduced. In this algorithm, a stochastic simulation is proposed to calculate the additional distance, moreover, a nonlinear adjustment strategy for the inertia weight and a local search strategy on sub-route are designed at the stage of location updating of each bat, on the other hand, to improve the global search ability of this algorithm and avoid premature convergence, crossover operation on the worst bats is applied. To illustrate the effectiveness and good performance of the proposed algorithm, an example is carried out by using the random experimental data, and the influence of the decision-maker’s preference on the objective of this problem is discussed, moreover, the improved bat algorithm is compared with other algorithms.