IJE TRANSACTIONS C: Aspects Vol. 30, No. 9 (August 2017) 1336-1345    Article in Press

PDF URL: http://www.ije.ir/Vol30/No9/C/6.pdf  
downloaded Downloaded: 0   viewed Viewed: 118

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

Abstract    In this paper, a combinatorial reverse auction mechanism is used 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 combinatorial reverse auction mechanism is formulated as a combinatorial optimization problem with two objectives: (1) minimizing the total requested cost, and (2) minimizing the average time for supplying the required service in multiple regions by potential service-providers. However, finding a feasible solution for the formulated problem as well as its solving is NP-complete. Since exact methods are failed in solving this kind of problems in a reasonable time, a problem specific NSGA-II which 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 for 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 winner determination problem.


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


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

References    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.Hsieh, F.S., “Combinatorial reverse auction based on revelation of Lagrangian multipliers”, Decision Support Systems, Vol. 48, (2010), 323-330.Cramton, P., Shoham, Y. and Steinberg, R., “Introduction to combinatorial auctions”, in Cramton, P., Shoham, Y. and Steinberg, R. (Eds.), “Combinatorial Auctions”, MIT Press, (2010).Abrache, J., Crainic, T.G., Gendreau, M. and Rekik, M., “Combinatorial auctions”, Annals of Operations Research, Vol. 153, No. 1, (2007), 131-164.Blumrosen, L. and Nisan, N., “Combinatorial auctions”, in Nisan, N., Roughgarden, T., Tardos, E. and Vazirani, V. (Eds.), “Algorithmic Game Theory”, Cambridge University Press, (2007).Bichler, M., Davenport, A., Hohner, G. and Kalagnanam, J., “Industrial procurement auctions”, in Cramton, P., Shoham, Y. and Steinberg, R. (Eds.), “Combinatorial Auctions”, MIT Press, (2010).Hoffman, K.L., “Combinatorial auctions”, in Gass, S.I. and Fu, M.C. (Eds.), “Encyclopedia of Operations Research and Management Science”, (2013), 181-192.Ball, M., Donohue, G. and Hoffman, K., “Auctions for the safe, efficient and equitable allocation of airspace system resources”, in Cramton, P., Shoham, Y. and Steinberg, R. (Eds.), “Combinatorial Auctions”, MIT Press, (2010).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. 10.  Ghassemi-Tari, F. and Alaei, R., “Scheduling TV commercials using genetic algorithms”, International Journal of Production Research, Vol. 51, No. 16, (2013), 4921-4929. 11.  Cramton, P., “Spectrum auction design”, Review of Industrial Organization, Vol. 42, No. 2, (2013), 161-190. 12.  Caplice, C. and Sheffi, Y., “Combinatorial auctions for truckload transportation”, in Cramton, P., Shoham, Y. and Steinberg, R. (Eds.), “Combinatorial Auctions”, MIT Press, (2010). 13.  Cantillon, E. and Pesendorfer, M., “Auctioning bus routes: the London experience”, in Cramton, P., Shoham, Y. and Steinberg, R. (Eds.), “Combinatorial Auctions”, MIT Press, (2010). 14.  Hohner, G., Rich, J., Ng, E., Reid, G., Davenport, A., Kalagnanam, J., Lee, H. and An, C., “Combinatorial and quantity-discount procurement auctions benefit Mars, Incorporated and its suppliers”, Interfaces, Vol. 33, No. 1, (2003), 23-35. 15.  Metty, T., Harlan, R., Samelson, Q., Moore, T., Morris, T., Sorensen, R., Schneur, A., Raskina, O., Schneur, R., Kanner, J., Potts, K. and Robbins, J., “Reinventing the supplier negotiation process at Motorola”, Interfaces, Vol. 35, No. 1, (2005), 7-23. 16.  Sandholm, T., Levine, D., Concordia, M. and Martyn, P., “Changing the game in strategic sourcing at Procter & Gamble: expressive competition enabled by optimization”, Interfaces, Vol. 36, No. 1, (2006), 55-68. 17.  Alaei, R. and Setak, M., “Selecting unique suppliers through winner determination in combinatorial reverse auction: scatter search algorithm”, Scientia Iranica, Transactions E: Industrial Engineering (in press). 18.  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. 19.  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. 20.  Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., “Introduction to Algorithms”, 3rd Edition, MIT Press, (2009), 1048-1105. 21.  Sandholm, T., Suri, S., Gilpin, A. and Levine, D., “Winner determination in combinatorial auction generalizations”, in First International Joint Conference on Autonomous Agents and Multiagent Systems, 1, ACM, (2002), 69-76. 22.  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-258. 23.  Fakhrzad, M.B., Sadegheih, 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, (2013), 207-218. 24.  Bashiri, M. and Rezanezhad, M., “A reliable multi-objective p-hub covering location problem considering hubs capabilities”, International Journal of Engineering, Transactions B: Applications, Vol. 28, No. 5, (2015), 717-729. 25.  Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T.A.M.T., “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, (2002), 182-197. 26.  Reeves, C., “Using genetic algorithms with small populations”, in 5th International Conference on Genetic Algorithms (ICGA), 590, (1993), 92-99. 27.  E. Zitzler, E. and Thiele, L., “Multiobjective optimization using evolutionary algorithms - a comparative case study”, in International Conference on Parallel Problem Solving from Nature, Springer Berlin Heidelberg, (1998), 292-301.

Download PDF 

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