论文研究-求解VRPTW问题的多目标模糊偏好蚁群算法.pdf

所需积分/C币:13 2019-07-22 22:30:02 260KB .PDF
收藏 收藏 1
举报

通过分析多目标的、有时间窗的车辆路径问题,对各个目标进行多属性模糊评判,结合相关专家的综合意见以及决策者自身对专家意见的偏好,将决策者对目标属性的离散意见转换为对各目标的综合意见;通过定义一种模糊综合排序指标来确定决策者对各目标的偏好权重,依据目标权重和各目标函数的规范化处理值,构建评价有时间窗的车辆路径问题的多目标模糊综合适应度函数;采用最大—最小蚂蚁系统算法对该问题进行求解;最后通过一个算例来说明该算法的有效性。
第12期 李世威,等:求解ⅤPW问题的多日标模糊偏好蚁群算法 4497 解。由于VRPW的复杂性,导致产生一个可行的初始解非 常复杂。本文采用文献中一种基于客户时间窗下限较小 T (15)优先的快速产生初始解的算法。该算法选择下一个客户的策 b)一旦信息素更新后,调整Tm 略为:从当前路径的最后一个客户出发,到所有未访问过的客 户中开始服务时间最早的那个客户。只有当开始服务时间超 (16) 过这个客户的时问窗时,才需要新开辟一条路径,并从未访问 其屮:表示精英蚂蚁的个数。 过的客户中重新选择出发点,将所有未访问过的客户中开始服 Tm利用式(15)进行调整 务时间最早的那个客户作为新路径的第一个客户。该算法流 2.1路径构造 程如下 每只蚂蚁选择下一个城市时,在满足车辆容量和时间窗约 a)初始化。 東的条件下,需要考虑两个方面的因素: b)将所有未被访问过的客户放入集合C中。 a)通往下一个城市的路径长度及路径上信息素的多少。 t)C={co,…,c;,…,c,…}。C中的元素按如下规则进行 b)时间窗的择优选择性。它出下一个客户方的时间窗宽排列:对任意的is设n是当前路径R最后一个客户时所花 度和所在客户i到达客户的时间等因素决定,所以这种择优费的总时间用W表示,是当前路径R最后一个客户时所花 性的优先选择为需等待时间较短优先原则时间窗较小优先费的总时间用聊表示(当前路径R是随着时间动态更新的), 原则2 满足W≤W;令k=1。 综合以上两个方面的因素,第k条路径上的蚂蚁在城市n d)如果集合C为空,转至g)。 选择城市v的概率计算式2为 e)如果W(ck,c1)=T,保存当前路径R;重新开辟一条路 径,从当前未被访问的客户中随机选择一个客户c作为新路 (T)(1;)B 径的出发点,C=C-c;转至c)。其中,W(c,c1)的返回值为 P max(ck的开始服务时+ck的服务所需时间+从ck到c;的 行驶时间)。如果到达c;的时间晚于客户的时间窗,则W 其中:={n1v1为可被访问的城市}U{},to为配送中心;1(c,)返回一个很大的7值,表示该客户不能加入路径。 和ω2为权重系数,满足0≤0,02≤1,且o1+2=1;[a,b] f)如果客户k为当前路径R的合法客户,将c:加入当前 为客户j的时间窗;t为由客户i到达客户j的时间,即开始为路径R中;C=C-c;k=k+1;转至d)。 客户i服务的时间+客户氵所需的服务时间+从客户i到j的 g)输出计算结果,程序结束。 路程消耗时间;和β为轨迹上的信息素与该轨迹可见性的权 重系数;为n与b之间轨迹上的信息素,且T∈[Tm,Tm];3算例分析 n为轨迹的可见性,本文取n=1/da,d为客户i与j之间的 假设有三名专家辅助一名决策者解决有三个目标(总体 距离。 行驶时间最少、总体行驶路程最短f、总体使用车辆数月最 2.2信息素更新 少)的车辆路径优化问题。从盈利能力、客户满意度、配送可 信息素更新有局部更新和全局更新两种方法。本文采靠性三个属性来综合平衡三个日标,其评价是模糊语义,评价 用全局更新方法,只将最好的蚂蚁用于信息素的更新,将路径信息如表1所示。其中,属性权重是决策者对各属性重要程度 构造中排名前几位的精英蚂蚁用于信息素的更新。更新规的模糊评断。 则为 表1决策者对各日标的模糊评价信息 决策者/专家1/专家2/专家3 =(1-p)+∑△+0△r 18 目标 盈利能力 客户满意度 配送可靠性 其中:当且仅当轨迹(v,v)被排名第h好的蚂蚁利用时,其信 时间最短重要/较重夏 重要/重要 较差/般 较重要/较重要 重要/重要 般/较差 息素才增加△=(0-以)L,L为排名为h的路径长度;所 路程最短较重要/较重要/按重要较重要 般/一般/ 有属于当前最好路径的轨迹上的信息素都被统一加强σ△T= 般/较差 1/L",L为当前最好解路径的长度。 车辆最少重要/较重要/ 较差/一般 般/一般/ 较重要/重要 一般/一般 由于单纯使用该方法,使得算法收敛速度缓慢,而且其全属性权重 局优化性能乜不明显。为了加快其收敛速度,同时又不影响全 决策者对自身和专家的评价从信任度、了解度、客观性和 局优化能力,在该规则基础上加入一个复合规则:在迭代过程风险观念四个方面的指标进行权衡,采用模糊语义对这四个指 中,对出现优于上一代解的本代解给予激励,对于劣于上一代标的重要性以及对白身和专家的决策重要程度进行评价,由此 解的本代解给予惩罚,从而加快算法的收敛速度。对史新过的可以得到综合有效的决策者权重。该决策者的评价指标信息 路径具体激励与惩罚计算公式为 如表2所示。 L 19 表2决策者的评价指标模糊信息 指标者砾权重决策者专家1专家2 专家3 2.3初始解构造 信任度 较重安 車要 股 了解度较重要较重夏 重要 一般较重要 在构造初始解时,需要確定τm与τm的值,而确定它们的 客观性较重要较重要较要较重夏 般 值首先要明确L()的值,所以在最初就必须有一个较好的可_风险观念一股较重要较要较重 4498· 计算机应用研究 28 首先将表Ⅰ和2的模糊语义转换为三角模糊数,得到决策用式(4)(6)计算决策者综合属性评判阵A 者对各目标的评判矩阵P和评价指标评判矩阵D。转换结果 0.652,0.814,D.926)(0.800,1.000,1.00)(0.277,0.427,0.577) 如表3和4所示。 A-(0.694,0.867,0.947)(0.542,0.692,0.42)(0.315,0.465,0.615) 表3决簧者对各目标的评判矩阵P 0.698,0.872,D.949)(0.311,0.461,0.611)(0.350,0.500,0.65U) 目标 盈利能力 客户满意度 项目可靠性 综合属性权重ω′和决策者综合属性评判阵A,得到加权 (.8,1,1)(0.2,0.35,0.5)的综合评判阵A 时最短 (0.6,0.75,0.9)(0.8,1,1)(0.35,0.5,0 A′=Ao'= (0.6,0.75,0.9 (0.8,1,1)(0.35,0.5,0.65 (0.6,0.75,0.9)(0.8,1,1)(0.2,0.35,0.5) (0.209,0.326,0.370)(0.192,0.300,0.360)(0.066,0.128,0.208) (0.6,0.75,0.9)(0.6,0.75.0.9 (0.22.0.347,0.379)(0.130,0.208,0.303)(0.076,0.140,0.221) 路程最短(6.0.75,0.9)(0.6,0.75,0.9)(0.35,0.5,0.65 0.6,0.75,0.9 0.35,0.5,0 (0.223.0.349,0.380)(0.075,0.138.0.220)(0.084,0.150,0.234) (0.8,1,1 (0.35,0.5,0.65)(0.2,0.35,0.5) 采用模糊加权平均法计算各目标函数的模糊综合效用矩 0.8.1,1)(0.2.0.35,0.5)(0.35,0.5,0.65 阵A': 车辆最少(.6:0.3:)2.31.0.65030565 (0.467,0.754,0.938) (0.8,1,1 (0.35,0.5,0.65)(0.35,0.5,0.65 A′=(0.428,0.694,0.903) 属性权重 (0.8,1,1 0.6,0.75,0.9)(0.6,0.75,0.9) (0.382,0.637,0.834) 表4决策者对评价者标评判矩阵D 计算模糊综合效用矩阵A′中各目标模糊数的均值和 信任度 了解度 客观性 险观念 方差 指标权重0.8,1,1)(0.6,0.75,0.9)(0.6,0.75,0.9)(0.35,0.5,0.65 nean(A'1)=0.720,mean(A)=0.675,mean(A'3)=0.618 决策者(0.6,0.75,0.9)(0.6,0.75,0.9)(0.6,0.75,0.9)(0.6,0.75,0.9) G(A'1)=0.087,(A2)=0.097,0(A3)=0.092 40.8.1.1 0).8,,1)(0.6,0.75,9)(0.6,0.75,9) 专家2(0.35,0.5,0.65)(0.35,0.5,0.65)(0.6,0.75,0.9)(0.6,0.75,0.9) 计算模糊排序指标函数F(A') 专家3(0.35,0.5,0.65)(0.6.0.75,0.9)(0.35,0.5,0.65)(0.35,0.5,0.65) F(A'1)=0.811,F(A′2)=0.789,F(A'3)=0.763 利用式(1)~(3)对属性权重ω和指标权重inex进行归 然后对各目标的排序指标函数值进行归一化处理,得刭决 化处理 策者日标偏好权重ω(i=1,2,3) (0.320,0.400,0.400),(0.240,0.300,0.360) o1=0.343,O2=0.334,3=0.323 (0.240,0.300,0.360) 由于行驶时间、行驶路程和使用车辆数日都是成本型目标 index′=[(0.267,0.333,0.333),(0.200,0.250,0.300), 函数,因此采用式(11)进行规范化处理,得到规范化后的目标 (0.200,0.250,0.300),(0.117,0.167,0.217)] 函数f(i=1,2,3)。最后根据各日标的偏好权重o)和规范 利用式(5)确定决策者加权评价指标矩阵D 化后的目标函数〃,确定多目标模糊综合适应度函数ftes 0.160,0.250,0.300)(0.120,0.188,0.270) fitness=∑o/=0.343/1′+0.3342′+0.323/3′ (0.214,0.333,0.333)(0.160,0.250,0.300) D= DO index'= 将构建的多目标模糊综合适应度函数 fitness应用于 (0.093,0.167,0.216)(0.070,0.125,0.195) MMAS算法中,采用文献[6]中所述的标准ⅤRPW数据集,该 (0.093,0.107,0.216)(0.120,0.188,0.270) 数据集共有56个实例,每个实例均含有100个客户和1个中 0.120,0.188,0.270)(0.070,0.125,0.195) 心仓库,并规定了车辆负载、客户的时间窗和车辆的运行时间。 (0.120,0.188,0.270)(0.070,0.125,0.195) 实例分为六类:R1、R2、C1、C2、RC1、RC2。其中:R1和R2中的 (0.120,0.188,0.270)(0.070,0.125,0.195) (0.070,0.125,0.195)(0.041,0.084,0.141) 客户为随机分布;C1和C2中的客户有聚类趋势;RC1和RC 中的客户兼有R类和C类的特征。 利用式(6)计算决策者模糊综合效用阵D 实验过程中,在每个城市放置一只蚂蚁(蚂蚁个数等于客 D=(0.470,0.751,1.035),(0.564,0.896,1.098) 户的数目),设置α=1.0,B=5.0;信息素挥发系数p在0.02 (0.354.0.604,0.877),(0.324,0.563,0.823))T 0.3间取值;精英蚂蚁个数σ在3-6间取值;路径上的信息素 利用式(7)(8)计算出决簧者模糊综合效用阵D中各模初始化为Tm;权重系数的取值设定为0.5<0<1.0,0< 糊数的均值和方差: 2<0.5。 mean、D1)=0.752,mean(D2)=0.853 图1和2分别描述了实例RC101和RC102在多目祘模糊 mean 0.612,mean(D‘4)=0.570 综合适应度函数 fitness作用下的收敛曲线。从图中可以看出 D'1)=0.115,U(D′2)=0.110 该算法在初期就能使当前解得到很好的改善,并且收敛速度较 G(D'3)=0.107,U(D′4)=0.102 快,为求解有时间窗的车辆路径问题提供了一种有效的方法。 根据式(9)计算决策者和专家的模糊排序指标值F(D′) F(D'1)=0.818,F(D2)=0.871 09 031 日3 F(D3)=0.752,F(D'3)=0.734 0.7 然后对F(D)进行归一化处理,得到决策者权重oD 06 日后 法0s UD.=F(D'1)/∑F(D1)=0.258 0 03 03 D2=0.274,03=0.237,0m3=0.23 010203a3如h09 根据决者权重ω和决策者对各目标的评价矩阵P,采 店代次 代坎数 图1例RC101收敏曲线 图2文例RCQ2收敛曲线 第12期 李世威,等:求解VRPW问题的多目标模糊偏好蚁群算法 4499· 辆路径问题中的应用[J].计算机集成制造系统,2005,11(4) 4结束语 572-57 [9]刘志硕,申金升、柴跃廷,基于自逅应蚁群算法的牟辆路径问题研 本文针对决策者在面对多目标的、有时间窗的车辆路径问 究[J].控制与决策,2005,20(5):562-566 题时,对各个目标进行多属性模糊评判,结合专家的综合意见[10 JACKSON D E, HOLCOMBE M, RATNIEKS FL W. Trail geometry 以及决策者自身对专家意见的偏好,将决策者对目标属性的离 gives polarity to ant foraging networks[J]. Nature, 2004, 432 散意见转换为对各目标的综合意见,通过定义一种模糊综合排 (7019):907-909 序指标来确定决策者对各目标的偏好权重,依据目标权重和各11 MOHAMMAD A, MIGUEL M. Application of an ant algorithm for 目标函数的规范化处理,构建评价有时间窗的车辆路径冋题的 layout optimization of tree network J|. Engineering Optimization 多目标模糊综合适应度函数,进而采用MMAS算法对该问题 2006,38(3);353-369 进行求解。最后采用标准实验数据集进行验证,结果表明,该[12 CHE C H,ING,C. An improved ant colony system algorithm for 算法能够有效地解决多目标的、有时间窗的车辆路径问题,为 the vehicle routing problem[J]. Journal of the Chinese Institute of Industrial Engineers, 2006, 23(2): 115-126 解决带有时间窗的车辆路径多日标问题提供了一种现实可行 [13] BAHREININEJAD A, HESAMFAR P Subdomain generation using 的方法 emergent ant colony opt imization[J]. Computers and Structures 参考文献 2006,4(5):1719-1728 [1]汪定伟,王俊伟,王洪峰,等.智能优化方法M].北京:高等教育「14. ISSMAIL E, CALAMAI P, BASIR O. Exchange strategies for multiple 出版社,2007:198-205 ant colony systen[J. Joumal of Information Sciences, 2006. 3 [2]马良,朱刚,宁爱兵.蚁群优化算法[M].北京:科学出版社,2009 (1):46-63 15 CHU Shu-chuan, RODDICK J F, PAn J S. Ant colony system with [3]雷德明,新平.多目标智能优化算法及其应用[M].北京:科 communication strategies[ J] Information Sciences, 2004, 167(7): 出版社,2009:12-19 63-76 4」吴国华,潘德惠.一种消费者品牌偏好的模糊排序方法LJ」.系统[6· SIQUEIRA PH, STEINER M T, SCHEER S. A new approach to solve 工程理论与实践,2004,9(1):28-32 the traveling salesman problem[ J]. Neurocomputing, 2006, 70(4) [5]李世威,王建强,曾俊伟.一种模糊偏好排序的多目标粒亍群算法 1013-1021 ].计算机应用研究,2011,28(2):477-480 17 ONWUBOLU G C, CLERC M. Optimal path for antomated drilling [6 MARIUS M, SOLOMON M. Algorithms for vehicle routing and schedu operations by a new heuristic approach using particle swarm optimiza th time windo Operations Re LJ. Journal of P search,1987,35(2):736-78 18 BIANCHII L, KNOWLES J, BOWLER J. Local search for the probabi [7]邵晓巍,邵长胜,赵长安.利用信息量留存的蚁群遗传算法[J].控 listic traveling salesman problem: correction to the 2-p-opt and I-shift 削与决策,2004,19(10):1187-1189 algorithms. European Journal of Operational Research [⑧]万旭,林健良,杨晓伟.改进的最大一最小蚂蚁算法在有时间窗车 2005,162(1):206-219 (上接第4488页) [13. XU Zhi-hong, HOU Xiang-dan, SUN Ji-zhou. Ant algorithm-based task [7]徐志伟,冯百明,李伟.网格计算技犬[M].北京:电子工业出版 scheduling in grid computing[C//Proc of TEF.F. Canadian Confer ence on electrical and Compliter Engineering. 2003: 1107-1110 [8] LIU Jue-fu, LI Gang. An improved Min-min grid tasks scheduling al- [14 AJITH A, RAJKUMAR B, NATH B. Nature's heuristics for schedu gorithm based on QoS constraints[ C]//Proc of International Confe ling jobs on computational grids [C//Proc of the &th International rence on Optics Photonics and Energy Engineering. 2010: 281-283 Conference on Advanced Computing and Communications. Cochin [9] MUTHUCUMARU M, SHOUKAT A, HOWARD J, et al. Dynamic [s.n.],2000:45-52 matching and scheduling of a class of independent tasks onlo heteroge- [15. RUZ-CHAVEZ M A, RODRIGUEZ-LEON A, VILA-MELGAR Y A, el neous computing syslems[ C]//Proc of the: Sth Heterogeneous Compu- al Genetic-annealing algorithm in grid environment for scheduling ting Workshop. Washington DC: IEEE Compuler Society, 1999: 30 problems[ M//KIM T H, CHANG R S. Security-Enriched Urban Computing and Smart Grid. Berlin: Springer, 2010: 1 10 SAEED P, REZA E M. RASA: a new grid task sche duling algorithm 16 LIU Jing, CHEN Li, DUN Yu-qing, et al. The research of ant colony I J. International Journal of Digital Content Technology and Its and genetic algorithm in grid task scheduling C //Proc of Interna Applications, 2000, 3(4): 91-99 tional Conference on Multimedia and Information Technology [11 CHENC S T, HSIEH M T, CHEN B F. Fairness based scheduling Washington dc ∶ E Compt uter Sociely, algorithm for time division duplex mode IEEE 802. 16 broadband wire[17 MA Ting-huai, YAN Qiao-qiao, LIU Wen-jie, et al. Crid task schedu less access systems[J]. IET Communications, 2010, 4(9): 1065 ling: algorithm review[J]. IETE Technical Review, 2011, 28(2) l072 158-167 [12 Di MARTION V, MILILOTTI M Scheduling in a grid computing env [18 AREZOU M, SELIM G A Heuristie sche duling algorithms des ignee ronment using genetic algorithmE[ C //Proc of the 16th International based on properties of optimal algorithm for soft real-time tasks[C]// Parallel and Distributed Processing Symposium. Florida:[s. n] Proc of Summer Computer Simulation Conference. San Diego, CA: So- 2002:235-239 cietv for Modeling Simulation International, 2007

...展开详情
试读 5P 论文研究-求解VRPTW问题的多目标模糊偏好蚁群算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-求解VRPTW问题的多目标模糊偏好蚁群算法.pdf 13积分/C币 立即下载
    1/5
    论文研究-求解VRPTW问题的多目标模糊偏好蚁群算法.pdf第1页
    论文研究-求解VRPTW问题的多目标模糊偏好蚁群算法.pdf第2页

    试读已结束,剩余3页未读...

    13积分/C币 立即下载 >