The single-source capacitated multi-source Weber problem with fixed opening costs and distance limits

Abstract

The single-source capacitated multi-source Weber problem with fixed costs and distance limits (SSC-MSWP-FC-DL) is an NP-hard problem. The aim is to open facilities to satisfy the demand of a set of customers. This involves determining the number of facilities to open, where to open them, and to which (single) facility each customer is allocated. This allocation has to take into consideration the maximum capacity of the facilities and the distance limit of their service. In contrast to discrete facility location problems, there are no candidate positions for the facilities: they can be opened at any position in the Euclidean plane. The objective is to minimize the total cost, that is, the sum of the Euclidean distance between each customer and its assigned facility multiplied by the customer demand and the cost of opening the facilities. A continuous location-allocation method which does not violate the constraints is proposed and tested on 75 instances from the literature and 25 instances derived from base instances from the literature. The proposed method produces competitive results to those published on our problem without the single-source capacity constraint and finds solutions on average 37% better than a commercial solver in 0.03% of the time the solver was given.

O problema de Weber de múltiplas fontes com limite de capacidade de fonte única com custos fixos e limites de distância é um problema NP-difícil. O objetivo é abrir instalações para satisfazer a demanda de um conjunto de clientes. Isso envolve determinar o número de instalações a serem abertas, onde abri-las e para qual (única) instalação cada cliente será alocado. Essa alocação precisa levar em conta a capacidade máxima das instalações e o limite de distância do serviço. Diferentemente dos problemas discretos de localização de instalações, não existem posições candidatas às instalações: elas podem ser abertas em qualquer posição do plano Euclidiano. O objetivo é minimizar o custo total, isto é, a soma da distância Euclidiana entre cada cliente e a instalação a que ele está alocado multiplicada pela demanda do cliente e o custo de se abrir as instalações. Um método de localizaçãoalocação contínua de que não viola as restrições é proposto e testado em 75 instâncias da literatura e 25 instâncias obtidas a partir de instâncias existentes na literatura. O método proposto produz resultados competitivos aos publicados sobre o nosso problema sem a restrição de capacidade de fonte única e encontra soluções em média 37% melhores do que as encontradas por um solver comercial em 0,03% do tempo dado para o solver.