帶硬時間窗的共同配送車輛調度問題研究

賓　厚，王　縉

（湖南工業大學 商學院，湖南 株洲 412007）

帶硬時間窗的共同配送車輛調度問題研究

賓厚，王縉

（湖南工業大學 商學院，湖南 株洲 412007）

針對帶硬時間窗的共同配送車輛調度問題，提出Sweep算法和PMX算子相結合的遺傳算法。以長株潭城市群生鮮食品共同配送中心區域內的配送數據作為實驗對象，采用組合遺傳算法進行分析，在客戶要求的時間范圍內，合理安排車輛的行駛路線，使共同配送總費用最低。最后，將本算法與啟發式算法、遺傳算法進行比較，分析結果表明，本算法得到的共同配送車輛調度方案更優。

硬時間窗；共同配送；車輛調度

0　引言

隨著國民經濟的迅速發展、人民生活水平的提高，消費者的需求日益多樣化、個性化。企業為滿足消費者的各種需求，物流配送的壓力越來越大。因此，如何整合社會資源以提高物流作業效率，成為了企業物流信息化建設的重要方向。

國內學者們從車輛調度問題、共同配送和需求分析3個方面對物流配送進行了研究。蹇潔等［1］構建了油耗費用和固定費用最小的車輛調度模型，并采用云自適應遺傳算法進行求解。任偉［2］為優化帶時間窗的車輛調度計算問題，引入量子進化算法，提出了一種混合量子免疫進化算法。邵麗麗［3］提出了利用蟻群算法優化遺傳算法來解決物流車輛調度問題。劉華旭［4］對共同配送模式下電動汽車配送調度的優化問題，提出用蟻群算法進行求解。陳磊等［5］用混合算法構建了物流配送總成本最小的目標函數，得到配送時刻不斷變化下的車輛調度方案。鄺海山［6］將客戶需求分析、共同配送與動態車輛調度問題相結合進行研究，提出采用共同配送模式來實現車輛調度方案的合理化。崔麗等［7］采用分配-節約啟發式算法，尋找需求驅動下的城市配送車輛動態調度問題的滿意解。Xu Zhoucong等［8］利用基于車輛實時數據的有序樣本聚類方法對特征周期進行劃分，采用最小的車輛數量和最低的總運營成本，建立車輛調度優化模型。

以上文獻運用云自適應遺傳算法、量子進化算法、蟻群算法等對共同配送的車輛調度問題進行研究，建立了相應模型，得出合理的優化方案。但是，學者們對帶硬時間窗的共同配送車輛調度優化問題的研究還較少。針對帶硬時間窗的共同配送車輛調度優化問題，本文提出Sweep算法和PMX算子相結合的遺傳算法（hybrid genetic algorithm， HGA），并以長株潭城市群生鮮食品共同配送中心區域內的配送數據作為實驗對象，驗證了該算法能得到更優的共同配送車輛調度方案。

1　數學描述

帶硬時間窗的共同配送車輛調度問題主要考慮的因素有服務及時性、物流成本等。本文先建立數學模型，再分析如何在車輛性能相同、服務時間不同的情況下，高效地完成配送任務。

1.1模型假設

假設：1）在現有備選點中，選取共同配送中心點，配送中心的固定成本記為常數；2）已知供應商的供貨能力，且能針對客戶的需求實現一對多的服務；3）不計配送中心的處理時間，采用最低成本運輸方式來降低服務總成本。令ld為共同配送中心d的運量；F為供應商數；G為運輸車輛數；lfg為車輛從供應商到共同配送中心的運量；Ld為所有供應商總的運量（見式（1））；xd為備選點是否選為配送中心點（見式（2）） ；ycg為配送的時間是否有延誤（見式（3））。

1.2模型表達

根據上述假設，模型的目標函數為總費用最小，

由式（4）可知，目標函數Fmin包含4個部分。

1）第一部分是配送中心到客戶目的地所產生的物流費用。其中，D為共同配送中心數；C為客戶數；為車輛從共同配送中心到客戶的運輸單價；為車輛從共同配送中心到客戶的運輸量。

2）第二部分是供應商到共同配送中心的運輸費用。其中，Kfdg為車輛從供應商到共同配送中心的運輸單價；Vfdg為車輛從供應商到共同配送中心的運輸量。

3）第三部分是共同配送中心到客戶的變動費用。其中，Sd為共同配送中心的貨物流轉單價；Vcdg為從客戶返回共同配送中心的運輸量；考慮到配送過程中會有意外損毀的情況，本文加入調節指數，且該指數滿足條件0＜≤1。

4）第四部分是車輛在時間窗范圍內由配送服務產生的懲罰費用。由式（3）得，在客戶“不允許延誤”即ycg=1時，車輛沒有在時間窗范圍內完成客戶的配送服務將產生懲罰值；當ycg=0時，就沒有懲罰費用，即不存在延誤情況。其中，Tcg為客戶要求的車輛運輸時間；cg為客戶對車輛延時的懲罰（補償）函數，即為車輛在時間窗范圍外到達客戶的懲罰值；cg為車輛在客戶允許服務時間段之前到達而產生的懲罰函數，即為車輛在配送中心或客戶時閑置或等待裝卸而產生損失的機會成本；為車輛從共同配送中心到客戶的運輸用時；tfdg為車輛從供應商到共同配送中心的運輸用時；“+”表示括號內結果為正時才有意義。

為了方便求解模型，需要對共同配送中心、供應商和客戶的基本條件進行限定。

1） 每個共同配送中心的進出產品數量相同，

2）供應商的供應能力約束，即

式中Wfg為供應商供應車輛的能力。

3）時間約束，即

4）至少有一個共同配送中心被選中，

5）滿足客戶對產品數量需求的約束，

式中Q為共同配送中心的處理能力。

2　遺傳算法設計

利用單一的遺傳算法（genetic algorithm， GA）求解物流車輛調度問題，往往得不到最優解［9］。為彌補其不足，本文加入Sweep算法，構成組合遺傳算法。該算法的具體步驟如下。

1）生成編碼和初始種群。首先用整數序號表示客戶點，問題的解集（即車輛路徑的集合）用長度為N（N為有待接受服務的客戶點數目）的整數數組進行編碼，數組中相應的元素的順序表示服務客戶的順序。在初始生成的隨機編碼中，取適當編碼對應的路徑組成初始群組，并令進化初值t=0，最大為T。

2）構造適應度函數。遺傳算法的搜索過程只是以適應度函數為依據，運用種群的每個個體的適應度進行搜索。適應度函數用來判斷個體的優劣，且成正相關性變動，即個體的適應度大，其性能優。適應度函數為

3）選擇運算。選擇運算是從種群中對個體進行優勝劣汰，根據適應度來確定再生個體。適應度比值法操作簡單，容易實現，是最簡單適用的選擇方法。適應度比例函數為

4）交叉運算。采用PMX確定交叉算子，即先對父代進行常規的兩點交叉，再根據交叉區域內各基因值之間的映射關系來修改交叉區域之外的各個基因組的基因值。挑選個體用于繁殖下一代時，互換選中的兩個不同個體上的相同位置的基因，進而繁殖出新一代個體。

5）變異運算。本文采用實數編碼的非一致性變異算子。令gr=（a1， a2，…， am， …）是第r代種群中的個體，選擇浮點數am進行變異，則其變異結果為g′r=（a1， a2，…，， …），

6）當t大于最大進化代數時，終止遺傳算法。

3　實驗分析及算法比較

本文通過一個實例分析比較組合遺傳算法、遺傳算法、啟發式算法，驗證本算法的可行性和有效性。

3.1實驗數據

本實驗數據來源于長株潭城市群的生鮮食品配送中心及其供應商。該共同配送中心在不同時間段，為長株潭區域內106位客戶提供服務，使用的運輸車輛統一為載重20 t的車輛，車輛在各個客戶處的服務時間均為調研統計所得，實驗數據如表1所示。

表 1　實驗數據表Table 1　Experimental data table

3.2算法比較

本文通過Matlab軟件，將組合遺傳算法、遺傳算法、啟發式算法3種算法分別對上述數據進行求解，并比較哪種算法得出的結果更優。

3.2.1組合遺傳算法

組合遺傳算法采用的數據容量是100，交叉率是0.77，變異率是0.06，迭代次數是310，穩態復制個體為4%，交叉算子用PMX。該算法的計算結果見表2。

表2　組合遺傳算法計算結果Table 2　Combined genetic algorithm with its calculation results

由表2可知，由組合遺傳算法得出平均路程為507.6 km，總平均成本為2 075.2元。9次平均迭代次數為234.1，效率較高。其中，9次運行中第6次的總成本最少，總成本為1 696元。根據第6次結果，由配送中心對106位客戶進行帶時間窗的定位，其運輸路徑安排如表 3所示，車輛數目為11，行駛路程為1 506.38 km，等待時間為644 min。表3中，每一行代表一輛車的行駛時間，如第一行是第一輛車到達每個客戶（客戶編號用1， 2，…，12表示）花費的時間，第一行第一列表示1號車從出發點到第一個客戶花費的時間，第一行第二列表示1號車從第一個客戶到第二個客戶所花時間，以此類推。

表 3　路徑安排表Table 3　Vehicle scheduling arrangement table

3.2.2遺傳算法

遺傳算法采用的數據容量100，迭代次數是310，交叉算子是0.8，變異算子是0.3。求解結果見表4。由表可知，第7次總成本最少，總成本為2 048元。

表 4　遺傳運算Table 4　Calculations of the genetic algorithm

3.2.3啟發式算法

表 5　啟發式運算結果Table 5　Calculation results of the heuristic algorithm

3.2.4算法比較分析

將上述3種算法得出的結果進行比較，如表6所示。組合遺傳算法（HGA）相比單獨用遺傳算法（GA）和啟發式算法（HA），其結果的各項指標都占有優勢。

表 6　算法比較Table 6　A comparison between algorithms

4　結語

為了滿足客戶個性化和多樣化的需求，針對帶硬時間窗的共同配送車輛調度優化問題，本文設計了基于Sweep算法和PMX算子的組合遺傳算法。通過選擇編碼、設計適應度函數、選取交叉算子，完成組合遺傳算法設計。最后將3種算法進行比較分析，結果表明：組合遺傳算法相比啟發式算法和遺傳算法性能更穩定，能得到更優的共同配送車輛調度方案。

［1］蹇潔，王旭，葛顯龍. 云自適應遺傳算法有能力約束的車輛調度優化［J］. 重慶大學學報，2013，36（8） ：40-46. JIAN Jie，WANG Xu，GE Xianlong. Research on Capacitated Vehicle Routing Problem with Cloud Adaptive Genetic Algorithm［J］. Journal of Chongqing University，2013，36（8） ：40-46.

［2］任偉. 基于量子免疫算法的車輛調度問題優化［J］. 計算機科學，2013，40（5） ：233-236，270. REN Wei. Optimization Algorithm for Vehicle Scheduling Problem Based on Quantum Immune［J］. Computer Science，2013，40（5） ：233-236，270.

［3］邵麗麗. 蟻群優化自適應遺傳算法物流車輛調度實現［J］.計算機測量與控制，2012，20（5） ：1423-1425，1441. SHAO Lili. Ant Colony Optimization Adaptive Gene Algorism Resolving Logistics Vehicle Schedule［J］. Computer Measurement and Control，2012，20（5） ：1423-1425，1441.

［4］劉華旭. 基于電動汽車技術特征的共同配送調度優化研究［D］. 北京：北京交通大學，2012. LIU Huaxu. Research on Scheduling Optimization of Common Based on Electric Vehicle Technical Feature［J］. Beijing：Beijing Jiaotong University，2012.

［5］陳 磊，霍永亮，霍波陶. 基于混合遺傳算法的物流車輛調度優化［J］. 重慶師范大學學報（自然科學版），2015，32（2） ：7-12. CHEN Lei，HUO Yongliang，Huo Botao. Vehicle Schedule Optimization of Logistics Based on Combinational Genetic Algorithm［J］. Journal of Chongqing Normal University（Natural Science），2015，32（2） ：7-12.

［6］鄺海山. 網購環境下城市共同配送動態車輛調度優化研究［D］. 重慶：重慶大學，2014. KUANG Haishan. Research on Dynamic Vehicle Scheduling Optimization for Urban Joint Distribution Under Online Shopping Background［J］. Chongqing：Chongqing University，2014.

［7］崔麗，王笑叢. 需求驅動下的城市配送車輛動態調度研究［J］. 計算機工程與應用，2015，51（2） ：241-244. CUI Li，WANG Xiaocong. Demand-Driven Dynamic Configuration of Vehicle on City Distribution［J］. Computer Engineering and Applications，2015，51（2） ：241-244.

［8］XU Zhoucong，HE Peijia，TENG Jing，et al. Transit Vehicles Intelligent Scheduling Optimization Based on the Division of Characteristic Periods［J］. Procedia-Social and Behavioral Sciences，2013，96 ：1502-1512.

［9］歐衛華，唐東黎，聞斌. 基于遺傳算法優化的模糊神經網絡車型識別［J］. 湖南工業大學學報，2010，24（2） ：39-42. OU Weihua，TANG Dongli，WEN Bin. Based on the Genetic Algorithm to Optimize the Fuzzy Neural Network Model Recognition［J］. Journal of Hunan University of Technology，2010，24（2） ：39-42.

（責任編輯：鄧彬）

On the Joint Distribution Vehicle Scheduling with Hard Time Windows

BIN Hou，WANG Jin
（Business School，Hunan University of Technology，Zhuzhou Hunan 412007，China）

A genetic algorithm， with the sweep algorithm combined with PMX operators， has been introduced to solve the problem of the joint distribution vehicle scheduling with hard time windows. With the distribution data of fresh produce joint distribution center in the Greater Changsha Metropolitan Region a test subject， the genetic algorithm has been introduced to make an analysis of a proper vehicle routing arranged for the clients， with a minimum total distribution cost， according to their deadline requirements. The result of a comparison made between this algorithm， the heuristic algorithm and the genetic algorithm shows that this algorithm provides a better solution to the joint distribution vehicle scheduling.

hard time window ；joint distribution ；vehicle scheduling

U492.2+2

A

1673-9833（2016）03-0086-05

10.3969/j.issn.1673-9833.2016.03.016

2015-12-25

湖南省哲學社會科學基金資助項目（14YBA133）

賓厚（1974-），男，湖南株洲人，湖南工業大學副教授，博士，主要研究方向為城市共同配送，E-mail：1173260751@qq.com

王縉（1991-），男，湖南益陽人，湖南工業大學碩士生，主要研究方向為城市共同配送，E-mail：871661468@qq.com