□ 曾 強,林 凱,王科峰

(1.河南理工大學(xué) 工商管理學(xué)院，河南 焦作 454000；2.河南理工大學(xué) 能源科學(xué)與工程學(xué)院,河南 焦作 454000)

1 引言

隨著客戶多樣化、個性化需求的不斷增強及制造企業(yè)向多品種、批量生產(chǎn)轉(zhuǎn)型，物流配送成為一種重要的物料送達(dá)方式。車輛調(diào)度在很大程度上決定了物流配送的速度、成本、能耗、效益、客戶滿意度等指標(biāo)[1]。車輛調(diào)度問題(Vehicle Scheduling Problem，VSP)的一般定義如下[2]：對一系列裝貨點和卸貨點，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(物料需求量、發(fā)送量、交貨時間、車輛容量限制、行駛里程限制)下，達(dá)到一定的目標(biāo)(路程最短、費用最少、時間盡量少、使用車輛盡量少等)。在實際工程實踐中，考慮到各種現(xiàn)實約束，車輛調(diào)度模型變得更為復(fù)雜，隨著研究的不斷深入，VSP演化出了不同的類型。按優(yōu)化目標(biāo)的數(shù)量可分為單目標(biāo)優(yōu)化問題[3]和多目標(biāo)優(yōu)化問題[4]；按車輛類型可分為單車型問題[5]和多車型問題[6]；根據(jù)物料的送達(dá)是否有時間限制可分為無時限問題[7]、帶硬時間窗問題[8]、帶軟時間窗問題[9]。VSP問題已被證實為NP-Hard難題[10-11]，在應(yīng)用和理論上都有較高的研究意義。

關(guān)于VSP的現(xiàn)有研究尚存在兩個方面的不足，使得理論與實踐脫節(jié)：一方面，構(gòu)建的數(shù)學(xué)模型對成本、路徑和時間的處理不夠精細(xì)化；另一方面，偏重于研究VSP求解算法，忽略了網(wǎng)絡(luò)化車輛調(diào)度系統(tǒng)的研究。

基于此，在現(xiàn)有車輛調(diào)度問題研究的基礎(chǔ)上，從數(shù)字化、智能化、網(wǎng)絡(luò)化在線調(diào)度入手，通過對成本、路徑和時間的精細(xì)化處理，設(shè)計開發(fā)了一種基于B/S架構(gòu)的物流配送車輛精細(xì)化多目標(biāo)調(diào)度系統(tǒng)，并將NSGA II((Non-dominated Sorting Genetic Algorithm with elite strategy,NSGA II)算法集成于系統(tǒng)中，通過案例分析驗證了物流配送車輛精細(xì)化調(diào)度系統(tǒng)的可行性和高效性。

2 問題描述

本文研究單一配送中心、多車型、各車型車數(shù)有限、多需求點、可混裝的多目標(biāo)VSP。在該問題中，考慮人工成本、調(diào)車費、油耗、高速過路費(考慮車輛自重)、卸貨時間等因素，以綜合成本最小和平均客戶滿意度最大為目標(biāo)的車輛精細(xì)化多目標(biāo)調(diào)度。假設(shè)：①每次配送車輛的出發(fā)點均為配送中心，配送任務(wù)完成后返回配送中心；②客戶時間窗、客戶服務(wù)時間、客戶需求量已知；③車輛配送的貨物總量不能超過每輛車的最大裝載量；④每個配送點有且只能被一輛車服務(wù)；⑤各需求點間的到達(dá)時間和普路里程、高速里程、當(dāng)前高速的收費標(biāo)準(zhǔn)已知；⑥車輛配送過程中車的載重量隨著卸貨操作變化而變化；⑦車輛配送中的高速收費情況按照當(dāng)前車輛的載重量且考慮自重動態(tài)變化；⑧駕駛員工資支出按照當(dāng)前駕駛車輛所完成調(diào)度的總時間來計算，不同路徑、不同車型駕駛員工資不同，要求：通過合理的在線調(diào)度，使得完成上述配送任務(wù)的綜合成本最低、平均客戶滿意度最大。

3 系統(tǒng)功能規(guī)劃

為保證系統(tǒng)的安全性，設(shè)計登錄界面，用戶信息經(jīng)MD5算法加密后存儲在遠(yuǎn)程數(shù)據(jù)庫SQL Sever中。用戶登錄后即可進(jìn)入系統(tǒng)主界面。系統(tǒng)主要包括用戶信息、參數(shù)設(shè)置和調(diào)度三個模塊。系統(tǒng)功能框架如圖1所示。

圖1 車輛調(diào)度系統(tǒng)功能框架

圖2 數(shù)據(jù)庫設(shè)計

4 數(shù)據(jù)庫設(shè)計

物流配送車輛在進(jìn)行精細(xì)化調(diào)度過程中會涉及到客戶信息、客戶需求信息、車型、調(diào)度員信息、路程時間表、過路費標(biāo)準(zhǔn)、調(diào)度任務(wù)等多種參數(shù)，因此，需要設(shè)計一個高效的數(shù)據(jù)管理系統(tǒng)。以SQL Sever作為數(shù)據(jù)庫管理系統(tǒng)，設(shè)計時遵循規(guī)范化設(shè)計原理，設(shè)計結(jié)果如圖2所示。

5 程序設(shè)計

以C#.NET為開發(fā)平臺，按照文獻(xiàn)[12]的流程設(shè)計了NSGA II算法，開發(fā)出基于B/S架構(gòu)的物流配送車輛精細(xì)化調(diào)度系統(tǒng)對上述VSP進(jìn)行求解。該系統(tǒng)主要由瀏覽器、Web服務(wù)器和數(shù)據(jù)庫組成，其中NSGA II算法被寫入.CS類中，由系統(tǒng)進(jìn)行調(diào)用。系統(tǒng)訪問流程如圖3所示。

圖3 系統(tǒng)訪問流程

系統(tǒng)調(diào)用NSGAⅡ算法對目標(biāo)值進(jìn)行計算步驟如下。

Step1 讀取參數(shù)，從SQL Sever中讀取車型、路程時間、過路費標(biāo)準(zhǔn)、客戶、需求信息等參數(shù)賦值給變量；

Step2 種群初始化，根據(jù)編碼隨機產(chǎn)生個體ch，判斷ch是否可行，若可行則將該個體加入種群Initpop，否則重新產(chǎn)生個體。通過該方法直到生成規(guī)模為Popsize初始種群Initpop；

Step3 解碼操作，根據(jù)編碼對種群Initpop中的個體ch的綜合成本、平均客戶滿意度、車輛總里程數(shù)、總調(diào)車費等數(shù)據(jù)進(jìn)行計算；

Step4 非支配排序及擁擠度計算，計算種群中個體的前沿值rank，將個體進(jìn)行分層；在此基礎(chǔ)上，分別對各級非支配個體集中的個體計算其擁擠度md；

Step5 遺傳操作包括交叉操作和變異操作，采用“基于客戶點順序”的交叉和變異方式來進(jìn)行交叉和變異,生成規(guī)模為Popsize的子種群Offpop；

Step 6 選擇操作，通過“聯(lián)賽機制”從父代種群Initpop選擇個體形成規(guī)模為Popsize/2的配對池pool。具體方法如下：設(shè)聯(lián)賽規(guī)模為tour，采用for循環(huán)每次從父代種群Initpop中隨機選出tour個個體，從tour個個體中根據(jù)個體前沿值rank和擁擠度md選擇最優(yōu)秀的個體加入配對池，直到for循環(huán)結(jié)束，返回Initpop。

6 案例分析

調(diào)度員首先通過系統(tǒng)對車型、路程時間、過路費標(biāo)準(zhǔn)、客戶、需求、調(diào)度任務(wù)等進(jìn)行設(shè)置(具體從略)。然后通過“調(diào)度計算”模塊調(diào)用NSGA II算法進(jìn)行調(diào)度計算得到Pareto解集。獨立運行多次，均能得到基本相同且均勻的Pareto解集，表明收斂效果較好。圖4是某次進(jìn)化計算得到的Pareto解集，調(diào)度員可以從中進(jìn)行選擇。圖5中所標(biāo)注的為某方案的詳細(xì)調(diào)度信息，其含義為：通過調(diào)度號為1001、方案5、綜合成本為14957元、平均客戶滿意度為0.59、車輛總里程數(shù)為2587.72公里、總調(diào)車費為2940元、總高速過路費為2856.15元、總油費為4601.29元、總車輛折舊費為1515.49元、總輪胎折舊費為515.4元；總需4輛貨車，車型分別為D、D、B、D型，每輛車載重分別為17噸、19噸、11噸、21噸；該調(diào)度解是前沿面Rank值為1的解，每輛車服務(wù)對象為D車型服務(wù)客戶號為3、10、7、4的客戶，D車型服務(wù)客戶號為9、12、5、8的客戶，B車型服務(wù)客戶號為11的客戶，D車型服務(wù)客戶號為1、13、6、2的客戶。

調(diào)度員針對當(dāng)前車輛調(diào)度的需求目標(biāo)可在優(yōu)化得到的Pareto解集中選取合適的調(diào)度方案進(jìn)行保存。在“調(diào)度集”界面可以查看所有保存的調(diào)度方案，各個調(diào)度方案以調(diào)度號來進(jìn)行區(qū)分。

圖4 Pareto 解集

圖5 調(diào)度方案

7 結(jié)束語

針對一類以總成本最低和客戶滿意度最大為優(yōu)化目標(biāo)的物流配送車輛多車型、多目標(biāo)調(diào)度問題，設(shè)計了一種基于B/S架構(gòu)的物流配送車輛精細(xì)化調(diào)度系統(tǒng)。通過對成本、路徑和時間進(jìn)行精細(xì)化在線處理，可計算出以綜合成本和平均客戶滿意度為目標(biāo)的車輛精細(xì)化調(diào)度方案，以更加系統(tǒng)、高效、便捷地解決物流配送車輛調(diào)度問題，從而更好地滿足企業(yè)、客戶和社會等多方面的利益。