送货路线设计问题物流配送问题的混沌优化算法研究.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.28M 资料格式：pdf 举报版权申诉

leeyg1224-2304410-4744302543466038037.pdf-第1页.png

第1页 / 共6页

leeyg1224-2304410-4744302543466038037.pdf-第2页.png

第2页 / 共6页

leeyg1224-2304410-4744302543466038037.pdf-第3页.png

第3页 / 共6页

leeyg1224-2304410-4744302543466038037.pdf-第4页.png

第4页 / 共6页

leeyg1224-2304410-4744302543466038037.pdf-第5页.png

第5页 / 共6页

leeyg1224-2304410-4744302543466038037.pdf-第6页.png

第6页 / 共6页

文本预览

1 2009 年 11 月第 18 卷　第 4 期 2 2 1 中央民族大学学报 (自然科学版) Journal of MUC(Natural Sciences Edition) 物流配送问题的混沌优化算法研究张　潜 (华侨大学商学院 ,福建泉州 362021) Nov. , 2009 Vol. 18 　No. 4 摘　要 : 　探讨了定位 ———运输路线安排问题的解决方法 ,提出一种首先用启发式规则将客户集聚类 ,从而划分出若干客户子类 ;然后 ,用混沌搜索算法求解 LRP 的优化方法. 提出将用于聚类分析的启发式规则和混沌搜索算法结合的混合算法求解物流配送路径优化问题是有效的. 由于混沌序列具有随机性与遍历性 ,容易寻找全局最优解 ,从而避免了传统优化方法中的“局部最优现象”的发生. 计算机仿真实例证明了该算法简洁、实用、性能良好 ,有利于解决带有约束的非线性物流配送路径 LRP 优化问题. 关键词 : 　聚类分析 ; 混沌 ; 混沌搜索算法 ; 定位 ———运输路线安排问题 (LRP) ; 物流配送 ; 优化中图分类号 : TP301 , TP18 　　文献标识码 :A 　　文章编号 :1005 8036 (2009) 04 0044 05 1 　引　　言定位 ———运输路线安排问题 (Location Routing Problem , LRP) 是物流配送路径优化问题之一. 国外许多学者对物流系统优化问题进行了一定的研究 ,构建了解决实际问题的优化模型 ,并找到了一些求解算 Gandy 和 Dohrn[1 ] 最早将运输车辆多点停留特性与定位 ———运输网络结合起来开展了研究. 法. Watson 由于 LRP 属于 NP hard 难题 ,其核心是建模和求解 ,已引起越来越多的学者进行广泛而深入的研究. 文献[2～6 ]给出了关于 LRP 的精确算法和启发式算法. LRP 的精确算法可以分为以下四类 :分支定界法 , 动态规划 ,整数规划 ,非线性规划 ;启发式算法包括先解决定位配给问题 ,然后解决运输路线安排问题 ; 先解决运输路线安排问题 ,然后解决定位配给问题 ;费用降低插入算法 ;路线扩展交换算法. 混沌是存在于非线性动力学系统中的一种较为普遍的现象 ,混沌系统具有一些独特的动力学性质[7 ] . 混沌具有初值敏感性、内在随机性和遍历性 ,因此适合于完成优化搜索 ,利用混沌进行优化方法研究是混沌应用的一个新领域. 国内的学者用混沌搜索求解非线性约束优化问题. 混沌优化方法不要求优化目标函数对参数具有连续性和可微性 ,又可以在一定范围内遍历求解 ,适用于解决变量较多 ,约束复杂的优化问题. 因此 ,可以克服传统优化方法中的“局部最优现象”的缺陷 ,从而找到全局最优解. 本文将聚类分析和混沌搜索算法结合 ,形成混合优化算法 ,提出先用启发式规则将客户集聚类成若干子类 ; 然后 ,再用混沌搜索算法求解物流配送路径 LRP 优化问题得到了良好的结果. 2 　LRP 的含义和模型 2 1 　L RP 的含义定位 ———运输路线问题 (Location Routing Problem LRP) 可以表示为给定与实际问题相符的一系列潜在的设施点 ,在这些潜在的点中确定出一系列的设施位置 ,同时要确定出一套以各个设施到各个客户点 07 07 收稿日期 :2009 基金项目 :霍英东教育基金会第十届高等院校优选资助课题资助项目 (No 3502Z20073038) . 作者简介 :张潜 (1971 - ) ,女 (汉族) ,辽宁沈阳人 ,华侨大学商学院副教授 ,博士 ,硕士生导师 ,物流系统工程研究所 104009) 、厦门市科学计划资助项目 (No 所长 ,研究方向 :物流运输调度 ,复杂系统的建模与控制等.

Π Π 　第 4 期张潜 : 物流配送问题的混沌优化算法研究 54 的运输路线 ,确定的依据是满足问题的目标 (通常是总的费用最小) . 客户点的位置和客户的需求量是已知的或可估算法的 ,货物有一个或多个设施点位置已知 ,问题的目标是把那些潜在的设施建立起来 ,以使总的费用最小[8 ] . 2 2 　L RP 的问题的描述( 假设前提) 本文研究的 LRP 问题模型是基于如下假设前提 : (1) 货物均能按要求准时供应给客户. (2) 物品流向为双向 (即涉及的设施中的一部分既要有输入又要有输出) . (3) 供 (4) 潜在设施 (仓库) 的数量是多个. (5) 运输工具数量为多车辆 ,同时满足单车的容量大于运输路线上客户的总需求. 每辆车在完成全需求量是已知的 ,并在一定时期内相对稳定) . 需特征满足确定型的特点 (指物品供应部运输任务后回到出发点. 文中假定运输车辆足够多 ,完全可以满足运输路线上的客户服务. (6) 基于供应/ 需求的复杂性 ,只考虑一个客户仅由一个设施提供服务. 即供方为零售业市场 (如为超市提供服务的消费品市场) . (7) 由于考虑运输的经济性 ,假定每个设施 (仓库) 至少为两个以上的客户供货. (8) 目标数为单目标 ,符合满足 LRP 的单目标通常是总的费用 (包括车辆运输费用 ,建设设施和运营费用) 最小. 2 2 3 　L RP 的数学模型 3 1 　模型中的决策变量 xijk = Zr = 1 　　　如果第 k 个运输工具从仓库 i 到 j , i ∈ S , j ∈ S , k ∈V , i ≠ j , 0 　　　否则 1 　　　如果在 r 处建立一个设施 , r ∈ G 0 　　　否则 3 2 　模型中的参数含义 2 G r r = 1 , …, R 是一系列可行 R 处的潜在设施 ; i = R + 1 , …, R + N 是一系列需要服务的顾客 ; H i S G ∪ H 是指所有的地点和顾客总和 (也包括仓库) ; V vk k = 1 , …, K 是 K 个运输工具可以到达设施的路线 ; Cij 为从仓库 i 到仓库 j 的平均运输成本 ; Fr 为在 r ( r = 1 , …, R) 处建立并运作一个设施所需要的平均成本 ; qj 为顾客 j ( j ∈ H) 需求的平均数量 ; Qk 为运输工具 k ( k = 1 , …, K) 的容量 ; dij 为从仓库 i 到仓库 j 的距离. 2 目标函数 3 　模型的建立 3 f ( x) = min ∑ ∑ ∑ Cij Xijk dij + ∑ i ∈S j ∈S k ∈V Fr Zr r ∈G 　　满足约束条件 k ∈V j ∈H i ∈S ∑ ∑ ∑ ∑ ∑ ∑ r ∈G k ∈V k ∈V j ∈S i ∈S qj Xijk ≤ Qk 　　　　　　 Xijk = 1 　　　　　　　 ∑ ∑ Xipk - ∑ ∑ j ∈H Xrmk + Zr + Zm ≤2 　　　　 Xrjk ≤1 　　　　　　　 Xpjk = 0 　　　　 j ∈S Xrjk - Zr ≥0 　　　　　 ∑ j ∈H j ∈ H , k ∈V , k ∈V , p ∈ S , k ∈V , m = 1 , …, R , r ∈ G r ∈ G , (1) (2) (3) (4) (5) (6)

1 1 64 中央民族大学学报 (自然科学版) (8) (9) 　　在这个公式中 ,目标函数为总的成本 (包括运输成本 ,选择和运作仓库所需成本) 求极小值. 约束条件 (1) 确保每一个顾客仅由一个运输工具提供服务. 第 (2) 个为运输工具容量的约束条件 ,满足在路线上行驶的每台车辆都不超过其容量. 公式 (3) 是一系列路线连续约束 ,它是指运至某一点的货物由同一辆车辆运出. 约束条件 (4) 保证每一个运输车辆的路线最多从一个仓库驶出. 约束条件 (5) 保证在任意两个仓库之间没有其他连接方式. 约束条件 (6) 和 (7) 提供了每一运输工具的行驶源于一个仓库且只能有一个起点. 最后的两个约束条件保证满足取整数约束. i , j ∈ S , k ∈V r ∈ G. 3 　LRP 问题的聚类 ———混沌搜索混合算法 3 1 　L RP 问题的聚类分析聚类分析是运用数学方法来研究类的划分以及各类之间的亲疏程度 ,也是研究事物分类的一种方法 ,它根据一批样本的多个观测数据 ,设法找出表征样本间相似程度的统计量 ,把一些相似程度较大的样本聚合成一类 ,把另一些彼此间相似程度较大的样本聚合成另一类 ;如此下去 ,直至把所有样本聚合完毕. 文中应用海明距离法将客户集 C 划分成若干子类 ,具体操作如下 : 假设 m 个潜在设施对应的点及其坐标分别为 PF1 (X1 , Y1 ) , PF2 (X2 , Y2 ) , …, PFi (Xi , Yi ) , …, PFm (Xm ,Ym ) ;任意两个设潜在设施 PFi (Xi ,Yi ) 和 PFj (Xj ,Yj ) , Rij 为 PFi 和 PFj 之间距离的一半 ,并且满足客户的数量为 N , Rij = 1 2[ (Xi - Xj ) 2 + ( Yi - Yj ) 2 ]1 2 ; 客户集 C = [ C1 , C2 , ……, CN ] ; 客户对应的点及其坐标分别为 C1 (x1 ,y1 ) , C2 (x2 ,y2 ) , …, Cp (x p ,y p) , …, CN (xN ,yN ) ; 　　rip为任意一个潜在设施 PFi 到任意客户 p 的距离 ,以 Rij 为半径做相切圆 O1 , O2 , …, Oi , Oj , …, Om 对应半径分别为 R1 , R2 , …, Ri , , Rj , …, Rm ; 若 rip对应的坐标点 Cp 落在某一圆 Oi 内 ,则将 Cp 列入 Oi 类 ;即满足如下判定准则 ,将其聚为一类. 判定准则为 :如果满足 rip < Rij ,则将客户 Cp 聚为设施 PFi 类 ;否则 ,不列入此类. 注意 : (1) 在邻界相切圆半径上的客户点还应满足到与其最近的两客户点的距离和小于距离其次近两个客户点的距离和 ; (2) 如果存在某一客户 Cq 到任意设施 PFj 的距离 rjq大于最大的两个设施距离和的一半 ( rjq > max Rij ) ,从经济学提高经济效益的观点考虑 ,则取消对此客户供应 ,或者重新调整潜在设施 (仓库) 位置. 以上两个注意事项主要适用于容易引起奇异的客户点的聚类分析. 3 2 　L RP 问题的混沌搜索优化算法混沌优化搜索算法的基本思想是 :利用混沌系统构造混沌序列 ,即属于[0 ,1 ]间的遍历点 ,经变换和平移将其转化为优化问题解空间中作混沌遍历变量 ,再经过搜索寻找问题最优解[9～10 ] ,混沌序列可由混沌方程产生 ,其中 Logistic 方程是研究混沌问题最典型模型之一. Logistic 方程为 Logistic 映射有如下特性 : f : xk +1 = λ·xk ·(1 - xk ) 控制参数λ ∈ (2 ,4 ] , f : [0 ,1 ] →[0 ,1 ] (1) 当 λ ∈ (2 ,3) 时 ,映射 f 有稳定的不动点 ; (2) λ ∈[3 ,3 (3) λ ∈(3 57 ] 时 ,映射 f 处于倍周期分岔阶段 ; 57 ,4) 时 ,映射 f 失去稳定的周期轨道 ,出现混沌 ,但难以确定在那些点上其混沌集的一维 Lebesgue 测度大于 0 ; Xrjk - Zr ≤0 　　　　　　 ∑ j ∈K Xijk = 0 或 1 　　　　　　　　 Zr = 0 或 1 　　　　　　　　　 k ∈V , r ∈ G , 第 18 卷　 (7)

1 1 张潜 : 物流配送问题的混沌优化算法研究 74 1 　第 4 期 2 (4) λ = 4 时 ,映射 f 混沌不变集. 在 Logistic 混沌不变集中 ,当时间足够长 , f 的任一轨道在其中稠密 ,即对于 x ∈ [0 ,1 ] ,开球 B ∈ ( x ,ε) 中必包含 f 的一条轨道中的点. 反之 ,就是 f 的任意轨道能以任意精度逼近 [0 ,1 ]中的所有点[11 ] . ε > 0 , 以及本文就是利用λ = 4 时的 Logistic 混沌不变集的上述特性搜索问题最优解. 对于求解 s 维最优问题 ,相当于在 s 维空间中确定一个目标函数值最小的点 ,为此需要用 s 个独立的 Logistic 映射来产生该空间中点的 s 个坐标分量. 因为每一个坐标分量都能在[ 0 ,1 ]中稠密 ,所以这样产生的点将能在 s 维单位超立方体中稠密. 即这些点的序列能以任意精度逼近超立方体中所有点 ,当然也能够以任意精度逼近超立方体中的全局最优解. Logistic 混沌模型不但可以求解连续最优化问题 ,而且离散组合最优化问题. 3 3 　L RP 问题的混合算法文中 LRP 问题的混合算法分两步 :第一步如上所述的聚类方法 ,即运用启发式规则将客户集分类 ; 第二步利用混沌遍历搜索的特性 ,将客户类中的不同客户进行混沌随机搜索 ,产生不同的客户类中最优路径 ,并且满足目标函数取极小. 把 Logistic 混沌模型用于本文离散最优化 LRP 问题 ,还需作如下变换 : 对于给定某一客户类中有 r 个客户 ,要确定一条合法回路 ,就是要确定在这一客户类中 r 个客户的排列顺序. 目标函数是客户类中使路径 d 最小化 : r d ( Ci , Ci +1 ) , min ∑ i = 1 其中规定　 Cr+1 = C1 , d ( Ci , Ci +1 ) 为客户 Ci 与客户 Ci + 1间的距离. 具体聚类步骤 1 :启发式规则将客户分类. 混沌搜索优化混合算法的实现步骤如下 : (a) 将客户集 C 初始化 ,分别计算 Rij和 rip ; (b) 判断 :如果满足 rip < Rij ,则将客户 p 归入 Oi 类 ;归入 Oi 类 ; (c) 否则 ,返回 (a) 步. f = 0 ,对控制参数 k 赋一个较大的 ,对照 X ( i) , Y ( i) 求得当前一个搜索路径 ,再按混合算法得到当步骤 2 :对 X ( i) 　赋随机初值 , i = 1 ,2 , …r ,最优目标函数初值 opt 初值 ; 步骤 3 :对 X ( i) 到排序结果赋给 Y ( i) 前一个合法路径 ; 步骤 4 :计算当前合法路径目标函数值 f ; 步骤 5 :记忆最小目标值 opt 如果 f < opt f = f 步骤 6 :判断是否结束迭代 :如果 step = k 则停止 ; 步骤 7 :用 Logistic 映射产生下一组 X(1 , m) : f : ,step = 0 ,并记忆当前合法路径 ; f 则 opt 步骤 8 :返回第 3 步. xk +1 = 4 ·xk ·(1 - xk ) ; step = step + 1 ; 4 　仿真实例分析本文选择同型车从三个潜在设施给十个客户提供运输服务. 假设车的单位运输成本 Cij 为 2 元吨公里 ,建立和运营一个潜在设施的成本 Fr 为 160 元 ,十个客户的总的需求量为 30 吨. 潜在设施 (3 个) 和客户 (10 个) 的坐标位置如表 1 所示. 结合以上数据 ,针对不同的客户 ,用文中提出的聚类 —混沌优化搜索算法求解优化运输路线. 算法程序采用 VC + + 语言编制 ,程序运行在 P Ⅲ微机上 ,表 2 分别给出了聚类分析和程序 50000 次迭代运行 60. 从上面的仿真数据结果 ,可以发现文中的结果提出的聚类 —混沌优化搜索算法求解 LRP 问题是有效的此方法能够自适应多个潜在设施和不同的通过仿真实验求出聚类分析的目标函数值为 1923

ΠΠ 第 18 卷　 84 中央民族大学学报 (自然科学版) 客户情况下 ,快速寻找全局最优解 (或近优解) . 本文的算法对于解决大规模的物流配送生产实际问题提出了新思路. 表 1 　潜在设施 (3 个) 和客户 (10 个) 的坐标位置潜在设施客户号 Tab. 1 　Position for three potential facilities and ten customers 标号 PF1 PF2 PF3 1 2 3 4 5 6 7 8 9 10 23 20 86 45 87 69 23 09 56 77 09 03 03 86 20 07 52 76 18 30 30 72 68 76 0 5 5 0 1 1 1 4 4 5 4 2 4 坐标位置 0 0 6 1 3 2 2 2 1 1 2 6 6 点的表示 PF1 PF2 PF3 A B C D E F G H I J 表 2 　3 个潜在设施和 10 个客户的 LRP 确定问题的聚类和求解结果 Tab. 2 　The result for three potential facilities and ten customers of LRP 问题规模 3 10 客户聚类结果 ①A B C D ②F G H E ③I J PF1 PF2 PF3 最优解近似最优解目标函数值 PF1 ; PF2 ; 1936 30 A G C H I J D B F E PF3 5 　结束语 (1) 本文用启发式规则将客户聚类分析为若干子类 ;然后 ,采用混沌优化搜索算法求解单目标 LRP 的优化方法 ,为 LRP 优化问题提供了新的思路和途径. (2) 由于混沌全局遍历搜索的特性 ,可以将客户类中的不同客户进行混沌随机优化搜索 ,在全局进行最优解寻找 ,避免了传统优化算法中的“局部最优现象”的发生 ,同时能够进行大规模物流配送路径快速寻优. 计算机仿真实验证明了该算法的有效性. (3) 本文将聚类分析和混沌搜索算法有效的结合提出了混合算法为进一步研究物流配送优化调度问题并将研究成果应用于物流生产调度的实际工作 ,提高企业的经济效益 ,提供了参考. 参考文献 : [ 1 ] 　WATSON [ 2 ] 　LAPORTE , G. NOBERT , Y. An exact algorithm for minimizing routing and operating costs in depot location [J ]. European A practical approach[J ]. Omega , 1973 ,1(3) :321 - 329. GANDY C. ,DOHRN ,P. Depot location with van salesmen J ournal of Operation Research , 1986 , (6) :224 - 226. [ 3 ] 　LAPORTE ,G. Hamiltonian location problems[J ]. European J ournal of Operation Research ,1983 , (12) :80 - 87. [ 4 ] 　BOOKBINDER J . H. , REECE K. E. Vehicle routing considerations in distribution system design [J ]. European J ournal of Operation Research ,1988 , (37) :204 - 213. [ 5 ] 　WILLIAM P. N. ,J . WESLEY B. Solving the pickup and delivery problem with time windows using reactive tabu search [J ]. Transportation Research Part B ,2000 ,34 :107 - 121. [ 6 ] 　CAMPOS V. ,MOTA E. Heuristic Procedures for the Capacitated Vehicle Routing Problem [J ]. Computational Optimization and Applications , 2000 ,16 :265 - 277. [ 7 ] 　骆晨钟 ,邵惠鹤. 用混沌搜索求解非线性约束优化问题[J ]. 系统工程理论与实践 ,2000 ,20 (8) :54 - 57. [ 8 ] 　林岩 ,胡祥培. 物流系统优化中的定位 ———运输路线安排问题 (LRP) 研究评述 [ C] 管理科学与系统科学新进展 ———第 6 届全国青年管理科学与系统科学学术会议暨中国科协第 4 届青年学术年会卫星会议论文集. 大连 :大连理工大学出版社 ,2001 :227 - 235. [ 9 ] 　张静. 基于混沌优化方法的 PID 控制器设计[J ]. 襄樊学院学报 ,2001 ,22 (3) :63 - 66. [10 ] 　李昊 ,胡云昌 ,曹宏铎. 加速沌优化方法及其应用[J ]. 系统工程学报 ,2002 ,17 (2) :41 - 44. [11 ] 　柳贺 ,黄猛 , 柳桂国 ,等. 基于混沌搜索和模式搜索的混合优化方法 [J ]. 华东理工大学学报 (自然科学版) ,2008 , (下转第 67 页) (1) :126 - 130.

　第 4 期韩存梅 : 反应测试仪的原理及设计 76 4 　结　　论以 8255 芯片、8253 芯片 ,数码管为核心设计的反应测试仪具有精度高、硬件简单的突出优点 ,可降低测试仪成本 ,简化测试仪的开发过程. 设计的反应测试仪在常规量程内 ,具有较高的测量精度. 参考文献 : [ 1 ] 　黄道君. 微型机算计原理及应用[M]. 北京 :高等教育出版社 ,2004. [ 2 ] 　黄道君.《接口技术》课程设计学习与指导[M]. 杨凌 :西北农林科技大学出版社 ,2004. [ 3 ] 　谭浩强. C 语言程序设计 (第二版) [M]. 北京 :清华大学出版社 ,2003. [ 4 ] 　沈美明 ,温冬蝉. IBM PC 汇编语言程序设计 (第二版) [M]. 北京 :清华大学出版社 ,2001. Principle and Designing of Reaction Tester HAN Cun mei ( Department of Public Teaching of Tibet Agriculture and Animal Husbandry College ,Linzhi 860000 , China) Abstract : The author puts forward a system scheme to design a instrument for testing people’s reaction time by lower cost. This paper has designed the corresponding software to test the reaction time through the assembly language. The hardware derigning is taken with by 8255 parallel interface chip . The reaction time is devermined by the time difference of time function of 8253 chips anb OFFFFH. The precisim of centisecond is achived with the 8253 frequency sub - chip functions. The test results show that the design of the reaction tester has higher precision. Key words : Reaction Tester ; 8255 chips ; 8253 chips ; 8 SEGLED [责任编辑 :关紫烽 ] (上接第 48 页) Research on Location Routing Problem (L RP) of Optimization Based On Chaotic Search Algorithm ( CSA) ZHANG Qian ( School of Business , Huaqiao University , Quanzhou 362021 , China) Abstract : The hybrid algorithm is emphatically presented for the solution of location routing problem (LRP) . First , the candidate facilities and their customers are determined by clustering analysis with fitting rules. Second , chaotic searching algorithm(CSA) is used to search optimal routes. The preference suggested method of mixture algorithm is proved efficiently for routes of logistics distribution optimization. For the ergodicity and randomness of chaotic sequence , this CSA architecture makes it possible to search the solution space easily and effectively overpass computation. A computer simulation shows that the CSA system achieves improvement over a recent LRP with nonlinear constrained optimization problem. Key words : clustering analysis ; chaos ; chaotic searching algorithm (CSA) ; location routing problems (LRP) ; logistics distribution ; optimization [责任编辑 :关紫烽 ]

分享到：

赞收藏

资料库

送货路线设计问题物流配送问题的混沌优化算法研究.pdf

相关推荐

开发技术

热门标签

最新资料