跳到主要內容

臺灣博碩士論文加值系統

(35.172.136.29) 您好!臺灣時間:2021/07/25 00:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔡世民
研究生(外文):Shih-Min Tsai
論文名稱:基於組合式反向拍賣的高效能演算法
論文名稱(外文):A Lagrangian Relaxation Approach For Combinatorial Reverse Auction
指導教授:謝富雄
指導教授(外文):Fu-Shiung Hsieh
學位類別:碩士
校院名稱:朝陽科技大學
系所名稱:資訊工程系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:49
中文關鍵詞:獲勝者決策問題組合式競標拉格朗日NP問題
外文關鍵詞:Lagrangian relaxationCombinatorial AuctionsWinner determinationNP-complete
相關次數:
  • 被引用被引用:0
  • 點閱點閱:212
  • 評分評分:
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
近年來網路拍賣的市場不斷成長,已經成為電子商務相當重要的一種商業模式。現今許多的拍賣網站都只能對單一商品進行競標,組合式競標,讓參與者可以在單一次的拍賣活動中同時對多樣商品進行投標,改善了傳統只能針對單一商品進行競標的效率。組合式競標是使眾多的競標者都能夠在一次的拍賣過程中,依照自己的喜愛、偏好,針對不同的商品組合去競標。他們能夠一次選取多樣物品,並且給予這些物品的組合一個金額。反向拍賣是將拍賣模式應用在採購商品的一種商業模式,目的在讓買方以最低的價格同時採購到所需求的多樣商品。在本篇文章中,我們將會提出一個反向拍賣的模式,為了解決最佳化分配問題和NP-complete的問題,我們使用了Lagrangian relaxation的方法,然後運用subgradient最佳化技術去做調整,讓最佳化問題能夠以有效率地尋找到近似解及數據的統計。
Auction is a kind of important business model for e-commerce. Combinatorial reverse auction can be applied in procurement to purchase goods at the lowest possible cost if there is complementarity or substitutability between the goods. A buyer can hold a reverse auction to try to obtain the goods from a set of sellers who can provide the goods. Each seller places bids for each bundle of goods he can provide. Although combinatorial reverse auction has attracted much attention recently, design of effective mechanism to guide the bidders to modify or submit their bids to collectively find a feasible solution requires further study. The problem is to determine the winners. In this paper, we consider a winner determination problem in which a buyer wants to acquire items from a set of sellers to process the task on hand. The task requires a minimal set of items for executing the operations. Each seller owns a set of items to bid for the task. The problem is to determine the winners to minimize the total cost to acquire the required items. The main results include: (1) a problem formulation for the combinatorial reverse auction problem; (2) a solution methodology based on Lagrangian relaxation; (3) an economic interpretation and (4) specification of the requirements for the implementation of our solution algorithms.
目錄
摘要..........................................................VI
Abstract.....................................................VII
致謝........................................................VIII
目錄..........................................................IX
第一章序論....................................................1
1.1 研究背景與動機................................ ................................ .................. 1
1.2 研究目標與方法................................ ................................ .................. 3
1.3 論文架構................................ ................................ .............................. 6
第二章文獻回顧................................................7
2.1 拍賣模式................................ ................................ ................................ .. 7
2.2 LAGRANGIAN................................ ................................ ........................... 8
2.3 SUBGRADIENT................................ ................................ .......................... 9
2.4 DUALITY GAP ................................ ................................ ........................... 9
第三章問題描述...............................................10
3.1 組合式反向拍賣................................ ................................ .................... 10
3.2 數學模式................................ ................................ ................................ 11
X
第四章解決方法...............................................13
4.1 LAGRANGIAN RELAXATION ................................ ................................ ....... 13
第五章實驗結果與分析.........................................17
5.1.1 例子一................................ ................................ ................................ . 17
5.1.2 例子二................................ ................................ ................................ . 18
第六章結論與未來展望.........................................23
6.1 結論................................ ................................ ................................ ....... 23
參考文獻......................................................25
附錄..........................................................28
Publication List..............................................49
XI
圖目錄
圖(一) SUBGRADIENT ................................ ................................ .................... 9
圖(二) 組合式反向拍賣................................ ................................ ............. 10
圖(三) 調解方法流程圖................................ ................................ ............. 16
圖(四) 例子一結果................................ ................................ ..................... 18
圖(五) 例子二結果................................ ................................ ..................... 20
圖(六) I 變數對於時間的影響................................ ................................ ... 21
圖(七) J 變數對於時間的影響................................ ................................ ... 21
圖(八) K 變數對於時間的影響................................ ................................ . 22
[1]Ali Haydar Özer, Can Özturan (2007), A model and heuristic algorithms for multi-unit nondiscriminatory combinatorial auction, Computers & Operations Research 36 (2009) 196 – 208.
[2]Aiying Rong, Risto Lahdelma, Peter B. Luh(2008), Lagrangian relaxation based algorithm for trigeneration planning with storages ,European Journal of Operational Research, Volume 188, Issue 1, 1 July 2008, Pages 240-257
[3]Chia-Ho Chen, Ching-Jung Ting(2007), Combining Lagrangian heuristic and Ant Colony System to solve the Single Source Capacitated Facility Location Problem, Transportation Research Part E: Logistics and Transportation Review, Volume 44, Issue 6, November 2008, Pages 1099-1122.
[4]Don Perugini, Dale Lambert, Leon Sterling, Adrian Pearce (2005),From Single Static to Multiple Dynamic Combinatorial Auctions, Intelligent Agent Technology, IEEE/WIC/ACM International Conference on 19-22 Sept. 2005 Page(s):443 – 446.
[5]Huiye Ma, Ho-fung Leung(2005), Adaptive soft bid determination in bidding strategies for continuous double auctions, Tools with Artificial Intelligence, 2005. ICTAI 05. 17th IEEE International Conference on 14-16 Nov. 2005 Page(s):5 pp.
[6]Iglesias, O. Ribeiro, R.A. Fonseca, J.R.(2004), A Fuzzy Multi-Agent Bidding Model, ntelligent Agent Technology, 2004. (IAT 2004). Proceedings. IEEE/WIC/ACM International Conference on 2004 Page(s):517 – 520.

[7]Kaj Holmberg, Martin Joborn, Kennet Melin(2008), Lagrangian based heuristics for the multicommodity network flow problem with fixed costs on paths, European Journal of Operational Research, Volume 188, Issue 1, 1 July 2008, Pages 101-108.
[8]Leonardo Meeus , Karolien Verhaegen, Ronnie Belmans(2008), Block order restrictions in combinatorial electric energy auctions, European Journal of Operational Research .
[9]Matsuo, T. Ito, T. Shintani, T.(2005), An approach to avoiding shill bids based on combinatorial auction in volume discount, Rational, Robust, and Secure Negotiation Mechanisms in Multi-Agent Systems, 2005, 25 July 2005 Page(s):25 - 38
[10]Mu Xia , Jan Stallaert , Andrew B. Whinston (2005), Solving the combinatorial double auction problem, European Journal of Operational Research, Vol.164, p. 239-251.
[11]Peter Cramton, Yoav Shoham, Richard Steinberg(2006), Introduction to Combinatorial Auctions, MIT Press.
[12]Riikka-Leena Leskelä, Jeffrey Teich, Hannele Wallenius , Jyrki Wallenius (2007), Decision support for multi-unit combinatorial bundle auctions, Decision Support Systems 43 (2007) 420–434.
[13]Shi-Chung Chang, Member, IEEE, and Da-Yin Liao, Student Member, IEEE (1994), Scheduling Flexible Flow Shops with No Setup Effects, IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 10, NO. 2, APRIL 1994.
[14]Shouxi Yanga, Alberto Maria Segrea, Bruno Codenottib(2007), An optimal multiprocessor combinatorial auction solver, Computers & Operations Research 36 (2009) 149-166.
[15]Sunju Park, Michael H. Rothkopf(2005), Auctions with bidder-determined allowable combinations, European Journal of Operational Research,Vol.161, p. 399–415.
[16]Sven de Vries, Rakesh V. Vohra(2003), Combinatorial Auctions: A Survey, INFORMS Journal on Computing, Vol. 15, No. 3.
[17]Tuomas Sandholm(2000),Approaches to winner determination in combinatorial auctions, Decision Support Systems 28 2000.165–176.
[18]Tuomas Sandholm(2002), Algorithm for optimal winner determination in combinatorial auctions, Received 9 March 1999; received in revised form 18 September 2000.
[19]Tuomas Sandholm, Subhash Suri, Andrew Gilpin, David Levine (2002), Integer Programming for Combinatorial Auction Winner Determination, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: July 2002
[20]Tuomas Sandholm , Subhash Suri(2003),Improved winner determination in combinatorial auctions and generalizations, Artificial Intelligence 145 (2003) 33–58
[21]Y. Guo, A. Lim, B. Rodrigues, J. Tang2(2005), Using A Lagrangian Heuristic For A Combinatorial Auction Problem, Tools with Artificial Intelligence,2005. ICTAI 05. 17th IEEE International Conference on14-16 Nov. 2005 Page(s):5 pp. Digital Object Identifier 10.1109/ICTAI.2005.126.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top