湯雅連，蔡延光，趙學才

（廣東工業(yè)大學 自動化學院，廣東 廣州 510006）

多車場多車型關聯(lián)物流運輸調(diào)度（RVRP）在現(xiàn)實生活中有很強的應用背景。針對多車場VRP問題，不少學者[1-4]已經(jīng)做了很多研究，并取得了很好的成果，但是對于RVRP的探討甚少。一般是若干個客戶有一定的貨物需求且貨物之間有某種關聯(lián)性，有多個車場為所有客戶提供服務，車輛將貨物送到各個客戶地點，然后返回車場。由于車輛在行駛過程中，會受到路況[5]等因素的影響，所以本文主要考慮在路況約束下，對車輛和配送路線進行合理安排，滿足所有客戶要求的前提下，使配送成本最低。

1 問題描述及數(shù)學模型的建立

1.1 問題描述

道路容量約束的多車場、多車型關聯(lián)物流運輸調(diào)度問題簡單描述為，假設給定車場信息以及客戶信息（位置和貨物需求量等），貨物之間的關聯(lián)系數(shù)，不同類型車輛信息（載重約束、里程約束和容量約束等），要求合理安排車輛和運輸路線，在滿足所有客戶需求的前提下，使配送成本最低。

1.2 數(shù)學模型

有 l個客戶（1，2，…，l），第 i個客戶的需求量為 gi（i=1，2，…，l），需要從車場將貨物運給客戶，可派出載重為qh的貨車，已知gi＜qh?？蛻粢笏拓浀臅r間窗為[eti，lti]，每小時等待費用和延遲費用分別為 s1和 s2，早到或者晚到都會受到懲罰。Ti表示車輛到達i的時間。以表示車場 n中h類型的車輛k從i到j的運輸成本（距離、費用、時間等），=。每種類型的車為Knh，客戶 i，j之間的距離為 dij。rij表示 i貨物與 j貨物的關聯(lián)系數(shù)。目標為考慮路況約束、載重約束、關聯(lián)約束、多車場、多車型、軟時間窗等情況下，使各車場的車輛能滿足所有用戶的需求，并使總運輸成本最小。

假設客戶編號為 1，2，…，l，車場編號為 l+1，l+2，…，l+N。定義變量如下：

目標函數(shù)式（3）表示成本最低，以 cnijh表示n車場h類型的車輛從i點到j點的費用，rij表示貨物之間關聯(lián)度越高，兼容性越好，懲罰費用越低。式（4）、式（5）表示每個客戶只能由一輛車服務；式（6）表示車場派出的車輛數(shù)不能超過該車場的車輛總數(shù)；式（7）表示 n車場 h類型車輛的里程約束；式（8）表示車輛必須回到原車場；式（9）表示不能從車場直接到車場；式（10）表示不能超過車輛載重限制；式（11）tij表示i到 j的行駛時間，wij為路段i與 j的路況系數(shù)，wij越大，說明路況越好，車輛行駛速度越快，時間越短；式（12）cs為單位配送費用。

2 算法設計

2.1 編碼及初始種群的產(chǎn)生

本文采用參考文獻[6]提出的編碼方式及產(chǎn)生初始種群的方式。

2.2 適應度值計算與選擇操作

fi=Z/Zi，即當前群體中最佳染色體的目標函數(shù)值z與當前染色體的目標函數(shù)值Zi的比值作為適應度值。根據(jù)輪盤賭策略，按適應度值的大小分配復制概率。

2.3 交叉

本節(jié)設計了與進化代數(shù)相關而與個體適應度無關的交叉概率計算公式（13）。t為當前進化代數(shù)，Tgen為預設的最大進化代數(shù)，pcmax為預設最大概率，pcmin為預設最小概率，pc（t）為當前種群的交叉概率。本文采取均勻交叉的方式。

2.4 變異

本文采用混沌變異策略，混沌變異形式如式（14）所示。 K（0，1）為（-2，2）按混沌規(guī)律變化的序列。

在進化初期采用逐漸縮小的變異尺度，利用參考文獻[3]提出的變異策略，如式（16）所示。k為當前代數(shù)，Gen為最大迭代次數(shù)，δ為當前群體中某個體的某分量的變異尺度，α、β、γ為控制尺度收縮參數(shù)。

2.5 終止條件

當算法運行達到最大迭代次數(shù)或者多次產(chǎn)生同樣的最優(yōu)解，算法終止。

3 仿真分析

根據(jù) Logistic映射[3]，如式（15）所示。 式中，u表示種群序號，u=0，1，…，n；β 表示混沌變量，0≤β≤1；μ 表示吸引子，當 μ 取 0～4時，Logistic映射為[0，1]間的不可逆映射，μ=4時，完全處于混沌的狀態(tài)，此時產(chǎn)生的混沌變量 β（u）具有很好的遍歷性。 β（u）經(jīng)過放大和平移可得 K（0，1）。

表1 車場位置信息

表2 客戶信息

某供應處有3個車場，每個車場有不同類型的車輛，車場信息表見表1，客戶信息表見表2。每輛車的正常行駛速度為60 km/h，最大配送里程為200 km。單位配送費用為 1元/t×km，等待費用為 10元/h，延遲費用為 100元/h。最早發(fā)車時間為 7：00。

本文中的實驗是在 Intel（R）CoreTMi3 CPU2.53 GHz、內(nèi)存2.0 GB的PC機上采用Microsoft Visual C++6.0編程實現(xiàn)。遺傳算法中參數(shù)設置：種群規(guī)模為100，最大迭 代 次 數(shù) Gen=100，pcmax=0.1，pcmin=0.005， 變 異 概 率0.05，尺度收縮參數(shù)為 α=1，β=10，γ=0.5，δ=0.5。運行程序20次，得到該算法求解本算例的最優(yōu)結果見表3，配送示意圖如圖1所示。

表3 各配送車輛的配送數(shù)據(jù)

圖1 配送路徑示意圖

本文考慮了收斂精度與進化代數(shù)的關系，混沌變異結合了“尺度收縮”思想，并采用了避免近親繁殖的策略，達到了提高算法性能的效果。實驗證明，改進的自適應混沌遺傳算法求解此類問題是有效的。

[1]李臻，雷定猷.多車場車輛優(yōu)化調(diào)度模型及算法[J].交通運輸工程學報，2004，4（1）：83-86.

[2]李敏，郭強，劉紅麗.多車場多配送中心的物流配送問題研究[J].計算機工程與應用，2007，43（8）：202-204.

[3]鐘石泉，王雪蓮.多車場集送一體化車輛調(diào)度問題及其遺傳算法研究 [J].西安電子科技大學學報，2009，19（1）：63-68.

[4]YADLAPALLI S， BAE J， RATHINAM S，et al.Appriximation algorithms for a heterogeneous multiple depot hamiltonian path problem[C].2011 American Control Conference.2011.

[5]鐘石泉，賀國光.單車場復雜情況下的車輛調(diào)度[J].系統(tǒng)工程，2005（5）：29-31.

[6]楊元峰.多車場多車型車輛路徑問題的改進遺傳算法 [J].計算機與現(xiàn)代化，2008（9）：10-12.