Subjects: Geosciences >> Geography Subjects: Management Science >> Management Engineering submitted time 2021-06-09
Abstract： This article proposes a matheuristic algorithm for the single-source facility location problem (SSCFLP) and its variants: SSCFLP with K facilities (SSCKFLP), SSCFLP with connective service areas (CFLSAP), and SSCFLP with K facilities and connective service areas (CKFLSAP). The algorithm starts from an initial solution, and then iteratively improves the solution by searching large-scale neighborhood of current solution. The neighborhood is defined by determining a subset of candidate facilities and a subset of customers: (1) randomly select a customer; (2) select Q nearest facilities and their customers from the current solution; (3) select nearest candidate facilities of all the customers; and (4) randomly drop some candidate facilities if too many facilities are selected in previous step. The size of neighborhood is critical to the performance of the algorithm: it is hard to solve an extra-large neighborhood and it is difficult to find a better solution in a small neighborhood. The value of Q is suggested according to the number of facilities in current solution. The current solution might be improved by finishing the following steps: (1) formulate a sub-problem model using the selecting facilities and customers; (2) solve the model and update the current solution using sub-problem solution; and (3) for CFLSAP or CKFLSAP, repair the non-connective service areas, and improve solution with local search operators. Two set of instances were generated to test the algorithm. Experimentation shows that the instances of SSCFLP and its variant problems can be solved by the proposed matheuristic algorithm effectively and efficiently. The solutions found by the proposed algorithm approximate optimal solutions or the lower bounds with average gaps of 0.01% for SSCFLP, 0.22% for CFLSAP, 0.00% for SSCKFLP, and 0.08% for CKFLSAP. Solution results show that the solution objective would be slightly increased by adding the contiguity constraints on SSCFLP or SSCKFLP. The optimal facility locations of SSCFLP/SSCKFLP might be different from those of CFLSAP/CKFLSAP. " "
Peer Review Status:
Awaiting Review
Hits
Hits
Downloads
Comment