道路限行的城市配送路徑優(yōu)化方法設計

何玉蘭

（重慶交通大學交通運輸學院，重慶 400041）

1 配送優(yōu)化模型的構(gòu)建

1.1 問題描述

有關(guān)城市貨車交通管制相關(guān)的配送優(yōu)化研究能夠看成是對存在時間窗約束影響下的車輛調(diào)度研究的深層次擴展：由單個配送中心，選擇多輛貨車對若干個需求點完成必要的送貨服務支持，并且在各個需求點時間窗、需求量與位置約束以及車輛載重以及通行時段與路段的情況下，更加科學合理地確定行車路徑，由此獲得配送最優(yōu)的效果。

本文實現(xiàn)模型構(gòu)建期間涉及的目標要素對應是：

（1）車輛數(shù)最少：為能夠更好地與客戶需求相符，各個企業(yè)都需要配備充足的車輛來保障送貨任務順利實施；（2）行駛距離最短：車輛的行駛距離與企業(yè)需要投入的配送成本有很明顯的正相關(guān)聯(lián)系，而且道路通行以及油耗等都與行駛距離密切相關(guān)，故而將行駛距離確定為最短的目標能夠更大程度上達成配送成本最少的功能目標；（3）碳排放最低：政府推出通行管制的目標就是降低車輛通行，減少污染影響。

為能夠順利達成如上目標，在實現(xiàn)配送優(yōu)化分析期間還需要重視下述條件約束：

（1）各個配送線上需求點的總體貨物需求與車輛的最高載重量相符；（2）各個需求點相關(guān)的需求量都能夠獲得有效滿足，并且僅僅是單輛車對其實施單次服務支持；（3）配送車輛經(jīng)配送中心發(fā)出，配送完成后回歸配送中心；（4）不得在進行路段內(nèi)行車；（5）管制時段內(nèi)車輛維持等待情況。

1.2 變量與參數(shù)

針對配送相關(guān)的有向連通圖G=（N，M）而言，其呈現(xiàn)出下述特征情況：mij表征需求點i與j兩者間的弧，全部弧選擇M加以表征；頂點0表征的是配送中心位置，頂點1，2，……，n表征的是需求點位置，包含頂點0的時候全部頂點的集合表征是N，即可得N=｛0，1，2，……，n｝；不包含頂點0的時候，全部頂點的集合表征是C，即可得到C=｛1，2，……，n｝；mij表現(xiàn)的是時間值tij以及其距離值dij，前者表征的是兩個需求點i與j需要的運輸時間情況；需求點i位置需要的服務時間表征是si，而且需求量對應表征是qi；V=｛1，2，……，k，……，K｝表征的是全部車輛合集，其中Qk表征的是車輛k能夠達成的最大載重量；E表征的是禁行路段所在的合集，能夠滿足M∩E=E；其中，[Rb1，Re1]表征的是早高峰期間的管制時段，[Rb2，Re2]表征的是晚高峰間的管制時段，R表征的是管制時段內(nèi)全部限行路段合集，存在R∩E=Φ，M∩R=R的條件約束。此外，選擇α表征單位運輸期間的距離變動成本情況，β表征的是單位車輛開啟需要的固定成本 情況。此處，dij，tij，qi，si，Qk，Rb，Re，α以及β對應都是非負數(shù)的存在。

在此模型內(nèi)存在決策變量xijk，針對存在的弧mij以及車輛k而言，xijk=1，此時車輛k由其需求點i來到j；反之，xijk=0。

1.3 模型構(gòu)建

目標函數(shù)：

約束條件：

式（1）表征的是配送總成本最低，其涉及碳排放、車輛行駛距離、車輛延誤懲罰以及車輛啟用四部分的成本內(nèi)容；式（2）表征的是各個需求點僅能夠被單輛車加以服務；式（3）與式（4）約束各輛車在出發(fā)后，實現(xiàn)相關(guān)的配送要求后再行返回配送中心；式（5）是避免所得規(guī)劃內(nèi)出現(xiàn)子回路的情況；式（6）表征的是不得在禁行路段內(nèi)行車；式（7）表征的是不得在禁行時段內(nèi)行車；式（8）表征的是各路徑上需求量綜合能夠與車輛最大載重相符的要求；式（9）表征的是決策變量呈現(xiàn)出來的整數(shù)化約束影響；式（10）表征與到達時間相關(guān)的非負性約束影響。

2 基于道路限行的混合遺傳算法設計

2.1 初始種群生成

為保障初始解能夠在其可行域內(nèi)呈現(xiàn)出隨機分布狀態(tài)，需要設計獲得與此種群生成相關(guān)的啟發(fā)式規(guī)則。假定N表征的是種群規(guī)模情況，Ak表征的是第k條配送鏈情況，Akw表征的是與該鏈相聯(lián)系的第w個客戶，假定客戶集合B=C并且Mw表征從第w個客戶（配送中心）開始后能夠達到集合B相關(guān)的客戶情況，假定此處的變量k=1，如此就能夠?qū)⒁?guī)則表征是：

Stepl：如果B=Q5規(guī)則符合，就結(jié)束執(zhí)行。反之，就繼續(xù)執(zhí)行操作；

Step2：于Mo內(nèi)按照1/|Mo|概率的方式隨機選定客戶i，將其于B內(nèi)移開，確定w=1，Akw=i。

①于Mo內(nèi)按照1/|Mo|概率的方式隨機選定客戶i，將其于B內(nèi)移開，確定w=w+1，Akw=i；繼續(xù)②；

此處Ak對應著的是配送路徑情況，k對應著的是被調(diào)度車輛情況。

2.2 適應度函數(shù)

當個體所得到的適應度值更高的情況下，則算法具備更好的性能。鑒于管制影響下的配送優(yōu)化本質(zhì)上是最小化問題，即獲得最小的配送成本，目標函數(shù)值對應著的就是效用值求和，優(yōu)劣解相差的數(shù)值并不高。為確保目標函數(shù)能夠更好地轉(zhuǎn)換適應度的情況，此處選定目標函數(shù)值對應著的倒數(shù)充當其適應度函數(shù)，明確f=1/z。

2.3 選擇操作

本文用到的選擇策略是最佳個體保留以及輪盤賭，全部個體參照其適應度情況由大到小加以排列，并且適應值最大的個體復制為下一代，由此確保最優(yōu)個體能夠在遺傳期間繼承下去，其余的個體則參照輪盤賭的情況加以選擇，得到其適應度和值，單一個體相關(guān)的概率情況對應是，獲得其累計概率由此獲得隨機數(shù)rand，如果出現(xiàn)pi-1＜rand≤pi就需要將個體i選出到下一代，反之，就繼續(xù)操作一直到與規(guī)模N要求相符。

2.4 變異操作

參照確定的變異概率Pm，選擇需要的個體G，即：

Stepl：于其染色體內(nèi)得到客戶i與j，互換位置得到最新的G’，如果G`對應是不可行解，就需要放棄，繼續(xù)Stepl。反之，繼續(xù)Step2；

Step2：對比G與G'兩者的適應度函數(shù)值情況，如果出現(xiàn)f（G）＞ f（G’），繼續(xù)Step。反之，就接受G’，變異分析完成。

3 結(jié)語

本文針對貨運交通管制影響下的城市配送優(yōu)化情況展開分析，明確帶時間窗作用的車輛調(diào)度能夠歸屬到NP-hard的問題。由于專業(yè)經(jīng)驗積累以及時間等限制，本研究還存在諸多不足，后續(xù)將從以下方向深化：（1）考慮由多個配送中心實現(xiàn)聯(lián)合配送安排；（2）實際工作期間，客戶對貨物需要多變，配送企業(yè)也需要安排更多車型配送，考慮多車型情況的配送方案使整個調(diào)度優(yōu)化分析更貼合現(xiàn)實。