Evolutionary Winner Determination in Advanced Combinatorial Reverse Auctions
type: CreativeWork
description: Traditional Combinatorial Reverse Auctions (CRAs) are already very hard problems to solve. By considering the multiplicity of units, attributes and objectives of items; the complexity of CRAs increases. Winner Determination (WD) is one of the main challenges of CRAs, and which has been shown to be NP-complete. Researchers limit the auction features because of the issue of time efficiency. We address several types of advanced CRAs by varying the auction parameters. We tackle the combinatorial procurement problem instances using Genetic Algorithms (GAs). In the first instance, we consider multiple units, single attribute and objective. To this end, we propose a modified crossover operator and two routines. Our proposed WD method is capable of finding the winner(s) with a minimum procurement cost and an efficient processing time. To validate our GA-based method, we conduct several experiments and the results clearly demonstrate the good-time performance and the high quality of the solution. In the second problem, we tackle CRAs with two attributes, single objective and multiple units and rounds. We make this problem more interesting by considering all-units discounts and the availability of sellers’ stock. To evaluate our proposed method, we conduct several experiments. In the next problem instance, we include additional constraints, such as seller stocks and discount rate. In this part, we perform a comparative study of several exact and evolutionary techniques addressing different types of CRAs. In particular, we show that our technique based on GAs outperforms some other methods in terms of time efficiency. Lastly, we address CRAs with multiple units, attributes, objectives and rounds. We define optimization approach based on GAs that we integrate with our own variants of diversity and elitism strategies to greatly improve the solution quality. We conduct a case study as well as simulated testing to illustrate the importance of the diversity and elitism schemes. We …
abstract: Traditional Combinatorial Reverse Auctions (CRAs) are already very hard problems to solve. By considering the multiplicity of units, attributes and objectives of items; the complexity of CRAs increases. Winner Determination (WD) is one of the main challenges of CRAs, and which has been shown to be NP-complete. Researchers limit the auction features because of the issue of time efficiency. We address several types of advanced CRAs by varying the auction parameters. We tackle the combinatorial procurement problem instances using Genetic Algorithms (GAs). In the first instance, we consider multiple units, single attribute and objective. To this end, we propose a modified crossover operator and two routines. Our proposed WD method is capable of finding the winner(s) with a minimum procurement cost and an efficient processing time. To validate our GA-based method, we conduct several experiments and the results clearly demonstrate the good-time performance and the high quality of the solution. In the second problem, we tackle CRAs with two attributes, single objective and multiple units and rounds. We make this problem more interesting by considering all-units discounts and the availability of sellers’ stock. To evaluate our proposed method, we conduct several experiments. In the next problem instance, we include additional constraints, such as seller stocks and discount rate. In this part, we perform a comparative study of several exact and evolutionary techniques addressing different types of CRAs. In particular, we show that our technique based on GAs outperforms some other methods in terms of time efficiency. Lastly, we address CRAs with multiple units, attributes, objectives and rounds. We define optimization approach based on GAs that we integrate with our own variants of diversity and elitism strategies to greatly improve the solution quality. We conduct a case study as well as simulated testing to illustrate the importance of the diversity and elitism schemes. We …
author: Shil, Shubhashis Kumar
language: en
date published: 2017-09
date modified: 2026-07-24T04:03:30Z
provider: University of Regina
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Faculty of Graduate Studies and Research, University of Regina

PropertyValue
property ID: Handle
value: https://hdl.handle.net/10294/8496

PropertyValue
property ID: DOI
value: 10.82465/4066