ortools系列：分配問題

1. 分配問題

組合優化中最重要的問題之一是分配問題，其中一組工作者必須執行一組任務。對於每個工人和任務，該工人執行任務的成本是固定的。問題是給每個工人分配不同的任務，以使總成本最小化。分配問題的一個典型就是工作排班，對於工廠這種三班倒或者公交司機兩班倒，該怎麼排班，才能照顧到每個人的工作和休息時間。

這裡有一個例子，假設一家計程車公司有四個客戶在等車，四個計程車司機(工人)可以接他們，任務是給每個客戶分配一名司機去接他們。任務的成本是司機接一個特定客戶所花費的時間，問題是，將司機分配給客戶，以最小化總等待時間。

你可以在下面的二部圖中想像這個問題。左邊的節點表示worker(司機)。右邊的節點表示任務(客戶)，這些邊表示將工作人員分配給任務的所有可能方法。

成本矩陣

下表給出了司機接客戶的成本(等待時間)，稱為成本矩陣。

from ortools.graph import pywrapgraph
import time

# 數組為代價矩陣，其中i, j項為工作者i執行任務j的代價。
# 矩陣的行對應4個工作者，列對應4個任務。
def create_data_array():
cost = [[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115]]
return cost

def main():

# 創建數據
cost = create_data_array()
rows = len(cost)
cols = len(cost[0])

# 創建分配問題的求解器
# 這裡使用 線性賦值求解器，這是一種針對賦值問題的專用求解器
assignment = pywrapgraph.LinearSumAssignment()

# 添加分配網路的弧的成本，以構建分配問題的網路
# 實用assignment.AddArcWithCost
for worker in range(rows):
for task in range(cols):
if cost[worker][task]:
assignment.AddArcWithCost(worker, task, cost[worker][task])

# 求解問題，並列印結果
solve_status = assignment.Solve()
if solve_status == assignment.OPTIMAL:
print(Total cost = , assignment.OptimalCost())
print()
for i in range(0, assignment.NumNodes()):
print(Worker %d assigned to task %d. Cost = %d % (
i,
assignment.RightMate(i),
assignment.AssignmentCost(i)))
elif solve_status == assignment.INFEASIBLE:
print(No assignment is possible.)
elif solve_status == assignment.POSSIBLE_OVERFLOW:
print(Some input costs are too large and may cause an integer overflow.)

if __name__ == "__main__":
start_time = time.clock()
main()
print()
print("Time =", time.clock() - start_time, "seconds")

# 結果
Total cost = 265

Worker 0 assigned to task 3. Cost = 70
Worker 1 assigned to task 2. Cost = 55
Worker 2 assigned to task 1. Cost = 95
Worker 3 assigned to task 0. Cost = 45

Time = 0.0003038 seconds

我們看這裡使用的求解器，pywrapgraph.LinearSumAssignment(),這裡使用線性賦值求解器，這是一種針對賦值問題的專用求解器，線性賦值求解器只接受整數類型的權重和數值。關於這個問題可以參考Using_a_solver_with_non-integer_data.

我們的求解結果如下：虛線旁邊的數字是它們的成本。這個任務的總等待時間是虛線的代價之和，即265。

再看圖上圖，在圖論中，對半圖中的一組邊，它匹配左邊的每個節點和右邊的一個節點，稱為完全匹配。

2. 解決工人不能完成所有任務的問題

在前面的例子中，我們假設所有的worker都可以執行所有的任務。但情況並非總是如此，工作人員可能由於各種原因無法執行一個或多個任務。但是，我們很容易修改上面的代碼來處理這個問題。

例如，假設worker 0無法執行task 3。要修改程序以考慮到這一點，則進行以下更改：

# 1.將成本矩陣的某個成本設置為NA
cost = [[90, 76, 75, NA],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115]]

# 2.在設置弧的時候，跳過成本為NA的弧
for worker in range(0, rows):
for task in range(0, cols):
if cost[worker][task] != NA:
assignment.AddArcWithCost(worker, task, cost[worker][task])

3. 參考

  • google_ortools_guide

大家看完記得關注點贊.

master蘇.


推薦閱讀：
相關文章