A mathematical negotiation mechanism for distributed procurement problems and a hybrid algorithm for its solution

Document Type : Article

Authors

1 Faculty of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, P.O. Box 14115-143, Iran

2 Department of Industrial and Manufacturing Engineering, California State Polytechnic University, Pomona, CA, USA.

3 Faculty of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, P.O. Box 14115-143, Iran.

Abstract

In this paper, a mathematical negotiation mechanism is designed to minimize the negotiators’ costs in a distributed procurement problem at two echelons of an automotive supply chain. The buyer’s costs are procurement cost and shortage penalty in a one-period contract. On the other hand, the suppliers intend to solve a multi-period, multi-product production planning to minimize their costs. Such a mechanism provides an alignment among suppliers’ production planning and order allocation, also supports the partnership with the valued suppliers by taking suppliers’ capacities into account. Such a circumstance has been modeled via bi-level programming, in which the buyer acts as a leader, and the suppliers individually appear as followers in the lower level. To solve this nonlinear bi-level programming model, a hybrid algorithm by combining the particle swarm optimization (PSO) algorithm with a heuristic algorithm based on A* search is proposed. The heuristic A* algorithm is embedded to solve the mixed-integer nonlinear programming (MINLP) sub-problems for each supplier according to the received variable values determined by PSO system particles (buyer’s request for quotations (RFQs)). The computational analyses have shown that the proposed hybrid algorithm called PSO-A* outperforms PSO-SA and PSO-Greedy algorithms.

Keywords


References:
1. Kuo, R. and Han, Y. "A hybrid of genetic algorithm and particle swarm optimization for solving bi-level linear programming problem-A case study on supply chain model", Applied Mathematical Modelling, 35(8), pp. 3905-3917 (2011). https://doi.org/10.1016/j.apm.2011.02.008.
2. Hejazi, S.R., Memariani, A., Jahan Shahloo, G., et al. "Linear bilevel programming solution by genetic algorithm", Computers & Operations Research, 29(13), pp. 1913-1925 (2002). https://doi.org/10.1016/S0305-0548(01)00066-1.
3. Ben-Ayed, O. and Blair, C.E. "Computational difficulties of bilevel linear programming", Operations Research, 38(3), pp. 556-560 (1990). DOI: 10.1287/opre.38.3.556.
4. Cheng, G., Zhao, S., and Zhang, T. "A bi-level programming model for optimal bus stop spacing of a bus rapid transit system", Mathematics, 7(7), p. 625 (2019). https://doi.org/10.3390/math7070625.
5. Chalmardi, M.K. and Camacho-Vallejo, J.-F. "A bilevel programming model for sustainable supply chain network design that considers incentives for using cleaner technologies", Journal of Cleaner Production, 213, pp. 1035-1050 (2019). DOI: 10.1016/j.jclepro.2018.12.197.
6. Roghanian, E., Aryanezhad, M.-B., and Sadjadi, S.J. "Integrating goal programming, Kuhn-Tucker conditions, and penalty function approaches to solve linear bi-level programming problems", Applied Mathematics and Computation, 195(2), pp. 585-590 (2008). https://doi.org/10.1016/j.amc.2007.05.004.
7. Kaheh, Z., Baradaran Kazemzadeh, R., and Sheikh-El-Eslami, M.K. "A solution based on fuzzy max-min approach to the bi-level programming model of energy and exiramp procurement in day-ahead market", Scientia Iranica, 27(2), pp. 846-861 (2020). DOI: 10.24200/sci.2018.20915.
8. Kaheh, Z., Baradaran Kazemzadeh, R., and Sheikh- El-Eslami, M.K. "A trilevel programming model for  flexiramp and reserve procurement in high penetration of wind farms and participation of a large industry and a DR aggregator", International Transactions on Electrical Energy Systems, 29(7), p. e12105 (2019). DOI: 10.1002/2050-7038.12105.
9. Kaheh, Z., Kazemzadeh, R.B., and Sheikh-El-Eslami, M.K. "Simultaneous consideration of the balancing market and day-ahead market in Stackelberg game for flexiramp procurement problem in the presence of the wind farms and a DR aggregator", IET Generation, Transmission & Distribution, 13(18), pp. 4099-4113 (2019).DOI: 10.1049/iet-gtd.2018.6666.
10. Jung, H., Jeong, B., and Lee, C.-G. "An order quantity negotiation model for distributor-driven supply chains", International Journal of Production Economics, 111(1), pp. 147-158 (2008). https://doi.org/10.1016/j.ijpe.2006.12.054.
11. Jang, J. and Do Chung, B. "Aggregate production planning considering implementation error: A robust optimization approach using bi-level particle swarm optimization", Computers & Industrial Engineering, 142, p. 106367 (2020). https://doi.org/10.1016/j.cie.2020.106367.
12. Soares, I., Alves, M.J., and Antunes, C.H. "A bi-level hybrid PSO: MIP solver approach to define dynamic tariffs and estimate bounds for an electricity retailer profit", in Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 33-34 (2019). DOI: 10.1145/3319619.3326759.
13. Jiang, Y., Li., X., Huang, C., et al. "Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bilevel programming problem", Applied Mathematics and Computation, 219(9), pp. 4332-4339 (2013). https://doi.org/10.1016/j.amc.2012.10.010.
14. Wan, Z., Wang, G., and Sun, B. "A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems", Swarm and Evolutionary Computation, 8, pp. 26-32 (2013). https://doi.org/10.1016/j.swevo.2012.08.001.
15. Ocampo, L.A., Vasnani, N.N., Chua, F.L.S., et al. "A bi-level optimization for a make-to-order manufacturing supply chain planning: a case in the steel industry", Journal of Management Analytics, 8(4), pp. 598-621 (2021). DOI: 10.1080/23270012.2020.1871431.
16. Carrion, M., Arroyo, J.M., and Conejo, A.J. "A bilevel stochastic programming approach for retailer futures market trading", IEEE Transactions on Power Systems, 24(3), pp. 1446-1456 (2009). DOI: 10.1109/TPWRS.2009.2019777.
17. Moiseeva, E. and Hesamzadeh, M.R. "Strategic bidding of a hydropower producer under uncertainty: Modified benders approach", IEEE Transactions on Power Systems, 33(1), pp. 861-873 (2017). DOI: 10.1109/TPWRS.2017.2696058.
18. Kadadevaramath, R.S., Chen, J.C.H., Shankar, B.L., et al. "Application of particle swarm intelligence algorithms in supply chain network architecture optimization", Expert Systems with Applications, 39(11), pp. 10160-10176 (2012). https://doi.org/10.1016/j.eswa.2012.02.116.
19. Cheng, C.-B. "Reverse auction with buyer-supplier negotiation using bi-level distributed programming", European Journal of Operational Research, 211(3), pp. 601-611 (2011). https://doi.org/10.1016/j.ejor.2011.01.017.
20. Fang, F. and Wong, T. "Applying hybrid casebased reasoning in agent-based negotiations for supply chain management", Expert Systems with Applications, 37(12), pp. 8322-8332 (2010). https://doi.org/10.1016/j.eswa.2010.05.052.
21. Sandholm, T., Suri, S., Gilpin, A., et al. "Winner determination in combinatorial auction generalizations", in Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems Part 1 (2002). DOI: 10.1016/S0004-3702(03)00015-8.
22. Sedighizadeh, D. and Masehian, E. "Particle swarm optimization methods, taxonomy and applications", International Journal of Computer Theory and Engineering, 1(5), p. 486 (2009). DOI: 10.7763/IJCTE.2009.V1.80.
23. Akartunali, K. and Miller, A.J. "A heuristic approach for big bucket multi-level production planning problems", European Journal of Operational Research, 193(2), pp. 396-411 (2009). https://doi.org/10.1016/j.ejor.2007.11.033.
24. Danna, E., Rothberg, E., and Le Pape, C. "Exploring relaxation induced neighborhoods to improve MIP solutions", Mathematical Programming, 102(1), pp. 71-90 (2005). DOI:10.1007/s10107-004-0518-7.
25. Russell, S. and Norvig, P., Artificial Intelligence: A Modern Approach Prentice-Hall, Englewood cliffs (1995).
26. Hansen, E.A. and Zhou, R. "Anytime heuristic search", Journal of Artificial Intelligence Research, 28, pp. 267-297 (2007). https://doi.org/10.1613/jair.2096.
27. Baradaran Kazemzadeh, R., Kaheh, Z., and Masehian, E. "A mixed integer nonlinear programming model for order replenishment and a heuristic algorithm for its solution", Journal of Industrial Engineering Research in Production Systems, 2(3), pp. 63-75 (2014).
28. Hart, P.E., Nilsson, N.J., and Raphael, B. "A formal basis for the heuristic determination of minimum cost paths", IEEE Transactions on Systems Science and Cybernetics, 4(2), pp. 100-107 (1968). DOI: 10.1109/TSSC.1968.300136.
29. Kaheh, Z., Baradaran Kazemzadeh, R., Masehian, E., et al. "Developing a bi-level programming model for procurement management and a hybrid algorithm for its solution", Sharif Journal of Industrial Engineering & Management, 33(2.1), pp. 21-33 (2018). DOI: 10.24200/j65.2018.5501.
30. Hamta, N., Fatemi Ghomi, S.M.T., Jolai, F., et al. "A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect", International Journal of Production Economics, 141(1), pp. 99-111 (2013). https://doi.org/10.1016/j.ijpe.2012.03.013.
31. Renna, P. and Argoneto, P. "Production planning and automated negotiation for SMEs: An agent based e-procurement application", International Journal of Production Economics, 127(1), pp. 73-84 (2010). https://doi.org/10.1016/j.ijpe.2010.04.035.
32. Kim, H.S. and Cho, J.H. "Supply chain formation using agent negotiation", Decision Support Systems, 49(1), pp. 77-90 (2010). https://doi.org/10.1016/j.dss.2010.01.004.
33. Lang, F. and Fink, A. "A quota-based multi-agent negotiation protocol for complex contracts", in International Conference on Agents and Artificial Intelligence. SciTePress (2012). DOI: 10.5220/0003717501130118.
34. Hariga, M.A. and Al-Ahmari, A. "An integrated retail space allocation and lot sizing models under vendor managed inventory and consignment stock arrangements", Computers & Industrial Engineering, 64(1), pp. 45-55 (2013).
https://doi.org/10.1016/j.cie.2012.09.013.
35. Jia, Z.-Z., Deschamps, J.-C., and Dupas, R. "A negotiation protocol to improve planning coordination in transport-driven supply chains", Journal of Manufacturing Systems, 38, pp. 13-26 (2016). https://doi.org/10.1016/j.jmsy.2015.10.003.
36. Proch, M., Worthmann, K., and Schluchtermann, J. "A negotiation-based algorithm to coordinate supplier development in decentralized supply chains", European Journal of Operational Research, 256(2), pp. 412-429 (2017). https://doi.org/10.1016/j.ejor.2016.06.029.
37. Shokr, I. and Torabi, S.A. "An enhanced reverse auction framework for relief procurement management", International Journal of Disaster Risk Reduction, 24, pp. 66-80 (2017). https://doi.org/10.1016/j.ijdrr.2017.05.019.
38. Zhang, R. and Wang, K. "A multi-echelon global supply chain network design based on transfer-pricing strategy", Journal of Industrial Integration and Management, 4(01), p. 1850020 (2019). DOI: 10.1142/S2424862218500203.