IJE TRANSACTIONS C: Aspects Vol. 30, No. 9 (September 2017) 1342-1351   

PDF URL: http://www.ije.ir/Vol30/No9/C/7-2567.pdf  
downloaded Downloaded: 83   viewed Viewed: 1015

R. Alaei and M. Setak
( Received: January 22, 2017 – Accepted in Revised Form: July 07, 2017 )

Abstract    In this paper, a combinatorial reverse auction mechanism is proposed for selecting the most efficient service-providers for resolving sustained power interruptions in multiple regions of an electric power distribution company’s responsibility area. Through this mechanism, supplying the required service in each region is assigned to only one potential service-provider considering two criteria including cost and service time. So, the corresponding winner determination problem of the proposed auction mechanism is formulated as a bi-objective combinatorial optimization problem. However, finding a feasible solution for the formulated problem as well as its solving is NP-complete. Since exact optimization algorithms are failed in solving this kind of problems in a reasonable time, a problem specific metaheuristic called NSGA-II that is an evolutionary algorithm for solving multi-objective optimization problems is developed to estimate the set of Pareto optimal solutions of the formulated bi-objective winner determination problem. In our developed NSGA-II, two problem-specific operators are proposed for creating initial feasible solutions and converting infeasible solutions to feasible ones. Furthermore, a new method for determining the population size based on the size of problem instance is proposed. We conduct a computational experiment in which several randomly generated problem instances are solved using the proposed NSGA-II in different settings. Computational results of proposed algorithm in different settings are compared using a quality measure and statistical hypothesis tests. The results of performance comparison show that the proposed NSGA-II with a population size determined by proposed method and a different form of binary tournament method performs better in finding non-dominated solutions for different instances of formulated bi-objective optimization problem.


Keywords    supplier selection, electric power distribution industry, combinatorial reverse auction, winner determination problem, multi-objective optimization, NSGA-II


چکیده    در این مقاله، یک مکانیزم مناقصه ترکیبی برای انتخاب بهترین تأمین­کنندگان خدمات رفع خاموشی­ها در مناطق چندگانه محدوده مسئولیت یک شرکت توزیع نیروی برق ارائه می­شود که با استفاده از این مکانیزم، تأمین خدمات مورد نیاز در هر منطقه تنها به یک تأمین­کننده بالقوه با در نظر گرفتن دو معیار هزینه و مدت زمان تأمین خدمات تخصیص داده می­شود. بنابراین، مسئله تعیین برندگان متناظر با مکانیزم مناقصه ترکیبی به صورت یک مسئله بهینه­سازی ترکیبی دو هدفه فرموله می­شود. اما یافتن جواب موجه برای مسئله فرموله شده و نیز حل آن خیلی پیچیده است و الگوریتم­های بهینه­سازی دقیق قادر به حل این نوع از مسائل در مدت زمان معقول نمی­باشند. به این دلیل، از نسخه دوم الگوریتم ژنتیک با مرتب­سازی ناچیرگی که یک روش فراابتکاری برای حل مسائل بهینه­سازی چند هدفه است، برای تخمین مجموعه جواب­های پارتو مسئله دو هدفه فرموله شده استفاده می­شود. در این الگوریتم، دو عمل­گر خاص مسئله برای ایجاد جواب­های موجه اولیه و تبدیل جواب­های غیرموجه به موجه و همچنین روش جدیدی برای تعیین اندازه جمعیت بر اساس اندازه مسئله ارائه شده است. عملکرد الگوریتم ارائه شده در تنظیمات مختلف با حل مجموعه­ای از مسائل نمونه که به صورت تصادفی ایجاد شده­اند، ارزیابی می­شود. کیفیت نتایج الگوریتم ارائه شده در تنظیمات مختلف با استفاده از یک سنجه مناسب و آزمون فرض­های آماری مقایسه می­شود. نتایج حاصل از مقایسه عملکرد نشان می­دهد که الگوریتم ارائه شده با اندازه جمعیت تعیین شده با روش جدید و با شکل متفاوتی از روش تورنمنت دودویی، عملکرد بهتری در یافتن جواب­های ناچیره مسئله دو هدفه فرموله شده دارد.


1.      Setak, M., Sharifi, S. and Alimohammadian, A., "Supplier selection and order allocation models in supply chain management: A review", World Applied Sciences Journal,  Vol. 18, No. 1, (2012), 55-72.

2.      Azadnia, A., "A multi-objective mathematical model for sustainable supplier selection and order lot-sizing under inflation", International Journal of Engineering-Transactions B: Applications,  Vol. 29, No. 8, (2016), 1141.

3.      Hsieh, F.-S., "Combinatorial reverse auction based on revelation of lagrangian multipliers", Decision Support Systems,  Vol. 48, No. 2, (2010), 323-330.

4.      Cramton, P., Shoham, Y. and Steinberg, R., "Introduction to combinatorial auctions", in, MIT Press., (2010).

5.      Abrache, J., Crainic, T.G., Gendreau, M. and Rekik, M., "Combinatorial auctions", Annals of Operations Research,  Vol. 153, No. 1, (2007), 131-164.

6.      Blumrosen, L. and Nisan, N., "Combinatorial auctions", Algorithmic Game Theory,  Vol. 267, (2007), 300-308.

7.      Bichler, M., Davenport, A., Hohner, G. and Kalagnanam, J., "Industrial procurement auctions", Combinatorial Auctions,  (2006), 593-612.

8.      Hoffman, K.L., "Combinatorial auctions", Encyclopedia of Operations Research and Management Science,  (2013), 181-192.

9.      Ball, M., Donohue, G. and Hoffman, K., "Auctions for the safe, efficient, and equitable allocation of airspace system resources", Combinatorial Auctions,  Vol. 1, (2006).

10.    Alaei, R. and Ghassemi-Tari, F., "Development of a genetic algorithm for advertising time allocation problems", Journal of Industrial and Systems Engineering,  Vol. 4, No. 4, (2011), 245-255.

11.    Ghassemi Tari, F. and Alaei, R., "Scheduling tv commercials using genetic algorithms", International Journal of Production Research,  Vol. 51, No. 16, (2013), 4921-4929.

12.    Cramton, P., "Spectrum auction design", Review of Industrial Organization,  Vol. 42, No. 2, (2013), 161-190.

13.    Farnia, F., Frayret, J.-M., Lebel, L. and Beaudry, C., "Agent-based simulation of multiple-round timber combinatorial auction", Canadian Journal of Forest Research,  Vol. 47, No. 1, (2016), 1-9.

14.    Caplice, C. and Sheffi, Y., "Combinatorial auctions for truckload transportation", Combinatorial Auctions,  Vol. 21, (2006), 539-571.

15.    Triki, C., "Location-based techniques for the synergy approximation in combinatorial transportation auctions", Optimization Letters,  Vol. 10, No. 5, (2016), 1125-1139.

16.    Cantillon, E. and Pesendorfer, M., "Auctioning bus routes: The london experience",  (2006).

17.    Hohner, G., Rich, J., Ng, E., Reid, G., Davenport, A.J., Kalagnanam, J.R., Lee, H.S. and An, C., "Combinatorial and quantity-discount procurement auctions benefit mars, incorporated and its suppliers", Interfaces,  Vol. 33, No. 1, (2003), 23-35.

18.    Metty, T., Harlan, R., Samelson, Q., Moore, T., Morris, T., Sorensen, R., Schneur, A., Raskina, O., Schneur, R. and Kanner, J., "Reinventing the supplier negotiation process at motorola", Interfaces,  Vol. 35, No. 1, (2005), 7-23.

19.    Sandholm, T., Levine, D., Concordia, M., Martyn, P., Hughes, R., Jacobs, J. and Begg, D., "Changing the game in strategic sourcing at procter & gamble: Expressive competition enabled by optimization", Interfaces,  Vol. 36, No. 1, (2006), 55-68.

20.    Alaei, R. and Setak, M., "Selecting unique suppliers through winner determination in combinatorial reverse auction: Scatter search algorithm", Scientia Iranica, Transactions E: Industrial Engineering,  (2017).

21.    Buer, T. and Pankratz, G., "Solving a bi-objective winner determination problem in a transportation procurement auction", Logistics Research,  Vol. 2, No. 2, (2010), 65-78.

22.    Buer, T. and Kopfer, H., "A pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction", Computers & Operations Research,  Vol. 41, (2014), 208-220.

23.    Cormen, T.H., "Introduction to algorithms, MIT press,  (2009).

24.    Blum, C. and Roli, A., "Metaheuristics in combinatorial optimization: Overview and conceptual comparison", ACM Computing Surveys (CSUR),  Vol. 35, No. 3, (2003), 268-308.

25.    Talbi, E.-G., "Metaheuristics: From design to implementation, John Wiley & Sons,  Vol. 74,  (2009).

26.    Sharma, A.K., Datta, R., Elarbi, M., Bhattacharya, B. and Bechikh, S., Practical applications in constrained evolutionary multi-objective optimization, in Recent advances in evolutionary multi-objective optimization. (2017), Springer.159-179.

27.    Sandholm, T., Suri, S., Gilpin, A. and Levine, D., "Winner determination in combinatorial auction generalizations", in Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, ACM. , (2002), 69-76.

28.    Deb, K., Multi-objective optimization, in Search methodologies. (2014), Springer.403-449.

29.    Tavakkoli-Moghaddam, R., Makui, A., Khazaei, M. and Ghodratnama, A., "Solving a new bi-objective model for a cell formation problem considering labor allocation by multi-objective particle swarm optimization", International Journal of Engineering-Transactions A: Basics,  Vol. 24, No. 3, (2011), 249-256.

30.    Fakhrzad, M., Sadeghieh, A. and Emami, L., "A new multi-objective job shop scheduling with setup times using a hybrid genetic algorithm", International Journal of Engineering-Transactions B: Applications,  Vol. 26, No. 2, (2012), 207-216.

31.    Bashiri, M. and Rezanezhad, M., "A reliable multi-objective p-hub covering location problem considering of hubs capabilities", International Journal of Engineering-Transactions B: Applications,  Vol. 28, No. 5, (2015), 717-126.

32.    Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T., "A fast and elitist multiobjective genetic algorithm: NSGA-ii", IEEE Transactions on Evolutionary computation,  Vol. 6, No. 2, (2002), 182-197.

33.    Reeves, C.R., "Using genetic algorithms with small populations", in ICGA. Vol. 590, (1993), 92-100.

34.             Zitzler, E. and Thiele, L., "Multiobjective optimization using evolutionary algorithms—a comparative case study", in international conference on parallel problem solving from nature, Springer., (1998), 292-301.

Download PDF 

International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir