基于改進差分進化的車輛路徑優化算法

鄔開俊，王鐵君

1.蘭州交通大學 電子與信息工程學院，蘭州 730070

2.西北民族大學 數學與計算機科學學院，蘭州 730030

基于改進差分進化的車輛路徑優化算法

鄔開俊1，王鐵君2

1.蘭州交通大學 電子與信息工程學院，蘭州 730070

2.西北民族大學 數學與計算機科學學院，蘭州 730030

1 引言

車輛路徑問題（Vehicle Routing Problem，VRP）是指由一組車輛從一個或多個車場點出發對分布在不同地理位置的一系列顧客點進行服務，要求每個顧客點的需求必須被滿足，每個車輛的路線開始于車場點，并最終結束于車場點[1]。如圖1所示，左圖是一個有1個車場一系列顧客點的VRP的實際問題，右圖為一種動用5輛車的可行方案。優化一般以動用車輛數盡可能少，以及所有車輛的總運行路線長度盡可能短為目標。它是組合優化和運籌學研究領域的熱點問題之一，在現實生活中應用廣泛，如城市垃圾收集，包裹配送，校車接送路線安排等。研究滿足生產經營和運作需要的車輛路徑問題，并構建具有高質量和高魯棒性的問題求解算法，對于提高生產經營管理水平和降低運作成本具有重要的理論意義和現實價值。

圖1 一個VRP實例（左）及其可行解（右）

VRP是很多實際問題求解的最終轉化形式，同時也是著名的NP難題，在短時間內精確地求出其最優解非常困難，尤其對于大規模問題，很難求得最優解。近年來，遺傳、粒子群、蟻群、禁忌等算法在解決這一類問題時得到了初步的應用[2-5]，但是在求解精度和求解效率等方面還有待于提高。……