警察人員排班問題之研究

Abstract

人員排班（Crew Scheduling）的問題是在許多領域中最為被廣泛的討論的課題之一。就警察人員的排班問題而言，除了必須考慮動、靜態之勤務與日、夜間之勤務相互配合外，尚須考慮合理的休息與休假方式，因此，警察人員排班問題為一個相當複雜且難以求解的問題。 本研究主要是以『台灣省公路警察大隊』為實證對象，我們首先以0-1整數規劃（0-1 Integer Programming）的方法，配合其排班的制度與規則，完整定義其排班模式。以只有7名警員的簡化模式為例，即有高達將近1600個變數及900個限制式；而理論上，雖然以分枝定限法（Branch-and-Bound）的方式應可求得該問題之最佳解，但受限於警察排班模式的變數過多，經實際測試後的結果發現相當不理想。 因此本研究依循分枝定限法的架構。在演算法中加入三個主要功能：前置處理（Preprocessing）、加入有效不等式（Add Valid Inequalities）以及終止測試（Termination Test），來增進傳統分枝定限法之求解效率。 在前置處理部份，主要是利用一些簡單的數學方法，將模式中多餘的變數以及限制條件加以去除，使模式精簡化。接著本研究則針對值勤班表以及各服勤別之值勤特性加以分析，並依據分析結果加入數個有效不等式（Valid Inequalities），以達到緊縮（Tightening）可行解區域之目的，進而減少分枝定限法不必要之時間浪費。在模式經過上述步驟的處理過後，則將模式以傳統的分枝定限法進行求解。但依文獻以及過去的測試經驗顯示，其求解效率並不好。因此本研究特別在過程中加入一終止測試程序（Termination Test），以協助判斷目前的可行解是否已達最佳化。 而最後經由測試例題的結果可看出，對於現階段省公大之人員編制（14人）而言，本研究所提出之演算法已足以在短時間內快速獲得警察人員排班模式之最佳解。同時，若考量因業務增加而致使人員擴編（21人），本演算法亦可在相當短的時間內求解出排班模式之最佳解；而雖然在此部份本研究仍有一題無法驗證其為最佳解，但將暫時解與其上界比較後我們即可發現，該暫時解之品質與最佳解相比，已相差無幾。所以我們即可看出，本研究所提出之演算法對於省公大人員排班模式而言，為一求解效率相當良好之演算法。

The crews scheduling problem is one of those that have been widely studied. In addition to the tradition crews scheduling constraints, the police crews scheduling problems have to follow some specific governmental rules. Because of its problem size, the problem is complex and can not be solved efficiently. In this study we focus on the Bureau of Provencial Highway Patrol (BPHP). We formulate the scheduling model as a set-packing problem with side constraints. There are almost 1600 variables and 900 constraints just in a 7-people simplified model. Although it can be solved by traditional branch-and-bound method theoretically, the time consumption is too much to implement practically. We propose three components into the branch-and-bound method as an attempt to speed up the process. They are “Preprocessing”, “Adding Valid Inequalities”, and “Termination Test”. In the preprocessing part, the redundant variables and constraints are deleted so that the model can be simplified. Next, we analyze the labor rules and the characteristics of BPHP to derive some valid inequalities. The purpose of these valid inequalities is to tighten the feasible region. Then we use a commercial solver to solve the scheduling model by traditional branch-and-bound method. Finally, a “Termination Test” is adopted to test whether the optimality is reached while the Branch-and-Bound fails to find a better solution in a pre-specified amount of time. The testing results show that the modified method can converge to optimal solution efficiently. Among the 37 trials, only one fails to reach its optimality. However, the gap to the upper bound is small enough. Thus, we can conclude that the proposed algorithm is efficient in solving the police crew scheduling problems of BPHP.