Capacity limited facility location problem

Capacitated Facility Location Problem

Questions as follows

Give the capacity of all plants and the cost of opening the plant , Needs of all customers , And the allocated cost assigned by the customer to a factory , The problem to be solved is ： Find a distribution plan , Minimize the total cost . Instance data download address ：Download: p1-p71

Algorithm ideas

Train of thought ： greedy

It's easy to think of , From the perspective of each user , To minimize the total cost , Then each user can choose a facility with the lowest cost . At first I thought that all the facilities would not be opened , Then each user will greedily choose , Calculate the cost of choosing a facility , If the facility is not open , Add the cost of opening the facilities , Finally, choose the one with the lowest cost . But then think about it , In fact, this is not in line with the greedy strategy , Because users will tend to choose the facilities that have been opened , In this way, users can not really choose to allocate lower cost facilities , Therefore, we can not make full use of the characteristics of greed . Therefore, the opening or closing of facilities should not have too much impact on the selection , A simple thing to do is to decide in advance which facilities to open , Then choose greedily in the open facilities . I opened all the factories , The effect of running out is really better than the initial idea . Here is python Code implementation ： First, create the classes you need .

#  Greedy Algorithm 
def greed(self, status):
    facilities = copy.deepcopy(self.facilities)
    customers = copy.deepcopy(self.customers)
    total_cost = 0
    self.assignment = [-1] * self.cnum
    for i in range(self.fnum):  #  First calculate the cost of opening the factory 
        if status[i] == 1:
            total_cost += facilities[i].opening_cost
    for i in range(self.cnum):  #  Assign a factory to each user 
        min_cost = 999999999
        for j in range(self.fnum):  #  Select from the plants that have been opened that have sufficient surplus 、 With the least cost 
            if status[j] == 1 and facilities[j].rest >= customers[i].demand:
                cost = customers[i].assign_cost[j]
                if cost < min_cost:
                    min_cost = cost
                    self.assignment[i] = j
        if self.assignment[i] != -1:  #  Plus the distribution fee 
            total_cost += min_cost
            facilities[self.assignment[i]].rest -= customers[i].demand
        else:  #  If no factory can accommodate , It doesn't work 
            return -1
    self.status = status
    self.total_cost = total_cost
    return self.total_cost

Copy

experimental result ：（ Read the dispatch cost incorrectly while reading the data , It should have started from the equipment , The cost allocated by the device to each user , But it reads as starting from the user , The cost of each device for the user , I read it backwards , Therefore, there is a certain gap between the calculated minimum value and the reference value , But because of the data structure , It's troublesome to change it , Algorithm is the key , So there is no change ） result_table_greeddetail_greed

Train of thought two ： Simulated annealing

Simulated annealing is the simulation of physical annealing process , Annealing is a process in which metallurgists repeatedly heat or cool metals to achieve certain special crystal structures , The control parameters of this process are T. The basic idea of simulated annealing is , In the process of the change of the system towards the decreasing energy , Occasionally allow the system to jump to a higher energy state , In order to avoid the local minimum , Finally, it is stable to the global minimum . The simulated annealing method is actually the mountain climbing method （ A local search algorithm ） An improvement of . The process of mountain climbing is as follows ：

（1） Generate the first possible solution , If it is a target, stop ; Otherwise, go to the next step . （2） Starting from the current possible solution , Generate a new set of possible solutions .

• Test the elements in the new possible solution set with the test function , If solution , Then stop ; If it is not the solution , Go to the next step .
• Compare it with that tested so far “ Explain ” Comparison . If it is closest to solution , Is retained as the best element ; If it is not the closest solution, discard .

（3） Start with the current best element , Transfer to （2） Step . The mountain climbing method looks for the optimal solution among the generated elements , It's easy to fall into a local optimum , An important improvement of simulated annealing is to accept the difference solution with a certain probability , Thus expanding the search space , More likely to enter the global optimum . Simulated annealing takes a temperature as a parameter , And when there is a difference solution , Accept the difference solution with a probability related to the temperature , The lower the temperature , The smaller the probability , Finally, it's stable . And at every temperature , Judge whether the equilibrium state is reached by certain criteria , For example, carry out a certain number of internal cycles 、 continuity 200 There is no better solution for the second time . For the problem of facility location , List the allocation of users as an array , As a solution space , Search in this solution space . The code is as follows ：

#  Simulated annealing 
def SA(self):
    #  Set the initial temperature 
    T = 1000
    for i in range(self.cnum):
        self.assignment[i] = -1
    current = self.assignment
    _next = None
    # good = 0
    #  cool 
    while T > 0.01:
        no = 0  #  Record how many times you have not received the optimal solution 
        # print(T)
        T *= 0.95
        #  Internal circulation until stable at this temperature 
        for i in range(1000):
            #  Generate a new solution 
            _next = self.generate(current)
            while not self.is_valid(_next):
                _next = self.generate(current)
            dE = self.total(_next) - self.total(current)
            if dE < 0:  #  Receive a better solution 
                no = 0
                # good += 1
                current = _next
                if self.total(self.assignment) > self.total(current):  #  Record the best solution so far 
                    self.assignment = current
            else:  #  Accept the difference solution with a certain probability 
                no += 1
                rd = random.random()
                if math.exp(-dE / T) >= rd:
                    current = _next
            if no > 200:
                break
    self.total_cost = self.total(self.assignment)
    for i in range(self.cnum):
        self.status[self.assignment[i]] = 1
    self.show()
    # print(good)

Copy

The function that generates the adjacency solution is as follows ：

#  Generate new solutions through domain operations 
def generate(self, current):
    customer_1 = random.randint(0, self.cnum - 1)
    customer_2 = random.randint(0, self.cnum - 1)
    _next = copy.deepcopy(current)
    while customer_2 == customer_1:
        customer_2 = random.randint(0, self.cnum - 1)
    method = random.randint(1, 4)
    if method == 1:  #  Swap two values randomly 
        _next[customer_1] = current[customer_2]
        _next[customer_2] = current[customer_1]
    elif method == 2:  #  Change two values randomly 
        _next[customer_1] = random.randint(0, self.fnum - 1)
        _next[customer_2] = random.randint(0, self.fnum - 1)
    elif method == 3:  #  Randomly insert a value into another position 
        if customer_1 < customer_2:
            for i in range(customer_1, customer_2):
                _next[i] = current[i + 1]
            _next[customer_2] = current[customer_1]
        else:
            a = range(customer_2 + 1, customer_1 + 1)
            for i in reversed(a):
                _next[i] = current[i - 1]
            _next[customer_2] = current[customer_1]
    elif method == 4:  #  The horse 
        if customer_1 < customer_2:
            for i in range(customer_2 - customer_1):
                _next[customer_1 + i] = current[customer_2 - i];
        else:
            for i in range(customer_1 - customer_2):
                _next[customer_2 + i] = _next[customer_1 - i]
    return _next

Copy

A function of the total cost ：

#  Calculate the total cost of an allocation 
def total(self, assignment):
    status = [0] * self.fnum
    for i in range(self.cnum):
        status[assignment[i]] = 1
    cost = 0
    for i in range(self.cnum):  #  Calculate the total distribution expenses 
        cost += self.customers[i].assign_cost[assignment[i]]
    for i in range(self.fnum):  #  Calculate the total cost of opening the factory 
        if status[i] == 1:
            cost += self.facilities[i].opening_cost
    return cost

Copy

Because each generated adjacency solution may be invalid , So the above uses is_valid function , Its definition is as follows ：

#  Determine whether an allocation sequence is valid 
def is_valid(self, assignment):
    if not isinstance(assignment, list):
        return False
    for i in range(self.fnum):  #  For all plants , Calculate the total demand for a factory 
        total_demand = 0
        for j in range(self.cnum):
            if assignment[j] == i:
                total_demand += self.customers[j].demand
                if total_demand > self.facilities[i].capacity:  #  If the total demand for a factory exceeds the total capacity , It doesn't work 
                    return False
    return True

Copy

This algorithm is obviously much more time-consuming than the above greedy , But basically, we can find a better solution than greed .

experimental result ： result_table_SAdetail_SA

Train of thought three ： greedy + Simulated annealing

Method 3 is actually a combination of the two methods , But it is not to say that the greedy solution is the initial solution of simulated annealing . When using greedy algorithm , It is to fix the opening and closing state of the facilities , To avoid the cost of opening the facility affecting the greedy choice of users （ As I said before ）, But the fixed opening and closing state is not necessarily the best , For example, the previous greed is to open all the facilities , But several facilities may be shut down , Again greedy , The cost may be less . So the third idea is , The greedy algorithm is used to allocate the array , Take the on or off of facilities as the solution space , Then the simulated annealing method is used to solve .

The code is as follows ：

#  Simulated annealing 2
def SA2(self):
    min_cost = 99999999
    T = 10
    self.status = [1]*self.fnum
    current = self.status
    greed_current = self.greed(current)
    _next = None
    while T > 0.1:
        no = 0  #  Record how many times you have not received the optimal solution 
        T *= 0.95
        for i in range(12):
            #  Generate a new solution 
            _next = self.generate2(current)
            greed_next = self.greed(_next)
            while greed_next == -1:
                _next = self.generate2(current)
                greed_next = self.greed(_next)
            dE = greed_next - greed_current
            if dE < 0:  #  Receive a better solution 
                no = 0
                current = _next
                greed_current = greed_next
                if min_cost > greed_current:  #  Record the best solution so far 
                    min_cost = greed_current
                    self.best_assignment = self.assignment
            else:
                no += 1
                rd = random.random()
                if math.exp(-dE / T) >= rd:
                    current = _next
                    greed_current = greed_next
                    if min_cost > greed_current:  #  Record the best solution so far 
                        min_cost = greed_current
                        self.best_assignment = self.assignment
            if no > 5:
                break
    self.total_cost = min_cost
    self.assignment = self.best_assignment

    for i in range(self.cnum):
        j = self.assignment[i]
        self.status[j] = 1
    self.show()

#  Generate new solutions through domain operations 
def generate2(self, current):
    facility_1 = random.randint(0, self.fnum - 1)
    facility_2 = random.randint(0, self.fnum - 1)
    _next = copy.deepcopy(current)
    while facility_1 == facility_2:
        facility_2 = random.randint(0, self.fnum - 1)
    method = random.randint(1, 4)
    if method == 1:  #  Swap two values randomly 
        _next[facility_1] = current[facility_2]
        _next[facility_2] = current[facility_1]
    elif method == 2:  #  Randomly flip two values 
        _next[facility_1] = 1 - current[facility_1]
        _next[facility_2] = 1 - current[facility_2]
    elif method == 3:  #  Randomly insert a value into another position 
        if facility_1 < facility_2:
            for i in range(facility_1, facility_2):
                _next[i] = current[i + 1]
            _next[facility_2] = current[facility_1]
        else:
            a = range(facility_2 + 1, facility_1 + 1)
            for i in reversed(a):
                _next[i] = current[i - 1]
            _next[facility_2] = current[facility_1]
    elif method == 4:  #  The horse 
        if facility_1 < facility_2:
            for i in range(facility_2 - facility_1):
                _next[facility_1 + i] = current[facility_2 - i];
        else:
            for i in range(facility_1 - facility_2):
                _next[facility_2 + i] = _next[facility_1 - i]
    return _next

Copy

The solution space of this idea is much smaller than that of idea 2 , So the number of cycles is relatively small , More efficient , The quality of the solution is even better than that of train of thought 2 , But because of greed , So we can't find the optimal solution , Some smaller solutions can be reached with train of thought 2 , And train of thought three can't reach . experimental result ： result_table_SA2detail_SA2

Instance data download address ：Download: p1-p71 All source codes and experimental results github Address ：CFLP