模糊遗传算法的混合车辆路径的选择博弈

 1954年Dantzig和Fulkerson等研究较大规模的TSP，并首次引出车辆路径问题(Vehicle Routing Problem, VRP)，1959年Dantzig和Ramser正式提出VRP概念及求解方法，并指出TSP是VRP的一个特例。假设只有一个车场的模型称为单车场VRP，即车辆从车场出发、到配送中心取货、再服务顾客、然后返回同一车场，其研究重点在于车辆服务顾客的顺序。在现代商业模式下，为提高经济效益有时需要多车场、多配送中心同时进行配送，多于一个车场的问题称为多车场VRP，即车辆从不同车场出发服务顾客然后返回原车场。
    Mirabi和Fatemi Ghomi等(2010)研究最小化配送时间的多配送中心VRP模型，提出一种基于模拟退火思想的三步启发式算法进行求解。Crevier和Cordeau等(2007)研究了车辆可在不同配送中心补充货物的问题，建立了多配送中心VRP整数规划模型，提出一种融合了适应性记忆规则的禁忌搜索算法进行求解。Zhang和Tang等(2011)考虑车辆行驶费用与其装载货物的重量相关，以此建立多车场VRP模型并进行求解。蓝伯雄和张跃(2004)研究了带时间窗的装卸一体VRP问题，提出一种概率式禁忌搜索算法，通过给禁忌表中的点赋予权值来表示选择该点的概率。王征和张俊等(2011)研究带时间窗的多车场VRP问题，提出一种改进的变邻域搜索算法进行求解。李敏和郭强等(2007)给出一个多车场、多配送中心的模型，并提出一种具有路径标记功能的Floyd算法。王晓博和李一军等(2010，2009)建立了单配送中心、多车型的模型和多车场、多车型的模型，并提出混合遗传算法进行求解。杨元峰(2008)建立多车场、多车型的模型，并提出模拟退火遗传算法进行求解。钟石泉、贺国光等(2005)针对多车场、多车型、有时间窗的车辆调度问题进行研究，并设计了改进的禁忌搜索算法进行实现。刘冉、江志斌等(2009)建立多车场满载的协同运输模型，并提出基于贪婪算法的两阶段启发式算法进行求解。戎丽霞(2009)建立模糊需求的多车场车辆路径模型，并提出改进的遗传算法进行求解。
    国内外关于多车场、多配送中心VRP问题的研究成果不少，但是很少有考虑到配送多种产品的情况。然而，商业物流中经常需要配送家具、家电、中小型设备等不同体积、不同重量的货物，通常商家都会在几个配送点储存这些货物，每个配送点设有一些不同型号的车辆，商家根据顾客位置选择最近的配送点发货，并以成本最小为目标安排车辆和路线。针对这样一类物流配送问题，本文提出多配送中心、多车型、多产品的混合车辆路径问题(Multi-Depot, Multi-Type and Multi-Product Vehicle Routing Problem, MDTPVRP)，建立了相应的数学模型并给出一个求解方法。
    VRP是典型的NP-Hard问题，其解空间的维数随着问题的规模呈指数增长，其求解算法主要分为精确算法和近似算法两大类。遗传算法(Genetic Algorithm, GA)是由生物进化系统演变而来的一种近似算法。遗传算法作为一种快捷、简便、容错性强的算法，在各类优化问题中显示出明显的优势，但也具有一些固有的缺点。早熟收敛是遗传算法的一个重要问题，伴随着选择和交叉作用遗传算法中较优个体的繁殖速度非常之快，该个体很快占据种群的大部分，此时已经很难产生优于亲本的子代个体，就会发生早熟收敛且算法陷入局部最优解。造成早熟收敛的因素主要有群体规模、初始群体分布、选择和交叉概率及适应度函数等，解决这一问题的简单处理方法包括：当种群收敛到同一个体时，就对个体的许多位同时进行变异，以增加个体的适应度值；生成不同的个体，重新开始；使用启发式爬山法进行搜索。
    为了克服遗传算法的早熟收敛问题，本文提出改进的模糊遗传算法求解MDTPVRP模型，算法设计了包含更多种群信息的模糊逻辑控制器。模糊逻辑控制器可以在遗传算法的运行过程中控制交叉概率和变异概率，从而维持种群多样性并加速收敛。模糊规则的基本原理是根据当前种群的最佳适应度、平均适应度和待交叉、待变异个体适应度之间的关系，来控制交叉概率和变异概率。而该原理中适应度之间的关系是一个模糊概念，这些模糊概念很难用精确的数学方法进行衡量，因此需要引入隶属度函数。
    2　MDTPVRP数学模型
    2.1　问题描述
    
    VRP的解空间由简单回路的集合组成，每个简单回路都表示一条最短路线，目标是求所有简单回路弧长之和最小，并且满足以下约束：每个回路都包括0，即配送中心；每个顶点i∈v｛0｝都只存在于一条回路中；每条回路上所有顶点需求之和不能超过一辆车的载重W。
    本文建立的多配送中心、多产品、多车型的混合VRP模型可以描述为：
    (1)有多个配送中心，车场和配送中心在同一个位置，配送中心存储和供应足够多的多种产品；
    (2)每个配送中心都有一定数量不同型号(载重量不同、车厢容积不同、最大行驶里程不同)的车辆，车辆从配送中心出发送完线路上的全部货物返回原配送中心；
    (3)有多个顾客点，顾客之间的路程是确定的，顾客对不同产品的需求量是确定的；
    (4)每条线路上的顾客总需求不能超过完成该线路车辆的载重和容积限制，每条线路总长度不能超过完成该线路车辆的最大行驶里程；
    (5)目标为总成本最小，总成本由车辆行驶总距离构成。
    2.2　建立MDTPVRP模型
    根据问题描述给出各个符号的意义，如表1所示。
    
    由此可建立MDTPVRP数学模型如下：
    
    
    目标函数中的表示车辆行驶总距离，并以此作为车辆行驶总成本；约束(2)表示每个顾客仅由一辆车提供服务；约束(3)表示任何车辆经过某节点，也必须从该节点离开，同时保证车辆从配送中心出发必须返回原配送中心；约束(4)表示每种产品的送货量不超过每个配送中心的存货；约束(5)表示每条线路上的顾客总需求产品的重量不能超过完成该线路车辆的最大载重；约束(6)表示每条线路上的顾客总需求产品的体积不能超过完成该线路车辆的最大容积；约束(7)表示每条线路总长度不能超过完成该线路车辆的最大行驶里程；约束(8)表示决策变量的取值只能是0和1，若从配送中心g出发且车型为h的车辆是从节点m行驶到节点n，取值为1，否则，取值为0。
    3　模糊遗传算法
    3.1　遗传算法
    遗传算法是一种有效的全局搜索算法，由美国Michigan大学的Holland教授在1975年提出的。遗传算法是一种并行搜索算法，模拟自然进化中的自然选择 机制和优胜劣汰机制，主要部分包括：染色体(个体)种群、选择操作、交叉操作和变异操作。遗传算法各部分的策略为：
    (1)编码规则。根据多配送中心、多车型和多产品VRP的特点，采用简单直观的自然数编码方式，并把每条染色体分为两个部分。假设有2个配送中心，每个配送中心都有Ⅰ型车两辆、Ⅱ型车一辆，如图1所示，染色体的第一部分表示每个配送中心的每辆车的车型及其服务的顾客数，染色体的第二部分表示车辆服务顾客的顺序。当前染色体可表示的配送方案是：配送中心1的第一辆I型车按顺序服务顾客10和4，配送中心1的第二辆I型车按顺序服务顾客5和12，配送中心1的Ⅱ型车按顺序服务顾客9、7、2和8；配送中心2的第一辆Ⅰ型车按顺序服务顾客3和1l，配送中心2的第二辆Ⅰ型车按顺序服务顾客15和13，配送中心2的Ⅱ型车按顺序服务顾客1、14和6。
    
    图1　染色体编码方案
    (2)适应度函数。一个满足约束的配送路线方案可以作为一条染色体，通常采用目标函数(车辆行驶总距离)的倒数作为染色体适应度，但是这样计算的适应度值通常会很小且无法调节，不同问题的取值范围也相差很大，因此泛化能力较差。考虑用如下公式作为适应度函数：
    
    (3)选择算子。选择操作提供了遗传进化的驱动力，驱动力太大则遗传搜索将过早终止，驱动力太小则进化过程将非常缓慢。本文采用Holland提出的轮盘赌选择策略，其基本原理是根据每个染色体适应度的比例来确定该个体的选择概率或生存概率。为了实现最优保存策略，当前种群中的最优染色体直接进入下一代。
    (4)交叉算子。交叉操作是交换两个染色体部分基因的遗传操作。依据交叉概率选择进入配对池的个体，然后根据概率选择配对的父代个体，把父代染色体中的部分基因加以替换重组，产生子代个体。由于本文染色体编码由两部分组成，所以需要采用混合交叉算子，具体方式为：第一部分采用均匀交叉；第二部分采用顺序交叉。均匀交叉算子：首先随机地产生一个与染色体第一部分基因串等长的二进制串，0表示不交换，1表示交换，根据二进制串判断是否交换父代个体对应位置上的基因。通常顺序交叉随机产生交叉段，如果交叉点处的基因为0(即配送中心)，则直接进行顺序交叉，否则移动交叉段至交叉点基因都为0为止，但是本文染色体编码没有表示配送中心的基因，因此需要采用新的顺序交叉算子。新的顺序交叉算子：在父代染色体的第一部分基因串中随机选择一个基因，该基因对应的数字作为第二部分基因串的交叉段，然后把交叉段内的基因互换，把换出基因放在换入基因原来的位置上，当父代基因对应的数字不相同时，第二个父代向后移动至数字相同为止。如图2所示，以A和B两个父代为例进行混合交叉操作，X为二进制串，设产生的子代个体为C和D。
    
    图2　染色体交叉操作
    (5)变异算子。变异操作是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。变异操作依据变异概率对每代种群中的染色体进行基因突变，常用的基因突变方式有均匀、交换、逆转和位移等，根据本文编码规则的特点采用混合变异算子。对染色体第一部分基因串使用均匀变异算子，对染色体第二部分基因串使用位移变异算子，具体操作过程如图3所示。
    (6)调整非可行解。经过交叉操作和变异操作，染色体对应的解可能变成非可行解，因此需要进行调整。顾客数是确定的，因此染色体第一部分基因串上的数字之和必须等于顾客数，当基因值之和小于顾客数时，随机选择一个基因值加1，当基因值之和大于顾客数时，随机选择一个基因值减1，重复操作至基因值之和与顾客数相等。在产生初始种群及进行遗传操作的染色体中可能会有一些染色体不符合模型中的一个或多个约束条件，显然对于本文的染色体编码方式，所有染色体都自然满足约束(1)、(2)、(3)和(8)，因此确定非可行解的时候只需检查约束(4)、(5)、(6)和(7)，采用的约束控制策略是根据染色体对约束的违反程度降低染色体的适应度值。
    3.2　模糊逻辑控制器
    模糊逻辑控制器由模糊化、模糊推理及清晰化三个部分组成。目前有一些学者提出了应用于遗传算法的模糊逻辑控制器，其中Zeng和Rabenasolo的方法利用染色体适应度值和当前种群最大适应度值的相关信息作为输入变量，Wang和Hu的方法利用当前种群的平均适应度变化作为输入变量，Xu和Vukovich(1994)的方法采用遗传代数和种群规模作为输入变量。考虑到遗传代数和染色体适应度值对交叉和变异概率的影响，本文提出一种新的模糊逻辑控制器，主要思想是同时考虑遗传代数、染色体之间的距离、平均适应度值及适应度值的方差对交叉操作和变异操作的影响，并把交叉操作的模糊控制过程分为两步：选择进入配对池的染色体；选择配对染色体进行交叉。基本原则为：
    (1)进化前期交叉概率较大，以促进种群较快收敛；进化中期交叉概率稳定，以促进种群充分地进行局部搜索；进化后期交叉概率变小，以保护最优解。
    (2)种群适应度值的离散程度小，则增大交叉概率，以避免收敛到局部最优解；相反，降低交叉概率。
    (3)适应度值与最高适应度值差距较大的染色体应增加变异概率，以淘汰适应度值较低个体；相反，降低变异概率。
    (4)平均适应度值的变化很小，则增大变异概率，避免早熟收敛；平均适应度值的变化很大，则降低变异概率；若平均适应度值变化趋于零，应迅速增大变异概率。
    (5)两个具有较高适应度值且距离较近的个体有较高几率进行配对交叉，以实现对最优区域的局部搜索。
    
    图3　染色体变异操作
    以上这些原则会有一些冲突，但是通过正确的调整可以消除这些冲突，得到效率较高的遗传算法。
    
    遗传算法的变异操作通常作为辅助进化手段，因此变异概率的取值一般小于0.1，故取10×作为变异概率的输出变量。模糊逻辑控制器的输出变量为、10×及，所有输入变量和输出变量的取值范围均为区间［0，1］，这样可以使用一个隶属度函数描述所有变量。设定模糊逻辑控制器有9个语意值，分别是ES(极小)、VS(非常小)、S(小)、RS(较小)、M(中等)、RL(较大)、L(大)、VL(非常大)和EL(极大)。关于隶属度函数的选择并没有理论性的研究，根据经验本文选择三角隶属度函数。隶属度函数定义如图4所示。
    
    
    图4　输入变量和输出变量的隶属度函数
    根据基本原则及隶属度函数可以确定模糊规则，模糊规则由表 3、表4和表5给出。
    
    4　实例检验及仿真测试
    4.1　TSPlib实例检验
    为了测试模糊遗传算法的效果，选择TSPlib实例库中的16个实例进行计算，并将计算结果与传统遗传算法进行比较，具体结果如表6所示。由表6可得出模糊遗传算法的效果要大大高于传统遗传算法，其计算结果比目前已知最优解多出部分的比例平均小于5％，其中实例Bayg29的解与已知最优解相同，实例Ulysses22的解优于已知最优解。
    
    
    
    4.2　MDTPVRP模型仿真测试
    假设某个配送问题有2个配送中心、2种车型、4种产品以及30个顾客，表7给出随机产生的配送中心和顾客节点的坐标，表8给出配送中心的存货量及顾客的需求量，并假设配送中心备有足够多的存货。车型I的最大载重为5吨、最大容积为250L、最大行驶距离为1，车型II的最大载重为10吨、最大容积为500L、最大行驶距离为2。产品P1每个的重量为20公斤、体积为1L，产品P2每个的重量为30公斤、体积为1L，产品P3每个的重量为40公斤、体积为2L，产品P4每个的重量为50公斤、体积为2L。
    
    计算得出5条路线，总有效路程为5.2937，最优配送路径如图5所示。
    
    5　结语
    本文同时考虑多配送中心、多车型及多产品的车辆路径问题，建立了混合车辆路径问题的数学模型，并提出改进的模糊遗传算法进行求解。混合车辆路径模型更好地体现了真实配送状况，在实际应用中有一定的参考价值。仿真测试结果表明改进的模糊遗传算法具有很好的计算性能，为类似的组合优化问题提供了很好的解决思路。
    
    图5　最短配送路径
    本文研究的是确定性情况下的车辆路径问题，还可以进一步考虑随机需求、动态调度等不确定性因素，把不确定性的混合车辆路径模型作为研究方向。此外，本文以货物总重量不超过车辆载重、货物总体积不超过车厢容积为约束，下一步研究可以结合装箱问题，建立考虑实际装货环境的VRP模型。