物流配送車輛調度路徑優化問題算法研究
理論研究
作者:馬毅
[摘要]:麵對能源及用工成本的不斷上升,企業必須對物流網絡進行高效管理。物流配送是指按用戶的訂貨要求,在配送中心進行分貨、配貨,並將配好的貨物及時交給收貨人的活動。在遼寧物流配送業務中,存在著很多優化決策的要素。比如,路徑的選取,供應點、中轉點、需求點的位置,運輸的費用、時間和容量等等諸多因素。這些因素之間的關係錯綜複雜,側重考慮不同的因素,會得到不同的配送方案。對運輸調度問題進行了分類總結,並討論了其求解現狀,對未來研究方向進行展望,指出改進混合現有算法,開拓新算法將是更有效解決遼寧配送車輛調度問題的好方法。
[關鍵詞]:遼寧物流配送車輛 調度路徑 優化算法
隨著物流體係的發展,人們常將配送的各個環節綜合起來考慮,而核心部分就是配送的車輛、貨物裝卸及送貨。因而配送車輛優化調度就成為人們關注的焦點,其中包括集貨線路優化、貨物配裝及送貨線路優化,以及集貨、貨物配裝和送貨一體化優化等等。
一、物流配送車輛調度算法綜述
在求解車輛優化調度問題時,可以將問題歸類為幾個簡單的組合優化基本原型,如旅行商問題(TSP)、最短路徑問題、最小費用流問題、中國郵遞員問題等,再用相關的理論和方法進行求解,得到模型最優解或較優解。
1.遺傳算法。遺傳算法是根據自然選擇和遺傳理論,將生物進化過程中適者生存規則與同一群染色體的隨機信息交換相結合的智能算法。遺傳算法的基本思想是:首先,通過一組編碼,將問題在表現型與基因型之間轉換,並形成初始種群,計算種群中個體的適應度;其次,設計遺傳算子(包括複製、交叉、變異),從對已產生的解(“父代”)中根據交叉率,從部分個體中選取部分基因,按某種組合形成新的個體;根據變異率,從部分個體中選取部分基本變異,產生新的個體;同時將“父代”中適應度高的個體進行複製,成為新一代個體,不斷操作、迭代,以形成新的一組解(“子代”),計算個體適應度。如此反複,可求出整個種群的最優解。遺傳算法具有良好的全局搜索能力,可以快速求出全局最優解,但存在過早收斂和搜索效率低、局部搜索能力低的缺點,導致算法比較費時。目前,許多遺傳算法在車輛調度問題中應用的研究都通過對編碼、遺傳算子的設計、基因構建和定義、適應度定義等方麵來改進算法效能。如用3-OPT算法結合遺傳算法來加強算法的局部搜索能力,得到針對車輛調度優化問題的混合算法等,而隨著模型變化,車輛調度優化問題的求解算法也會有所改變,可見,遺傳算法正從多方麵影響著車輛調度問題。
2.模擬退火算法。模擬退火法是源於材料科學和物理領域的一種搜索過程。模擬退火算法的基本思想是:首先,任意選擇一個初始狀態,並設定初始溫度和降溫次數,並在鄰域中產生另一個解,根據控製參數t選擇接受和舍棄,經過大量操作後,求得給定t時優化問題的相對最優解;其次,通過降溫函數,不斷減小t的值直到0時的最後係統狀態對應優化問題的全局最優解。前半部分是通過加熱增加物體能量;後半部分是通過降溫和冷卻降低物體的能量。對應數學模式時,問題的解就是係統狀態,而問題的目標函數就是物體的能量,因此求最優解的過程就是求能量最低態的過程。如用模擬退火算法求解多重運輸調度問題等。由於模擬退火算法一個顯著缺點就是收斂速度慢,因此在求解車輛優化調度問題時,多將模擬退火算法與其它智能算法結合,加快收斂速度。