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

快遞公司的配送問題摘要 配送是物流系統(tǒng)中非常重要的一個環(huán)節(jié)，在物流的各項成本中，配送成本占了相當高的比例，減少配送里程以降低物流配送成本成為物流管理過程中首要考慮的問題之一。本文在已知貨運車容量、各客戶所需貨物重量、快遞公司與客戶以及客戶與客戶之間的距離的條件下，建立了以單車場路徑問題模型（即VRP模型）為基礎、以車輛總行程最短為目標函數(shù)、以貨物運輸量小于汽車載重量以及在客戶要求的時間范圍內(nèi)運送貨物等為約束條件的單目標線性規(guī)劃模型。 對于問題一，本文建立了兩個模型：模型I：硬時間窗車輛路徑規(guī)劃模型 首先根據(jù)題目所給條件，對運貨所需的車輛數(shù)進行預估，然后結(jié)合貨物運輸量小于汽車載重量、一個客戶點的貨物僅由一輛車配送等約束條件，同時考慮線路的連通性和汽車到達客戶點的時間范圍，采用0-1規(guī)劃法建立使總運行里程最小的車輛路徑規(guī)劃模型。 模型II：軟時間窗車輛路徑規(guī)劃模型在模型I硬時間窗車輛路徑規(guī)劃模型的基礎上，將模型I中的關(guān)于時間范圍的約束條件，通過設定懲罰函數(shù)的系數(shù)，變成目標函數(shù)的一部分。本文在考慮路程最短的目標的同時，也要求盡可能在時間范圍內(nèi)到達。因此，建立了以成本（包括懲罰成本以及行駛過程中帶來的成本）最小為目標的函數(shù)，以運輸量小于汽車載重量以及線路的連通性等為約束條件，建立軟時間車輛路徑規(guī)劃模型。最后運用遺傳算法求解模型。對于問題二，根據(jù)題目所提供的數(shù)據(jù)，利用硬時間窗車輛路徑規(guī)劃模型。首先，根據(jù)貨運車的載重量和客戶點的需求總量，估計出運貨所需車輛數(shù)為3，然后，借助Lingo求解該模型。得到最優(yōu)路徑的總里程數(shù)為910千米，快遞公司每天的配送方案應為:每天出動3輛車。3輛車的行駛路徑分別為：0-3-1-2-0，0-6-4-0，0-8-5-7-0關(guān)鍵詞： VRPTW 遺傳算法 0-1規(guī)劃法 Lingo目錄一、問題重述2二、模型假設和符號說明2三、問題分析3四、模型的建立與求解44.1問題一的解答44.1.1模型的準備44.1.2模型的建立44.1.3模型的求解74.2問題二的解答84.2.1對貨運車輛數(shù)的估計84.2.2路線的規(guī)劃8五、 模型的評價與改進105.1模型的優(yōu)缺點分析105.2 模型的改進11六、參考文獻11七、附錄12一、問題重述某快遞公司在某個地區(qū)擁有一支貨運車隊，每臺貨運車輛的載重量（噸）相同、平均速度（千米/小時）相同，該快遞公司用這樣的車為若干個客戶配送物品，快遞公司與客戶以及客戶與客戶之間的公路里程（千米）為已知。每天，各客戶所需物品的重量（噸）均已知，并且每個客戶所需物品的重量都小于一臺貨運車輛的載重量，所有送貨車輛都從快遞公司出發(fā)，最后回到快遞公司。快遞公司每天的配送方案應當包括：當天出動多少臺車？行駛路徑如何？由此形成的當天總運行里程是多少？一個合格的配送方案要求送貨車輛必須在一定的時間范圍內(nèi)到達客戶處，早到達將產(chǎn)生等待損失，遲到達將予以一定的懲罰；而一個好的配送方案還應該給出使配送費用最小或總運行里程最短的車輛調(diào)度方案。該快遞公司希望你們：1. 建立送貨車輛每天總運行里程最短的一般數(shù)學模型，并給出求解方法。2. 具體求解以下算例，并給出你們實際使用的軟件名稱、命令和編寫的全部計算機源程序。算例載重量為 8 噸、平均速度為 60千米/小時 的送貨車輛從快遞公司（0）出發(fā)，為編號是 1，2，8 的8個客戶配送物資。某日，第個客戶所需物品的重量為噸（），在第個客戶處卸貨時間為小時，第個客戶要求送貨車輛到達的時間范圍 由表1給出?？爝f公司與各客戶以及各客戶間的公路里程（單位：千米）由表2給出。問當日如何安排送貨車輛（包括出動車輛的臺數(shù)以及每一臺車輛的具體行駛路徑）才能使總運行里程最短。 二、模型假設和符號說明2.1模型假設1、所有的貨運車輛都沒有超載。2、 快遞公司能提供充足的貨運車輛。3、 一個客戶點只有一輛貨運車進入和離開。4、 每條配送路徑都在貨運車輛的配送范圍內(nèi)。5、 同一個客戶所需要的物品只由一輛貨運車配送。6、 不考慮貨物的類型和貨運車的車型，貨物可混裝。7、 不考慮貨運車速度及運輸時間因天氣、交通等因素的影響。8、 快遞公司與客戶以及客戶與客戶之間的距離、每天各客戶所需物品的重量均視為不變。2.2符號說明m 派出的貨運車輛總數(shù)N 客戶的數(shù)量Q 每臺送貨車的載重量 第i個客戶與第j個客戶之間的距離 第i個客戶所需貨品的重量v 每臺送貨車的平均速度 送貨車從客戶點i到客戶點j所需要的時間 送貨車到i的時間 送貨車在客戶點i卸貨的時間 第i個客戶要求送貨車到達的時間范圍的下限 第i個客戶要求送貨車到達的時間范圍的上限三、問題分析 這是一個單配送中心、多客戶點、非滿載、帶有時間窗的車輛配送路線問題（簡稱VRPTW）。問題的解決在于對一系列客戶點，組織適當?shù)男熊嚶肪€，使貨運車有序地通過它們，在滿足一定的約束條件（各客戶點貨物需求量、交貨時間、車輛載重限制等）下，達到總行程最短的目的。 問題一：題目要求建立送貨車輛每天總運行里程最短的一般數(shù)學模型。因為問題要求制定的配送方案與車輛數(shù)目和時間（包括：卸貨時間和送貨途中所需時間）有關(guān)，所以,首先對運貨所需的車輛數(shù)進行預估。通過討論時間窗口是硬窗口還是軟窗口，本題分別建立了兩個數(shù)學模型。對于硬窗口的VRPTW問題，送貨車必須在給定的時間范圍內(nèi)到達客戶點，所以加入對每輛運貨車到達客戶點的時間限制，綜合求出總里程數(shù)最短的路線。而對于軟窗口的VRPTW問題，沒有嚴格的時間限制。但是，貨車早到或晚到產(chǎn)生的損失和懲罰會對配送公司的成本產(chǎn)生影響，所以，配送方案應該保證車輛行駛里程最短，且盡可能的在客戶點要求的時間范圍內(nèi)到達。 問題二：基于問題一的模型，將具體數(shù)據(jù)代入模型，即可求出最短的路程方案。首先根據(jù)總配送量和運貨車載重限制約束，求出送貨運車派遣輛數(shù)。然后根據(jù)配送中心目標和客戶點之間距離等，確定目標函數(shù)即最短行程模型。根據(jù)目標函數(shù)和時間窗約束，采用數(shù)學軟件Lingo9.0編寫程序，最終得出各貨運車的行程線路。四、模型的建立與求解4.1問題一的解答4.1.1模型的準備為了安排路線，我們首先要對送貨車的數(shù)量進行估計。約束條件越多，則安排線路越難，一輛車完成的任務越少，安排的車輛越多。我們可以按下述公式1估計所需貨車的數(shù)量。其中，表示取整，a為參數(shù)，且0a3- 1- 2- 0 0- 6- 4- 0 0- 8- 5- 7- 0運行總里程：910千米 行程規(guī)劃示意圖：5、 模型的評價與改進5.1模型的優(yōu)缺點分析優(yōu)點：一、考慮全面：通過討論客戶對送貨車輛的到達是否有嚴格的時間限制，分別建立帶軟時間窗和硬時間窗的兩個模型。同時，考慮到軟時間窗的成本問題，創(chuàng)新性的將懲罰及損失之和作為目標函數(shù)的一部分，保證了在行程最短的情況下配送成本不會較高。二、約束條件完整：每個約束條件都與題目的內(nèi)容一一對應，且比較清楚的在論文中對每個式子的意義做了闡述。三、遺傳算法的應用：利用遺傳算法解決車輛路徑規(guī)劃問題，有廣泛的適應性與靈活性。缺點：1、 值的不同會影響估計出來的車輛數(shù)，僅用一種值來確定車輛數(shù)目局限性很大。 二、模型具有局限性：只適用于客戶點數(shù)較小且配送中心單一、送貨車型號相同的情況。5.2 模型的改進根據(jù)估算車輛數(shù)目的公式：對進行多次賦值。在保證車輛數(shù)目大于3輛（Q=8，）的前提下，尋找接近于m的值，并帶入模型，將求出的解與m=3時求得的結(jié)果進行對比，得到使行程最短的配送方案。六、參考文獻1中南大學，物流車輛調(diào)度問題研究，/p-.html，2013.8.72朱樹人 李文彬 匡芳君，一種帶軟時間窗的物流配送優(yōu)化遺傳算法，計算機工程與科學，27（12）,108-110,20073胡一萍 徐海，一種基于粗糙集的模糊數(shù)學形態(tài)學方法J，數(shù)據(jù)采集與處理，17（3），333-3364李軍 謝秉磊 郭耀煌，非滿載車輛調(diào)度問題的遺傳算法，系統(tǒng)工程理論與方法應用，9（3）,235-239,20005周屹 李海龍 王銳，遺傳算法求解物流配送中帶時間窗的VRP問題，吉林大學學報（理學版），46（2）,300-303,2008 6閻慶 邰蕾蕾，用混合遺傳算法解決有時間窗的車輛路徑規(guī)劃為題，安徽大學學報（自然科學版），31（2）,41-44,20077鄒彤 李寧 孫德寶，不確定車輛數(shù)的有時間窗的車輛路徑問題的遺傳算法，系統(tǒng)工程理論與實踐，第6期，134-138,2004 8張欽 李輝，帶有時間窗約束的車輛路徑問題的一種改進遺傳算法，系統(tǒng)管理學報，19（5）,589-592,2010 9供應鏈網(wǎng)絡物流配送與車輛路徑問題，/p-.html ，2013.8.7七、附錄1、表1客戶12345678（噸）21.54.531.542.53（小時）121322.530.81, 44, 61, 24, 73, 5.52, 55, 81.5, 42、表2 0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000 3、 有關(guān)程序 MODEL:SETS: points/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 100 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.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_ai