物流配送車輛路徑問題-預(yù)覽頁
【正文】 后返回原出發(fā)點，或者是若要求返回原出發(fā)點，則沿原去程路線返回時（即車輛的行駛路線是開放式的），稱之為 開放式車輛路徑問題 （ Open VRP，OVRP） 。 ? 車輛類型相同且都停放在一個配送中心。頂點 i = 1,…, n表示客戶，而頂點 0表示配送中心。 yj j (xj, yj) yi i (xi, yi) xj xi ? ? ? ?22 jijiij yyxxc ????12 ?在配送中心備有相同類型的車輛，每輛的裝載能力為 C。 ?總費用一般包括所使用的車輛數(shù)（即回路數(shù)）和車輛行駛費用兩項。 在 TSP中，要求確定一條經(jīng)過圖 G中所有頂點的、費用最小的回路（哈密頓回路），當CVRP中的 C≥∑di和 K=1時就為此情形。 ?當弧的長度代表的是行駛時間時，每個客戶 i就對應(yīng)著一個服務(wù)時間 si， 表示車輛必須在該客戶點停留的時間長度。 ? 特點 ?客戶的服務(wù)必須在相應(yīng)的時間窗內(nèi)開始，車輛在客戶點的服務(wù)時間長度為 si。 ?應(yīng)注意的是，時間窗的要求導致每條線路 具有隱含的方向性， 以及 線路長度的限制 ，最大線路長度為 L =b0?？啥x懲罰函數(shù)來計算。 19 帶回程運輸?shù)?VRP （VRP with backhauls， VRPB） ? 特點 ?客戶集：去程客戶， L={1, 2, …, n} 回程客戶， B={n+1, …, n+m} ?先服務(wù)去程客戶，后服務(wù)回程客戶。 ?描述 ?求一個具有最小總費用的由 K條簡單回路組成的集合，并滿足 （ 1）、（ 2） 同 CVRP； （ 3） 車輛的當前負載必須保持非負且 ≤C； 22 （ 4） 當 Oi不是配送中心時，它必須與客戶 i在同一線路上且先于客戶 i得到服務(wù)； （ 5） 當 Di不是配送中心時，它必須與客戶 i在同一線路上且后于客戶 i得到服務(wù)。 ?1964年， Clarke和 Wright提出一種對 DantzigRamser方法進行改進的較有效的啟發(fā)式算法 ——ClarkeWright節(jié)約算法。 ?1995年出版的《 Handbooks in Operations Research and Management Science 》中，第八卷就是專門討論車輛路徑問題的。 25 車輛路徑問題的模型 ? CVRP的三下標車輛流模型。 ?目前 已提出了許多求解 VRP的算法， 究其實質(zhì)，可 分為 精確算法 和 啟發(fā)式算法 兩大類。 ?從實際應(yīng)用的角度來說，公認的明智做法是設(shè)計相應(yīng)的啟發(fā)式算法來求出問題的近優(yōu)解。 ?求出的解高出最優(yōu)解（或已知最好解）： ? 基于 經(jīng)典啟發(fā)式方法： 210%； ? 基于 通用啟發(fā)式方法： % 30 ? 發(fā)展趨勢 ?為了使現(xiàn)代啟發(fā)式算法能在商業(yè)軟件中得到應(yīng)用，開發(fā)更快、更簡單、更健壯的算法已成為一種趨勢，盡管這將在解的質(zhì)量方面帶來一些小損失
教學課件相關(guān)推薦
鄂ICP備17016276號-1