快遞公司的配送數(shù)學(xué)建模

1、快遞公司的配送問題摘要 配送是物流系統(tǒng)中非常重要的一個(gè)環(huán)節(jié)，在物流的各項(xiàng)成本中，配送成本占了相當(dāng)高的比例，減少配送里程以降低物流配送成本成為物流管理過程中首要考慮的問題之一。本文在已知貨運(yùn)車容量、各客戶所需貨物重量、快遞公司與客戶以及客戶與客戶之間的距離的條件下，建立了以單車場路徑問題模型（即VRP模型）為基礎(chǔ)、以車輛總行程最短為目標(biāo)函數(shù)、以貨物運(yùn)輸量小于汽車載重量以及在客戶要求的時(shí)間范圍內(nèi)運(yùn)送貨物等為約束條件的單目標(biāo)線性規(guī)劃模型。 對(duì)于問題一，本文建立了兩個(gè)模型：模型I：硬時(shí)間窗車輛路徑規(guī)劃模型 首先根據(jù)題目所給條件，對(duì)運(yùn)貨所需的車輛數(shù)進(jìn)行預(yù)估，然后結(jié)合貨物運(yùn)輸量小于汽車載重量、一個(gè)客戶點(diǎn)的

2、貨物僅由一輛車配送等約束條件，同時(shí)考慮線路的連通性和汽車到達(dá)客戶點(diǎn)的時(shí)間范圍，采用0-1規(guī)劃法建立使總運(yùn)行里程最小的車輛路徑規(guī)劃模型。 模型II：軟時(shí)間窗車輛路徑規(guī)劃模型在模型I硬時(shí)間窗車輛路徑規(guī)劃模型的基礎(chǔ)上，將模型I中的關(guān)于時(shí)間范圍的約束條件，通過設(shè)定懲罰函數(shù)的系數(shù)，變成目標(biāo)函數(shù)的一部分。本文在考慮路程最短的目標(biāo)的同時(shí)，也要求盡可能在時(shí)間范圍內(nèi)到達(dá)。因此，建立了以成本（包括懲罰成本以及行駛過程中帶來的成本）最小為目標(biāo)的函數(shù)，以運(yùn)輸量小于汽車載重量以及線路的連通性等為約束條件，建立軟時(shí)間車輛路徑規(guī)劃模型。最后運(yùn)用遺傳算法求解模型。對(duì)于問題二，根據(jù)題目所提供的數(shù)據(jù)，利用硬時(shí)間窗車輛路徑規(guī)劃模型

3、。首先，根據(jù)貨運(yùn)車的載重量和客戶點(diǎn)的需求總量，估計(jì)出運(yùn)貨所需車輛數(shù)為3，然后，借助Lingo求解該模型。得到最優(yōu)路徑的總里程數(shù)為910千米，快遞公司每天的配送方案應(yīng)為:每天出動(dòng)3輛車。3輛車的行駛路徑分別為：0-3-1-2-0，0-6-4-0，0-8-5-7-0關(guān)鍵詞： VRPTW 遺傳算法 0-1規(guī)劃法 Lingo目錄一、問題重述2二、模型假設(shè)和符號(hào)說明2三、問題分析3四、模型的建立與求解44.1問題一的解答44.1.1模型的準(zhǔn)備44.1.2模型的建立44.1.3模型的求解74.2問題二的解答84.2.1對(duì)貨運(yùn)車輛數(shù)的估計(jì)84.2.2路線的規(guī)劃8五、 模型的評(píng)價(jià)與改進(jìn)105.1模型的優(yōu)缺點(diǎn)分

4、析105.2 模型的改進(jìn)11六、參考文獻(xiàn)11七、附錄12一、問題重述某快遞公司在某個(gè)地區(qū)擁有一支貨運(yùn)車隊(duì)，每臺(tái)貨運(yùn)車輛的載重量（噸）相同、平均速度（千米/小時(shí)）相同，該快遞公司用這樣的車為若干個(gè)客戶配送物品，快遞公司與客戶以及客戶與客戶之間的公路里程（千米）為已知。每天，各客戶所需物品的重量（噸）均已知，并且每個(gè)客戶所需物品的重量都小于一臺(tái)貨運(yùn)車輛的載重量，所有送貨車輛都從快遞公司出發(fā)，最后回到快遞公司?？爝f公司每天的配送方案應(yīng)當(dāng)包括：當(dāng)天出動(dòng)多少臺(tái)車？行駛路徑如何？由此形成的當(dāng)天總運(yùn)行里程是多少？一個(gè)合格的配送方案要求送貨車輛必須在一定的時(shí)間范圍內(nèi)到達(dá)客戶處，早到達(dá)將產(chǎn)生等待損失，遲到達(dá)將予

5、以一定的懲罰；而一個(gè)好的配送方案還應(yīng)該給出使配送費(fèi)用最小或總運(yùn)行里程最短的車輛調(diào)度方案。該快遞公司希望你們：1. 建立送貨車輛每天總運(yùn)行里程最短的一般數(shù)學(xué)模型，并給出求解方法。2. 具體求解以下算例，并給出你們實(shí)際使用的軟件名稱、命令和編寫的全部計(jì)算機(jī)源程序。算例載重量為 8 噸、平均速度為 60千米/小時(shí) 的送貨車輛從快遞公司（0）出發(fā)，為編號(hào)是 1，2，8 的8個(gè)客戶配送物資。某日，第個(gè)客戶所需物品的重量為噸（），在第個(gè)客戶處卸貨時(shí)間為小時(shí)，第個(gè)客戶要求送貨車輛到達(dá)的時(shí)間范圍 由表1給出?？爝f公司與各客戶以及各客戶間的公路里程（單位：千米）由表2給出。問當(dāng)日如何安排送貨車輛（包括出動(dòng)車輛的

6、臺(tái)數(shù)以及每一臺(tái)車輛的具體行駛路徑）才能使總運(yùn)行里程最短。 二、模型假設(shè)和符號(hào)說明2.1模型假設(shè)1、所有的貨運(yùn)車輛都沒有超載。2、 快遞公司能提供充足的貨運(yùn)車輛。3、 一個(gè)客戶點(diǎn)只有一輛貨運(yùn)車進(jìn)入和離開。4、 每條配送路徑都在貨運(yùn)車輛的配送范圍內(nèi)。5、 同一個(gè)客戶所需要的物品只由一輛貨運(yùn)車配送。6、 不考慮貨物的類型和貨運(yùn)車的車型，貨物可混裝。7、 不考慮貨運(yùn)車速度及運(yùn)輸時(shí)間因天氣、交通等因素的影響。8、 快遞公司與客戶以及客戶與客戶之間的距離、每天各客戶所需物品的重量均視為不變。2.2符號(hào)說明m 派出的貨運(yùn)車輛總數(shù)N 客戶的數(shù)量Q 每臺(tái)送貨車的載重量 第i個(gè)客戶與第j個(gè)客戶之間的距離 第i個(gè)客

7、戶所需貨品的重量v 每臺(tái)送貨車的平均速度 送貨車從客戶點(diǎn)i到客戶點(diǎn)j所需要的時(shí)間 送貨車到i的時(shí)間 送貨車在客戶點(diǎn)i卸貨的時(shí)間 第i個(gè)客戶要求送貨車到達(dá)的時(shí)間范圍的下限 第i個(gè)客戶要求送貨車到達(dá)的時(shí)間范圍的上限三、問題分析 這是一個(gè)單配送中心、多客戶點(diǎn)、非滿載、帶有時(shí)間窗的車輛配送路線問題（簡稱VRPTW）。問題的解決在于對(duì)一系列客戶點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使貨運(yùn)車有序地通過它們，在滿足一定的約束條件（各客戶點(diǎn)貨物需求量、交貨時(shí)間、車輛載重限制等）下，達(dá)到總行程最短的目的。 問題一：題目要求建立送貨車輛每天總運(yùn)行里程最短的一般數(shù)學(xué)模型。因?yàn)閱栴}要求制定的配送方案與車輛數(shù)目和時(shí)間（包括：卸貨時(shí)間

8、和送貨途中所需時(shí)間）有關(guān)，所以,首先對(duì)運(yùn)貨所需的車輛數(shù)進(jìn)行預(yù)估。通過討論時(shí)間窗口是硬窗口還是軟窗口，本題分別建立了兩個(gè)數(shù)學(xué)模型。對(duì)于硬窗口的VRPTW問題，送貨車必須在給定的時(shí)間范圍內(nèi)到達(dá)客戶點(diǎn)，所以加入對(duì)每輛運(yùn)貨車到達(dá)客戶點(diǎn)的時(shí)間限制，綜合求出總里程數(shù)最短的路線。而對(duì)于軟窗口的VRPTW問題，沒有嚴(yán)格的時(shí)間限制。但是，貨車早到或晚到產(chǎn)生的損失和懲罰會(huì)對(duì)配送公司的成本產(chǎn)生影響，所以，配送方案應(yīng)該保證車輛行駛里程最短，且盡可能的在客戶點(diǎn)要求的時(shí)間范圍內(nèi)到達(dá)。 問題二：基于問題一的模型，將具體數(shù)據(jù)代入模型，即可求出最短的路程方案。首先根據(jù)總配送量和運(yùn)貨車載重限制約束，求出送貨運(yùn)車派遣輛數(shù)。然后根據(jù)

9、配送中心目標(biāo)和客戶點(diǎn)之間距離等，確定目標(biāo)函數(shù)即最短行程模型。根據(jù)目標(biāo)函數(shù)和時(shí)間窗約束，采用數(shù)學(xué)軟件Lingo9.0編寫程序，最終得出各貨運(yùn)車的行程線路。四、模型的建立與求解4.1問題一的解答4.1.1模型的準(zhǔn)備為了安排路線，我們首先要對(duì)送貨車的數(shù)量進(jìn)行估計(jì)。約束條件越多，則安排線路越難，一輛車完成的任務(wù)越少，安排的車輛越多。我們可以按下述公式1估計(jì)所需貨車的數(shù)量。其中，表示取整，a為參數(shù)，且0a3- 1- 2- 0 0- 6- 4- 0 0- 8- 5- 7- 0運(yùn)行總里程：910千米 行程規(guī)劃示意圖：5、 模型的評(píng)價(jià)與改進(jìn)5.1模型的優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：一、考慮全面：通過討論客戶對(duì)送貨車輛的到達(dá)

10、是否有嚴(yán)格的時(shí)間限制，分別建立帶軟時(shí)間窗和硬時(shí)間窗的兩個(gè)模型。同時(shí)，考慮到軟時(shí)間窗的成本問題，創(chuàng)新性的將懲罰及損失之和作為目標(biāo)函數(shù)的一部分，保證了在行程最短的情況下配送成本不會(huì)較高。二、約束條件完整：每個(gè)約束條件都與題目的內(nèi)容一一對(duì)應(yīng)，且比較清楚的在論文中對(duì)每個(gè)式子的意義做了闡述。三、遺傳算法的應(yīng)用：利用遺傳算法解決車輛路徑規(guī)劃問題，有廣泛的適應(yīng)性與靈活性。缺點(diǎn)：1、 值的不同會(huì)影響估計(jì)出來的車輛數(shù)，僅用一種值來確定車輛數(shù)目局限性很大。 二、模型具有局限性：只適用于客戶點(diǎn)數(shù)較小且配送中心單一、送貨車型號(hào)相同的情況。5.2 模型的改進(jìn)根據(jù)估算車輛數(shù)目的公式：對(duì)進(jìn)行多次賦值。在保證車輛數(shù)目大于3輛

11、（Q=8，）的前提下，尋找接近于m的值，并帶入模型，將求出的解與m=3時(shí)求得的結(jié)果進(jìn)行對(duì)比，得到使行程最短的配送方案。六、參考文獻(xiàn)1中南大學(xué)，物流車輛調(diào)度問題研究，/p-.html，2013.8.72朱樹人 李文彬 匡芳君，一種帶軟時(shí)間窗的物流配送優(yōu)化遺傳算法，計(jì)算機(jī)工程與科學(xué)，27（12）,108-110,20073胡一萍 徐海，一種基于粗糙集的模糊數(shù)學(xué)形態(tài)學(xué)方法J，數(shù)據(jù)采集與處理，17（3），333-3364李軍 謝秉磊 郭耀煌，非滿載車輛調(diào)度問題的遺傳算法，系統(tǒng)工程理論與方法應(yīng)用，9（3）,235-239,20005周屹 李海龍 王銳，遺傳算法求解物

12、流配送中帶時(shí)間窗的VRP問題，吉林大學(xué)學(xué)報(bào)（理學(xué)版），46（2）,300-303,2008 6閻慶 邰蕾蕾，用混合遺傳算法解決有時(shí)間窗的車輛路徑規(guī)劃為題，安徽大學(xué)學(xué)報(bào)（自然科學(xué)版），31（2）,41-44,20077鄒彤 李寧 孫德寶，不確定車輛數(shù)的有時(shí)間窗的車輛路徑問題的遺傳算法，系統(tǒng)工程理論與實(shí)踐，第6期，134-138,2004 8張欽 李輝，帶有時(shí)間窗約束的車輛路徑問題的一種改進(jìn)遺傳算法，系統(tǒng)管理學(xué)報(bào)，19（5）,589-592,2010 9供應(yīng)鏈網(wǎng)絡(luò)物流配送與車輛路徑問題，/p-.html ，2013.8.7七、附錄1、表1客戶12345678（

13、噸）21.54.531.542.53（小時(shí)）121322.530.81, 44, 61, 24, 73, 5.52, 55, 81.5, 42、表2 0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000 3、 有關(guān)程序 MODEL:SETS: point

14、s/0,1,2,3,4,5,6,7,8/:f; point_aim/1,2,3,4,5,6,7,8/:timea,timeb,q,s; roads(points,points):d,x1,time_between; cars/1.3/; reach/1 2 3 4 5 6 7 8/:time_reach; road_car(roads,cars):x; task_car(points,cars):y; task_aim(point_aim,cars):y1;ENDSETSDATA:d=0 40 60 75 90 200 100 160 80 40 0 65 40 100 50 75 110 1

15、00 60 65 0 75 100 100 75 75 75 75 40 75 0 100 50 90 90 150 90 100 100 100 0 100 75 75 100 200 50 100 50 100 0 70 90 75 100 75 75 90 75 70 0 70 100 160 110 75 90 75 90 70 0 100 80 100 75 150 100 75 100 100 0;m=3;timea=1 4 1 4 3 2 5 1.5;timeb=4 6 2 7 5.5 2.5 8 4;q=2 1.5 4.5 3 1.5 4 2.5 3;s=1 2 1 3 2 2

16、.5 3 0.8;capacity=8;time_between=0 0.8 1.2 1.5 1.8 4 2 3.2 1.6 0.8 0 1.3 0.8 2 1 1.5 2.2 2 1.2 1.3 0 1.5 2 2 1.5 1.5 1.5 1.5 0.8 1.5 0 2 1 1.8 1.8 3 1.8 2 2 2 0 2 1.5 1.5 2 4 1 2 1 2 0 1.4 1.8 1.5 2 1.5 1.5 1.8 1.5 1.4 0 1.4 2 3.2 2.2 1.5 1.8 1.5 1.8 1.4 0 2 1.6 2 1.5 3 2 1.5 2 2 0;ENDDATAmin=sum(roads(i,j):d(i,j)*sum(cars(k):x(i,j,k);for(road_car:bin(x);for(task_car:bin(y);for(task_