Buer, Tobias and Kopfer, Herbert (2012): A Paretometaheuristic for a biobjective winner determination problem in a combinatorial reverse auction.

PDF
MPRA_paper_36062.pdf Download (494kB)  Preview 
Abstract
The biobjective winner determination problem (2WDPSC) of a combinatorial procurement auction for transport contracts comes up to a multicriteria set covering problem. We are given a set B of bundle bids. A bundle bid b in B consists of a bidding carrier c_b, a bid price p_b, and a set tau_b of transport contracts which is a subset of the set T of tendered transport contracts. Additionally, the transport quality q_t,c_b is given which is expected to be realized when a transport contract t is executed by a carrier c_b. The task of the auctioneer is to find a set X of winning bids (X is subset of B), such that each transport contract is part of at least one winning bid, the total procurement costs are minimized, and the total transport quality is maximized. This article presents a metaheuristic approach for the 2WDPSC which integrates the greedy randomized adaptive search procedure, large neighborhood search, and selfadaptive parameter setting in order to find a competitive set of nondominated solutions. The procedure outperforms existing heuristics. Computational experiments performed on a set of benchmark instances show that, for small instances, the presented procedure is the sole approach that succeeds to find all Paretooptimal solutions. For each of the large benchmark instances, according to common multicriteria quality indicators of the literature, it attains new bestknown solution sets.
Item Type:  MPRA Paper 

Original Title:  A Paretometaheuristic for a biobjective winner determination problem in a combinatorial reverse auction 
Language:  English 
Keywords:  Pareto optimization; multicriteria winner determination; combinatorial auction; GRASP; LNS 
Subjects:  R  Urban, Rural, Regional, Real Estate, and Transportation Economics > R4  Transportation Systems > R40  General C  Mathematical and Quantitative Methods > C6  Mathematical Methods; Programming Models; Mathematical and Simulation Modeling > C63  Computational Techniques; Simulation Modeling C  Mathematical and Quantitative Methods > C4  Econometric and Statistical Methods: Special Topics > C44  Operations Research; Statistical Decision Theory C  Mathematical and Quantitative Methods > C6  Mathematical Methods; Programming Models; Mathematical and Simulation Modeling > C61  Optimization Techniques; Programming Models; Dynamic Analysis 
Item ID:  36062 
Depositing User:  Tobias Buer 
Date Deposited:  19. Jan 2012 18:57 
Last Modified:  15. Feb 2013 19:43 
References:  [1] Kopfer H, Pankratz G. Das GroupageProblem kooperierender Verkehrsträger. In: Kall P, Lüthi HJ, editors. Operations Research Proceedings 1998. Berlin: Springer; 1999, p. 453–62. [2] Pankratz G. Analyse kombinatorischer Auktionen für ein MultiAgentensystem zur Lösung des GroupageProblems kooperierender Speditionen. In: Inderfurth K, Schwödiauer G, Domschke W, Juhnke F, Kleinschmidt P, Wäscher G, editors. Operations Research Proceedings 1999. Berlin: Springer; 2000, p. 443–8. [3] She Y. Combinatorial auctions in the procurement of transportation services. Interfaces 2004;34(4):245–52. [4] Ledyard JO, Olson M, Porter D, Swanson JA, Torma DP. The first use of a combinedvalue auction for transportation services. Interfaces 2002;32(5):4–12. [5] Elmaghraby W, Keskinocak P. Combinatorial auctions in procurement. In: Harrison T, Lee H, Neale J, editors. The Practice of Supply Chain Management: Where Theory and Application Converge. New York: SpringerVerlag; 2004, p. 245–58. [6] Caplice C, She Y. Combinatorial auctions for truckload transportation. In: Cramton P, Shoaham Y, Steinberg R, editors. Combinatorial Auctions. Cambridge, MA: MIT Press; 2006, p. 539–71. [7] Caplice C, She Y. Optimizationbased procurement for transportation services. Journal of Business Logistics 2003;24(2):109–28. [8] Abrache J, Crainic T, Gendreau M, Rekik M. Combinatorial auctions. Annals of Operations Research 2007;153(34):131–64. [9] Goossens D, Spieksma F. Exact algorithms for the matrix bid auction. Computers & Operations Research 2009;36(4):1090 –109. [10] Yang S, Segre AM, Codenotti B. An optimal multiprocessor combinatorial auction solver. Computers & Operations Research 2009;36(1):149 –66. [11] de Vries S, Vohra RV. Combinatorial auctions: A survey. INFORMS Journal on Computing 2003;15(3):284–309. [12] Catalán J, Epstein R, Guajardo M, Yung D, Martínez C. Solving multiple scenarios in a combinatorial auction. Computers & Operations Research 2009;36(10):2752 –8. [13] Chen RLY, AhmadBeygi S, Cohn A, Beil DR, Sinha A. Solving truckload procurement auctions over an exponential number of bundles. Transportation Science 2009;43(4):493–510. [14] Buer T, Pankratz G. Solving a biobjective winner determination problem in a transportation procurement auction. Logistics Research 2010;2(2):65–78. [15] Buer T, Pankratz G. Grasp with hybrid path relinking for biobjective winner determination in combinatorial transportation auctions. Business Research 2010;3(2):192–213. [16] Buer T, Kopfer H. Shipper decision support for the acceptance of bids during the procurement of transport services. In: Böse J, Hu H, Jahn C, Shi X, Stahlbock R, Voß S, editors. Proceedings of the 2nd International Conference on Computational Logistics (ICCL’11); vol. 6971 of LNCS. Springer; 2011, p. 18–28. [17] Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, editors. Complexit of Computer Computations. New York: Plenum Press; 1972, p. 85–103. [18] Serafini P. Some considerations about computational complexity for multi objective combinatorial problems. In: Jahn J, Krabs W, editors. Recent advances and historical development of vector optimization; vol. 294 of Lecture Notes in Economics and Mathematical Systems. Berlin, Germany.: SpringerVerlag; 1986, p. 222–32. [19] Talbi EG. Metaheuristics – From Desing to Implementation. Hoboken, New Jersey, USA: WileyVerlag; 2009. [20] Chvátal V. A greedy heuristic for the setcovering problem. Mathematics of Operations Research 1979;4(3):233–5. [21] Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactons on Evolutionary Computation 2003;7:117–32. [22] Zitzler E, Thiele L. Multiobjective optimization using evolutionary algorithms  a comparative case study. In: Eiben A, Bäck T, Schoenauer M, Schwefel HP, editors. Parallel Problem Solving from Nature – PPSN V; vol. 1498 of LNCS. Springer Berlin / Heidelberg; 1998, p. 292–301. [23] Zitzler E, Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation 1999;3(4):257–71. [24] Knowles JD, Thiele L, Zitzler E. A tutorial on the performance assessment of stochastic multiobjective optimizers. TIKReport 214; Computer Engineering and Networks Laboratory, ETH Zurich; 2006. [25] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. TIKReport 103; Federal Institute of Technology (ETH) Zurich, Zurich (2001); 2001. [26] Hoos HH, Stützle T. Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artificial Intelligence 1999;112(12):213–32. [27] Ribeiro C, Rosseti I, Vallejos R. On the use of run time distributions to evaluate and compare stochastic local search algorithms. In: Stützle T, Birattari M, Hoos H, editors. Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Eective Heuristics; vol. 5752 of LNCS. SpringerVerlag; 2009, p. 16–30. [28] Feo TA, Resende MG, Smith SH. A greedy randomized adaptive search procedure for maximum independent set. Operations Research 1994;42(5):860–78. [29] Aiex R, Resende M, Ribeiro C. Ttt plots: a perl program to create timetotarget plots. Optimization Letters 2007;1:355–66. 24 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/36062 