The p-median problem selects p source locations to serve n destinations such that the average distance between the destinations and corresponding sources is minimized. It is a well-studied NP-hard combinatorial optimization problem with many existing heuristic solutions, however, existing algorithms are not scalable for large-scale problems. The fast interchange (FI) heuristic which yields results close to the optimal solution with respect to the objective function value becomes suboptimal with respect to time requirements for large-scale problems. We present a novel distributed divide and conquer algorithm, EM-FI, to solve large-scale p-median problems quickly even with limited computing resources. The algorithm identifies the existing spatial clusters of the destination locations using expectation maximization (EM) and solves them as independent p-median problems using integer programming or FI concurrently. The proposed algorithm showed an order of magnitude improvement in time without the loss of quality in terms of the objective function value on synthetic and real datasets.
1 July 1998 in Journal of Network and Computer Applications
Due to situational fluidity and intrinsic uncertainty of emergency response, there needs to be a fast vehicle routing algorithm that meets the constraints of the situation, thus the receiving-staging-storing-distributing (RSSD) algorithm was developed. Benchmarking the quality of this satisficing algorithm is important to understand the consequences of not engaging with the NP-Hard task of vehicle routing problem. This benchmarking will inform whether the RSSD algorithm is producing acceptable and consistent solutions to be used in decision support systems for emergency response planning. We devise metrics in the domain space of emergency planning, response, and medical countermeasure dispensing in order to assess the quality of RSSD solutions. We conduct experiments and perform statistical analyses to assess the quality of the RSSD algorithm’s solutions compared to the best known solutions for selected capacitated vehicle routing problem (CVRP) benchmark instances. The results of these experiments indicate that even though the RSSD algorithm does not engage with finding the optimal route solutions, it behaves in a consistent manner to the best known solutions across a range of instances and attributes.