基于廣義多子代遺傳算法的外賣配送問題研究.pdf

1、隨著網(wǎng)絡(luò)訂餐平臺的發(fā)展，外賣配送在網(wǎng)絡(luò)訂餐平臺的運營中占據(jù)越來越重要的地位。提高外賣配送效率成了未來網(wǎng)絡(luò)訂餐平臺發(fā)展的必要選擇。運輸路線的合理性直接影響到配送速度、配送成本和顧客滿意度，特別是多餐廳、多顧客、多車輛的復雜配送網(wǎng)絡(luò)的配送線路確定確實是一項復雜的系統(tǒng)工程。選取恰當?shù)能囕v路徑，可以加快對客戶需求的相應速度，提高服務(wù)質(zhì)量，增強客戶對配送環(huán)節(jié)的滿意度、提高運營效率。
　　現(xiàn)存的外賣配送決策方法是人工決策，由于人的計算能力限制

2、，人工決策無法將不同餐廳的訂單聯(lián)合考慮，因而無法進行多餐廳聯(lián)合配送，降低了總體配送效率。本文將外賣配送問題轉(zhuǎn)化為車輛路徑問題，通過求解車輛路徑問題來對外賣配送進行決策。由于車輛路徑問題采用計算機進行求解，可以在有限的時間內(nèi)求解大規(guī)模的車輛路徑問題，因此，車輛路徑問題模型求解外賣問題可以多餐廳聯(lián)合配送，減少了重復配送和餐廳負載不平衡的人員浪費問題，提高了效率。實驗結(jié)果表明，車輛路徑問題配送方法較人工配送方法具有明顯的優(yōu)勢—平均配送距離短、

3、最大配送時間短、顧客平均等待時間短。
　　車輛路徑問題是著名的NP-hard問題，有很廣泛的工程和現(xiàn)實背景，許多實際問題可轉(zhuǎn)化為車輛路徑問題來解決，如本文研究的外賣配送，可以轉(zhuǎn)變?yōu)橐幌盗熊囕v路徑問題來求解。由于車輛路徑問題是NP-hard問題，大規(guī)模的車輛路徑問題無法在多項式時間內(nèi)求得精確解，需要采用啟發(fā)式算法來求其近似解，本文使用遺傳算法來求解VRP問題。
　　遺傳算法是模擬生物選擇和進化機制的一種并行、隨機的自適應搜索算

4、法，適合于處理傳統(tǒng)搜索算法不易解決的復雜、非線性問題。它可以在全局進行并行搜索，具有搜索效率高的特點。然而，外賣配送對求解時間要求很高，要求算法盡快給出結(jié)果，這就需要一種能快速收斂的算法，本文使用了多子代遺傳算法來求解車輛路徑問題。但是，這種多子代遺傳算法要求子代數(shù)量取值為父代數(shù)量的整數(shù)倍，缺少靈活性，導致子代數(shù)量的取值極有可能錯過最優(yōu)值，本文擴展了多子代遺傳算法，改進了子代生成方法，提出了廣義多子代算法。廣義多子代遺傳算法的子代產(chǎn)生更