基于B/S架構(gòu)的物流配送車輛精細(xì)化調(diào)度*

□ 曾 強(qiáng),林 凱,王科峰

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

1 引言

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

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

基于此，在現(xiàn)有車輛調(diào)度問題研究的基礎(chǔ)上，從數(shù)字化、智能化、網(wǎng)絡(luò)化在線調(diào)度入手，通過對(duì)成本、路徑和時(shí)間的精細(xì)化處理，設(shè)計(jì)開發(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)中，通過案例分析驗(yàn)證了物流配送車輛精細(xì)化調(diào)度系統(tǒng)的可行性和高效性。

2 問題描述

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

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

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

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

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

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

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

5 程序設(shè)計(jì)

以C#.NET為開發(fā)平臺(tái)，按照文獻(xiàn)[12]的流程設(shè)計(jì)了NSGA II算法，開發(fā)出基于B/S架構(gòu)的物流配送車輛精細(xì)化調(diào)度系統(tǒng)對(duì)上述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Ⅱ算法對(duì)目標(biāo)值進(jìn)行計(jì)算步驟如下。

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

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

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

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

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

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

6 案例分析

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

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

圖4 Pareto 解集

圖5 調(diào)度方案

7 結(jié)束語

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