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