[数理最適化]-人員配置最適化問題を解いてみた

特定のタスクを実行するために必要な作業時間と、各従業員の労働可能時間を考慮して、タスクの割り当てと人員配置を最適化しようとするものです。

最適な人員配置を見つけるために、[数理最適化]　の　線形プログラムを使用しています。具体的には、Xpressという最適化ライブラリを使用しています。

(1)はじめに

機械学習と数理最適化 Advent Calendar 2023 チャレンジ の文書です。

機械学習と数理最適化のカレンダー | Advent Calendar 2023 - Qiita

の下図のとおり、数理最適化の分です。

Xpressとは！？
最適化問題を解くための高性能な最適化ライブラリです。Xpressは、線形最適化、整数最適化、混合整数最適化、非線形最適化など、さまざまな最適化問題の解法を提供します。

XpressはPythonプログラミング言語でよく使用します。Pythonのインタフェースを介してXpressの機能を利用することができます。Pythonのシンタックスを使用して、制約式や目的関数を定義し、ソルバーを呼び出して最適解を求めることができます。

Xpressは、高度な最適化技術を使用して、効率的かつ高速に最適解を見つけることができます。また、制約条件や変数の設定には多くの柔軟性があります。さらに、Xpressは大規模な最適化問題にも対応しています。

(2)想定している活用シーン

1. 輸送・物流最適化: 複数の製品や資源、輸送手段などを効率的に配置し、輸送・物流コストを最小化する問題に適用することができます。例えば、倉庫から顧客への製品の輸送ルートを最適化する。

2.生産スケジューリング: 複数の製品や生産ライン、資源などの制約を考慮しながら、生産スケジュールを最適化する問題に適用することができます。これにより、生産コストを最小化し、納期の遵守やリソースの効率的な利用を図ることができます。

(3)コードの概要

このコードは、特定のタスクを実行するために必要な作業時間と、各従業員の労働可能時間を考慮して、タスクの割り当てと人員配置を最適化しようとするものです。最適な人員配置を見つけるために、線形プログラムを使用しています。具体的には、Xpressという最適化ライブラリを使用しています。

(4)コード詳細説明

1. 環境設定

この部分では、必要なライブラリのインストールとデータの読み込みを行います。

• Xpressライブラリをインストールします。

• 必要なPythonライブラリ（numpy、pandasなど）をインポートします。

• 2つのCSVファイルからデータを読み込みます。1つは従業員の労働可能時間、もう1つはタスクとその時間に関する情報です。

2. 処理実施

この部分では、最適化問題を構築し、最適解を見つけるための手順が記述されています。

2.1 変数設定

• 従業員の労働可能時間（sr_expected_hour）と、各タスクに必要な人数（sr_n_employee）と時間（sr_task_hour_per_employee）を取得します。

• n_peopleとn_taskは、従業員数とタスク数を表す変数です。

• xsは、各従業員とタスクの割り当てを表すバイナリ変数の行列です。

• vsは、各従業員の割り当てを合計した値を表す変数のベクトルです。

2.2 目的関数

• 最小化すべき目的関数を設定します。目的関数は、各従業員の割り当てを合計した値を最小化しようとするものです。

2.3 制約条件

• 様々な制約条件を設定します。例えば、各従業員が割り当てられたタスクの合計時間が、その従業員の労働可能時間を超えないように制約を設定します。

• その他の制約条件には、各タスクに必要な人数が割り当てられた人数と等しいことや、各従業員に少なくとも1つのタスクが割り当てられることが含まれます。

2.4 最適化実施

• 最適化問題を解くために、Xpressを使用します。最適化の計算時間も表示されますが、出力は無効にされています。

3. 結果出力

• 最適な人員配置をDataFrameとして取得し、表示フォーマットを設定して表示します。

• また、人員配置の差分を計算し、表示フォーマットを設定して表示します。

このコードは、従業員とタスクの情報を元に、タスクの割り当てと人員配置を最適化するための効率的な手法を提供します。

Google Colaboratory（通称Colab）は、Googleが提供するクラウドベースのJupyterノートブック環境で動作するようにしてあります。
自社環境に合う形で使ってください。

示まで

# ----------------------
# ---- 1.環境設定 ------
# ----------------------
# **********************
# [0] 環境設定 *********
# **********************
#インストール
!pip install -q xpress

import contextlib
import numpy as np
import os
import pandas as pd
import xpress as xp

# データの読みこ込み
# 本番環境
# CSVファイルを読み込む際、特定の列だけを読み込む
columns_to_read = ['氏', '名','労働可能時間']  # 読み込みたい列の名前

#個人のGITHUB環境です
# 要員の稼働時間一覧です。
df_employee = pd.read_csv('https://miraimeisatu.github.io/covid19_2021/employee2.csv', usecols=columns_to_read)


#個人のGITHUB環境です
# 要員に割り当てるタスクとその時間一覧です。
df_task = pd.read_csv('https://miraimeisatu.github.io/covid19_2021/task2.csv')

#　データ内容確認
print(df_employee)
print(df_task)

#実際の処理はここから

# ----------------------
# ---- 2.処理実施 ------
# ----------------------
# **********************
# [1] 変数設定 *********
# **********************
sr_expected_hour = df_employee['労働可能時間']
sr_n_employee = df_task['必要人数']
sr_task_hour_per_employee = df_task['必要時間'] /df_task['必要人数']

n_people = len(sr_expected_hour)
n_task = len(sr_task_hour_per_employee)

xs = np.array(
      [xp.var(name=f'x{i}', vartype=xp.binary)
       for i in range(n_people*n_task)]).reshape(n_people, n_task)

vs = np.array(
      [xp.var(name=f'v{i}')
       for i in range(n_people)]).reshape(-1, 1)

m = xp.problem()
m.addVariable(xs, vs)

# **********************
# [2] 目的関数 *********
# **********************
m.setObjective(xp.Sum(vs), sense=xp.minimize)

diff = xs.dot(sr_task_hour_per_employee) - sr_expected_hour.values
diff_rev = sr_expected_hour.values - xs.dot(sr_task_hour_per_employee)

# **********************
# [3] 制約条件 *********
# **********************
const = [
      xp.Sum(diff[i]) <= vs[i].sum()
      for i in range(n_people)]
const += [
      xp.Sum(diff_rev[i]) <= vs[i].sum()
      for i in range(n_people)]
const += [
      xp.Sum(xs.T[i]) ==n for i,
      n in enumerate(sr_n_employee)]
const += [xp.Sum(xs[i]) >= 1 for i in range(n_people)]

m.addConstraint(const)

# **********************
# [4] 最適化実施 *******
# **********************
with contextlib.redirect_stdout(open(os.devnull, 'w')):
     %time m.solve()

df_out = pd.DataFrame(m.getSolution(xs)) * sr_task_hour_per_employee
df_out.index = df_employee['氏'] + ' ' + df_employee['名']
df_out.columns = df_task['業務']

# **********************
# [5] 結果出力 *********
# **********************
#人員配置表示
#display(df_out)

# 表示フォーマットの設定（小数点1以下　四捨五入）
pd.set_option('display.float_format', '{:.1f}'.format)

#人員配置表示(df_out)の表示
display(df_out)

# **********************
# [4] 最適化実施 *******
# 差分計算
# **********************
 #人員配置 差分計算
df_diff = pd.DataFrame(
      df_employee['労働可能時間'] - df_out.sum(axis=1).values)

df_diff.index = df_out.index
df_diff.columns = ['差分']

# **********************
# [5] 結果出力 *********
# 差分計算
# **********************
# 表示フォーマットの設定（小数点2以下　四捨五入）
pd.set_option('display.float_format', '{:.2f}'.format)

display(df_diff)

Colabについてわかりやすく説明します。

1. 無料で利用可能： Colabは無料で利用できます。Googleアカウントを持っていれば、ブラウザ上で簡単に利用できます。GPUやTPUも利用でき、機械学習やディープラーニングのトレーニングなどに便利です。

2. Jupyterノートブック形式： ColabはJupyterノートブック形式を採用しています。コードセルとテキストセルを組み合わせ、コードの実行と説明文を同じ場所で管理できます。

3. クラウドベース： Colabはクラウド上で動作するため、自分のマシンに環境を構築する必要がありません。また、Google Driveとの連携も容易で、ノートブックを保存し、共有することができます。

4. 豊富なライブラリとハードウェアアクセラレーション： Colabには多くの機械学習やデータサイエンスに使用されるライブラリが事前にインストールされています。また、GPUやTPUなどのハードウェアアクセラレーションも利用可能で、大規模な計算を高速に行うことができます。

5. 共有と協力： ノートブックはGoogle Driveに保存され、他のユーザーと共有しやすいです。また、リアルタイムで共同作業も可能です。

6. データの可視化と解析： Colabにはデータの可視化や解析に役立つツールが豊富に組み込まれています。例えば、MatplotlibやSeabornなどのライブラリを使ってグラフを描画することができます。

Colabは教育、研究、プロトタイピング、データ解析、機械学習のトレーニングなど、さまざまな目的に利用されています。無料で使えるため、手軽に始めることができ、Googleのクラウドリソースを利用できる点が魅力です。

追記：

機械学習と数理最適化について

機械学習と数理最適化 Advent Calendar 2023 チャレンジ している理由

#機械学習 , #ChatGPT , #量子コンピューター , #AI ,
#クリスマス , #アドベントカレンダー , #量子コンピューター , #数理最適化 , #量子アニーリング