配送中心車輛調度問題的分級求解

[摘 要]本文根據配送中心運輸任務類型的復雜程度不同，將車輛調度問題分為四個等級。進而描述每個等級的約束條件，并結合實際應用對各個等級問題的求解方法進行了討論。

[關鍵詞]配送 分級 約束 車輛調度

由于配送運輸業務類型的多樣性和復雜程度不同，需要對實際應用中的車輛調度問題按照復雜程度進行分級介紹。為方便討論，本文中將工廠、配送中心、倉庫等裝貨點統稱為資源點或發點，而把不同的貨物發送到另外的一些卸貨點，稱為需求點或收點。下文便將車輛調度問題分為四個不同等級問題并逐一討論。

三、Ⅲ級問題：現實約束下（時間約束、車輛約束）的配送運輸調度問題

（1）問題描述。由于用戶通常對發送或交貨的時間有具體的期望，配送往往受到時間的約束。譬如一個小組需求送貨到n個需求點，并表示為1，...，a，...n，需求點a完成時間是固定的，值為Ta，服務時間（如卸貨時間）也是固定的，為Sa。假設Ta為9：00，Sa為2小時，那么車輛必須能夠在7：00到達需求點a。此處我們用H（a，b）表示從收點a到b之間的運輸時間，用dab表示兩點的距離。假若Tb-Sb>Ta+H（a，b）成立，則弧（a，b）就有存在的可能性。將弧（a，b）成本Cab指定為H（a，b）或dab的函數。此時，這個問題就轉變為：依據已知給定數量的從起點a到終點b的路徑，要求包括所有的節點，并使得在全部車輛的安排計劃中，運輸總時間（或運輸總距離）為最小值。

（2）求解討論。一般可以采用兩步算法求解該問題。第一步：查找無圈有向網絡，確定從a到b并經過包括全部節點的路徑的最小數目（最大流或最小費用流算法可用來求解）。就是確保滿足所有需求點的需求所必須的車輛數的最小值，然后將車輛數固定，求解對應的費用流最小化問題。這個解的合理性在于，一方面能夠保證車隊規模的最小化，另一方面能夠使得路線行駛成本為最小值。

四、Ⅳ級問題：多個發車點的配送運輸問題

（1）問題描述。如果將上述的問題進行直接延伸，允許若干車輛的發點不止一個，可以是從多個配送中心出發，此時，配送問題就轉變為巡回銷售員問題，即可能存在多個封閉的循環回路。顯然，這是一個多組合優化的問題。此時，車輛調度的目標是以最少的車輛通過最經濟的線路完成所有的運輸任務。

（2）求解討論。對于此類問題，可以采用兩類方法求解。

1.先分組，然后制定路線時間計劃表。首先把客戶依據一定的調度標準劃分成獨立的集合，每個集合指定一個車庫。然后，用Ⅱ級問題的方法求解每個車庫。如果破壞了任一車庫的容量限制（包括極大和極小容量），就需要重新修正客戶的最初集合，再結合Ⅱ級問題進行新一輪的求解。按這種方式繼續運行這一過程，直到得到較優解。

2.先安排路線時間計劃表，然后制定分組。對整個網絡求解Ⅱ級問題，而忽略用來存放任一車輛的車庫情況。這樣，就構造了一條大的路線或回路（通常不可行），它包括了所有需求對象（即節點或弧）。然后，將任一車輛的路線表指定為對應車庫，其目標使總的運輸距離為極小值并限制車庫所存放車輛數量的最大值與最小值。當各個車輛進出車庫的里程與路線表上的運輸距離的比值越小時，這種方法的合理性就越大。

配送中心的車輛調度工作，應在符合約束條件的基礎上，對調度問題按復雜程度進行歸類，并針對實際情況，提出合理的求解方法。從而，有利于從節約運輸里程等角度，控制和降低運輸總成本，提升經濟效益。

參考文獻：

[1]陳君蘭. 物流配送車輛調度問題算法綜述.物流科技，2012.3

作者簡介：于斌，，男，（1982—），籍貫：江蘇連云港，學歷：碩士研究生，研究方向：物流管理 ，單位：常州機電職業技術學院。