第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)保证每个运输工具要么不被使