A Mathematical Negotiation Mechanism for Distributed Procurement Problems and a Hybrid Algorithm for its Solution

Document Type : Article


1 Faculty of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, Iran

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


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.


  1. References

    1. Kuo, R. and Y. Han, "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): p. 3905-3917. 2011.
    2. Hejazi, S.R., et al., "Linear bilevel programming solution by genetic algorithm". Computers & Operations Research, 29(13): p. 1913-1925. 2002.
    3. Ben-Ayed, O. and C.E. Blair, "Computational difficulties of bilevel linear programming". Operations Research. 38(3): p. 556-560. 1990.
    4. Cheng, G., S. Zhao, and T. Zhang, "A Bi-Level Programming Model for Optimal Bus Stop Spacing of a Bus Rapid Transit System". Mathematics, 7(7): p. 625. 2019.
    5. Chalmardi, M.K. and J.-F. Camacho-Vallejo, "A bi-level programming model for sustainable supply chain network design that considers incentives for using cleaner technologies". Journal of Cleaner Production, 213: p. 1035-1050. 2019.
    6. Roghanian, E., M.-B. Aryanezhad, and S.J. Sadjadi, "Integrating goal programming, Kuhn–Tucker conditions, and penalty function approaches to solve linear bi-level programming problems". Applied Mathematics and Computation, 195(2): p. 585-590. 2008.
    7. Kaheh, Z., R. Baradaran Kazemzadeh, and M.K. Sheikh-El-Eslami, "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): p. 846-861. 2020.
    8. Kaheh, Z., R. Baradaran Kazemzadeh, and M.K. Sheikh‐El‐Eslami, "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.
    9. Kaheh, Z., R.B. Kazemzadeh, and M.K. Sheikh-El-Eslami, "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): p. 4099-4113. 2019.
    10. Jung, H., B. Jeong, and C.-G. Lee, "An order quantity negotiation model for distributor-driven supply chains". International Journal of Production Economics, 111(1): p. 147-158. 2008.
    11. Jang, J. and B. Do Chung, "Aggregate production planning considering implementation error: A robust optimization approach using bi-level particle swarm optimization". Computers & Industrial Engineering, 142: p. 106367. 2020.
    12. Soares, I., M.J. Alves, and C.H. Antunes. "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. 2019.
    13. Jiang, Y., et al., "Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bilevel programming problem". Applied Mathematics and Computation, 219(9): p. 4332-4339. 2013.
    14. Wan, Z., G. Wang, and B. Sun, "A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems". Swarm and Evolutionary Computation, 8: p. 26-32. 2013.
    15. Ocampo, L.A., 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, p. 1-24. 2021
    16. Carrión, M., J.M. Arroyo, and A.J. Conejo, "A bilevel stochastic programming approach for retailer futures market trading". IEEE Transactions on Power Systems, 24(3): p. 1446-1456. 2009.
    17. Moiseeva, E. and M.R. Hesamzadeh, "Strategic bidding of a hydropower producer under uncertainty: Modified benders approach". IEEE Transactions on Power Systems, 33(1): p. 861-873. 2017.
    18. Kadadevaramath, R.S., et al., "Application of particle swarm intelligence algorithms in supply chain network architecture optimization". Expert Systems with Applications, 39(11): p. 10160-10176. 2012.
    19. Cheng, C.-B., "Reverse auction with buyer–supplier negotiation using bi-level distributed programming". European Journal of Operational Research, 211(3): p. 601-611. 2011.
    20. Fang, F. and T. Wong, "Applying hybrid case-based reasoning in agent-based negotiations for supply chain management". Expert Systems with Applications, 37(12): p. 8322-8332. 2010.
    21. Sandholm, T., 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.
    22. Sedighizadeh, D. and E. Masehian, "Particle swarm optimization methods, taxonomy and applications". International journal of computer theory and engineering, 1(5): p. 486. 2009.
    23. Akartunalı, K. and A.J. Miller, "A heuristic approach for big bucket multi-level production planning problems". European Journal of Operational Research, 193(2): p. 396-411. 2009.
    24. Danna, E., E. Rothberg, and C. Le Pape, "Exploring relaxation induced neighborhoods to improve MIP solutions". Mathematical Programming, 102(1): p. 71-90. 2005.
    25. Russell, S. and P. Norvig, "Artificial intelligence: A modern approach prentice-hall". Englewood cliffs, 1995.
    26. Hansen, E.A. and R. Zhou, "Anytime heuristic search". Journal of Artificial Intelligence Research, 28: p. 267-297. 2007.
    27. Baradaran Kazemzadeh, R., Z. Kaheh, and E. Masehian, "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): p. 63-75. 2014.
    28. Hart, P.E., N.J. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths". IEEE transactions on Systems Science and Cybernetics, 4(2): p. 100-107. 1968.
    29. Kaheh, Z., 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): p. 21-33. 2018.
    30. Hamta, N., 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): p. 99-111. 2013.
    31. Renna, P. and P. Argoneto, "Production planning and automated negotiation for SMEs: An agent based e-procurement application". International Journal of Production Economics, 127(1): p. 73-84. 2010.
    32. Kim, H.S. and J.H. Cho, "Supply chain formation using agent negotiation". Decision Support Systems, 49(1): p. 77-90. 2010.
    33. Lang, F. and A. Fink. "A quota-based multi-agent negotiation protocol for complex contracts". in International Conference on Agents and Artificial Intelligence. SciTePress. 2012.
    34. Hariga, M.A. and A. Al-Ahmari, "An integrated retail space allocation and lot sizing models under vendor managed inventory and consignment stock arrangements". Computers & Industrial Engineering, 64(1): p. 45-55. 2013.
    35. Jia, Z.-Z., J.-C. Deschamps, and R. Dupas, "A negotiation protocol to improve planning coordination in transport-driven supply chains". Journal of Manufacturing Systems, 38: p. 13-26. 2016.
    36. Proch, M., K. Worthmann, and J. Schlüchtermann, "A negotiation-based algorithm to coordinate supplier development in decentralized supply chains". European Journal of Operational Research, 256(2): p. 412-429. 2017.
    37. Shokr, I. and S.A. Torabi, "An enhanced reverse auction framework for relief procurement management". International journal of disaster risk reduction, 24: p. 66-80. 2017.
    38. Zhang, R. and K. Wang, "A multi-echelon global supply chain network design based on transfer-pricing strategy". Journal of Industrial Integration and Management, 4(01): p. 1850020. 2019.