張國晨，孫超利，石 慧，李曉波

(太原科技大學(xué)1.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院；2.電子信息工程學(xué)院，山西 太原030024)

預(yù)拌混凝土(ready-mixed concrete,RMC)具有節(jié)約水泥、提高生產(chǎn)率、節(jié)約施工用地等優(yōu)點(diǎn)，是當(dāng)今世界用量最大、用途最廣泛的建筑材料之一[1]。混凝土罐車調(diào)度問題包含車輛時(shí)序、攪拌站的裝載時(shí)序、施工現(xiàn)場的連續(xù)遞送需求、及時(shí)生產(chǎn)等多個(gè)子問題，屬于復(fù)雜的組合優(yōu)化問題?，F(xiàn)階段混凝土罐車調(diào)度問題的研究主要關(guān)注在模型中引入更加符合實(shí)際情況的調(diào)度因素，并研究適用的優(yōu)化算法。Liu等[2]研究了每個(gè)攪拌站有多個(gè)攪拌設(shè)備的問題，并采用一種基于鄰閾值搜索的算法求解問題。Zhang等[3]、Yan等[4]研究了運(yùn)輸時(shí)間隨機(jī)的罐車調(diào)度問題，建立了罐車調(diào)度問題的網(wǎng)絡(luò)流模型和基于網(wǎng)絡(luò)流模型的混合整數(shù)機(jī)會(huì)規(guī)劃模型。De Miranda Sá等[5]在罐車調(diào)度中使用google地圖API獲取實(shí)時(shí)距離數(shù)據(jù)。Moons等[6]、Devapriya等[7]研究了將攪拌站的生產(chǎn)時(shí)序與罐車運(yùn)輸時(shí)序相結(jié)合的罐車調(diào)度問題。Schmid等[8]研究了多攪拌站以及罐車裝載量不同的罐車調(diào)度問題。Yan等[9]研究了攪拌站隨機(jī)故障時(shí)調(diào)度方案的調(diào)整策略。Asbach等[10]的研究中不僅有攪拌站工作時(shí)間約束，同時(shí)也考慮客戶工作時(shí)間限制的問題。還有很多研究關(guān)注了混凝土罐車調(diào)度過程引入更切合實(shí)際的調(diào)度因素，例如調(diào)度中包含特殊的泵車車輛類型、罐車運(yùn)輸中的隨機(jī)故障等。在求解罐車調(diào)度問題的優(yōu)化算法研究方面，目前主要有啟發(fā)式規(guī)則算法和智能優(yōu)化算法2大類。Schmid等[8]研究了結(jié)合啟發(fā)式的大規(guī)模鄰域搜索算法對問題優(yōu)化求解。Albayrak等[11]研究結(jié)合線性規(guī)劃的遺傳算法對問題求解。Mayteekrieangkrai等[12]、Choi等[13]研究蜂群算法、蟻群算法在罐車調(diào)度問題中的優(yōu)化求解。Yan等[4,14]采用結(jié)合啟發(fā)式的線性規(guī)劃算法，并用CPLEX工具對問題求解。Lin等[15]將罐車調(diào)度問題建模為一類車間作業(yè)問題，并采用結(jié)合啟發(fā)式的仿真優(yōu)化方法進(jìn)行求解。Naso等[16]采用結(jié)合遺傳算法的兩階段優(yōu)化方法對問題求解。Graham等[17]采用了神經(jīng)網(wǎng)絡(luò)對罐車調(diào)度問題進(jìn)行求解。

混凝土罐車是比較特殊的一類配送車輛，包含機(jī)械設(shè)備、電器設(shè)備等多個(gè)部件子系統(tǒng)，混凝土罐車的狀態(tài)直接決定了混凝土企業(yè)在完成混凝土配送過程中的收益情況，決定了客戶需求是否能及時(shí)得到滿足。在實(shí)際混凝土的生產(chǎn)配送中，很多混凝土企業(yè)要求罐車每日必須在指定地點(diǎn)完成一次日常預(yù)防性維修，稱為日常檢測，以保證混凝土罐車的車輛狀態(tài)符合運(yùn)輸需求。因此，本文在混凝土罐車調(diào)度問題的基礎(chǔ)上，加入罐車日常檢測因素，建立基于網(wǎng)絡(luò)流的混合整數(shù)規(guī)劃模型。并且，針對該模型采用啟發(fā)式規(guī)則輔助的遺傳算法求解，同時(shí)在構(gòu)建車輛流的過程中提出一種沖突選擇策略以保證算法運(yùn)行的正確性。

1罐車調(diào)度問題的網(wǎng)絡(luò)流模型

1.1問題描述

結(jié)合日檢的混凝土罐車調(diào)度如圖1所示。問題中所有數(shù)據(jù)在每個(gè)工作日調(diào)度之前都是已知的，包含攪拌站因素、罐車因素、客戶因素、日檢點(diǎn)因素等多個(gè)因素。每輛混凝土罐車在工作日開始時(shí)需要從?？奎c(diǎn)(圖中A和B)出發(fā)，到達(dá)攪拌站裝載混凝土并運(yùn)輸至客戶施工現(xiàn)場為客戶服務(wù)，完成1次服務(wù)后，需要再次返回任意攪拌站(圖中有3個(gè)攪拌站位置)裝載混凝土為下一次客戶作業(yè)服務(wù)。在罐車的每日工作中需要且只需要1次到日檢位置做日常檢查保養(yǎng)，完成當(dāng)日工作后罐車需要返回任意1個(gè)?？奎c(diǎn)，?？奎c(diǎn)位置可以是單獨(dú)位置，如圖中B點(diǎn)，也可以是某個(gè)攪拌站，如圖中A點(diǎn)。為了建立問題有效的數(shù)學(xué)模型，本文采用網(wǎng)絡(luò)流模型構(gòu)建混凝土罐車調(diào)度問題模型，將問題表示為有向圖G={V,E,W,O}， 其中，V為模型中的結(jié)點(diǎn)集合，E為邊集，W為與每個(gè)結(jié)點(diǎn)相關(guān)的時(shí)間集合，O為邊集上的費(fèi)用集合。

客戶相關(guān)因素 有n個(gè) 客戶C={C1,C2,···Cn}需求混凝土，每個(gè)客戶在工作日內(nèi)都有混凝土需求量Qi，根據(jù)罐車的裝載量q將每個(gè)客戶的需求量轉(zhuǎn)換為多次作業(yè)N(Ci)=「Qi/q■，其中N(C i)表 示客戶Ci需求的所有作業(yè)數(shù)， 「■表示向上取整。每次作業(yè)由1輛罐車完成。每個(gè)客戶會(huì)指定第1次作業(yè)的服務(wù)時(shí)間窗[S(Ci),E(Ci)]，表示在該時(shí)間范圍內(nèi)客戶的準(zhǔn)備工作已經(jīng)完成，可以接收混凝土遞送，超出該時(shí)間范圍會(huì)造成人員、設(shè)備等資源的耗費(fèi)。由于混凝土的澆筑必須連續(xù)，否則已經(jīng)澆筑的混凝土?xí)霈F(xiàn)分層現(xiàn)象，因此，對同一個(gè)客戶2次連續(xù)澆筑作業(yè)開始時(shí)間的間隔要在[minCi,maxCi]之內(nèi)。其中，minCi是連續(xù)2次作業(yè)間隔時(shí)間的最小值，該時(shí)間值指一次卸載完成后施工現(xiàn)場完成平整、清理等操作以保證順利接收下一次作業(yè)所需要的時(shí)間；maxCi是連續(xù)2次作業(yè)間隔時(shí)間的最大值，如果連續(xù)2次作業(yè)的間隔時(shí)間大于該值，已經(jīng)澆筑的混凝土將會(huì)發(fā)生初凝現(xiàn)象，使得連續(xù)2次澆筑的混凝土出現(xiàn)分層，嚴(yán)重影響施工質(zhì)量。假設(shè)客戶連續(xù)2次作業(yè)的澆筑開始時(shí)間分別為 ωi和 ωi+1，則這2次作業(yè)必須滿足ωi+SevCi+minCi≤ωi+1≤ωi+SevCi+maxCi。每次作業(yè)的卸載時(shí)間和裝載量、施工現(xiàn)場的泵送設(shè)備、人員配備情況相關(guān)，SevCi表示施工現(xiàn)場服務(wù)時(shí)間。

在網(wǎng)絡(luò)流模型 G中，任意一個(gè)客戶Ci∈C的所有作業(yè)表示為其中，

攪拌站相關(guān)因素 問題中包含m個(gè)攪拌站[D1,D2,···,Dm]，由于攪拌站的生產(chǎn)率限制，同一個(gè)攪拌站的連續(xù)2次作業(yè)的裝載時(shí)間間隔需大于最小時(shí)間限制 minDi。根據(jù)交通管理部門要求，罐車在攪拌站裝載完成后需要在SevDi的時(shí)間內(nèi)完成相應(yīng)的清洗等工作才可以上路運(yùn)輸。

在網(wǎng)絡(luò)流模型G 中，將每一個(gè)攪拌站Di∈D表示為其 中，即在模型G中 將每個(gè)攪拌站模型轉(zhuǎn)化為可以滿足所有客戶作業(yè)次數(shù)的結(jié)點(diǎn)。

罐車相關(guān)因素 調(diào)度過程中涉及p輛混凝土罐車K=[K1,K2,···,K p]， 每輛罐車的裝載量為q。在每個(gè)工作日，混凝土企業(yè)使用任意一輛罐車都有固定的車輛使用費(fèi) λ。由于預(yù)拌混凝土產(chǎn)品有易凝固的特性，因此混凝土在罐車中停留的時(shí)間不能超過混凝土的初凝時(shí)間約束 γ，以保證混凝土施工質(zhì)量。每輛罐車在工作日開始時(shí)，需要從?？奎c(diǎn)Li∈L={L1,L2,···,Lo}行駛到攪拌站裝載混凝土，接著完成本次作業(yè)的遞送、卸載等工作后返回?cái)嚢枵救ネ瓿上乱淮巫鳂I(yè)。在罐車的每日工作過程中，任意2次作業(yè)之間或者第一次作業(yè)開始之前，最后一次作業(yè)完成之后，罐車需要行駛到日檢點(diǎn)I完成1次且每日只需完成1次的日常檢查工作，在完成工作日所有工作及日常檢查后，罐車需要返回停車點(diǎn)。停車點(diǎn)和日檢點(diǎn)的位置可以是某個(gè)攪拌站，也可以是不同于攪拌站的別的位置，如圖1所示，?？奎c(diǎn)B和日檢點(diǎn)為獨(dú)立位置，?？奎c(diǎn)A就是某個(gè)攪拌站。

由于每輛罐車的初始?？课恢檬且阎模虼嗽诰W(wǎng)絡(luò)流模型中，所有停靠點(diǎn)的出發(fā)車輛可以組成集合即將每輛罐車的出發(fā)位置作為模型G中的一個(gè)結(jié)點(diǎn)。每輛罐車結(jié)束當(dāng)日工作后可以返回任意?？奎c(diǎn)，因此將車輛?？奎c(diǎn)集合定義為表示每個(gè)?？奎c(diǎn)都可以停靠所有罐車，并且將每次停靠都作為一個(gè)結(jié)點(diǎn)加入網(wǎng)絡(luò)流模型中。

日檢相關(guān)因素 調(diào)度過程中只有1個(gè)日檢點(diǎn)，該日檢點(diǎn)的位置可以是某個(gè)攪拌站內(nèi)，或者是獨(dú)立于攪拌站的其他位置。罐車到達(dá)日檢點(diǎn)后需要服務(wù)時(shí)間 SevI完成車輛的日常檢查工作，當(dāng)同時(shí)有多輛罐車到達(dá)日檢點(diǎn)時(shí)，需要排隊(duì)等待。在網(wǎng)絡(luò)流模型中，將日檢點(diǎn)因素建模為IG={I K1,···,I K p}，即每輛罐車的日檢操作模型化為一個(gè)結(jié)點(diǎn)加入模型中。

綜上所述，模型G的結(jié)點(diǎn)集合V可以表示為其中為所有客戶結(jié)點(diǎn)集合；為所有攪拌站結(jié)點(diǎn)集合；為所有的車輛開始結(jié)點(diǎn)和結(jié)束結(jié)點(diǎn)集合；IG為所有的日檢相關(guān)結(jié)點(diǎn)集合。

網(wǎng)絡(luò)流模型G中的邊集為E=(u,v,k),u,v∈V,k∈K，表示調(diào)度方案中罐車k從結(jié)點(diǎn)u運(yùn) 行到結(jié)點(diǎn)v。時(shí)間集合ωu∈W表示與任意結(jié)點(diǎn)相關(guān)的操作開始時(shí)刻。當(dāng)結(jié)點(diǎn)u∈DG時(shí)， ωu表示罐車在結(jié)點(diǎn)u開始裝載混凝土的時(shí)刻；當(dāng)結(jié)點(diǎn)u∈CG時(shí)， ωu表示在結(jié)點(diǎn)u卸載混凝土的時(shí)刻；u∈LG時(shí)，表示離開?？奎c(diǎn)的時(shí)刻或到達(dá)停靠點(diǎn)的時(shí)刻；當(dāng)u∈IG時(shí)，表示罐車到達(dá)日檢點(diǎn)并開始檢測的時(shí)刻。費(fèi)用集合中Ou,v,k∈O，表示任意一次操作的相關(guān)費(fèi)用，包含從結(jié)點(diǎn)u到達(dá)結(jié)點(diǎn)v的運(yùn)輸費(fèi)用，在結(jié)點(diǎn)u,v的等待時(shí)間費(fèi)用，以及服務(wù)時(shí)間耗費(fèi)。費(fèi)用集合中 λ ∈C，表示每輛罐車的工作日固定使用費(fèi)用。

圖2給出了包含2個(gè)攪拌站、2個(gè)客戶(客戶C1有2次作業(yè)需求，客戶C2有3次作業(yè)需求)、3輛罐車、1個(gè)日檢點(diǎn)的網(wǎng)絡(luò)流模型示例圖。根據(jù)上述網(wǎng)絡(luò)流模型定義可知，該網(wǎng)絡(luò)流模型中包含5個(gè)客戶作業(yè)結(jié)點(diǎn)、10個(gè)攪拌站裝載結(jié)點(diǎn)、3個(gè)開始結(jié)點(diǎn)和3個(gè)結(jié)束結(jié)點(diǎn)以及3個(gè)日檢結(jié)點(diǎn)。圖中箭頭方向表示時(shí)間先后順序，第1輛罐車從停靠點(diǎn)出發(fā)到達(dá)攪拌站D1，裝載混凝土后為客戶作業(yè)服務(wù)，服務(wù)完成后到達(dá)日檢點(diǎn)完成日常檢測并返回?cái)嚢枵綝2為客戶作業(yè)服務(wù)；第2輛罐車從?？奎c(diǎn)出發(fā)到達(dá)攪拌站D2為客戶作業(yè)服務(wù)，完成后返回?cái)嚢枵綝1裝載混凝土并再次為客戶作業(yè)服務(wù)，服務(wù)完成后到達(dá)日檢結(jié)點(diǎn)完成日常檢測；第3輛罐車從停靠點(diǎn)出發(fā)直接到達(dá)日檢結(jié)點(diǎn)進(jìn)行日常檢測，完成檢測后返回?cái)嚢枵綝1裝載混凝土為客戶作業(yè)C23服務(wù)。圖2中僅給出了該示例的一種調(diào)度方案，而實(shí)際優(yōu)化中該網(wǎng)絡(luò)流模型因結(jié)點(diǎn)時(shí)間選擇不同，調(diào)度順序不同會(huì)有多種可行調(diào)度方案。

1.2基于網(wǎng)絡(luò)流的罐車調(diào)度數(shù)學(xué)模型

根據(jù)上述問題描述及網(wǎng)絡(luò)流模型定義，建立結(jié)合日檢的罐車調(diào)度問題混合整數(shù)規(guī)劃模型，模型中的決策變量如下。

圖2網(wǎng)絡(luò)流模型示例圖Figure 2 An example diagram of network flow model

其中，xuvk為0，1變量，當(dāng)問題空間內(nèi)有罐車k從結(jié)點(diǎn)u到 達(dá)v時(shí)，變量的值為1，否則為0； ωu為時(shí)間變量，表示在結(jié)點(diǎn)u開始相關(guān)操作的時(shí)刻(攪拌站結(jié)點(diǎn)裝載開始時(shí)刻，客戶結(jié)點(diǎn)卸載開始時(shí)刻，日檢點(diǎn)檢測時(shí)刻，離開或到達(dá)?？奎c(diǎn)時(shí)刻)。

模型的目標(biāo)函數(shù)如式(1)所示。該目標(biāo)函數(shù)分為3部分。第1部分為最小化罐車調(diào)度過程中的運(yùn)輸費(fèi)用、等待費(fèi)用。第2部分為最小化未完成作業(yè)的懲罰費(fèi)用，即某個(gè)客戶作業(yè)未完成時(shí)會(huì)有一個(gè)固定的懲罰費(fèi)用β。第3部分為最小化固定車輛使用費(fèi)，在工作日每使用一輛罐車會(huì)有固定的車輛使用費(fèi)，如果罐車直接從開始結(jié)點(diǎn)到達(dá)日檢點(diǎn)并完成日檢，日檢完成后返回停靠點(diǎn)，則該車輛在當(dāng)日工作中沒有配送任務(wù)，沒有固定車輛使用費(fèi)。α為每輛罐車的固定使用費(fèi)。

約束(2)、(3)表示一輛罐車在工作日開始時(shí)只能從停靠點(diǎn)出發(fā)1次，并返回?？奎c(diǎn)1次。當(dāng)出發(fā)結(jié)點(diǎn)為開始結(jié)點(diǎn)到達(dá)結(jié)點(diǎn)為結(jié)束結(jié)點(diǎn)時(shí)，表示該罐車k未參與配送工作，因此這類邊集上的費(fèi)用函數(shù)為O(uvk)=Tranu,I+minI+Tran(I,v)，表示即便該車輛沒有參與工作，也必須到達(dá)日檢點(diǎn)做1次日檢。約束(4)表示模型需要滿足攪拌站結(jié)點(diǎn)、客戶結(jié)點(diǎn)、日檢結(jié)點(diǎn)的出入度平衡，車輛到達(dá)結(jié)點(diǎn)裝載、卸載或日檢后，必須離開該結(jié)點(diǎn)去服務(wù)客戶或結(jié)束當(dāng)日工作。約束(5)表示每個(gè)客戶作業(yè)至多只能被完成1次。約束(6)表示因?yàn)閿嚢枵镜纳a(chǎn)率限制，同一個(gè)攪拌站不能同時(shí)裝載2輛罐車，因此模型 G中每個(gè)攪拌站結(jié)點(diǎn)至多只能訪問1次。約束(7)、(8)表示每輛罐車只能訪問日檢點(diǎn)1次，每個(gè)日檢點(diǎn)只能被訪問1次，即每輛罐車每個(gè)工作日有且只有1次日檢操作。約束(9)表示對于任意客戶，其第j+1次作業(yè)只有在第j次作業(yè)完成后才能完成。即同一客戶的作業(yè)必須按順序完成。約束(10)將變量xuvk與變量 ωu通過服務(wù)時(shí)間 Sev(u)與運(yùn)輸時(shí)間函數(shù)關(guān)聯(lián)在一起，用一個(gè)極大的數(shù)M來保證到達(dá)結(jié)點(diǎn)u的時(shí)間與到達(dá)結(jié)點(diǎn)v的時(shí)間符合運(yùn)輸及服務(wù)的時(shí)間約束。約束(11)用來保證混凝土在車輛中停留的時(shí)間不會(huì)超出混凝土特性所決定的混凝土初凝時(shí)間 γ。約束(12)、(13)保證客戶的第1次作業(yè)開始時(shí)間在客戶指定的工作時(shí)間窗之內(nèi)。約束(14)保證同一客戶的連續(xù)2次作業(yè)開始時(shí)間間隔滿足客戶指定的時(shí)間窗約束。約束(15)和約束(5)保證在攪拌站不會(huì)同時(shí)有2輛罐車被裝載，并且滿足攪拌站生產(chǎn)率約束。約束(16)和約束(8)共同保證同時(shí)只有1輛罐車在日檢點(diǎn)做檢測，并滿足日檢時(shí)間約束。約束(17)、(18)定義了模型中變量的定義域。

2仿真優(yōu)化方法

本文采用啟發(fā)式輔助的遺傳算法求解基于網(wǎng)絡(luò)流的罐車調(diào)度問題。模型中的啟發(fā)式規(guī)則如下。1)針對實(shí)際罐車調(diào)度過程中的操作時(shí)間限制，模型中的時(shí)間變量 ω精確到秒沒有實(shí)際意義，因此在求解的過程中，將時(shí)間變量的精度定義為分；2)因?yàn)槊枯v罐車的完成順序必須在攪拌站裝載后再去服務(wù)客戶，服務(wù)完客戶后返回?cái)嚢枵净蛉ト諜z點(diǎn)檢測，最終完成所有服務(wù)循環(huán)。因此，以此為基礎(chǔ)對模型變量進(jìn)行編碼，并采用沖突選擇策略完成適應(yīng)度計(jì)算及約束處理。算法1步驟如下。

步驟1編碼：根據(jù)簡化后的時(shí)間變量對問題進(jìn)行編碼。

步驟2初始化：生成由 Pop_size個(gè) 個(gè)體組成的初始種群P opi。

步驟3參數(shù)設(shè)定：設(shè)定迭代次數(shù) Round_times，交叉概率，變異概率。

步驟4 交叉變異：根據(jù)參數(shù)，針對本代種群Popi執(zhí)行交叉和變異操作。

步驟5多樣化：再次生成由 Pop_size個(gè)個(gè)體組成的插入種群P optemp。

步驟6 構(gòu)建車輛流：針對種群P opi和 P optemp中的每個(gè)個(gè)體，根據(jù)沖突選擇策略處理約束并組成車輛流。

步驟7計(jì)算適應(yīng)度：針對每個(gè)個(gè)體的車輛流，計(jì)算本輪2 ×Pop_size個(gè)個(gè)體的適應(yīng)度。

步驟8選擇：針對2×Pop_size個(gè)個(gè)體的適應(yīng)度，采用最優(yōu)保留策略及輪盤賭策略選擇Pop_size個(gè)個(gè)體作為下一代種群Popi+1

步驟9 循環(huán)：重復(fù)執(zhí)行步驟3～8 R ound_times次 。

步驟10保存：獲取最優(yōu)結(jié)果并輸出。

在算法中為了保持種群的多樣性，采用加入新生代種群的策略，在每次選擇下一代個(gè)體時(shí)，首先生成一代臨時(shí)種群，然后結(jié)合本代種群和臨時(shí)種群一起選擇下一代種群。經(jīng)過試驗(yàn)得出該策略可以為算法執(zhí)行過程中引入新的選擇因素，更有利于算法跳出局部最優(yōu)。

2.1編碼方案

由問題描述可知，車輛的裝載量相同，即每個(gè)客戶的需求作業(yè)數(shù)已知。遺傳算法的編碼結(jié)構(gòu)如圖3所示。

編碼中的第1部分表示所有客戶作業(yè)的開始卸載時(shí)刻，如果編碼中基因位置表示的是某個(gè)客戶的第1次作業(yè)則該基因位置的取值范圍為E(Ci)]內(nèi)的隨機(jī)整數(shù)值。如果該基因位置非某個(gè)客戶的第1次作業(yè)，則該基因位置的取值依賴于前1個(gè)基因的值為內(nèi)的隨機(jī)整數(shù)值。編碼中的第2部分表示所有客戶作業(yè)的完成攪拌站結(jié)點(diǎn)，每個(gè)基因位置的取值為模型 G中結(jié)點(diǎn)集合DG中的任意一個(gè)值，并且每個(gè)值只能使用1次。編碼中的第3部分表示每個(gè)客戶作業(yè)由哪輛罐車完成，取值為[1,···,m]內(nèi)的任意值i，表示該客戶作業(yè)由車輛Ki完 成。編碼的第4部分是由m輛罐車的日檢位置組成的，這部分每個(gè)基因表示罐車Ki完成了工作日的第幾次作業(yè)后去日檢點(diǎn)完成日檢操作。

圖3編碼方式Figure 3 Coding mode

2.2適應(yīng)度計(jì)算

針對每個(gè)個(gè)體計(jì)算適應(yīng)度時(shí)，需要首先構(gòu)建由該個(gè)體組成的車輛流，再由車輛流計(jì)算車輛運(yùn)輸費(fèi)用、等待費(fèi)用、車輛固定使用費(fèi)、未完成作業(yè)的懲罰，最終得到該個(gè)體的適應(yīng)度值。車輛流構(gòu)建過程(算法2)如下。

步驟1將個(gè)體中的所有客戶作業(yè)按客戶作業(yè)開始裝載時(shí)間排序。步驟2根據(jù)步驟1的排序結(jié)果組成初始車輛流。步驟3采用沖突選擇策略，將個(gè)體中不符合約束的因素剔除。

步驟4根據(jù)沖突處理后的個(gè)體，重新構(gòu)建所有可行車輛流。

步驟5計(jì)算可行車輛流的適應(yīng)度，并保留適應(yīng)度最高的車輛流。

構(gòu)建車輛流的過程中，首先要根據(jù)個(gè)體中的第1、2部分，計(jì)算每個(gè)客戶作業(yè)在攪拌站的開始裝載時(shí)刻，再根據(jù)該時(shí)刻對客戶作業(yè)排序，然后組成初始車輛流。例如車輛i的車輛流為Ki:(Ki,1,Ki,2,···,Ki,j,···)，其中i表 示罐車Ki，j表示該車輛需要完成的第j次作業(yè)(客戶的混凝土需求作業(yè)或該車輛的日檢作業(yè))。該車輛流表示該車輛需要在完成第1次作業(yè)Ki,1后返回相關(guān)攪拌站去裝載并完成第2次作業(yè)Ki,2，以此類推直到完成當(dāng)日的所有作業(yè)。在初始車輛流中，假設(shè)第j次作業(yè)是客戶Ca的作業(yè)，第j+1次作業(yè)的裝載攪拌站為Db，如果第j+1次作業(yè)在攪拌站Db的開始裝載時(shí)間小于第j次作業(yè)完成后到達(dá)攪拌站Db的時(shí)間則表明這2次作業(yè)有沖突，即罐車在完成第j次作業(yè)后，無法及時(shí)到達(dá)攪拌站Db為下一次作業(yè)服務(wù)。因此，需要將初始車輛流中的沖突剔除并重新構(gòu)建車輛流。沖突處理策略(算法3)如下。

輸入 所有罐車的初始車輛流[K1:(K11,···,K1j,

步驟1設(shè)定i=1,j=1,l=j+1。

步驟2計(jì)算作業(yè)Kil與 作業(yè)Ki j是否沖突，如果沖突則將其記錄在作業(yè)Ki j的沖突集合 C o(Ki j)中。

步驟3設(shè)l=l+1，重復(fù)執(zhí)行步驟2和步驟3直到到達(dá)車輛流Ki:(···)的最后一次作業(yè)，得到與作業(yè)Ki j沖 突的所有作業(yè)集合C o(Ki j)。

步驟4將j=j+1，重復(fù)執(zhí)行步驟2～4，得到與作業(yè)Ki(j+1)沖突的所有作業(yè)集合Co(Ki(j+1))，直到得到車輛流Ki:(···)中的每個(gè)作業(yè)的沖突集合。

步驟5將i=i+1，重復(fù)執(zhí)行步驟2～5，得到所有車輛流中的每個(gè)作業(yè)的沖突集合。

步驟6清洗沖突集合操作：針對每一次作業(yè)的沖突集合，如果該集合中包含同一個(gè)客戶的多次作業(yè)，表明該客戶的多次作業(yè)中最多只能完成一個(gè)。因此同一個(gè)沖突集合中，同一個(gè)客戶的作業(yè)只保留最早的作業(yè)。例如，一個(gè)沖突集合中包含客戶C1的多次作業(yè)則在該沖突集合中只保留并從所有車輛流中將客戶C1的第8次作業(yè)以后的作業(yè)全部剔除。

步驟7根據(jù)清洗后的沖突集合，每次只選擇每個(gè)沖突集合中的一個(gè)作業(yè)，組成車輛流，并計(jì)算目標(biāo)值。

輸出 返回所有可行車輛流及目標(biāo)值。

2.3交叉算子

個(gè)體交叉過程采用兩點(diǎn)交叉策略。當(dāng)交叉概率小于設(shè)定概率時(shí)(實(shí)驗(yàn)中交叉概率設(shè)定為0.3)，隨機(jī)選擇2個(gè)基因位置，并將2個(gè)個(gè)體交叉尋優(yōu)。在交叉算子執(zhí)行的過程中，個(gè)體第一部分的基因有可能會(huì)出現(xiàn)違反同一個(gè)客戶兩次連續(xù)的客戶作業(yè)要大于minC或小于 maxC約束的情況，這時(shí)需要將客戶作業(yè)前拉或后推使其滿足約束，即采用了約束保持法來處理模型中的約束。例如，交叉后對于客戶C1的2次作業(yè)出現(xiàn)了的情況，這時(shí)將推為并把不滿足最小約束的所有客戶C1的后續(xù)作業(yè)也做同樣的操作。若這則將前拉為并將后續(xù)不滿足m axC約束的所有該客戶作業(yè)同樣處理。

2.4變異算子

當(dāng)變異概率小于設(shè)定概率時(shí)(實(shí)驗(yàn)中變異概率設(shè)定為0.02)，隨機(jī)選擇1個(gè)基因位置，執(zhí)行變異操作。如果該基因位置為個(gè)體中的第1部分，則需要首先得到該基因的可變異值，該值由基因所代表的客戶作業(yè)C j+1決定，如果j=1時(shí)，該位置為某個(gè)客戶的第1次作業(yè)，則可變異值為時(shí)間窗內(nèi)的任意值；如果該位置表示的不是某客戶的第1次作業(yè)，則可變異值為時(shí)間窗的任意值。如果該基因位置為個(gè)體的第2、3、4部分，則可變異值與初始化時(shí)一致。

2.5選擇算子

采用輪盤賭的策略選擇下一代種群。然而遺傳算法求解組合優(yōu)化問題時(shí)常常陷入局部最優(yōu)，因此在執(zhí)行選擇操作時(shí)，為了增加群體的多樣性，使種群可以更好地覆蓋問題域空間，在每次選擇操作之前，會(huì)再次生成與本代種群規(guī)模相當(dāng)?shù)呐R時(shí)種群，(算法1中步驟5)。在選擇時(shí)，本代種群和臨時(shí)種群同時(shí)參與選擇操作，選出下一代種群。因?yàn)樵诿看芜x擇時(shí)都隨機(jī)生成臨時(shí)種群，所以執(zhí)行過程中，既可以保持最初種群的優(yōu)勢，又能隨機(jī)引入新的個(gè)體使得優(yōu)化過程盡快跳出局部最優(yōu)，達(dá)到全局最優(yōu)。

3結(jié)果及分析

采用上述算法對問題實(shí)例進(jìn)行優(yōu)化求解。所用測試數(shù)據(jù)為某混凝土企業(yè)的多次工作數(shù)據(jù)，本文給出實(shí)驗(yàn)中的2組測試數(shù)據(jù)，如表1所示。通過對比傳統(tǒng)調(diào)度方案的費(fèi)用值以及采用本文算法優(yōu)化后的費(fèi)用值可知，本文方法可以有效求解結(jié)合日檢問題的混凝土罐車調(diào)度問題。

表1實(shí)驗(yàn)中的2組測試數(shù)據(jù)Table 1 Two sets of test data in the experiment

3.1優(yōu)化結(jié)果與對比

表2給出2組實(shí)例的優(yōu)化結(jié)果，以及與傳統(tǒng)調(diào)度方案的對比結(jié)果。表3給出實(shí)例1采用本文算法得到的調(diào)度方案以及采用傳統(tǒng)調(diào)度方式得到的調(diào)度方案。與本文作者合作的混凝土企業(yè)采用傳統(tǒng)的人工調(diào)度的方式處理當(dāng)日的調(diào)度活動(dòng)，調(diào)度過程中采用的策略如下。1)首先將客戶根據(jù)需求時(shí)間、需求量、回款記錄等排序，得到客戶優(yōu)先級。2)根據(jù)客戶優(yōu)先級，連續(xù)為客戶安排車輛服務(wù)，無法滿足的客戶訂單則取消。3)當(dāng)車輛開始配送前或完成當(dāng)日的配送任務(wù)后，返回日檢點(diǎn)做1次日檢操作。表2給出傳統(tǒng)調(diào)度方式的調(diào)度結(jié)果與本文優(yōu)化后結(jié)果的對比數(shù)據(jù)，可以看出，優(yōu)化后的結(jié)果用同樣的車輛完成了更多的客戶作業(yè)、車輛在施工現(xiàn)場的等待時(shí)間更少、日檢操作可以插入2次作業(yè)之間完成，使得整個(gè)混凝土企業(yè)的時(shí)間耗費(fèi)最小，收益最大化。從表2的對比結(jié)果可以看到，采用本文算法在實(shí)例1中16輛罐車可以完成全部50次遞送作業(yè)，而采用傳統(tǒng)策略只能完成41次遞送作業(yè)，剩余的作業(yè)只能取消或外包給其他混凝土生產(chǎn)企業(yè)完成。在實(shí)例1中，采用本文算法，罐車在日檢點(diǎn)的等待總時(shí)長為14 min，即罐車到達(dá)日檢點(diǎn)基本上無需排隊(duì)就可以直接上線檢測。而采用傳統(tǒng)方式，罐車到達(dá)日檢點(diǎn)后還需排隊(duì)等待前面的車輛完成日檢后再上線檢測。實(shí)例2中，采用本文算法只需要20輛罐車就可以完成全部60次調(diào)度作業(yè)，而采用傳統(tǒng)方式，23輛罐車也只能完成50次調(diào)度作業(yè)。

表2優(yōu)化結(jié)果對比Table 2 Comparison of optimization results

表3實(shí)例1的2組調(diào)度方案Table 3 Two scheduling results of case 1

3.2參數(shù)分析

在實(shí)例1的環(huán)境下，調(diào)整混凝土企業(yè)的可使用車輛數(shù)從1輛到20輛，執(zhí)行本文算法得到最優(yōu)完成作業(yè)數(shù)、總費(fèi)用和最優(yōu)企業(yè)收益，如圖4～6所示。從圖4中可以看到，實(shí)例1需要16輛罐車完成全部50次作業(yè)。2輛罐車可以完成4次作業(yè)，但是當(dāng)罐車數(shù)量增加為3輛時(shí)，就可以完成12次作業(yè)，圖4中有5次(分為車輛數(shù)2—3，5—6，8—9，11—12，14—15)的躍變，每一次躍變都僅增加了1輛罐車，但是完成的遞送作業(yè)數(shù)大幅度增加。圖5和圖6給出了車輛數(shù)的變化帶來的總費(fèi)用變化以及企業(yè)收益的變化。從圖5可以看出，車輛數(shù)的增多必然帶來費(fèi)用的增加，然而車輛數(shù)的增加使得企業(yè)可以完成的客戶作業(yè)數(shù)增多，因此帶來的收益增加。當(dāng)車輛數(shù)為16時(shí)，收益達(dá)到最大，此時(shí)，車輛數(shù)如果繼續(xù)增加，收益會(huì)有所下降，因?yàn)橐獙δ切┪词褂玫能囕v做日常檢測。通過上述結(jié)果分析可以看到本文提出算法的有效性。這可以為混凝土企業(yè)制定外協(xié)車輛計(jì)劃，或購買車輛計(jì)劃做出有益指導(dǎo)。

圖4可用車輛數(shù)對完成作業(yè)數(shù)的影響Figure 4 The impact of the number of vehicles available on the finished jobs

圖5可用車輛數(shù)對費(fèi)用的影響Figure 5 The impact of the number of vehicles available on the cost

圖6可用車輛數(shù)對收益的影響Figure 6 The impact of the number of vehicles available on the revenue

4結(jié)論

混凝土罐車調(diào)度問題屬于一類復(fù)雜的組合優(yōu)化問題。問題本身的復(fù)雜性使得混凝土罐車調(diào)度問題模型可以作為很多類調(diào)度問題的通用基礎(chǔ)模型。比如，當(dāng)每個(gè)客戶只需求一次服務(wù)時(shí)，整個(gè)問題可以簡化為傳統(tǒng)的帶取貨問題的車輛調(diào)度問題，每次服務(wù)一個(gè)客戶并去下一個(gè)取貨點(diǎn)取貨；當(dāng)把每個(gè)客戶的作業(yè)設(shè)為一次，并且把一次可服務(wù)的多個(gè)客戶結(jié)點(diǎn)到攪拌站的返程時(shí)間設(shè)為0，可以將混凝土罐車調(diào)度問題模型簡化為外賣配送問題，因此罐車調(diào)度問題的研究在一定程度上具有通用性意義。本文在混凝土罐車調(diào)度問題中加入了罐車日常檢測因素，建立了更加符合實(shí)際調(diào)度需求的調(diào)度模型。研究中采用啟發(fā)式規(guī)則輔助的遺傳算法對問題求解，并通過實(shí)例驗(yàn)證了算法的有效性。在后續(xù)的研究中，擬將進(jìn)一步考慮罐車裝載量不同、攪拌站裝載不同類型混凝土的服務(wù)切換時(shí)間等因素，以期建立更加符合實(shí)際需求的罐車調(diào)度問題模型和優(yōu)化算法。