帶硬時間窗的共同配送車輛調(diào)度問題研究

賓　厚，王　縉

（湖南工業(yè)大學(xué) 商學(xué)院，湖南 株洲 412007）

帶硬時間窗的共同配送車輛調(diào)度問題研究

賓厚，王縉

（湖南工業(yè)大學(xué) 商學(xué)院，湖南 株洲 412007）

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

硬時間窗；共同配送；車輛調(diào)度

0　引言

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

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

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

1　數(shù)學(xué)描述

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

1.1模型假設(shè)

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

1.2模型表達

根據(jù)上述假設(shè)，模型的目標函數(shù)為總費用最小，

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

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

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

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

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

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

1） 每個共同配送中心的進出產(chǎn)品數(shù)量相同，

2）供應(yīng)商的供應(yīng)能力約束，即

式中Wfg為供應(yīng)商供應(yīng)車輛的能力。

3）時間約束，即

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

5）滿足客戶對產(chǎn)品數(shù)量需求的約束，

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

2　遺傳算法設(shè)計

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

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

2）構(gòu)造適應(yīng)度函數(shù)。遺傳算法的搜索過程只是以適應(yīng)度函數(shù)為依據(jù)，運用種群的每個個體的適應(yīng)度進行搜索。適應(yīng)度函數(shù)用來判斷個體的優(yōu)劣，且成正相關(guān)性變動，即個體的適應(yīng)度大，其性能優(yōu)。適應(yīng)度函數(shù)為

3）選擇運算。選擇運算是從種群中對個體進行優(yōu)勝劣汰，根據(jù)適應(yīng)度來確定再生個體。適應(yīng)度比值法操作簡單，容易實現(xiàn)，是最簡單適用的選擇方法。適應(yīng)度比例函數(shù)為

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

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

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

3　實驗分析及算法比較

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

3.1實驗數(shù)據(jù)

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

表 1　實驗數(shù)據(jù)表Table 1　Experimental data table

3.2算法比較

本文通過Matlab軟件，將組合遺傳算法、遺傳算法、啟發(fā)式算法3種算法分別對上述數(shù)據(jù)進行求解，并比較哪種算法得出的結(jié)果更優(yōu)。

3.2.1組合遺傳算法

組合遺傳算法采用的數(shù)據(jù)容量是100，交叉率是0.77，變異率是0.06，迭代次數(shù)是310，穩(wěn)態(tài)復(fù)制個體為4%，交叉算子用PMX。該算法的計算結(jié)果見表2。

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

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

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

3.2.2遺傳算法

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

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

3.2.3啟發(fā)式算法

表 5　啟發(fā)式運算結(jié)果Table 5　Calculation results of the heuristic algorithm

3.2.4算法比較分析

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

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

4　結(jié)語

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

［1］蹇潔，王旭，葛顯龍. 云自適應(yīng)遺傳算法有能力約束的車輛調(diào)度優(yōu)化［J］. 重慶大學(xué)學(xué)報，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］任偉. 基于量子免疫算法的車輛調(diào)度問題優(yōu)化［J］. 計算機科學(xué)，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］邵麗麗. 蟻群優(yōu)化自適應(yīng)遺傳算法物流車輛調(diào)度實現(xiàn)［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］劉華旭. 基于電動汽車技術(shù)特征的共同配送調(diào)度優(yōu)化研究［D］. 北京：北京交通大學(xué)，2012. LIU Huaxu. Research on Scheduling Optimization of Common Based on Electric Vehicle Technical Feature［J］. Beijing：Beijing Jiaotong University，2012.

［5］陳 磊，霍永亮，霍波陶. 基于混合遺傳算法的物流車輛調(diào)度優(yōu)化［J］. 重慶師范大學(xué)學(xué)報（自然科學(xué)版），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］鄺海山. 網(wǎng)購環(huán)境下城市共同配送動態(tài)車輛調(diào)度優(yōu)化研究［D］. 重慶：重慶大學(xué)，2014. KUANG Haishan. Research on Dynamic Vehicle Scheduling Optimization for Urban Joint Distribution Under Online Shopping Background［J］. Chongqing：Chongqing University，2014.

［7］崔麗，王笑叢. 需求驅(qū)動下的城市配送車輛動態(tài)調(diào)度研究［J］. 計算機工程與應(yīng)用，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］歐衛(wèi)華，唐東黎，聞斌. 基于遺傳算法優(yōu)化的模糊神經(jīng)網(wǎng)絡(luò)車型識別［J］. 湖南工業(yè)大學(xué)學(xué)報，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

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

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

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