锘?!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 宸磋タ绉戝闄㈤櫌澹獵elso Ribeiro鏁欐巿瀛︽湳鎶ュ憡閫氱煡-瑗垮畨浜ら€氬ぇ瀛︾粡娴庝笌閲戣瀺瀛﹂櫌
浜ゅぇ涓婚〉 | OA绯荤粺 | 淇℃伅闂ㄦ埛 | 鏁欏笀涓婚〉 | 鎬濇簮淇$ | 璧勬枡涓嬭浇
褰撳墠浣嶇疆: 瀛﹂櫌棣栭〉>>鏂伴椈璧勮>>閫氱煡鍏憡>>姝f枃

宸磋タ绉戝闄㈤櫌澹獵elso Ribeiro鏁欐巿瀛︽湳鎶ュ憡閫氱煡

2019骞?7鏈?1鏃?16:35  鐐瑰嚮锛歔]


鎶ュ憡棰樼洰锛?/b>A GRASP with path-relinking heuristic for the prize collecting generalized minimum spanning tree

(甯︽湁璺緞閲嶆柊閾炬帴鍚彂寮忕殑GRASP鏂规硶鍦ㄩ泦濂栧箍涔夋渶灏忕敓鎴愭爲涓殑搴旂敤)

鎶ュ憡鏃堕棿锛?/b>2019骞?鏈?9鏃ワ紙鏄熸湡浜旓級涓婂崍9锛?0-11:00

鎶ュ憡鍦扮偣锛?/b>璐㈢粡涓绘ゼ鍏ゼ鍥介檯瀛︽湳浜ゆ祦鍘?/p>

鎶ュ憡鎽樿锛?/b>

Given a graph with its vertex set partitioned into a set of groups, non-negative costs associated to its edges, and non-negative prizes associated to its vertices, the prize-collecting generalized minimum spanning tree problem consists in finding a subtree of this graph, spanning exactly one vertex of each group and minimizing the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization of the NP-hard generalized minimum spanning tree optimization problem. We propose a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic for its approximate solution, incorporating path-relinking for search intensification and a restart strategy for search diversification. The hybridization of the GRASP with path-relinking and restarts heuristic with a data mining strategy that is applied along the GRASP iterations, after the elite set is modified and becomes stable, contributes to make the heuristic more robust. The computational experiments show that the heuristic developed in this work found very good solutions for test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are made available from Mendeley Data.

缁欏畾涓€涓浘锛屽畠鐨勯《鐐硅鍒掑垎涓轰笉鍚岀殑缁勶紝璧嬩簣鍏舵瘡鏉¤竟涓€涓潪璐熸垚鏈紝姣忎釜椤剁偣涓€涓潪璐熷鍔憋紝闆嗗骞夸箟鏈€灏忕敓鎴愭爲闂闇€瑕佹壘鍒颁竴涓鍥剧殑瀛愭爲锛屼娇鍏跺寘鍚笖浠呭寘鍚瘡涓€缁勯《鐐逛腑鐨勪竴涓偣锛屽悓鏃舵渶灏忓寲杩欎釜瀛愭爲鎵€鏈夎竟鐨勬垚鏈箣鍜屼娇鍏跺皬浜庨€夊畾鐨勪竴缁勯《鐐瑰鍔变箣鍜屻€傝繖涓棶棰樻槸瀵筃P闅鹃棶棰樺箍涔夋渶灏忕敓鎴愭爲浼樺寲闂鐨勪竴涓帹骞裤€傛垜浠彁鍑轰簡涓€涓惎鍙戝紡鏂规硶GRASP锛圙reedy Randomized Adaptive Search Procedure, 甯﹁嚜閫傚簲鎼滅储姝ラ鐨勯殢鏈鸿椽濠柟娉曪級鏉ユ眰瑙e緱鍒板畠鐨勮繎浼艰В锛岃繖涓柟娉曞寘鍚矾寰勯噸閾炬帴姝ラ浠ュ己鍖栨悳绱互鍙婁竴涓噸寮€濮嬬瓥鐣ヤ互鍒嗘暎鍖栨悳绱€侴RASP鏂规硶灏嗚矾寰勯噸閾炬帴绛栫暐涓庨噸寮€濮嬬瓥鐣ヨ繘琛屾贩鍚堜娇寰楁暣涓畻娉曟洿鍔犻瞾妫掞紝褰撳閫夐泦鍚堜慨鏀瑰悗鍙樺緱绋冲畾鏃讹紝GRASP鏂瑰紡鍩轰簬鏁版嵁鎸栨帢绛栫暐娌跨潃杩唬姝ラ噰鐢ㄩ噸寮€濮嬬瓥鐣ャ€傛暟鍊煎疄楠岀粨鏋滆〃鏄庯紝鎴戜滑鎻愬嚭鐨勫惎鍙戝紡鏂规硶閽堝涓€涓嫢鏈?39涓《鐐圭殑渚嬪瓙涔熷彲浠ユ壘鍒伴潪甯稿ソ鐨勮В銆傛墍鏈夋祴璇曚緥瀛愮殑杈撳叆鏁版嵁浠ュ強璇︾粏鐨勬暟鍊肩粨鏋滃彲浠ュ湪Mendeley Data涓婃壘鍒般€?/p>

鎶ュ憡浜虹畝浠嬶細

Celso Ribeiro鏄疷niversidade Federal Fluminense (UFF)鏁欐巿锛屽反瑗跨瀛﹂櫌闄㈠+锛岀編鍥紸T&T瀹為獙瀹や腑蹇冪殑瀹㈠骇鐮旂┒鍛橈紝涓昏鐮旂┒鍏磋叮鏄鏁d紭鍖栥€佸惎鍙戝紡鏂规硶銆侀殢鏈烘柟娉曘€佸苟琛岃绠椼€佸浘涓庣綉缁滅瓑锛屽叡鍑虹増涓撹憲鍏儴锛屽彂琛ㄦ枃绔犱竴鐧惧洓鍗佷綑绡囷紝鐜颁换International Transactions in Operational Research (Wiley)鏉傚織鐨勪富缂栵紝浠ュ強涓€浜涘浗闄呯煡鍚嶆湡鍒婄殑鍓富缂栥€?/p>

 

缁忛噾瀛﹂櫌

2019骞?鏈?1鏃?/p>

涓婁竴鏉★細鍛ㄦ檽鑸熷壇鏁欐巿璁插骇 涓嬩竴鏉★細瑗垮畨浜ら€氬ぇ瀛︾粡娴庝笌閲戣瀺瀛﹂櫌2019骞村浠よ惀娲诲姩瀹夋帓

銆?a href="javascript:window.opener=null;window.open('','_self');window.close();">鍏抽棴銆?/p>

鎮ㄦ槸鏈珯绗?
04519677
浣嶈闂€咃紝褰撳墠 浜哄湪绾?
鐗堟潈鎵€鏈夛細瑗垮畨浜ら€氬ぇ瀛︾粡娴庝笌閲戣瀺瀛﹂櫌
鍦板潃锛氶檿瑗跨渷瑗垮畨甯傞泚濉旇タ璺?4鍙?鐢佃瘽锛?29-82656840 閭紪锛?10061