第1期 彭扬，等：定位运输路线安排问题的改进离散粒子群优化算法 ·75· PS0)是一种较新的进化计算技术[8]，和遗传算法和 制.或者说本文所研究的是侧重于设施选址分配的 蚁群算法一样，PS0也是一类基于群体智能的随机 层次，它是一类特殊的融合考虑了巡回配送路径的 优化方法.由于该算法具有简单高效的特点，目前已 定位-运输路线安排问题.模型中忽略了实际配送中 广泛应用于函数寻优、神经网络训练、模式分类、模 的一些复杂因素，比如多车型车辆、时间窗约束等 糊系统控制等许多领域.Kennedy和Eberhart)进一 等，相应的数学模型如下所述 步提出了离散二进制版的PS0算法，为解决工程实 1.1基本假设与参数设定 际中的组合优化问题提供了新的方法.Salman[io]通 1)设施（配送中心或仓库、分销中心等）多个， 过适当的粒子编码求解任务指派问题，Tasgetiren I={li=1,2,…,M表示候选设施点的集合，其中 等Ⅲ把连续PS0算法应用到Fow-hop及单一机器 M表示候选设施点的数量，i是设施的编号 调度中.国内李宁等2]用PS0算法求解带时间窗的 2)为了简化计算，假设设施点只进行单车配 车辆路径问题，粒子的位置和速度采用整数表示，运 送，即此时设施点运输工具集合为K={k|k=1,2, 算仍采用连续量的运算法则.钟一文等3]通过重新 …,M},k即表示设施点的运输工具，同时也表示编 定义粒子运算法则，应用离散粒子群优化算法求解 号为k的配送路线，该路线的配送量限制（或车辆 ISP问题.高尚等「4]把遗传算法中的交叉算子和变 装载量)为Qk,该配送容量大于为其分配的运输线 异算子引人粒子位置移动中，提出求解TSP的混合 路上的客户总需求量，而且每辆车供应超过一个客 粒子群优化算法.国内外学者对复杂组合优化问题 户的货物，且每辆车自某个设施点出发，沿着运输路 的尝试解决，也体现了PS0算法在该领域应用的有 线完成配送后必须返回到该设施点， 效性和较好的求解性能， 3)客户集合为J={jj=1,2,…,N},N为所需 借鉴PS0算法求解组合优化问题方面的贡献， 服务的客户数量，J为客户编号.在配送决策中，每个 提出针对一类LRP问题的改进离散粒子群优化算 客户只被一个设施点的某一辆车服务（即从属于一 法.该方法旨在将LAP和VRP进行集成优化，采用 个运输路线)，客户的平均需求量为D,决策结果要 新颖的粒子编码设计，并改进粒子运动方程，以及引 求每个客户的需求得到满足， 入改善算法性能的算子等，实验结果证明了该方法 4)S为配送网络的所有结点集合，S=IUJ, 是有效的， 5)决策的目标是使方案的总成本最小，这里的 1定位-运输问题数学模型 总成本包括设施点的固定设置成本、设施点使用车 辆的租赁（或持有）成本和配送的运输成本，设配送 Nag描述了关于LRP的相关问题背景、模型、 结点间的距离为d:(i,j∈G),从客户结点i到j的单 求解算法以及研究现状等.一般的RP可表述如 位运距运输成本为c:,设施i的设置成本为F:,车辆 下：某公司从一个或多个设施为客户配送货物，客户 k的租赁（或持有）成本为Gk· 的数量、位置、需求量已知或可估计出，设施为工厂、 1.2 模型中的决策变量 仓库、分销中心等，现有若干个设施的位置可供选 「1，设施点的车辆k从结点i行行驶j, X= 择，但每个客户仅从一个设施得到货物，即在一定的 l0, 其他； 时间内，每个客户仅被运输车辆访问一次21.需要 Yy= 1,客户j被分配给设施i服务， 解决的问题是：在满足一定约束条件下，1)选择设 l0, 其他； 施的位置和数量；2)确定最佳的运输行程路线，使 Z= 1,设施点i被选择， 得总费用最低.总费用指设施的建设成本、运作成本 l0, 其他。 以及车辆的固定成本、运输成本等.约束条件包括： 为计算需要，增加辅助变量A2,l∈J,k∈K,且A4≥ 设施和运输车辆的容量和数量的限制、交货时间窗 0.该变量的引入是为了消除路线k中的子回路， 口限制等 1.3模型建立 如Na罗所述，LRP问题是集成2个层次的物流 模型式(1)中的目标函数有3项组成，分别表 决策问题，在实际应用中，可有不同的问题背景和侧 示配送成本、设施设置成本和车辆的持有成本，式 重.考虑到小批量、多频度配送是现代物流的一个特 (2)表示每个客户都有且只有一个设施为之服务， 征，本文所研究的是有多个候选设施，每个设施每次 式(3)表示配送路线的容量（运输工具装载量）约 可使用一辆具有一定装载量限制的车辆进行配送， 束，式(4)保证路线的连续性，式(5)消除配送路线 而车辆装载量这里也可以看成是设施的服务容量限 中的子回路，式(6)保证每个运输工具要么不被使