物流配送優(yōu)化(第二章)(編輯修改稿)
2025-03-28 15:36 本頁面
【文章內(nèi)容簡介】 ，一般把最小化車輛使用數(shù)作為第一優(yōu)化目標，最小化行駛費用作為第二目標。 14 ?當備有的車輛類型不是同一種時，即有不同的裝載能力 Ck， k =1,…, K， 則就為經(jīng)?？紤]的另一種變形。 ?CVRP是 NP難的，并且是旅行商問題 （ TSP） 的一般化 。 在 TSP中，要求確定一條經(jīng)過圖 G中所有頂點的、費用最小的回路（哈密頓回路），當CVRP中的 C≥∑di和 K=1時就為此情形。 15 帶路程長度的 VRP（ DistanceConstrained and Capacitated VRP， DCVRP） ? 特點 ? 既有車輛裝載能力限制，又有最大路程長度限制。 ? 描述 ?每條弧對應(yīng)著一個非負的長度 tij， 一般地，費用矩陣與長度矩陣相一致，即 cij = tij。 ?每條線路上各弧的總長度不能超過線路的最大長度 L。 ?當弧的長度代表的是行駛時間時，每個客戶 i就對應(yīng)著一個服務(wù)時間 si， 表示車輛必須在該客戶點停留的時間長度。 16 帶時間窗的 VRP （ VRP with time windows， VRPTW） ?除了車輛裝載能力約束外，每個客戶 i 都有一個與之相聯(lián)系的要求提供服務(wù)的時間區(qū)間 [ai, bi]。 硬 時間窗的 VRP（ VRP with hard time windows,VRPHTW）。 在不需要嚴格區(qū)分的場合，一般就稱為帶時間窗的 VRP。 ? 特點 ?客戶的服務(wù)必須在相應(yīng)的時間窗內(nèi)開始，車輛在客戶點的服務(wù)時間長度為 si。 ?當車輛提前到達客戶點時，必須等待到時刻 ai才可開始服務(wù)。不允許在 bi之后到達并開始服務(wù)。 17 ?對于配送中心，設(shè)服務(wù)時間 s0 = 0， 時間窗 [a0, b0]。 ?應(yīng)注意的是，時間窗的要求導(dǎo)致每條線路 具有隱含的方向性， 以及 線路長度的限制 ，最大線路長度為 L =b0。 ?描述 ?VRPHTW是求一個具有最小總費用的由 K條簡單回路組成的集合，并滿足 （ 1）、（ 2）、（ 3） 同 CVRP； （ 4） 對每個客戶 i， 服務(wù)在時間窗 [ai, bi]內(nèi)開始，車輛的停留時間長度為 si。 ?當 ai = 0, bi = +∞時 ， VRPHTW就為 CVRP。 18 軟 時間窗的 VRP （ VRP with soft time windows, VRPSTW） ?時間窗要求是軟的，即允許服務(wù)的開始時間有所偏離時間窗（早于 ai或晚于 bi ）， 但要根據(jù)所帶來的不方便程度支付一定的懲罰?？啥x懲罰函數(shù)來計算。 ?若某個客戶的時間窗不能被違反（硬的），則有偏離時應(yīng)支付的懲罰設(shè)為無窮大?？梢?VRPHTW實際上是 VRPSTW的一種特殊情形。 ?由于允許以支付懲罰偏離時間窗，與 VRPHTW相比， VRPSTW往往會在所需要的車輛數(shù)、或各線路總距離和總行駛時間方面獲得較大的節(jié)省。 19 帶回程運輸?shù)?VRP （ VRP with backhauls， VRPB） ? 特點 ?客戶集：去程客戶， L={1, 2, …, n} 回程客戶， B={n+1, …, n+m} ?先服務(wù)去程客戶，后服務(wù)回程客戶。 ?描述 ?求一個具有
教學課件相關(guān)推薦
鄂ICP備17016276號-1