面接スケジュールの最適化

#問題設定

##面接の日程調整における課題
採用候補者と面接担当者の日程調整を、従業員が担当する場合がある。
管理者は各従業員に対して以下の点に留意しなければならない状況を想定する。

・営業の勤務可能な日時の把握
・面接を担当する回数の偏りをなるべく減らす
・営業の得意分野と応募者の得意分野を近づける
・夜遅くに面接を担当することが続かないようにする

面接を担当する従業員のスキルなどを考慮してシフトスケジュールを作成する必要がある。そのため、管理者への大きな負荷が発生している。

##問題の解決
組合せ最適化技術を使い、問題の解決をおこなう。
・シフトスケジュール作成の自動化による管理業務負荷の低減
・従業員どうしの相性を考慮することで、全体の作業効率を向上させる。
　（例えば、営業Aと候補者Bが面談をすると内定受諾率が高まるなど）
・営業全体の作業効率を目的関数とし、全日程の全体最適化をおこなう。

##開発方針
・複数の手法による最適化プログラムを開発し、それぞれの対応できる問題規模、計算速度、解の最適性を比較評価する。

・面接担当者と応募者の相性については得点方式として人が入力する。
　（将来的には、勤務実績データから得点を抽出するアルゴリズムを考える）

##ソースコード

```python

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Nov 21 19:31:49 2019

@author: InagakiHirotakaf
"""

# -*- coding: utf-8 -*-
import ortools
#import janome

from ortools.linear_solver import pywraplp

import pandas as pd
#from janome.tokenizer import Tokenizer
import numpy as np
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfTransformer
from sklearn.metrics.pairwise import cosine_similarity

import copy


# 過去データ
data_train = pd.read_csv('InterviewTrain.csv', encoding="SHIFT-JIS")

#将来のデータ(テスト用データ)
data_test = pd.read_csv("InterviewTest.csv", encoding="SHIFT-JIS")

data_test_date = data_test[['dateStartTime',	'dateEndTime']]
data_test = data_test.drop(['dateStartTime',	'dateEndTime'], axis=1)

# ベクトル化ライブラリのインスタンス
vectorizer = CountVectorizer(token_pattern=u'(?u)\\b\\w+\\b')   # vectorizerの生成。token_pattern=u'(?u)\\b\\w+\\b'で1文字の語を含む設定
transformer = TfidfTransformer()                                # transformerの生成。TF-IDFを使用

# 営業さんのベクトル　******************************************************************************

wakati_list = []
for i in range(data_train.shape[0]):      
    # 分かち書き
    wakati = ''
    for j in range(1, data_train.shape[1]):
        aa = data_train.iloc[i,j]
        
        if data_train.iloc[i,j] is not np.nan:
            wakati = wakati + str(data_train.iloc[i,j]) + ' '

    wakati_list.append(wakati) # 分かち書き結果をリストに追加


# wakati_listを営業別に結合する
srp_wakati_list = []
uniqe_sales_rep_list = sorted(list(set(data_train['sales_rep'].tolist()))) # 営業さんのリスト
for srp in uniqe_sales_rep_list:
    srp_wakati = ''
    for i in range(data_train.shape[0]):
        if srp == data_train.iloc[i, 0]:
            srp_wakati = srp_wakati + wakati_list[i] + ' '
    srp_wakati_list.append(srp_wakati)
#srp_wakati_list_np = np.array(srp_wakati_list) # リストをndarrayに変換


# 応募予定者のベクトル ****************************************************************************
wakati_list_test = []
for i in range(data_test.shape[0]):      
    # 分かち書き
    wakati = ''
    for j in range(1, data_test.shape[1]):
        aa = data_test.iloc[i,j]
        
        if data_test.iloc[i,j] is not np.nan:
            wakati = wakati + str(data_test.iloc[i,j]) + ' '

    wakati_list_test.append(wakati) # 分かち書き結果をリストに追加
#wakati_list_test_np = np.array(wakati_list_test) # リストをndarrayに変換


wakati_list = srp_wakati_list + wakati_list_test
wakati_list_np = np.array(wakati_list)
tf = vectorizer.fit_transform(wakati_list_np) # ベクトル化
tfidf = transformer.fit_transform(tf) # TF-IDF
tfidf_array = tfidf.toarray()


    
srp_len = len(srp_wakati_list)
test_len = len(wakati_list_test)
srp_cs = cosine_similarity(tfidf_array[0:srp_len], tfidf_array[(srp_len):len(tfidf_array)])


print('縦軸', uniqe_sales_rep_list)
print('横軸', '応募者')
print(srp_cs)



solver = pywraplp.Solver('simple_mip_program', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)


I = len(uniqe_sales_rep_list)   # 営業の人数
J =  data_test.shape[0] # 応募者の人数

# 各営業の面談担当比率
Rate = [0.2, 0.3, 0.2, 0.1, 0.1, 0.1]

#応募者が１０人
Similarity = srp_cs
#                [
#               [100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
#               [100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
#               [100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
#               [100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
#               [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
#              ]

#
Night = [0, 0, 0, 0, 0, 0, 0, 0, 0]

#
Yesterday = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
# 決定変数x[i,j] 営業iを応募者jの面談に割り当てる
x = {}
for i in range(I):
    for j in range(J):
        x[i,j] = solver.IntVar(0, 1, 'x%i%i' %(i, j))
        
for j in range(J):
    solver.Add(solver.Sum([x[i,j] for i in range(I)]) == 1)

# 各営業の担当比率の誤差絶対値T
T = {}
for i in range(I):
    T[i] = solver.NumVar(0.0, 1000.0, 'T%i' %(i))
    solver.Add((Rate[i] - (solver.Sum([x[i,j] for j in range(j)]) / J)) <= T[i])
    solver.Add((Rate[i] - (solver.Sum([x[i,j] for j in range(j)]) / J)) >= -T[i])

# T[i]の合計を最小化する
# j1はj2は
solver.Minimize(solver.Sum(T[i] for i in range(I))
                - solver.Sum([x[i, j] * Similarity[i][j] for i in range(I) for j in range(J)])
                + solver.Sum(x[i, j] * Night[j1] * Night[j2] * Yesterday[j1][j2] for j1 in range(J) for j2 in range(j+1, J))
)

#最適化計算実施
result_status = solver.Solve()

#結果の判定
if result_status == pywraplp.Solver.OPTIMAL or result_status == pywraplp.Solver.FEASIBLE:
    print('計算結果:')
    print('比率誤差合計 =', solver.Objective().Value())
    count = [0 for i in range(I)]
    for j in range(J):
        for i in range(I):
            solval = x[i,j].solution_value()
            if solval > 0.5:
                print('応募者', j, '営業', i)
                count[i] += 1

    rate_result = [count[i] / J for i in range(I)]
    #rate_result = [count[i] for i in range(I)]
    print('担当比率', rate_result)

else:
    print('解を得られませんでした。')


```