考慮需求拆分的多時間窗集送貨車輛調度優化研究

蔣祿歡

考慮需求拆分的多時間窗集送貨車輛調度優化研究

蔣祿歡

（重慶交通大學 經濟與管理學院，重慶 400074）

車輛調度是連鎖超市物流配送的重要環節，目前只考慮時間或距離的單一約束條件下的車輛調度已經不能滿足市場需求，因此以JLF連鎖超市為研究對象，考慮了需求拆分、多時間窗和集送貨三者同時約束下的車輛調度模型，運用動態規劃順序法進行求解，研究表明考慮需求拆分的車輛調度問題更具現實意義。

車輛調度；需求拆分；多時間窗；動態規劃

1 引言

隨著現代經濟的高速發展，人民生活水平提高，連鎖超市在零售業行業得到了廣泛的關注。連鎖超市進行貨物配送時，大多數門店存在集貨和送貨需求，在各個門店規定的時間內，將貨物從配送中心配送到各個分店，這一過程涉及到運輸成本、懲罰成本和貨損成本等，研究如何進行配送車輛的分配和配送路線的規劃，可以達到降低成本、提高規模效益的目的，這樣就產生了連鎖超市車輛調度優化問題。

傳統的車輛調度問題由DANTZING和RAMSER[1]在1959年首次提出。目前，中國對于一般的車輛調度問題研究已經較深入。張江華等[2]建立了集送貨車輛調度問題的多目標規劃模型。針對需求可拆分車輛調度問題，劉旺盛等[3]設計了求解該問題的聚類算法，熊浩等[4]構建了一種基于雙層規劃模型的三階段禁忌搜索算法。王科峰等[5]提出了帶時間窗約束的需求可拆分的集送貨車輛調度問題，構建了該問題的數學模型。在上述研究中，大多數是單一約束條件下的車輛調度問題，并且對于具體的連鎖超市車輛調度問題，大部分文獻也只局限于考慮時間或距離最優化，沒有充分考慮連鎖超市復雜的配送要求。

和上述文獻不同，本文從連鎖超市統一配送特點出發，將研究對象確定為考慮需求拆分的多時間窗集送貨車輛調度優化研究。

2 需求拆分的多時間窗集送貨車輛調度模型

考慮需求可拆分的多時間窗集送貨車輛調度問題可以描述為：連鎖超市擁有一個配送中心，配送中心有一定數量已知載重量的運輸車輛，現在有個門店有貨物需求，其中每個門店的要求都包括集貨和送貨兩方面，車輛從配送中心出發，到達門店滿足其集送貨需求，每個門店的集送貨量允許拆分成為不同車輛完成，車輛滿足所有門店的需求后回到配送中心，同時每個門店對貨物有時間窗要求，超過要求時間會產生一定的懲罰成本，基于上述要求，求滿足配送需求的成本最少的車輛行駛路徑。

min=1+2+3+4（1）

j≤（4）

j≥i+j－j－（1－ijk） （5）

j≤i+j－j－（1－ijk） （6）

j=i+ij+i（7）

ik∈{0，1}，ijk∈{0，1} （10）

jk≥0 （11）

其中，公式（1）表示以成本最低為目標函數，公式（2）表示門店服務的車輛數等于離開點的車輛數，公式（3）表示車輛裝載量不超過總裝載量，公式（4）表示車輛裝載量不超過容量限制，公式（5）（6）表示車輛裝載量等于前裝載量減需求量加供應量，公式（7）表示時間窗約束，公式（8）表示門店的所有集送貨需求，公式（9）表示門店有一輛或以上車經過，公式（10）（11）表示變量和取值的約束。

3 案例分析

已知JLF配送中心的配送時間是05：00—08：00，配送中心有5輛容量為3 t的車輛，配送車輛05：00從配送中心出發，貨物運輸單價2元/km，車輛固定成本100元/輛，車輛行駛速度40 km/h，貨物平均單價3 000元/t，平均卸貨速度0.2 h/t，貨損系數0.2%，懲罰系數0.05%。門店距離、門店基本信息分別如表1和表2所示。

表1 門店距離表（單位：km）

PABCDEFGHI P0 A21.10 B2912.60 C30.912.220 D34.516.64.34.50 E35.417.65.73.53.40 F40.118.86.36.72.35.10 G38.818.8211921.718.523.60 H45.528.616.116.41215.59.930.10 I34.92920.822.720.724.219.641.721.80

表2 門店基本信息

送貨量（收貨）集貨量（退貨）要求時間窗可接受時間窗 P A1.50.505：1006：2005：0006：40 B1.0 05：2006：0005：0006：10 C1.20.205：4006：3005：3006：40 D0.7 06：0007：1005：5007：20 E1.2 05：5007：3005：4007：50 F1.3 06：1007：4006：0007：50 G1.1 05：3006：4005：2006：50 H0.90.206：1007：3006：0007：40 I1.0 05：2006：3005：1006：40

從門店P出發，分別計算各路線運輸成本、貨損成本和懲罰成本選擇總成本1（2）最小的路線為第一階段最優決策1（1）。第一次動態規劃第一階段如表3所示。

第一階段選出門店P到門店A點成本最小，進入第二階段規劃，從門店A出發，比較門店A到各門店的總成本，選出成本最小路線即為第二階段最優路線。第二階段如表4所示。

在第三階段計算中，門店E集送貨需求量被拆分，其送貨量1.2 t被拆分為1 t在此次運輸中完成，剩余0.2 t轉移到虛擬門店E1，虛擬門店E1與門店E地位相等，虛擬門店E1進入第二次動態規劃。第一次動態規劃第三階段如表5所示。

表3 第一階段

s2D1（s2）s1v1（s2，u1）v1（s2，u1）+f0（s1）f1（s2）最優決策u1（s1）車輛載重/t AP—AP51.2151.2151.2P—A1.0 BP—B64.0164.0164.0 CP—C69.0169.0169.0 DP—D81.9181.9181.9 EP—E78.0178.0178.0 FP—F107.2207.2207.2 GP—G84.2184.2184.2 HP—H98.8198.8198.8 IP—I75.8175.8175.8

表4 第二階段

s3D2（s3）s2v2（s3，u2）v2（s3，u2）+f1（s2）f2（s3）最優決策u2（s2）車輛載重/t BA—BA∞∞∞A—C CA—C31.6182.8182.82.0 DA—D37.4188.6188.6 EA—E42.4193.6193.6 FA—F45.4196.6196.6 GA—G44.2195.4195.4 HA—H 62.6213.8213.8 IA—I77.7228.9228.9

表5 第三階段

s4D3（s4）s3v2（s3，u2）v2（s3，u2）+f1（s2）f2（s3）最優決策u2（s2）車輛載重/t BC—BC∞∞∞C—E3.0 DC—D13.2196.0196.0 EC—E13.0195.8195.8 FC—F19.4202.2202.2 GC—G∞∞∞ HC—H38.2221.0221.0 IC—I∞∞∞

在考慮需求拆分的情況下，第一次動態規劃路線：P—A—C—E，總成本195.8元，運輸時間108 min，運輸距離36.8 km。剩余門店BDE1FGHI進行第二次動態規劃，經過4次動態規劃，完成所有門店的配送任務，得出考慮需求拆分下的4條配送路線如表6所示。

表6 數據對比

運輸路線成本/元時間/min距離/km車輛數/輛 需求不拆分P—G184.271.438.81 P—I—F222.8109.454.51 P—B—E—H244.6114.950.21 P—A—C—D196.0105.937.81 合計847.6114.9181.34 需求拆分P—I—F1—H—G308.2113.284.61 P—A—C—E195.810836.81 P—B—E1—D—F198.896.640.41 合計702.8113.21253 差值144.81.756.31

可以看出在考慮需求拆分的情況下，門店E和門店F的需求量被拆分為兩次完成，減少了車輛調度安排，一定程度上簡化了HY連鎖超市配送的復雜性。因此考慮需求拆分比不考慮需求拆分下的總成本降低了144.8元，運輸時間減少了1.7 min，運輸距離減少了56.3 km，考慮需求拆分下的車輛調度安排更合理。

4 結論

本文以JLF連鎖超市為例，運用動態規劃順序法，在考慮需求拆分的條件下，對門店E和門店F需求量進行拆分，讓配送車輛兩次訪問門店E和門店F，重新安排其配送路線，并且對比需求不可拆分的情況，考慮需求拆分下的HY連鎖超市集送貨車輛調度安排，可以有效減少JLF連鎖超市的配送成本和配送資源的浪費，提高企業效益，因此對于考慮需求拆分的連鎖超市集送貨車輛調度問題的研究具有一定的實際意義。

［1］DANTZING G B，RAMSER J H.The truck dispatching problem［J］.Management Science，1959，6（1）：80-91.

［2］張江華，李進，高敏剛.同時集散貨物的開放式車輛調度問題研究［J］.中國管理科學，2013，21（4）：187-192.

［3］劉旺盛，楊帆，李茂青，等.需求可拆分車輛調度問題的聚類求解算法［J］.控制與決策，2012，27（4）：535-541.

［4］熊浩，鄢慧麗.需求可拆分車輛調度問題的三階段禁忌算法［J］.系統工程理論與實踐，2015，35（5）：1230-1235.

［5］王科峰，葉春明，唐國春.帶時間窗分車運輸同時收發車輛調度問題及其啟發式算法［J］.運籌與管理，2012，21（2）：83-88.

U492.3

A

10.15913/j.cnki.kjycx.2020.18.007

2095－6835（2020）18－0018－03

蔣祿歡（1996—），女，研究生，研究方向為物流管理。

〔編輯：王霞〕