物流配送車輛路徑問題-文庫吧資料
2025-01-10 05:35本頁面
【正文】 規(guī)定先卸后裝。 ?描述 ?求一個具有最小總費用的由 K條簡單回路組成的集合，并滿足 （ 1）、（ 2） 同 CVRP； （ 3） 一條回路上各去程客戶點和回程客戶點的需求量之和分別不超過車輛裝載能力 C； （ 4） 所有去程客戶必須先于回程客戶得到服務(wù) 。 ?由于允許以支付懲罰偏離時間窗，與 VRPHTW相比， VRPSTW往往會在所需要的車輛數(shù)、或各線路總距離和總行駛時間方面獲得較大的節(jié)省。 ?若某個客戶的時間窗不能被違反（硬的），則有偏離時應(yīng)支付的懲罰設(shè)為無窮大。 18 軟 時間窗的 VRP （VRP with soft time windows, VRPSTW） ?時間窗要求是軟的，即允許服務(wù)的開始時間有所偏離時間窗（早于 ai或晚于 bi ）， 但要根據(jù)所帶來的不方便程度支付一定的懲罰。 ? 描述 ?VRPHTW是求一個具有最小總費用的由 K條簡單回路組成的集合，并滿足 （ 1）、（ 2）、（ 3） 同 CVRP； （ 4） 對每個客戶 i， 服務(wù)在時間窗 [ai, bi]內(nèi)開始，車輛的停留時間長度為 si。 17 ?對于配送中心，設(shè)服務(wù)時間 s0 = 0， 時間窗 [a0, b0]。 ?當車輛提前到達客戶點時，必須等待到時刻 ai才可開始服務(wù)。 在不需要嚴格區(qū)分的場合，一般就稱為帶時間窗的 VRP。 16 帶時間窗的 VRP （ VRP with time windows， VRPTW） ?除了車輛裝載能力約束外，每個客戶 i 都有一個與之相聯(lián)系的要求提供服務(wù)的時間區(qū)間 [ai, bi]。 ?每條線路上各弧的總長度不能超過線路的最大長度 L。 15 帶路程長度的 VRP（ DistanceConstrained and Capacitated VRP， DCVRP） ? 特點 ? 既有車輛裝載能力限制，又有最大路程長度限制。 ?CVRP是 NP難的，并且是旅行商問題 （ TSP） 的一般化 。通常都認為，多用一輛車所帶來的固定費用的增加，總是超過其因總行駛距離縮短所帶來的節(jié)省，因此，一般把最小化車輛使用數(shù)作為第一優(yōu)化目標，最小化行駛費用作為第二目標。 服務(wù)所有客戶至少所需要的車輛數(shù) ?????? ??CdK imi n13 ?CVRP是求一個具有最小總費用的由 K條簡單回路組成的集合 （ 每個回路對應(yīng)于一條配送車輛行駛線路） ， 并滿足 (1) 每個回路從配送中心出發(fā)并返回配送中心； (2) 每個客戶點只在一條回路上； (3) 一條回路上各客戶點的需求量之和不超過車輛裝載能力 C。每一條線路上的送貨任務(wù)只由一輛車承擔。 ?在一些測試算例中，頂點與給定坐標的平面上的點相對應(yīng)，且弧的費用 cij被定義為對應(yīng)于頂點 i和 j的兩點間的歐氏距離。有時配送中心用頂點 n +1來表示。 ? 問題的描述（可描述為如下的圖論問題） 11 ?設(shè) G = (V, A)為一個完備圖，其中 V = {0,…, n}為頂點集， A是弧集。 ? 對車輛只有裝載能力限制。 ? 所有客戶都屬于要送貨的或要取貨的，其需求量預(yù)先知道，且不能被分割。 9 ? 根據(jù)所包含的約束條件，問題又可進一步分類。 7 ? 當車輛完
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1