基于線性動態(tài)規(guī)劃的管材切割最優(yōu)使用率優(yōu)化研究

姬玉生 丁龍斌 鄭曉芳 白旭光 姜楊楊 尹高沖 李悅

摘 ?要：當(dāng)前軌道車輛管材切割技術(shù)，存在多種管路長度尺寸并存，無法通過一定手段獲取最優(yōu)管材切割尺寸分配和最優(yōu)使用率的情況。本文設(shè)計了一種線性動態(tài)規(guī)劃的求解思路，首先使用動態(tài)規(guī)劃算法算出所有單根管材可能的管路尺寸分布，然后將其作為系數(shù)矩陣構(gòu)建線性方程，利用線性規(guī)劃算法求出最優(yōu)解，最后利用One-hot算法將最優(yōu)解映射到最優(yōu)的管路尺寸切割分布上。設(shè)計并實現(xiàn)了基于該算法的GUI，能夠滿足生產(chǎn)中的使用，有效提升了管材切割尺寸的計算效率，并能在一定程度上節(jié)約管材，降低生產(chǎn)成本。

關(guān)鍵詞：管材切割 ?最優(yōu)使用率 ?動態(tài)規(guī)劃 線性規(guī)劃 ?One-Hot ?GUI開發(fā)

中圖分類號：TG385 ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A文章編號：1674-098X（2021）04（b）-0066-04

Research of Optimal Utilization of Pipe Cutting Based on Linear-Dynamic Programing

JI Yusheng ?DING Longbin* ?ZHENG Xiaofang ?BAI Xuguang ?JIANG Yangyang ?YIN Gaochong ? LI Yue

（CRRC Qingdao Co.， Ltd.， Qingdao， Shandong Province， 266111 China）

Abstract： In the current rail vehicle pipe cutting work， there are a variety of pipe lengths and sizes coexist， and it is impossible to obtain the optimal pipe cutting size distribution and optimal utilization rate through a certain means. This paper designed a kind of linear dynamic programming to solve the train of thought， all will be the first to use dynamic programming algorithm of single pipe may pipe size distribution， and then use it as a coefficient matrix to construct linear equation， using the linear programming algorithm to find the optimal solution， and finally using one - hot algorithm to map the optimum solution to optimal cutting line size distribution. The GUI based on the algorithm is designed and implemented， which can meet the requirements of production， effectively improve the calculation efficiency of pipe cutting size， and to a certain extent， save pipe material and reduce production cost.

Key Words： Pipe cutting; Optimal utilization; Dynamic programming; Linear programming; One-Hot; GUI development

軌道車輛的制動和給水裝置大多使用管路送風(fēng)給水，部分電路也通過管路保護(hù)電線，管路的管長、管徑等參數(shù)各有不同。在當(dāng)前的管材切割工藝中，需要根據(jù)下料表將不同長度的管料在一根較長的管材上面切割出來，當(dāng)管料較多時，所需要的管材數(shù)量各有不同。此時，由于存在鋸片厚度、最小前端余量和最小后端余量，在每根管材切割不同的管料時，需要的管材數(shù)量可能不同，管材所能夠達(dá)到的使用率也有所差異，造成管材和運(yùn)輸成本的增加。

本文提出了一種基于動態(tài)規(guī)劃和線性規(guī)劃的最優(yōu)管料長度切割方案，確保在給定前后余量和鋸片厚度條件下，管材數(shù)量達(dá)到最少，管材使用率達(dá)到最高，提升管路切割的效率，降低成本。

1 ?最優(yōu)管路切割方案

最優(yōu)管料長度切割方案是指，在管材總長度L一定的情況下，去除前端端部的規(guī)定最小余量長度m1，后端端部最小余量長度m2，鋸片厚度造成的損失N，切割出尺寸為的k根管料時，使管材使用數(shù)量n最少、管材使用率μ最高的方案。對于第i根管路，μ的計算方法如公式（1）所示：

（1）

其中，μi為第i根管材的使用率，ki為第i根管材要切割出的管料數(shù)量。

單根管材的實際使用長度l為公式（2）：

l=L-m1-m2-（ki+1）*N（2）

為最大化l，上式可化為式（3）：

∑（li+N）≤L-m1-m2-N（3）

式中，l為管材實際使用的長度，li為管材上下料管路長度，N為鋸片厚度。

對于多根管材的管路切割方案，對于多個管料長度的多種可行狀態(tài)組合，對應(yīng)著不同的管材利用率，因此需要選取合適的工作方案，使多根管材在整體上達(dá)到最優(yōu)的利用率。該問題可描述為可迭代的多級決策的最優(yōu)問題，對于多級決策的最優(yōu)問題可利用動態(tài)規(guī)劃解決，即對單根管材選擇的最佳切割方案，而這里多根管材組成了一個整體系統(tǒng)，局部最優(yōu)并不保證是全局最優(yōu)，因此有必要對動態(tài)規(guī)劃算法進(jìn)行改進(jìn)，使其能夠滿足多管材條件下的最優(yōu)化問題[1]。

1.1 動態(tài)規(guī)劃求解單根管管材切割方案

動態(tài)規(guī)劃（Dynamic Programming，DP）是運(yùn)籌學(xué)的一個分支，是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初，美國數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應(yīng)用極其廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事以及自動化控制等領(lǐng)域，并在背包問題、生產(chǎn)經(jīng)營問題、資金管理問題、資源分配問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題等中取得了顯著的效果。動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解[2]。

在使用動態(tài)規(guī)劃算法前，需要首先確定系統(tǒng)的目標(biāo)函數(shù)、控制變量和狀態(tài)變量。在本文中，由公式（3）可得目標(biāo)函數(shù)可表示為公式（4）：

（4）

設(shè)定兩個狀態(tài)量，當(dāng)前管路所使用長度方案下的管路下料集合，控制變量為最大管路可使用長度 ，應(yīng)滿足公式（5）：

（5）

狀態(tài)量的更新方程為公式（6）：

（6）

在優(yōu)化過程中，需要為該問題添加可行性約束，其主要包括管材可使用長度、管路數(shù)量等，如公式（7）所示：

（7）

其中，為方案中第i中管料長度的個數(shù)，為總體中相同管料長度的個數(shù)。

根據(jù)狀態(tài)方程求解，將符合約束條件的所有可能管路的數(shù)量組合儲存為一個長度為k的向量中，k為總體中不重復(fù)的管路個數(shù)。最后，將這些向量合并為一個k*n矩陣M，n為所有可能的方案數(shù)量。

1.2 線性規(guī)劃求解總體最優(yōu)切割方案

線性規(guī)劃（Linear Programming 簡記 LP）是了運(yùn)籌學(xué)中數(shù)學(xué)規(guī)劃的一個重要分支。自從1947年G. B. Dantzig提出求解線性規(guī)劃的單純形法以來，線性規(guī)劃在理論上趨向成熟，在實用中由于計算機(jī)能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題，線性規(guī)劃是現(xiàn)代管理中經(jīng)常采用的基本方法之一[3]。

在動態(tài)規(guī)劃得到的k*n維矩陣M中，每一列為單根管材可能采用的方案，記為，每一行為固定長度的管路在各個方案中的數(shù)量，記為。在總體中的固定長度管路數(shù)目記為。為使管材使用率最高，管材使用數(shù)目滿足最少且滿足管路生產(chǎn)需要的條件，即所需要的管路全部完成切割。此時，設(shè)每根管材可采用的方案ci對應(yīng)的方案數(shù)量為xi，則該優(yōu)化問題可描述為公式（8）：

最小化：（8）

在優(yōu)化過程中，需要為該問題添加可行性約束，使最后的結(jié)果滿足該問題中的約束條件，主要包括切割出的管料數(shù)目需要大于或等于所需要的數(shù)目，且各個方案的個數(shù)為整數(shù)。如公式（9）和公式（10）所示：

服從條件：

（9）

（10）

求解該問題，即可得到滿足給定條件的最優(yōu)管材數(shù)目和此時管材的切割方案。

1.3 One-Hot 映射求解可用最優(yōu)方案

One-Hot編碼，又稱為一位有效編碼，主要是采用N位狀態(tài)寄存器來對N個狀態(tài)進(jìn)行編碼，每個狀態(tài)都有獨(dú)立的寄存器位，并且在任意時候只有一位有效。One-Hot編碼是分類變量作為二進(jìn)制向量的表示，這首先要求將分類值映射到整數(shù)值。然后，每個整數(shù)值被表示為二進(jìn)制向量，除了整數(shù)的索引之外，它都是零值，被標(biāo)記為1。

當(dāng)?shù)玫阶顑?yōu)管材數(shù)目和管材切割方案后，由于條件給定的管路數(shù)目大于等于給定的數(shù)目，因此還需要將所得的方案映射到滿足問題給定數(shù)目的方案中，且保持盡可能多的管材使用率?；镜慕鉀Q思路是在使用率低的管材方案中將多余的管路去除，即可滿足要求。為解決這一問題，記管材切割方案為矩陣 P，每一行為一根管材的方案ci，每一列為固定長度管路在方案中的數(shù)量nj，管路冗余量residual如公式（11）所示：

（11）

對冗余量residual作one-hot編碼，將其化為每一個樣本只含有一個1的向量形式hj。然后，將cj與每個residual的向量求歐幾里得距離，如公式（12）所示：

（12）

當(dāng)di最小時，有ci與residual的距離最小，說明修改該方案能夠盡量保證其他方案不變，即可保持盡可能多的管材使用率。迭代運(yùn)算，直到residual中的剩余量全部為0。

2 ?GUI程序設(shè)計

2.1 最優(yōu)管材切割方案算法實現(xiàn)

本文選用Python編程語言實現(xiàn)，版本為3.5.1。使用模塊有數(shù)學(xué)科學(xué)計算工具包numpy，線性規(guī)劃模塊pulp. 算法共分為3個模塊，分別為動態(tài)規(guī)劃模塊，線性規(guī)劃模塊和最后的one-hot修正模塊[4-5]。

動態(tài)規(guī)劃模塊主要包括weights、nums和max_weight三個輸入值，分別表示下料管路的長度、下料管路的個數(shù)和最大管材使用長度。在最大管材可使用長度之內(nèi)，對下料管路長度進(jìn)行編輯，將所有滿足條的管路長度組合保存到weight_num中，最后返回該值，即得到所需要的所有可能的管路組合方案。動態(tài)規(guī)劃模塊的代碼如圖1所示。

線性規(guī)劃模塊包括動態(tài)規(guī)劃得到的可能的組合方案weight_num，將其映射為線性規(guī)劃中的num_arrs，以及各類下料管路個數(shù)nums，部分代碼如圖2所示。首先將num_arrs轉(zhuǎn)換為矩陣形式（k*n維矩陣M），然后依據(jù)公式（8）建立線性規(guī)劃問題描述，依據(jù)（9-10）建立線性規(guī)劃問題的約束條件，然后計算得出可能存在的結(jié)果。結(jié)果輸出后，將公式（8）中非零的xi取出，作為獲得的問題的解。

在線性規(guī)劃得到所有方案選擇出的個數(shù)組合之后，利用one-hot算法和公式（11）計算出residual，并利用公式（12）迭代計算，直到residual為0，此時的init即為全局最優(yōu)解，即最優(yōu)管材切割方案，如圖3所示。

2.2 最優(yōu)管材切割方案GUI設(shè)計與實現(xiàn)

為方便班組人員使用，本文設(shè)計了人機(jī)交互界面（GUI）供給其他人員使用。如圖4所示，該圖為本文的GUI實現(xiàn)圖，主要包含4個功能：從文件中取出下料管路的尺寸和數(shù)量;輸入管材長度L、頭部最小余量m1、尾部最小余量m2和鋸片厚度N;當(dāng)點(diǎn)擊開始計算后，在下方的嵌入顯示界面顯示計算過程和計算結(jié)果;最后點(diǎn)擊保存可將計算結(jié)果保存到選擇的文件中。

圖5為該GUI應(yīng)用程序的功能描述圖，當(dāng)選擇了讀取的文件后，將在下方顯示界面實時顯示讀取到的文件數(shù)據(jù);點(diǎn)擊開始計算后，程序會將計算的中間過程和計算結(jié)果實時顯示在界面，包括一些出錯信息等。

3 ?結(jié)語

本文運(yùn)用Python語言設(shè)計和實現(xiàn)了基于線性動態(tài)規(guī)劃的管材切割最優(yōu)方案選擇工具，該工具結(jié)合了一線管路彎管工作的生產(chǎn)實際，通過對管路下料選擇的數(shù)學(xué)理論進(jìn)行研究，利用動態(tài)規(guī)劃、線性規(guī)劃的優(yōu)化選擇算法實現(xiàn)了最優(yōu)方案選擇的功能，利用Python編程語言和科學(xué)工具包numpy，將其用編程語言實現(xiàn)，然后利用Qt編寫GUI提供給用戶使用，并添加了多種特殊情況判斷，能夠滿足生產(chǎn)中的使用，有效提升了管材切割尺寸的計算效率，并能在一定程度上節(jié)約管材，降低生產(chǎn)成本。

今后，可在本文研究的基礎(chǔ)上，繼續(xù)深入，進(jìn)一步將該解決方法應(yīng)用到其他類似的場景如地板鋪設(shè)、原材料尺寸選擇等等。此外，針對其他問題，也可結(jié)合本次設(shè)計，選擇其他相似的優(yōu)化算法進(jìn)行優(yōu)化，以提高生產(chǎn)效率，提質(zhì)增效[6]。

注：軟件源代碼可在https：//github.com/dlb123/dynamic_pipe_choose獲取

參考文獻(xiàn)

[1] 俞山青，鄭鈞，殳欣成，等.一種真假信息傳播能力評估的動態(tài)規(guī)劃算法[J].小型微型計算機(jī)系統(tǒng)，2021，42（1）：85-90.

[2] 何洪文，石曼，曹劍飛，等.基于動態(tài)規(guī)劃的再生制動能量管理策略[J/OL].重慶理工大學(xué)學(xué)報：自然科學(xué)：1-8[2021-01-25].http：//kns.cnki.net/kcms/detail/50.1205.t.20201222.1324.004.html.

[3] 黃紅，顧煒江.基于線性規(guī)劃模型的人力調(diào)配管理智能優(yōu)化系統(tǒng)設(shè)計[J].現(xiàn)代電子技術(shù)，2021，44（2）：135-139.

[4] 丁龍斌.隨機(jī)森林入侵檢測算法研究[D].蘭州：蘭州交通大學(xué)，2020.

[5] 蘇佳麗，伍忠東，丁龍斌，等.基于IGWO-RBF的LTE-R切換算法研究[J].計算機(jī)工程與應(yīng)用，2020，56（8）：74-80.

[6] 丁龍斌，伍忠東，蘇佳麗.基于集成深度森林的入侵檢測方法[J].計算機(jī)工程，2020，46（3）：144-150.