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

《模糊遗传算法的混合车辆路径的选择博弈》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、模糊遗传算法的混合车辆路径的选择博弈1954年Dantzig和Fulkerson等研究较大规模的TSP，并首次引出车辆路径问题(VehicleRoutingProblem,VRP)，1959年Dantzig和Ramser正式提出VRP概念及求解方法，并指出TSP是VRP的一个特例。假设只有一个车场的模型称为单车场VRP，即车辆从车场出发、到配送中心取货、再服务顾客、然后返回同一车场，其研究重点在于车辆服务顾客的顺序。在现代商业模式下，为提高经济效益有时需要多车场、多配送中心同时进行配送，多于一个车场的问题称为多车场V

2、RP，即车辆从不同车场出发服务顾客然后返回原车场。Mirabi和FatemiGhomi等(2010)研究最小化配送时间的多配送中心VRP模型，提出一种基于模拟退火思想的三步启发式算法进行求解。Crevier和Cordeau等(2007)研究了车辆可在不同配送中心补充货物的问题，建立了多配送中心VRP整数规划模型，提出一种融合了适应性记忆规则的禁忌搜索算法进行求解。Zhang和Tang等(2011)考虑车辆行驶费用与其装载货物的重量相关，以此建立多车场VRP模型并进行求解。蓝伯雄和张跃(2004)研究了带时间窗的装卸一

3、体VRP问题，提出一种概率式禁忌搜索算法，通过给禁忌表中的点赋予权值来表示选择该点的概率。王征和张俊等(2011)研究带时间窗的多车场VRP问题，提出一种改进的变邻域搜索算法进行求解。李敏和郭强等(2007)给出一个多车场、多配送中心的模型，并提出一种具有路径标记功能的Floyd算法。王晓博和李一军等(2010，2009)建立了单配送中心、多车型的模型和多车场、多车型的模型，并提出混合遗传算法进行求解。杨元峰(2008)建立多车场、多车型的模型，并提出模拟退火遗传算法进行求解。钟石泉、贺国光等(2005)针对多车场、

4、多车型、有时间窗的车辆调度问题进行研究，并设计了改进的禁忌搜索算法进行实现。刘冉、江志斌等(2009)建立多车场满载的协同运输模型，并提出基于贪婪算法的两阶段启发式算法进行求解。戎丽霞(2009)建立模糊需求的多车场车辆路径模型，并提出改进的遗传算法进行求解。国内外关于多车场、多配送中心VRP问题的研究成果不少，但是很少有考虑到配送多种产品的情况。然而，商业物流中经常需要配送家具、家电、中小型设备等不同体积、不同重量的货物，通常商家都会在几个配送点储存这些货物，每个配送点设有一些不同型号的车辆，商家根据顾客位置选择最

5、近的配送点发货，并以成本最小为目标安排车辆和路线。针对这样一类物流配送问题，本文提出多配送中心、多车型、多产品的混合车辆路径问题(Multi-Depot,Multi-TypeandMulti-ProductVehicleRoutingProblem,MDTPVRP)，建立了相应的数学模型并给出一个求解方法。VRP是典型的NP-Hard问题，其解空间的维数随着问题的规模呈指数增长，其求解算法主要分为精确算法和近似算法两大类。遗传算法(GeicAlgorithm,GA)是由生物进化系统演变而来的一种近似算法。遗传算法作为

6、一种快捷、简便、容错性强的算法，在各类优化问题中显示出明显的优势，但也具有一些固有的缺点。早熟收敛是遗传算法的一个重要问题，伴随着选择和交叉作用遗传算法中较优个体的繁殖速度非常之快，该个体很快占据种群的大部分，此时已经很难产生优于亲本的子代个体，就会发生早熟收敛且算法陷入局部最优解。造成早熟收敛的因素主要有群体规模、初始群体分布、选择和交叉概率及适应度函数等，解决这一问题的简单处理方法包括：当种群收敛到同一个体时，就对个体的许多位同时进行变异，以增加个体的适应度值；生成不同的个体，重新开始；使用启发式爬山法进行搜索。

7、为了克服遗传算法的早熟收敛问题，本文提出改进的模糊遗传算法求解MDTPVRP模型，算法设计了包含更多种群信息的模糊逻辑控制器。模糊逻辑控制器可以在遗传算法的运行过程中控制交叉概率和变异概率，从而维持种群多样性并加速收敛。模糊规则的基本原理是根据当前种群的最佳适应度、平均适应度和待交叉、待变异个体适应度之间的关系，来控制交叉概率和变异概率。而该原理中适应度之间的关系是一个模糊概念，这些模糊概念很难用精确的数学方法进行衡量，因此需要引入隶属度函数。2MDTPVRP数学模型2.1问题描述VRP的解空间由简单回路的集合组成，

8、每个简单回路都表示一条最短路线，目标是求所有简单回路弧长之和最小，并且满足以下约束：每个回路都包括0，即配送中心；每个顶点iv｛0｝都只存在于一条回路中；每条回路上所有顶点需求之和不能超过一辆车的载重DTPVRP模型根据问题描述给出各个符号的意义，如表1所示。由此可建立MDTPVRP数学模型如下：目标函数中的表示车辆行驶总距离，并以此作为车辆行