[PYTHON] Automatic roster creation using tabu search

at first

In this article, we will create a 10-day shift for 7 employees. There are variations of matrix elements: 4-hour work, 8-hour work, and 0-hour work (holiday). After reading this article, you will finally be able to create the following roster.

Let's start with the algorithm.

Tabu search algorithm

① Creation of initial solution ② Creation of neighborhood solution ③ Optimize using a penalty to meet the constraint conditions

That's it in a nutshell. It is an image that randomly extracts from the array of [0, 4, 8] and fills the array so as to satisfy the constraint condition.

Creating an initial solution

self.ns = np.zeros((person_num, days_num))
self.ns2 = np.zeros((person_num, days_num))
self.ns3 = np.zeros((person_num, days_num))

We are creating a matrix with all 0 elements (number of employees x number of days to calculate).

index_num = self.choice_index()
index_num2 = self.choice_index()
index_num3 = self.choice_index()

We have selected 3 indexes each to change to create 3 neighborhood solutions.

Constraints

if not(sum(self.ns[i]) < 64 and sum(self.ns[i]) >= 40):
    penalty = penalty + 1
if not(sum(self.ns2[i]) < 64 and sum(self.ns2[i]) >= 40):
    penalty2 = penalty2 + 1
if not(sum(self.ns3[i]) < 64 and sum(self.ns3[i]) >= 40):
    penalty3 = penalty3 + 1

We define a constraint that the weekly working hours of the three neighborhood solutions are within 40 to 64 hours. If the constraints are not met, the penalty will be increased by one.

The heart of tabu search

Using the "taboo list" that records the transitions that have fallen into a bad solution, we will investigate other than the one searched once. As a result, convergence becomes faster and an approximate solution can be obtained.

Whole code

%load_ext Cython

import numpy as np
import itertools
import matplotlib.pyplot as plt
import pandas as pd

class TabuSearch():
  tabu_list = []
  penalty_arr = []

  def __init__(self, person_num = 7, days_num = 10, select_num = 3):
    self.person_num = person_num
    self.penalty_old = 7 * 2 + 10
    self.days_num = 10
    self.select_num = select_num
    self.jikkou_num = 1
    #Initialization of approximate solution
    self.s_good = np.zeros((person_num, days_num))
    self.index_list = list(itertools.product(range(0, person_num), range(0, days_num), repeat=1))
    self.ns = np.zeros((person_num, days_num))
    self.ns2 = np.zeros((person_num, days_num))
    self.ns3 = np.zeros((person_num, days_num))

  def choice_index(self):
    return np.random.choice(list(range(0, self.person_num*self.days_num)), self.select_num, replace=False)

  def generate_near(self):
    #Creating a neighborhood solution
    #Since the neighborhood solution is locally transformed, select three elements. (3 is appropriate)
    #Index to replace
    index_num = self.choice_index()
    index_num2 = self.choice_index()
    index_num3 = self.choice_index()

    penalty = 0
    penalty2 = 0
    penalty3 = 0

    ns = np.zeros((self.person_num, self.days_num))
    ns2 = np.zeros((self.person_num, self.days_num))
    ns3 = np.zeros((self.person_num, self.days_num))

    chg_flag = True
    #Value to change
    new_var = [np.random.choice([8,4,0]) for i in range(0, self.select_num)]
    
    for j in range(0, len(self.tabu_list)):
      # tabu_See the first 7 values in the list
      if j == 7:
        break
      for k in range(0, self.select_num):
        if index_num[k] == TabuSearch.tabu_list[j][k]:
          chg_flag = False
        if index_num2[k] == TabuSearch.tabu_list[j][k]:
          chg_flag = False
        if index_num3[k] == TabuSearch.tabu_list[j][k]:
          chg_flag = False

    #Do not update the value if it is in the taboo list
    if chg_flag == True:
      for i in range(0, len(index_num)):
        self.ns[self.index_list[index_num[i]][0], self.index_list[index_num[i]][1]] = new_var[i]
        self.ns2[self.index_list[index_num2[i]][0], self.index_list[index_num2[i]][1]] = new_var[i]
        self.ns3[self.index_list[index_num3[i]][0], self.index_list[index_num3[i]][1]] = new_var[i]
      for i in range(0, len(self.ns)):
        if not(sum(self.ns[i]) < 64 and sum(self.ns[i]) >= 40):
          penalty = penalty + 1
        if not(sum(self.ns2[i]) < 64 and sum(self.ns2[i]) >= 40):
          penalty2 = penalty2 + 1
        if not(sum(self.ns3[i]) < 64 and sum(self.ns3[i]) >= 40):
          penalty3 = penalty3 + 1
      if penalty < self.penalty_old and penalty <= penalty2 and penalty <= penalty3:
        self.s_good = self.ns
        #Penalty only when there is no value in the taboo list_Add a value to arr
        TabuSearch.penalty_arr.append(penalty)
        for j in range(0, len(self.ns)):
          print(f"{j+1}Total value of the line", str(sum(self.ns[j])))
        self.jikkou_num = self.jikkou_num + 1
        return penalty
      elif penalty2 < self.penalty_old and penalty2 <= penalty3:
        self.s_good = self.ns2
        TabuSearch.penalty_arr.append(penalty2)
        for j in range(0, len(self.ns)):
          print(f"{j+1}Total value of the line", str(sum(self.ns2[j])))
        self.jikkou_num = self.jikkou_num + 1
        return penalty2
      elif penalty3 < self.penalty_old:
        self.s_good = self.ns3
        TabuSearch.penalty_arr.append(penalty3)
        for j in range(0, len(self.ns)):
          print(f"{j+1}Total value of the line", str(sum(self.ns3[j])))
        self.jikkou_num = self.jikkou_num + 1
        return penalty3
      else:
        #Record bad things and try to optimize good directions
        TabuSearch.tabu_list.insert(0, index_num)
        TabuSearch.tabu_list.insert(0, index_num2)
        TabuSearch.tabu_list.insert(0, index_num3)
        return self.penalty_old
    else:
      self.jikkou_num = self.jikkou_num + 1
      TabuSearch.penalty_arr.append(self.penalty_old)
      return self.penalty_old

  def execution(self, times=1000000):
    #Code to end if the sum of each line is within a certain range
    for i in range(0, times):
      penalty = self.generate_near()
      if penalty < self.penalty_old:
        print(f"{self.jikkou_num}Second execution")
        print("Penalty value", penalty)
        print("Overall penalty value", self.penalty_old)
        self.penalty_old = penalty
      if penalty == 0:
        df = pd.DataFrame(self.s_good, columns=("Month" , "fire", "water", "wood", "Money", "soil", "Day", "Month", "fire", "water"))
        print(df.to_markdown())
        break
  def plot_loss(self):
    plt.plot(TabuSearch.penalty_arr)

  def output_markdown(self):
    df = pd.DataFrame(self.s_good, columns=("Month" , "fire", "water", "wood", "Money", "soil", "Day", "Month", "fire", "water"))
    print(df.to_markdown())

Run

ts = TabuSearch()
ts.execution(100000)

Part of the output

Total value on the first line 56.0
Total value on the second line 48.0
Total value on the third line 40.0
Total value on the 4th line 40.0
Total value on the 5th line 40.0
Total value on line 6 48.0
Total value on line 7 40.0
232nd execution
Penalty value 0
Overall penalty value 1
|    |Month|fire|water|wood|Money|soil|Day|Month|fire|water|
|---:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|
|  0 |    0 |    8 |    8 |    8 |    4 |    0 |    8 |    8 |    8 |    4 |
|  1 |    4 |    8 |    4 |    4 |    4 |    8 |    0 |    8 |    4 |    4 |
|  2 |    0 |    8 |    4 |    0 |    0 |    4 |    8 |    4 |    4 |    8 |
|  3 |    4 |    0 |    8 |    0 |    0 |    4 |    4 |    8 |    4 |    8 |
|  4 |    8 |    0 |    4 |    4 |    4 |    0 |    0 |    8 |    4 |    8 |
|  5 |    4 |    4 |    4 |    0 |    4 |    8 |    0 |    8 |    8 |    8 |
|  6 |    0 |    8 |    4 |    8 |    4 |    8 |    0 |    4 |    4 |    0 |

Draw the transition of the penalty value

ts.plot_loss()

Display roster with markdown

ts.output_markdown()

|    |Month|fire|water|wood|Money|soil|Day|Month|fire|water|
|---:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|-----:|
|  0 |    0 |    8 |    8 |    8 |    4 |    0 |    8 |    8 |    8 |    4 |
|  1 |    4 |    8 |    4 |    4 |    4 |    8 |    0 |    8 |    4 |    4 |
|  2 |    0 |    8 |    4 |    0 |    0 |    4 |    8 |    4 |    4 |    8 |
|  3 |    4 |    0 |    8 |    0 |    0 |    4 |    4 |    8 |    4 |    8 |
|  4 |    8 |    0 |    4 |    4 |    4 |    0 |    0 |    8 |    4 |    8 |
|  5 |    4 |    4 |    4 |    0 |    4 |    8 |    0 |    8 |    8 |    8 |
|  6 |    0 |    8 |    4 |    8 |    4 |    8 |    0 |    4 |    4 |    0 |

Reference book

Metaheuristics and Natural Computing