道路限行的城市配送路徑優化方法設計

何玉蘭

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

1 配送優化模型的構建

1.1 問題描述

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

本文實現模型構建期間涉及的目標要素對應是：

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

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

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

1.2 變量與參數

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

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

1.3 模型構建

目標函數：

約束條件：

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

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

2.1 初始種群生成

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

Stepl：如果B=Q5規則符合，就結束執行。反之，就繼續執行操作；

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

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

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

2.2 適應度函數

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

2.3 選擇操作

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

2.4 變異操作

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

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

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

3 結語

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