模糊需求车辆路径问题及其优化算法研究

李子豪

摘要：在实际物流配送问题中，客户需求量可能在制定物流配送路径计划问题时无法被准确获取，随着配送工作的进行，才能逐步获取客户的实际需求量，在需求未明的预优化阶段建立初始路径规划模型，在获知实际需求的实时调整阶段，制定调整策略进行调整。通过对当前模糊需求车辆路径问题相关文献的研究，文章不仅对常见的模糊需求车辆路径问题模型进行了系统的归纳，还对现有的寻优算法进行总结归纳，指出不足，拓展今后可能的研究方向。

Abstract： In the actual logistics distribution problem， the customer demand may not be accurately obtained when formulating the logistics distribution path planning problem. With the progress of the distribution work， the actual customer demand can be gradually acquired. The initial path planning model is established in the pre-optimization stage with unknown demand， in the real-time adjustment stage when the actual demand is known， an adjustment strategy is formulated for adjustment. Based on the current literature on fuzzy demand vehicle routing problems， this article not only systematically summarizes common fuzzy demand vehicle routing problems， but also summarizes existing optimization algorithms， points out deficiencies， and expands possible future research direction.

关键词：车辆路径;模糊需求;模糊可信性;启发式算法

Key words： vehicle path;fuzzy demand;fuzzy credibility;heuristic algorithm

中图分类号：U116.2                                      文献标识码：A                                  文章编号：1006-4311（2020）06-0138-03

0  引言

作为物流配送的重要组成部分，车辆路径问题是物流运输决策的核心，能否实现物流现化关键因素也取决于车辆的路径问题。在满足约束条件的情况下，合理的运输路径能够帮助企业取得更高的经济效益，对于实现资源、环境和价值观的内在统一也有所帮助，对整个物流行业的飞速发展以及经济的可持续发展也起一定的推动作用。模糊需求车辆路径问题（VRPFD）考虑实际配送过程中客户需求存在模糊性这一情况，使研究更贴近实际。

通常采用两阶段法求解VRPFD，当客户发出需求指令时，由于需求未明，首先应根据当前信息制定预优化路径，在此基礎上随着配送活动的进行，确定客户的需求量后进行实时调整使得其配送活动顺利进行。已有文献研究从两方面进行：一是预优化阶段模型的构建，Teodorovic[1]等运用模糊推理求解;Luci和Teodorovic [2]提出运用模糊集合进行求解;Liu[3]运用模糊可信性理论进行求解。二是实时调整策略的选择，多数文献均采用文献[1]中的调整策略，即一种基于服务失败点返回配送中心的策略，当一辆车计划服务第p个客户后，其剩余车载量为DP，当DP<0时，标记p点为配送失败的点，车辆服务完第p个客户之后返回原配送中心补货，再回到p点继续服务紧接着再服务原路径剩余的客户点;由三角形三边定理可知，在失败点的前一个客户点返回配送中心会比在失败点返回路径更短，Yang[4]在此基础上做了改进，当DP<下一客户需求期望值时，车辆则返回配送中心进行补货，但此策略在降低配送失败概率的同时，却使得出现不恰当返回次数的可能性大大增加，产生不必要的成本;然而以上种种调整策略均要求车辆返回配送中心，装货（或者卸货），然后返回该客户点。这通常只适用于不考虑配送时效的车辆路径问题，然而实际配送活动中往往不能忽略客户的配送时间要求，针对单条配送线路服务客户点较多或客户点偏远的情况，若在该时间点重回车库再驶回客户点，必将冲破时间窗的约束，从而导致客户满意度及服务质量下降。因此带时间窗的模糊需求车辆路径问题不仅需要考虑车辆的行驶距离，同时也要兼顾车辆配送满足对客户服务时间的要求。

1  模糊需求车辆路径问题描述与一般模型

2  VRPFD的求解算法分析

VRPFD问题属于复杂的NP难问题，计算难度较高，通常使用优化算法进行求解。然而由于精确算法本身的局限性使其对求解数量规模较大的问题计算难度呈指数型提升，目前专家学者主要研究如何构造优质的启发式算法来提升求解效率和准确性。求解VRPFD问题的主要启发式算法如下：

①扫描算法（Sweep Algorithm）。扫描算法本质上是通过建立极坐标系，根据客户点与配送中心的位置关系，将邻近的客户点归并到一个子路径中去。首先在极坐标系下对客户点位置进行转换，以角度最小的两个客户首先建组，之后沿同一方向转动，将客户点逐步进行添组，当满足车辆载重量约束时，则该路线完成。重复此操作直至所有客户都被分到某个组为止。各个组中的客户点可看作独立的TSP问题，进行求解，最后进行线路优化。Teodorovic和Pavkovic[1]最早研究了考虑模糊需求这类车辆路径问题，以决策者风险偏好为基础建立模糊评判规则，用Sweep算法对路径进行优化。

②遗传算法（Genetic Algorithm，GA）。遗传算法的基本原理是模拟生物学中的遗传机制，针对问题具体情况对随机产生的种群中个体进行编码，设计合适的适应度函数，经过复制、交叉、变异等操作对种群进行不断优化，最后通过反复的迭代计算适应度值直至满足终止条件得到最优结果。王君等[5]提出了基于模糊需求车辆问题的动态管理策略，并通过在非支配排序混合遗传算法中运用模糊模拟的方法来进行模型的求解。针对带模糊需求与模糊时间窗的车辆路径问题，范厚明等[6]构建基于可信性测度理论的多目标模糊机会约束模型。为提高种群的多样性，改进了交叉算子，在引入局部优化算法及擂台法则的基础上，设计了适合求解多目标车辆路径问题的混合遗传算法。

③蚁群算法（Ant Colony Optimization  ACO）。蚁群算法是通过模仿自然界中蚁群觅食行为发展而来，是一种通过正反馈与分布式协作来寻找最优路径的随机优化仿生算法。刘金亮[7]在模糊可信性理论的基础上为解决单配送中心、单一车辆情况下的模糊需求车辆路径问题建立了模糊机会约束规划模型，并提出了一种混合蚁群算法求解此类问题。

④禁忌搜索算法（Tabu Search TS）。禁忌搜索是在搜索过程中构造一个短期记忆表，即为禁忌表，表中存放刚刚搜索过的结果。在一定次数范围r内，禁忌表中所存放的结果不能重复，r次之后，禁忌解除。禁忌表始终保持r个移动。当满足停止规则或迭代内所搜索到最好结果无法改进也无法离开时，搜索活动停止。李阳等[8]针对客户需求量模糊特点，提出分为两阶段法处理该问题，并设计了两阶段变邻域禁忌搜索算法（VNTS），第一阶段基于可信性理论构建模糊机会约束模型设计预处理方案，第二阶段通过重调度策略针对客户点实际需求调整预优化方案。

⑤粒子群算法（Particle Swarm Optimization PSO）。粒子群算法的提出源于研究者发现鸟群在飞行过程中其整体总保持着动态一致性，通过模拟生物群体这一特性，粒子群算法应运而生，属于经典的群智能算法，不同于遗传算法，粒子群算法没有交叉、变异算子，以及复杂多样的编码方式，他是通过个体位置和速度信息的不断更新，通过个体之间的相互联系和影响在解空间中不断进行搜索，最终求得全局最优解。Peng和Qian[9]结合模糊模拟运用PSO算法模糊需求车辆问题进行求解。

3  总结与展望

模糊需求车量路径优化問题由于各研究学者所设目标函数及约束条件不同使得问题模型与相应求解算法千差万别，各有优势与不足。本文总结了近年来相关学者对模糊需求路径优化的研究和求解算法，总结出当前研究有待于改进的问题和今后可能的研究方向：①现有的研究多是考虑路径最短或成本最小，研究目标太过理想化，而在实际应用中驾驶员可能因为诸多原因耽误行程，驾驶员工作时间，路上交通状况都应当考虑在内，更贴合实际。②目前模糊需求车辆路径优化问题多为单配送中心配送，配送模式较为单一，局限性较大，今后的研究可以考虑在多配送中心联合配送模式下进行，更好的解决企业的配送优化，使得成本进一步降低。③现有的智能优化算法虽然运行较为方便，搜索能力强，但很多算法求解存在不稳定的问题，容易陷入局部最优，或收敛时间较长等问题。应考虑对算法进行不断改进和创新，提高算法的稳定性和求解效率。

参考文献：

[1]TEODOROVIC D，PAVKOVICG.The Fuzzy Set Theory Approach to the Vehicle Routing Problem when Demand at Nodes Is Uncertain [J].Fuzzy Sets and Systems，1996，82 （3） ：307-317.

[2]LUCI P， TEODOROVIC D. Vehicle routing problem with uncertain demand at nodes： The bee system and fuzzy logic approach[C]. Fuzzy Sets in Optimization，2003：67-82.

[3]LIU B.Uncertain theory：an introduce to its axiomatic foundations[M].Berlin：Springer， 2004.

[4]YANG W，MATHUR K，BALLOU R H.Stochastic vehicle routing problem with restocking[J].Transportation Science，2000，34（1）：99-112.

[5]王君，李波.基于多目标优化的模糊需求VRPTW动态管理[J].管理学报，2013，10（02）：238-243，279.

[6]范厚明，吴嘉鑫，耿静，李阳.模糊需求与时间窗的车辆路径问题及混合遗传算法求解[J/OL].系统管理学报，2020（01）：107-118.

[7]刘金亮.求解模糊需求条件下车辆路径问题的混合蚂蚁算法[A].中国运筹学会智能计算分会.第三届中国智能计算大会论文集[C].中国运筹学会智能计算分会：清华大学数学科学系，2009：4.

[8]李阳，范厚明，张晓楠，杨翔.求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法[J].系统工程理论与实践，2018，38（02）：522-531.

[9]PENG Y，QIAN Y-M. A particle swarm optimization to vehicle routing problem with fuzzy demands [J]. Journal of Convergence Information Technology，2010，5（Compendex）： 11.