Solving Partitioning-Hub Location-Routing Problem using DCA

摘要

The Partitioning-Hub-Location-Routing Problem (PHLRP) is a hub location problem involving graph partitioning and routing features. PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. There are various important applications of PHLRP, such as in deployment of network routing protocol problems and in planing of a freight distribution problems. This problem is NP-hard problem. We first present the formulation of this problem as an Binary Integer Linear Programming (BILP) and then investigate a new solution method based on DC (Difference of Convex functions) programming and DCA (DC Algorithms). Preliminary numerical results are compared with CPLEX, the best solver for BILP. These results show that the proposed algorithm is an efficient algorithm.