Evolutionary Winner Determination in Advanced Combinatorial Reverse Auctions

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 also validate the proposed WD method through simulated experiments by generating large instances of our CRA problem. Moreover, we apply our WD approach to a real-life electricity application based on renewable energy sources. The option for public utilities to organize electricity CRAs to purchase the needed electricity from other power suppliers is a new concept. For this purpose, we develop a constrained CRA to procure power from diverse sources including residents and plants. In our CRA, subject to various trading constraints, an item denotes a time slot that has two conflicting attributes, energy volume and price. To secure electricity, we design our auction with two bidding rounds: the first one is for variable energy suppliers and the second one for other sources, like controllable load and other renewable technologies. Our CRA leads to a complex WD problem. We view this problem as a resource allocation optimization that we solve with multi-objective GAs in order to find the best trade-off solution that lowers the price and increases the energy. This solution consists of multiple winning suppliers, their prices, power volumes and schedules. We validate our WD approach based on simulated data by generating large instances of our multi-objective constrained auction problem. The goal of the experiments is to assess the time-efficiency of our WD method and its significant superiority to well-known heuristic and exact WD techniques. Furthermore, we implement two exact algorithms to solve our complex procurement problem in order to evaluate the accuracy of our WD method i.e. how near to optimal is the solution.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Doctoral -- first

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Faculty of Graduate Studies and Research, University of Regina

Year dc:date.issued

2017

Author dc:creator

• Shil, Shubhashis Kumar

Advisor dc:contributor.advisor

• Sadaoui, Samira

Committee members dc:contributor.committeemember

• Fan, Lisa
• Mouhoub, Malek
• El-Darieby, Mohamed

Language dc:language.iso

en

DOI

https://doi.org/10.82465/4066

OAI identifier oai:identifier

oai:uregina.scholaris.ca:10294/8496