基于优化的粒子群算法的物流配送路径问题研究

基于优化的粒子群算法的物流配送路径问题研究内容摘要：

到达客户 i 并且开始服务的时间是 ti,行驶时间是 ijt , wi 为所需的等待时间 ,Si 为服务时间 , iit 表示客户满意度 ,I是很大的整数。 定义变量 : ki 1 iky= 0 客 户 由 车 辆 配 送否 则 mkij 1 m k i jx= 0 车 场 的 车 从 用 户 行 驶 到否 则 基于顾客的满意程度可得求解目标有 : 第一步是最大化的平均客户满意度 : Niii=11max tN  (式 213) 其可以等价转化为最小化的平均客户不满意度 Niii= 11min 1 tN  （式 214) 第二步是最小化的车辆数 : KN k0jk=1 j=1min x (式 215) 第三步是最小化的车辆行驶距离和等待时间 : 11 / 40 K N N kij ijk=0 i=1 j=1min c x (式 216) Niii=1min t (式 217) 其有如下的约束条件 : iit i i = l,2… N (式 218) 1N ki i ki g y q  (式 219) 1 1K kik y  (式 220) 1N kkij ji xy  (式 221) 1N kkij ij xy  (式 222) , 1n kiji j s s xs    1,2...sN (式 223)  m ax ,j j i i ijt E t s t   (式 224) ijtN (式 225)  ( ) m ax 0,i j j jt t E  (式 226) 以上公式中 ,公式 (218)可以保障每个客户满意程度不低于 i 其中 i 是决策者根据自身的实际经验给出相应的值 ,其中给每个客户的值可以相同也可以不同 ,其是根据客户的重要程度进行划分的。 公式 (219)用来保证每辆车的承载能力。 公式 (220)用来确保每个客户都被服务到。 公式 (221)(222)确保每个客户只被一辆车服务 .公式 (223)用来消除子回路。 公式 (224)、 (225)、 (226)用来确保客户在确定时间窗内接受服务。 模型建立思路总结 根据前文介绍的几种模型 ,总结出对于物流配送路径问题建模的大致思路 首先 ,自定义变量。 大多是 amp。 和 7,对所求变量进行初始条件设置 ,即变量为 1 时则为服务到 ,变量为 0则为未服务到。 如 : ki 1 iky= 0 客 户 由 车 辆 配 送否 则 12 / 40 mkij 1 m k i jx= 0 车 场 的 车 从 用 户 行 驶 到否 则 第二步 ,设定最小化目标。 如最小化的费用、最小化的时间或者最小化的路径。 如 : K N N Kij ijK = 0 i= 1 j= 1m in Z= c x   第三步 ,自定义满足条件。 如顾客满意度、车辆分配总数或运输时间等。 如 : Niii=11max tN  第四步 ,保证每个客户都被服务到。 如 :1 1K kik y  第五步 ,保证每个客户都被服务一次。 有时候第四步和第五步可以合并。 如 : 1N kkij ji xy  第六步 ,保证消除子回路。 如 : , 1n kiji j s s xs    1,2...sN 第七步 ,保证车辆的承载能力。 如 : 1N ki i ki g y q  对于模型思路和每一种约束条件的分析与总结十分必要 ,利于根据实际要求建立对应的所需模型 ,并根据自身的要求加入相应的约束条件 ,改进模型 ,使模型更加贴合实际要求。 基于最短路径的多车场多车辆配送模型建立 根据前文对于模型建立的分析与总结 ,运用前文的方法 ,建立一种基于最短路径的多车场多车辆的配送模型 ,并加入新的约束条件。 配送路径中多个车场多个车辆的优化问题可以描述为 :某物流中心一共有 M 个车场 ,各自有 Ki(K1, K2 Km)台配送车辆 ,每辆车容量都为 q,向 N 个客户送货 ,用户 i 的货物需求为 gi, (i=l,2,...N)。 要求合理安排车辆配送方案 ,使车辆总运输成本最低 ,并满足以下条件 :(1)每辆车运送完后必须返回原车场。 (2)每个客户的需求必须满足。 (3)可以由任意一个车场的车辆服务 ,但只能由一台配送车辆送货。 (4)对车辆的服务数量进行限制。 根据以上条件 ,设全部用户的编号分别为 1,2, ......N。 车场具有编号为N+l,N+2, ......N+M。 定义变量 mkij 1 m k i jx= 0 车 场 的 车 从 用 户 行 驶 到否 则 (式 227) N:表示客户的总数目。 M:表示车场的总数目。 dij:表示节点 i与节点 j之间的距离。 km:表示车场 m所拥有的车辆总数。 gi:表示客户 i的要求。 q:车场 m中车辆 k载重负荷。 以上可以建立数学模型如下 : 13 / 40 1 1 1 1m inN N M K m mkij iji j m kZ d x     (式 228) 公式 228用来保证最小化的车辆行驶路径。 也是整个问题的核心需求 ,是下 步工作运用算法所需要完成的内容 ,即适应值。 接下来就要根据实际要求对运算加以限制 ,列出限制公式 ,以便于计算 ,获得与实际 相符的可行解。 11N Km mkijikx Km   1, 2. ..m N N N M    (式 229) 条件 229限制了从一个车场出发的车辆总数目 ,必须小于 !^。 此条件用于限制计算时车辆的数量 ,因为一个车场所含有的车辆数是固定的 ,因此必须加以限制。 , 1n mkiji j s s xs   1,2...sN  1,2...k Km (式 230) 公式 230保证了消除子回路。 即不能出现路径反复 ,出现误差。 1 1 1 1N M Km mkiji m k x     1,2...iN (式 231) 1 1 1 1N M Km mkijj m k x     1,2...jN (式 232) 条件 231和 232保证了每个客户仅被一辆车服务一次。 该公式的目的是控制每个客户都被服务到 ,并且仅被一辆车服务。 11N N M mki xjijg x q   1, 2. ..m N N N M     1,2...k Km (式 233) 公式 233表示每辆车的载重量不超过它的载重能力。 由于每辆车的承载能力是固定的 ,因此必须对车辆总承载数加以控制。 同时在前文研究的基础上发现 ,大部分的约束条件都是从客户的角度出发 ,要求每个客户都被服务到 ,每个客户都被一辆车服务 ,但是如果车辆所经过的客户过多 ,就会对车辆的行驶里程产生一定要求 ,车辆行驶的距离与车辆状态、储油量和车辆使用年限等都有一系列的关系 ,对车辆要求很高 ,而车辆本身具有一定的局限性 ,基于以上原因 ,本文从车辆行驶里程考虑 ,对车辆服务客户数量加以限制 ,加入了新的约束条件 ,如公式 234所示 : 11nnmkijijxR   1,2...iN  1,2...jN (式 234) 对于第 mk车辆 ,它所经历的客户总数量控制在 R以下 ,即最多为 R客户服务 ,这样可以保证车辆的客户服务数 ,同时也能在一定的范围内对车辆行驶里程加以限制 ,确保车辆正常行驶并能将货物送达每一个客户。 根据本章对物流配送路径模型定义、分类的研究 ,了解物流配送问题建模的内容与意义。 本章中选择三种常见的模型进行分析 ,分别是基于行驶距离最短和使用车辆最少的物流配送模型、基于开放式车辆路径的物流配送模型和基 于顾客满意度的物流配送模型 ,对模型进行深入研究 ,并总结建立模型的相关思路。 根据实际情况建立了一种基于最短路径的多车场多车辆的物流配送模型 ,并从车辆行驶里程角度分析加入了新的约束条件 ,保证车辆的正常行 14 / 40 驶 ,同时也保证车辆能将货物送达每一位客户。 3物流配送路径问题相关算法研究 物流配送算法主要的解决方案分为两大类 :人工智能算法和精确算法。 人工智能算法包括有 :扫描法、旅行商方法、分区配送算法、节约法以及一些现代优化计算方法 (禁忌搜索算法、遗传算法、模拟退火算法等 )。 人工智能算法虽然比精确算法精度低 ,但在求解大规 模 VRP 时 ,总可以求解 ,找到满意的可行解或次优解 ,这是精确算法无法做到的。 因此 ,人工智能算法更广泛的运用在实际生活中。 精确算法可以这样划分 :直接树搜索算法、割平面法、分枝定界法、网络流算法、整数线性规划和动态规划法。 总的来说 ,精确算需要十分严格的数学手段 ,所以在可以求解的情况下 ,其解要比人工智能算法更加优良。 但由于需要严格的数学方法 ,因而无法避开指数过多问题 ,所以该类算法有限制性 ,对于小规模的确定性 VRP才能有效求解。 (1)精确算法 精确算法指可求出最优解的算法 ,主要 有分枝定界法、割平面法、网络流算法、动态规划法等。 精确算法的计算量一般随着问题规模的增大而呈指数增长 ,所以 ,多用于规模较小的问题。 (2)启发式算法 通常情况下 ,通过自身发展的性质和生物系统 ,可以使许多复杂的问题得到令人满意的解决方案 ,计算机科学家从生物系统的研究中得到的灵感 ,、以模仿自然的世界 ,获取新的方法来解决复杂的计算问题。 在算法的设计过程中 ,设计灵感起源于或者是物理现象 ,或者是生物群体现象。 如模拟退火算法模拟的固体物质从高温度的不稳定状态的过程中向低温度稳定状态过度。 遗传算法从大自然的优胜劣汰的生存 现象中获得。 蚁群算法模仿蚁群觅食的费洛蒙应用 ,以便找到最短的觅食路径。 这些智能的优化算法的出现 ,一方面极大地丰富了优化技术 ,为那些传统的优化技术无法处理的组合优化问题提供了一个实用的解决方案 ,另一方面 ,他们也从另一个角度来探讨生物世界的机制为实际运用提供新的工具和技术。 虽然这些新的方法进行了优化 ,并且每个机制是不一样的 ,但它们有类似的特征。 他们都是迭代算法 ,通过在不断的迭代计算 ,一步一步从质量差的解决方案 ,以更优质的解决方案逼近。 因此 ,这些算法在多篇论文或其他著作被列为一类 ,概括起来 ,即启发式算法一一 Heuristic Algorithm。 启发式算法 ,是一种定义在可以接受的花费 (占用空间、计算时间等 )下解决组合优化问题的一个可行的解决方案 ,这种解决方案与最佳方案水平偏差不可预知。 另一种定义指定启发式算法是一种技术 ,使寻找最佳的解决方案在一个可接受的计算成本内 ,但不一定保证得到的解决方案是可行的和最优的 ,或者。