A new variant of the p-hub location problem with a ring backbone network for content placement in VoD services. (September 2021) - Atta, Soumen; Sen, Goutam
Highlights: A new variant of the p-hub location problem is proposed with a backbone ring network. Network flow-based and path-based MILP formulations of SApHLP are introduced. A customized PSO-based method with factoradic-based solution encoding is proposed. Problem instances are created from a real-world movie data set. CPLEX optimizer with Benders decomposition is used to generate benchmark solutions. Abstract: In this article, the single allocation p -hub location problem (SApHLP) with a ring backbone network for content placement in VoD services is proposed. In VoD services, a large volume of digital data is kept as data segments in spatially distributed hubs. In SApHLP, each user is restricted to be allocated only to a single hub, and here hubs form a ring backbone network. SApHLP jointly addresses (i) the locations of hubs, (ii) the placement of segments to hubs, (iii) the allocation of users to hubs as per their demands, and (iv) the optimal paths to route the demands from users to hubs. We have introduced network flow-based 3-subscripted and path-based 4-subscripted MILP formulations of SApHLP. This article presents a novel discrete particle swarm optimization (PSO)-based approach where factoradic numbers are used to encode solution. It also incorporates three problem-specific solution refinement methods for faster convergence. In this article, SApHLP instances are generated from a real-world database of video files obtained from a movie recommender system. The benchmark solutions are generated using IBM's CPLEX optimizer with default settings and Benders decomposition strategy. The performance of the proposed PSO is compared with the benchmark results produced by CPLEX.