【文章內容簡介】 以清楚知道配送車輛調度的理論知識，了解國內外的現(xiàn)狀水平和發(fā)展趨勢； （ 2）訪談咨詢法，在分析和研究的基礎上， 同公司相關的工作人員及經(jīng)理進行訪談，清楚了解具體資料，根據(jù)事實情況，提出相應的解決方案。 、研究思路 車輛調度的目標是提高效率和節(jié)約成本，在企業(yè)現(xiàn)有資源的約束下，以最合理的成本為客戶提供期望水平的服務。在車輛調度中不僅要確保運力和運量的平衡，合理地安排運輸，直接組織車輛運行并隨時進行監(jiān)督和檢查，而且不能忽視了物流量、流向和季節(jié)性的變化等因素。 在研究物流公司的車輛調度時，本文認為應從我 國物流公司的分布情況和市場的競爭趨勢入手，結合我國物流業(yè)的發(fā)展狀況和技術更新情況，借鑒現(xiàn)代科學管理一體化的理論與方法，對物流公司車輛調度策略進行詳細的分析，從而發(fā)現(xiàn)問題，提出車輛調度優(yōu)化方案。根據(jù)上述分析，其基本思路如圖 。 圖 基本思路圖 確定研究目的 查閱文獻 分析公司現(xiàn)狀 發(fā)現(xiàn)存在的問題 0— 1 規(guī)劃法 節(jié)約法 提出優(yōu)化方案 北京化工大學北方學院畢業(yè)設計（論文） 9 第 2 章 物流配送車輛調度概述 第 節(jié) 車輛調度的基本理論 、車輛調度的含義 國外將物流配送車輛調度問題歸結為 ，飛機、郵政投遞問題、水運船舶、公共汽車及鐵路車輛的調度問題、電力調度 問題、計算機網(wǎng)絡拓撲設計問題、管道鋪設問題等都可以抽象為物流配送車輛調度問題。 VRP 問題是對進行物流配送的車輛進行優(yōu)化調度，物流配送車輛調度問題可以說是對旅行商問題加以一定的限制而形成的，這些限制包含了：客戶有一定的貨物需求（或供應）數(shù)量且要求貨物在一定的時間范圍內送到（或者取走），配送車輛的裝載量限制級一次配送的最大行駛距離限制等，即物流配送車輛調度問題是一個多約束的旅行商問題。同時物流配送車輛調度問題還可以歸結為在每一個配送路線中的旅行商問題。 、車輛調度的構成要素 配送車輛調度問題的主要構 成要素包括以下：物流中心、車輛、約束條件和目標函數(shù)、貨物、運輸網(wǎng)絡和客戶等。 （ 1）物流中心：也可以稱作為物流基地或物流據(jù)點，是指進行集貨、分貨、配貨、配裝、送貨的配送中心、車站、倉庫和港口等。在某個配送系統(tǒng)中，物流中心的數(shù)量可以是一個，也可以不止一個，物流中心的位置既可以確定又可不確定，其供應的貨物可以是一種，也可以是很多種，而這些供應的貨物可以是滿足全部的客戶需求，也可是部分的需求。 （ 2）車輛：車輛是貨物的運載工具。它的屬性大致包括車輛的類型，一次配送的最大行駛的距離、配載量、配送前和配送完的車輛停放 位置。 車輛的類型包括通用車輛和專用車輛，通用車輛一般用于配送普通貨物，而專用北京化工大學北方學院畢業(yè)設計（論文） 10 車輛通常用于裝運一些性質較為特殊的貨物。 每臺車輛一次配送的最大行駛距離有以下幾種情況：無距離限制；有距離限制；有距離限制，但可以不履行，不履行時可通過另付加班費解決。 車輛的裝載量是指車輛最大裝載的容積和重量，是進行車輛裝載決策的依據(jù)，在某個配送系統(tǒng)中車輛的裝載量可以相同，也可以不同。 車輛配送前的停放位置可以是物流中心或某個停車場，也可以是客戶所在地。 車輛配送任務結束后，停放的位置可分為以下幾類：必須返回出發(fā)點或某停車場；可 以返回任何一個停車場；可停放在任何物流中心、某停車場、客戶所在地。 （ 3）約束條件：配送車輛調度要滿足的約束條件主要包括所有客戶對貨物規(guī)格、品種和數(shù)量的要求；在允許通行的時間內進行配送；客戶對貨物發(fā)到時間的要求；物流中心的現(xiàn)擁有的運力范圍內；車輛在配送過程中的實際載貨量不得超過規(guī)定的載貨量。 （ 4）目標函數(shù)：目標函數(shù)說白了就是車輛調度的最終目標，它可以是一個，也可以是很多個目標的集合。經(jīng)常被選用的目標函數(shù)分別是以下幾個： ①費用最低，實現(xiàn)配送業(yè)務經(jīng)濟效益的最基本要求便是降低費用，在運送貨物有關的費用包括：車 輛的行駛費用、車輛的管理維護費用、貨物卸載費用、有關人員工資費用等。 ②高準時率，為了滿足客戶對交貨時間有較高的要求，為提高配送服務質量，提高準時率也成為了目標函數(shù)之一。 ③配送路程最短，這直接與配送車輛的耗油量、磨損程度以及司機的疲勞程度直接掛鉤，同時它還決定了運輸?shù)某杀?，這對效益有很大的影響，當然它也是用來衡量的最多的指標。 ④配送車輛的噸位公里數(shù)最少，這是將車輛的載重量和配送距離相結合起來考慮的，即以所有配送車輛的噸位數(shù)和其行使距離的乘積的總和最少為最優(yōu)目標。 ⑤消耗最低的勞動力，以運用的司機最少，和 司機的工作時間最少為目標。 ⑥合理利用運力，用較少的車輛完成配送任務，并保證車輛的滿載率最高，以充分利用車輛的裝載量為目標。 （ 5）貨物：貨物也就是配送的對象，我們可以將每個客戶需求的貨物看成是一批貨物，而貨物本身具有的屬性包含體積、重量、包裝、品名、要求取走或送達的時間和地點、能否進行分批配送。 北京化工大學北方學院畢業(yè)設計（論文） 11 貨物的體積和重量是進行車輛調度決策的依據(jù)，當某個客戶需求貨物的重量和體積超過配送車輛規(guī)定的最大配載重量或容積，那么該客戶需要多個配送車輛進行運送。 貨物的包裝和品名是選用配送車輛的類型以及決定該批貨物能否和其他貨 物裝載在同一車輛的依據(jù)。比如有的比較特殊的貨物需要專用車輛來配送，但由于它的包裝比較好，完全可以和其他普通的貨物共用一輛普通車輛來進行運輸。 貨物被取走和送取的時間和地點是制定配送車輛的出行時間和配送路線的依據(jù)。 貨物的分批運送，是指某個客戶的需求貨物通過批準允許經(jīng)過多個車輛分批取走或送達，即使需求量在一個車輛運載量的范圍內。 （ 6）運輸網(wǎng)絡：運輸網(wǎng)絡是指由頂點（物流中心、停車場、客戶）、無向邊和有向弧組成的。邊和弧的屬性包括權值、方向和交通流量限制等。 運輸網(wǎng)絡的無向邊或有向弧的權值可以表示距離、費用或時 間。它們的權值變化有以下幾種：不隨時間和車輛的不同而變化，是固定的；隨著時間的不同而進行變化；隨著車輛的不同而進行的變化；既隨車輛的不同而變化，也隨著時間的不同而變化。對網(wǎng)絡權值之間的關系可以要求其滿足三角不等式，即兩邊之和要大于第三邊；當然也可以不加限制。 關于運輸網(wǎng)絡的方向可能只有有向弧或只有無向邊，也可能既有有向弧又有無向邊。 對運輸網(wǎng)絡中頂點、邊或者弧的交通流量要求分為：無流量限制；邊弧限制，就是每條邊和弧上同時行駛的車輛數(shù)量有限制；頂點的限制，也就是說在物流中心、停車場和客戶所在地同時裝卸貨物的車 輛有限；頂點、無向邊和有向弧都有限制。 （ 7）客戶：也可稱作為用戶，包括零售商店和倉庫等，客戶的本質屬性有：需求貨物的數(shù)量和時間、次數(shù)以及滿足程度等。 在某配送系統(tǒng)中，某客戶的需求數(shù)量可能會大于或者小于車輛的最大裝載量；而該系統(tǒng)的全部客戶的貨物需求總量可能超過或者低于所有車輛的裝載量。 某個客戶的需求貨物達到的時間，是指要求貨物取走到送達的時間，它有以下幾種要求的情況：無時間限制；要求在指定的時間內完成運輸?shù)娜蝿?；有時間限制，若不遵守，可以通過懲罰來解決。 某個客戶需求貨物的次數(shù)可能是一次，也可能需要進行多 次配送服務。 某個客戶對需求貨物的滿足程度，可以是全部滿足，也可能是部分滿足，當不滿北京化工大學北方學院畢業(yè)設計（論文） 12 足時需要受到一定的懲罰。 、車輛調度問題的分類 物流的配送車輛調度問題可以通過其構成要素劃分成不同的種類 。 （ 1）按物流中心的數(shù)目來分，存在單個物流中心問題，也存在著多個物流中心問題。 （ 2）按照車輛的裝載狀況來分，有滿載的問題，例如客戶需求的貨物大于或等于車輛的裝載量，若要完成這個運輸任務必須得有一輛或一輛以上的配送車輛，而且配送車輛需要滿載運行；也有非滿載問題，例如客戶需求的貨物小于車輛的裝載量，多項配送任務可 通過一輛配送車輛就能完成任務，而且車輛在配送過程中經(jīng)常處于不滿載的狀態(tài)；還有滿載和非滿載混合的問題，例如一部分客戶的需求的貨物數(shù)量大于或等于車輛的裝載量，而另一部分客戶的需求貨物數(shù)量小于車輛的裝載量，造成了一些車輛必須滿載行駛，還有些車輛經(jīng)常處于非滿載的狀態(tài)。 （ 3）按照優(yōu)化的目標來分，有單目標問題，也有多目標問題。 （ 4）按照車輛的類型來分，有單車型問題，也有多車型問題。 （ 5）按照客戶對貨物取送的時間要求來分，有無時間限制和有時間限制。有時間限制又可以分為硬時間窗問題，即客戶要求在規(guī)定的時間內將貨物取走 或送達，不能提前也不能拖后；軟時間窗問題，即客戶要求盡量能在規(guī)定的時間內將貨物取走或送達，若提前或推遲，要對配送企業(yè)進行一定的懲罰措施。 （ 6）按照車輛對車場的所屬關系來分，有車輛開放和封閉問題，前者是指車輛配送任務完成后可以不必回到出發(fā)車場，后者是指車輛在完成配送任務后必須回到其出發(fā)的車場。 （ 7）按照配送任務的特征來分，有純送貨問題和純取貨問題以及取送混合的問題。我們簡單的將純送貨問題和純取貨問題概括為單向車輛配送調度問題，而將取送混合的問題概括為雙向車輛配送調度問題。 第 節(jié) 車輛調度的方法 、 01 規(guī)劃法 北京化工大學北方學院畢業(yè)設計（論文） 13 01 規(guī)劃法是一種比較特殊形式的整數(shù)規(guī)劃法，它的決策變量取決于 1 或者 0，而且一個非負的整數(shù)也可以用二進制記數(shù)法用若干個 01 變量表示，所以我們又叫它二進制變量或 01 變量。 01 規(guī)劃法可以數(shù)量化地描述例如取與舍、有與無、開與關等現(xiàn)象所反映的離散型變量之間的順序關系、邏輯關系和互斥時的約束條件。所以說01 規(guī)劃法在針對工廠選址、旅行購物、人員安排、線路設計、生產(chǎn)計劃安排、代碼選取、背包問題等問題上都能應用到，并且都能有效的處理和解決。解決 01規(guī)劃模型時主要方法是隱枚舉法和窮舉法 ，前者只需要檢查變量的取值組合的一部分，若是這個取值組合的部分集合選的比較恰當，那么計算任務量則會大大下降。因而這類車輛調度問題的關鍵在于怎樣構造出變量取值組合的部分集合，從而盡可能的減少檢查的次數(shù)。窮舉法需要檢查變量的取值為 1或者 0的每一種組合，并且比較目標函數(shù)值。 （ 1）提出問題 設 B0 為物流網(wǎng)點， Bj（ j=1,2,? ,n）為需求用戶，各用戶的需求量為 bj（ j=1,2,? ,n）， 每輛汽車的載重量為 Q，且滿足 nj jb1＝≤ Q，這個可行的巡回路線由 n+1段路線構成，以 Xijr（ i=0,1,2,? ,n； j=0,1,2,? ,n； r=0,1,2,? ,n+1,i≠ j） 表示ij段路線作為某巡回路線中第 r段行程的決策變量，當 Xijr=1時表示在巡回路線上，當 Xijr=0時表示該段行程不在巡回路線上。 Cij表示各 點之間的最短距離，要達到總行程路線最短。 （ 2）分析問題 若要使這個方案可行，且能保證巡回路線不會間斷，各個路線能夠一次銜接，那么ni ijrx0＝ =nk ijrx0 1＝ ＋ （ r=1,2,? ,n； j=1,2,? ,n； i≠ j， j≠ k） ,若是要保證發(fā)貨車離開一個點后只能到另外一個點，并且各點在巡回路線上只出現(xiàn)一次，那么 njnr ijrx010＝＋＝=1（ i=0,1,2,? ,n,i≠ j） ,這也表示從 i 為 起始點的路段在巡回路線中必須而且只出現(xiàn)一次，從而保證發(fā)貨車離開 i 點只能到另一個 j點，同時也可以看出以點 j為起始點的路線若作為巡回路線中的 r+1 段行程而存在，那么肯定有以點 j為終點的路段作為r段行程存在于巡回路線中。這樣就能保證各段路線一次銜接且不會間斷。 （ 3）建立模型 min F=11 0 0＋＝ ＝ ＝nrninj ijC Xijr 北京化工大學北方學院畢業(yè)設計（論文） 14 ni ijrX0＝ =nk ijrX0 1＝ ＋ （ r=1,2,? ,n； j=1,2,? ,n； i≠ j， j≠ k） nj nr ijrX0 10＝ ＋＝ =1（ i=0,1,2,? ,n） 0,ij 作為巡回路線中的第 r 段行程不存在 Xijr = 1， ij作為巡回路線中的第 r段行程存在 、節(jié)約法 節(jié)約法最初是由懷特和克拉克在 1964 年提出來的，它屬于一種啟發(fā)式的方法，它是車輛調度程序的規(guī)劃法，也可以稱它為節(jié)約里程法。 （ 1）基本原理 如圖 21 所示，由物流中心 B0 給兩個配 送點 B1 ,B2 發(fā)貨，物流中心到各個配送點的最短的配送距離分別為 C01 和 C02 ，而各個配送點用戶的需求量分別是 b1 和b2 ，而兩個配送點的最短配送距離是 C12 。當用兩輛車分別給兩個配送點各自往返發(fā)貨時，車輛行程的總距離是 C1 =2(C01 +C02 )。 若是改用一兩車巡回送貨，而且該車的裝載量能夠負荷這兩個配送點的需求量，那么該車總的行程距離為 C2 =C01 +C02 +C12 。 第二種方案比第一種方案可以節(jié)約的配送里程為△ C12 =C01 +C02 C12 ，而該市就被稱為節(jié)約量公式，△ C12 就是 B1 ,B2 兩者之間的節(jié)約量。顯而易見，若是將節(jié)約量大的兩個配送點連接到一起，采用巡回方式送貨，則能獲得更多的節(jié)約量。要是在配送中心的供貨范圍內還有著第三