Upgrading Uncapacitated Multiple Allocation P-Hub‎ ‎Median‎ ‎Problem‎ ‎Using‎ ‎Benders Decomposition Algorithm

Abstract

‎The Hub Location Problem (HLP) is a significant problem in combinatorial optimization consisting of two main components‎: ‎location and network design‎. ‎The HLP aims to develop an optimal strategy for various applications‎, ‎such as product distribution‎, ‎urban management‎, ‎sensor network design‎, ‎computer network‎, ‎and communication network design‎. ‎Additionally‎, ‎the upgrading location problem arises when modifying specific components at a cost is possible‎. ‎This paper focuses on upgrading the uncapacitated multiple allocation p-hub median problem (u-UMApHMP)‎, ‎where a pre-determined budget and bound of changes are given‎. ‎The aim is to modify certain network parameters to identify the p-hub median that improves the objective function value concerning the modified parameters‎. ‎We propose a non-linear mathematical formulation for u-UMApHMP to achieve this goal‎. ‎Then‎, ‎we employ the McCormick technique to linearize the model‎. ‎Subsequently‎, ‎we solve the linearized model using the CPLEX solver and the Benders decomposition method‎. ‎Finally‎, ‎we present experimental results to demonstrate the effectiveness of the proposed approach‎.

Keywords

• hub location‎
• ‎multiple allocation p-hub median problem‎
• ‎benders decomposition‎
• ‎combinational optimization