1、課 程 設(shè) 計課程名稱: 交通運輸組織學 設(shè)計題目:聯(lián)華連鎖便利店配送線路優(yōu)化設(shè)計學生姓名:學 號:班 級:院系名稱:交通運輸工程學院 指導老師: 周騫、葉鴻、王佳2014 年 1 月交通運輸組織學課 程 設(shè) 計課程名稱:交通運輸組織學 設(shè)計題目: 聯(lián)華連鎖便利店配送線路優(yōu)化設(shè)計學生姓名:學 號:班 級:院系名稱:交通運輸工程學院 指導老師: 周騫、葉鴻、王佳 長沙理工大學課程設(shè)計任務(wù)書 交通運輸工程 學院 交通運輸 專業(yè)班課程名稱交通運輸組織學題目 聯(lián)華連鎖便利店配送線路優(yōu)化設(shè)計學生姓名學號同組設(shè)計者：無一、已知技術(shù)參數(shù)和設(shè)計要求1、已知技術(shù)參數(shù)與參考資料交通運輸部客貨運組織與管理相關(guān)標準與

2、規(guī)范董千里。交通運輸組織學M 。人民交通出版社，2008年李維斌。公路運輸組織學 M 。人民交通出版社，2008年崔書堂，朱艷茹。交通運輸組織學M。東南大學出版社，2010年戴彤焱。運輸組織學M。機械工業(yè)出版社，2008年2、設(shè)計要求本課程設(shè)計是針對學生學習和運用專業(yè)知識的綜合考核和檢查，是學生接受工程類基本訓練的重要環(huán)節(jié)，是交通運輸交通運輸組織學專業(yè)課程學習的必修內(nèi)容之一。本課程設(shè)計的特點是，內(nèi)容所涉及的知識面廣，有較強的系統(tǒng)性和綜合性，對建模、算法設(shè)計、繪圖、文本編寫等方面有較高的要求。本課程應(yīng)運用交通運輸組織學課程涉及的相關(guān)理論與方法，結(jié)合具體實踐背景，解決實際問題。要求所涉及方法、模型

3、與理論知識與本課程相關(guān)；有具體的實踐背景；課程實際要求完整、系統(tǒng)，從提出問題、解決問題與結(jié)論三個方面開展，思路清晰，條理清楚。二、課程設(shè)計應(yīng)完成的任務(wù) 1、詳述研究（設(shè)計）背景、意義與設(shè)計流程；2、圍繞課程中交通組織方面相關(guān)內(nèi)容，完成對其方法、模型的闡述與構(gòu)建；3、結(jié)合實際背景，采用以上理論，進行運輸組織優(yōu)化等針對性設(shè)計，提出方案；3、對方案結(jié)果進行分析。三、工作計劃本次課程設(shè)計安排時間為3周，2013年12月16日至2014年1月4日，具體工作計劃如下：1、2013年12月16日20日，項目背景資料的收集與整理；2、2013年12月21日23日，完成課程設(shè)計大綱；3、2013年12月24日2

4、013年12月29日，完成課程設(shè)計背景與基礎(chǔ)資料的分析部分書寫工作；4、2013年12月30日2014年1月1日，完成課程設(shè)計核心模型分析與問題解決部分的書寫工作；5、2014年1月2日2014年1月4日，完成繪圖與結(jié)論部分的書寫以及修改工作。四、課程設(shè)計完成提交文檔要求按照以下順序裝訂成冊：封面； 2、扉頁； 3、任務(wù)書； （4）指導書；5、目錄； 6、正文； 7、附錄（表格或圖紙）；8、成績評定表指導老師：同意按照任務(wù)書要求開展設(shè)計教研室意見：同意按照任務(wù)書要求開展設(shè)計教研室主任：時間：注：1、此任務(wù)書由指導老師填寫。如果不夠，可以加頁； 2、此任務(wù)書最遲必須在課程設(shè)計開始前一周下達給學生

5、；交通運輸組織學課程設(shè)計指導書一、課程設(shè)計目的與要求1、課程設(shè)計目的交通運輸組織學課程是交通運輸本科專業(yè)的必修課， 是一門理論與實踐結(jié)合緊密的核心課程。本課程設(shè)計是在該門課程的課堂教學完成之后，為鞏固課程涉及到的交通運輸組織學方面的方法、理論及應(yīng)用而開展的。通過課程設(shè)計，使學生能夠結(jié)合實際背景，應(yīng)用已學理論，解決實際問題，從而培養(yǎng)學生資料查閱能力、繪圖能力、理論聯(lián)系實際的能力、系統(tǒng)解決問題的邏輯思維能力等，為畢業(yè)論文設(shè)計及今后從事相關(guān)工作打下基礎(chǔ)。2、課程設(shè)計要求本課程設(shè)計要求學生根據(jù)課程涉及的相關(guān)內(nèi)容與方法，結(jié)合實際背景，系統(tǒng)解決交通運輸組織實際問題。從背景分析、提出問題、解決問題、主要結(jié)論

6、等幾個方面開展。要求課程設(shè)計具有系統(tǒng)性、完整性、與課程相關(guān)性并具有一定的研究深度。二、課程設(shè)計的依據(jù)與資料來源課程設(shè)計的依據(jù)：交通運輸部客貨運組織與管理相關(guān)標準與規(guī)范董千里。交通運輸組織學M 。人民交通出版社，2008年李維斌。公路運輸組織學 M 。人民交通出版社，2008年崔書堂，朱艷茹。交通運輸組織學M。東南大學出版社，2010年戴彤焱。運輸組織學M。機械工業(yè)出版社，2008年資料來源：指導教師提供相關(guān)資料；實際調(diào)研收集資料；相關(guān)書籍；網(wǎng)絡(luò)資料收集。三、課程設(shè)計學生應(yīng)完成的內(nèi)容（1）設(shè)計背景交代（實際現(xiàn)狀分析與問題分析），進行現(xiàn)狀分析，提出問題；（2）闡述解決問題的理論，構(gòu)建相關(guān)模型與優(yōu)化

7、算法；（3）提出優(yōu)化設(shè)計方案；（4）對優(yōu)化方案進行評價，得出相關(guān)結(jié)論。四、課程設(shè)計要求及其它1、時間安排：3周設(shè)計時間（2013年12月16日2014年1月4日），實際操作中，可提前進行相關(guān)資料的收集與大綱的完成；2、要求獨立完成，一人一題，每人提交1份打印的設(shè)計成果（A4）及電子文檔；3、格式要求：裝訂按照要求的順序依次裝訂成冊，文檔具體格式參考格式模板；4、紀律要求：集中在固定教室嚴格考勤，按時作息，一般不允許請假，如遇特殊情況，需要填寫請假條報院領(lǐng)導批準，否則按照每天曠課8節(jié)處理。另請假或曠課時數(shù)累計達全部設(shè)計時間的1/3以上，該課程設(shè)計按照零分計。運輸與物流工程系2013年12月目錄T

8、OC o 1-3 h u HYPERLINK l _Toc23092 前言 和掃描算法以及改進的最近插入法對建立的模型進行求解，對百源木業(yè)的配送路線進行優(yōu)化。最后對三種方法求得的結(jié)果進行比較分析，從而為聯(lián)華連鎖超市提供較合理的配送方案，以期減少配送里程，降低物流運輸成本，提高超市物流運作效率，客戶服務(wù)質(zhì)量和整體競爭力。第一章 聯(lián)華連鎖便利店背景和物流配送1.1 背景聯(lián)華超市創(chuàng)建于1991年5月，是上海首家以發(fā)展連鎖經(jīng)營為特色的超市公司，目前聯(lián)華已成為現(xiàn)今中國最大的商業(yè)零售企業(yè)，形成了大型綜合超市（大賣場）、超級市場、便利店等多元業(yè)態(tài)聯(lián)動互補的競爭優(yōu)勢。在上海、北京、天津、江蘇、浙江、安徽、江西

9、、廣東、山東、山西、河南、河北、遼寧、吉林、新疆、內(nèi)蒙等20多個省市和自治區(qū)的100多個城市建立了強大的連鎖經(jīng)營網(wǎng)絡(luò)，是消費者最信賴的商業(yè)品牌。發(fā)展壯大后的聯(lián)華著力打造核心競爭力，在戰(zhàn)略創(chuàng)新、經(jīng)營創(chuàng)新、管理創(chuàng)新、技術(shù)創(chuàng)新等方面不斷取得新突破。聯(lián)華在全國建起了商品采購網(wǎng)絡(luò)，建成了國內(nèi)首家大型智能化配送中心，先進的計算機信息系統(tǒng)已經(jīng)覆蓋了聯(lián)華的所有門店，實現(xiàn)了商業(yè)管理的自動化。2003年銷售規(guī)模達 200多億元，門店數(shù)近 2600家。再次以雄厚的實力奠定了在中國零售業(yè)的龍頭地位。 聯(lián)華超市股份有限公司，有“零售連鎖推土機” 之稱，至2004年，聯(lián)華公司以營業(yè)額計已連續(xù)6年位列中國零售業(yè)榜首，大型綜

10、合超市、超級市場及便利店是三大主要經(jīng)營零售業(yè)態(tài)。2004年以聯(lián)華為首的中國第一大零售集團百聯(lián)集團銷售規(guī)模達6762714萬元、5493門店數(shù)個，其中聯(lián)華超市公司銷售額為3068494萬元。廣西聯(lián)華超市股份有限公司（前身為廣西佳用商貿(mào)股份有限公司），主要經(jīng)營業(yè)態(tài)有大型會員制超市、綜合超市、社區(qū)超市、便利店，公司共代理和分銷國內(nèi)外知名日用化妝品和食品品類3000多個。是目前廣西連鎖店數(shù)量最多、年銷售總額最大、代理商品品牌最多、企業(yè)發(fā)展最快的民營商業(yè)企業(yè)。據(jù)全國工商聯(lián)統(tǒng)計，廣西聯(lián)華位列2002年中國民營企業(yè)500強第392位，中國連鎖經(jīng)營協(xié)會統(tǒng)計，廣西聯(lián)華位列連鎖企業(yè)百強第 85位，全國連鎖超市百強

11、第51位，全國成長企業(yè)百強第48位。連續(xù)12年獲得廣西區(qū)工商管理局評為“重合同、守信用”單位。廣西聯(lián)華成立于1991年，也是在中國成立較早的連鎖超市公司之一。目前擁有53家直營店，04年銷售額8億多元，涉及柳州、桂林、河池、來賓、貴港等五地市，經(jīng)營面積近10萬平方米。其中柳州有直營店39家，經(jīng)營面積 5萬多平方米。便利店，顧名思義是一種提供便利的商店。一般來說它的營業(yè)面積不大，約在60100平方米左右，有數(shù)名工作人員，能提供 3000種左右人們?nèi)粘Ｉ畋匦璧男∩唐?，并能提供一些人們?nèi)粘Ｋ璧姆?wù)。每天的營業(yè)時間一般長達16小時或24小肘通宵服務(wù)。由于營業(yè)面積不大，它可以深入到各個居民小區(qū)、車站

12、、碼頭等，貼近人們的生活，給人們帶來了極大的方便?，F(xiàn)在人們不難在各居民小區(qū)，各條馬路上發(fā)現(xiàn)便利店的身影。由于便利店規(guī)模較小，故在管理上更顯重要，采用連鎖經(jīng)營的方式，所有下屬便利門店采用統(tǒng)一的企業(yè)形象設(shè)計，統(tǒng)一的管理模式，能取得很好的品牌效應(yīng)。統(tǒng)一的進貨方式可保證所進商品的質(zhì)量，同時降低采購成本。統(tǒng)一的銷售價格，又可使顧客感到滿意和放心。該公司經(jīng)過幾年來的努力，已取得了良好的經(jīng)營業(yè)績。該公司各便利店所供商品的進貨渠道主要有以下三個方面。少部分鮮活商品（如面包。牛奶、蔬菜等）每天由供貨商直接送到各便利門店（以下簡稱門店）。公司自己建有一個冷凍倉庫，負責各門店冷凍商品的供應(yīng)，如冷凍肉食、禽類、速凍食

13、品等。公司還有一個配貨中心，負責其他常溫商品的供應(yīng)，如酒類、飲料、日用小商品等。門店根據(jù)各自的經(jīng)營狀況，在要貨當日的上午10時前，將要貨信息輸入電腦，經(jīng)通訊線路傳送到有關(guān)配貨中心和冷凍倉庫，而配貨中心等收到各門店的要貨信息，經(jīng)匯總后，組織好相應(yīng)商品，及時送到各門店。公司規(guī)定各門店每兩天可要貨一次。按目前400多家門店的總規(guī)模，每天要貨的門店達200多家，且分布在全市各個地方。冷凍倉庫由于供應(yīng)品種較少，根據(jù)經(jīng)驗，每輛送貨汽車一次滿載可送20家門店，每天每車送貨2次，現(xiàn)有車輛6輛。配貨中心，由于供應(yīng)品種較多，共有車輛11輛。如何合理地調(diào)度這些送貨車輛，在保證各門店要貨能及時得到滿足的前提下，使送貨

14、車輛經(jīng)過的路途最少，是一個十分有意義的工作。桂林市聯(lián)華連鎖便利店隸屬于廣西聯(lián)華超市股份有限公司，本文探討的就是桂林市的設(shè)立的十多家聯(lián)華連鎖便利店的配送路線情況。本文將對這十多家門店與運輸車輛進行調(diào)度優(yōu)化，闡述物流配送過程中配送線路設(shè)計與線路優(yōu)化問題。1.2 配送路線優(yōu)化的必要性和可行性分析1.2.1 配送路線優(yōu)化設(shè)計的必要性物流是現(xiàn)代企業(yè)發(fā)展的動脈，特別是對于商業(yè)連鎖企業(yè)來說，物流就是企業(yè)發(fā)展的咽喉，是制約很多企業(yè)發(fā)展的瓶頸。而隨著商業(yè)競爭的加劇，傳統(tǒng)的低層次的競爭（如銷售的競爭）在消費群體的消費心理日漸理性的今天，已轉(zhuǎn)化成了產(chǎn)、供、銷立體化的競爭，誰能在產(chǎn)供銷鏈條上減少中間的環(huán)節(jié)、降低經(jīng)營成

15、本，誰就能夠確立巨大的競爭優(yōu)勢。隨著全球經(jīng)濟一體化、顧客需求的個性化和多樣化發(fā)展，產(chǎn)品更新替換速度在不斷加快、產(chǎn)品的生命周期也不斷縮短，物流運輸配送變得越來越復雜，物流成本也變得越來越高。為了降低風險，減少物流成本，處于物流供應(yīng)鏈上各環(huán)節(jié)的部門或單位都紛紛采取各種措施以適應(yīng)這種多品種、小批量。多頻度的物流配送服務(wù)需求，如降低庫存水平，減少訂貨量，增加訂貨頻率，實行按訂單生產(chǎn)等措施，這在某種程度上滿足了發(fā)展的要求，但運輸和配送成本一直居高不下。造成物流運輸成本居高不下的主要原因是出現(xiàn)了一些不合理的運輸和方式，如對流運輸、迂回運輸、非最短路徑運輸和配送、非滿載運輸?shù)取＿@些都會致使運輸和配送服務(wù)水平

16、難以提高，因此對運輸和配送問題進行優(yōu)化就變得非常有意義。聯(lián)華超市配送中心的配送路線都是根據(jù)人的主觀意識來制訂的，缺乏科學依據(jù)，車輛裝載率不高，路徑也不是最短，造成了配送成本的居高不下，并且造成了資源的浪費。配送線路合理與否對配送速度、成本、效益影響很大，采用科學、合理的方法來確定配送線路，是配送活動中一項非常重要的工作。合理的選擇配送線路，對企業(yè)和社會都具有重要的意義。1.2.2 配送路線優(yōu)化設(shè)計的可行性聯(lián)華超市配送中心配送路線的優(yōu)化設(shè)計屬于車輛優(yōu)化調(diào)度問題，而求解車輛優(yōu)化調(diào)度問題的主要方法精確算法、啟發(fā)算法和智能算法。而精確算法的計算量和計算時間隨著車輛優(yōu)化問題規(guī)模的增大呈指數(shù)增長，對于較大

17、規(guī)模的車輛優(yōu)化調(diào)度問題不適用。啟發(fā)式算法當中的節(jié)約里程法，計算步驟簡單，計算速度快，且易于考慮各種實際問題，并不追求問題的最優(yōu)解，而強調(diào)問題解的滿意性，可以高效地得到問題的近似最優(yōu)解。本文針對零售業(yè)的實際情況，即各個門店對于某些常用商品的需求是穩(wěn)定而不間斷的，在研究這類問題的時候，不需要各個門店在不同時期對于不同貨物的需求，只要每次配送固定的商品即可，對于這類問題，本文建立了問題一的模型，這種模型往往運用于配送中心的某些常用的子系統(tǒng)，如某些常用的商品的配送，這類問題講求簡單高效，追求最快的滿意解。因此，用節(jié)約里程法解決問題一這類模型是可行的。而對于更為復雜的配送模型，比如大量的非常規(guī)商品的配送

18、，不同的門店需要不同的商品，針對這類錯綜復雜的模型，必須借助現(xiàn)代化的智能算法，使得配送方案更為科學合理，準確易行。因此，用智能算法當中的遺傳算法來解決問題二這類模型是可行的。1.3 配送路線優(yōu)化的意義配送合理化與否是配送決策系統(tǒng)的重要內(nèi)容，配送線路的合理與否又是配送合理化的關(guān)鍵。選擇合的理配送路線，對企業(yè)和社會都具有很重要的意義。 對企業(yè)來說，(1)優(yōu)化配送路線，可以減少配送時間和配送里程，提高配送效率，增加車輛利用率，降低配送成本;(2)可以加快物流速度，能準時、快速地把貨物送到客戶的手中，提高客戶滿意度;(3)使配送作業(yè)安排合理化，提高企業(yè)作業(yè)效率，有利于企業(yè)提高競爭力與效益。 對社會來說

19、，它可以節(jié)省運輸車輛，減少車輛空載率，降低了社會物流成本，對其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。與此同時，還能緩解交通緊張狀況，減少噪聲、尾氣排放等運輸污染，對民生和環(huán)境也有不容忽視的作用。第二章 聯(lián)華超市配送路線作業(yè)現(xiàn)狀目前聯(lián)華的物流體系是，所有貨物由供貨商直接送達店面，這種方式雖然靈活，但影響了供貨速度，也加重了供貨商的負擔。由于聯(lián)華各門店自行采購，供貨商不一，大大影響了供貨速度；并且，聯(lián)華目前的供貨方式也加重了供貨商負擔。隨著中國零售市場白熱化競爭的日趨激烈，建設(shè)區(qū)域物流配送中心無疑可以幫助聯(lián)華加快店面更新速度，鞏固市場。而聯(lián)華超市也應(yīng)在各個市區(qū)確立商品配送中心，以后供應(yīng)商只要將貨物運送

20、至物流中心，各分店商品的配送統(tǒng)一由物流中心來實現(xiàn)。作為便利店模式的首推者，“靈活”和“適應(yīng)”一直被視為聯(lián)華成功改變中國人購物習慣的法寶。店長的“欽點”讓聯(lián)華許多貨架上充盈著本地的產(chǎn)品。加上所開門店位置多位于大中型城市，這讓門店直送方式有了很強的操作性。聯(lián)華不用多費心思經(jīng)營物流，只需讓供應(yīng)商們接上它的訂單生成系統(tǒng)，再順手給個“deadline”（送貨的最后期限），一切就告萬事大吉?！靶∨?，多頻次”的訂貨原則，保證聯(lián)華可以盡量減少門店庫存。而使用時段限制，過期則不收貨的“殘酷”手段，來保證供應(yīng)商的準時到貨率，在中國也被認為是簡明有效的。近乎于零的物流費用和基本合格的配送質(zhì)量，曾讓聯(lián)華人頗感自豪。

21、真正傷腦筋的是供應(yīng)商們，本來利潤就不高，面對聯(lián)華在物流上的不作為，還得自己挖空心思節(jié)約成本。目前，聯(lián)華的商品配送分幾種情況，大部分情況是通過第三方物流實現(xiàn)的，費用由供應(yīng)商承擔。以北京地區(qū)為例，給聯(lián)華做配送的主要有上海成協(xié)，朝百批發(fā)，大榮物流等幾家公司。有一小部分品牌，包括可口可樂、寶潔和百事可樂等大公司以及一些生鮮食品等都具有直送的能力。有些聯(lián)華的門店還習慣于將降價損失、損耗和營業(yè)額、毛利率指標的完不成數(shù)，轉(zhuǎn)嫁給供應(yīng)商來承擔，也就是說供應(yīng)商與總部談好的交易條件到了門店是要附加的，因為聯(lián)華是最大的，供應(yīng)商也無可奈何；另外據(jù)悉，聯(lián)華近期采取的分區(qū)采購政策，也使得供貨商從過去習慣于以一對一的模式變成

22、了以一對多，這樣無疑加大了供貨商的運營成本，從而導致他們抱怨多多。第三章 配送線路優(yōu)化模型及算法3.1配送線路優(yōu)化的模型3.1.1多回路運輸VRP模型多回路運輸問題是現(xiàn)實中很普遍的一種調(diào)配問題，特別對于有大量服務(wù)對象的實體，例如擁有一個上千客戶的企業(yè)。此類調(diào)配的核心問題是如何對車輛進行調(diào)度。因此，VRP（Vehicle Routing Problem）模型也應(yīng)運而生，成了解決多回路問題的一個相當成功的模型。該問題研究目標是：對一系列顧客需求點設(shè)計適當?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等），達到一定的優(yōu)化目標（如里程最短，費用最

23、小，時間盡量少等）。它涉及了多輛交通工具的服務(wù)對象的選擇和路徑確定兩方面問題。一個典型的VRP模型可以如下表述：（1）基本條件 現(xiàn)有m輛相同的車輛停在一個共同的源點，它需給n個客戶提供貨物，顧客為。（2）模型目標 確定所需的車輛數(shù)N，并指派這些車輛到一個回路中，同時包括回路內(nèi)的路徑安排和調(diào)度，使總費用最小。（3）限制條件：N不大于m；每一個訂單都要完成；每輛車完成任務(wù)后都要回到源點；車輛的容量限制不能超過；特殊問題還需考慮時窗限制；運輸規(guī)章限制。3.1.2 PDPTW問題模型PDPTW問題是VRP問題的一個很有用的擴展，近段時期引起越來越多的研究者的注意，許多新的優(yōu)化思想和優(yōu)化方法被引入到此問

24、題中，并產(chǎn)生了一定的影響。PDPTW問題（Pickup and Delivery Problem with Time Windows，帶時間窗口的裝卸貨問題）是為一個車隊尋找最優(yōu)的運輸路徑來滿足所有客戶的運輸需求。車隊的每一輛車從車庫出發(fā)，沿優(yōu)化的路徑為客戶服務(wù)并最終返回車庫。每一輛車都給定最大容量和出發(fā)、返回車庫。每個運輸需求指定一個裝貨點、一個卸貨點和運輸貨物量。裝貨點、卸貨點以及車庫都有時間窗口。車輛必須在規(guī)定的時間窗內(nèi)訪問裝、卸貨點。也就是說，在運輸網(wǎng)絡(luò)中，已知待服務(wù)的裝、卸貨點和車庫的位置和時間窗口、車輛的最大容量以及運輸貨物量的前提下，設(shè)計車輛運輸路徑，使運輸成本最小化。PDPTW

25、的解是路徑的集合，每一輛車對應(yīng)一條路徑，包括以下方面：1、需要用到的車輛數(shù)目；即，有多少條路徑 2、 每輛車訪問每一個點的順序以及時刻PDPTW問題中，要求滿足的約束條件主要有以下幾種：1) 時間窗口約束：車輛必須在規(guī)定的時間窗內(nèi)服務(wù)裝貨點或卸貨點。如果車輛在 之前到達點 ，必須在點 等待到 才能開始裝卸貨。車輛在 時刻之后到達點 ，則無法按時完成該點的裝卸貨任務(wù)，因而是不允許的。2） 訪問約束：車輛到客戶指定的裝貨點裝貨，然后運輸?shù)较鄳?yīng)的卸貨點卸貨。每一個點都必須被一輛車服務(wù)且只能服務(wù)一次。3） 車庫約束：車輛必須從車庫出發(fā)到某一裝貨點，最后從某一卸貨點返回車庫。車輛返回車庫后不允許再次出發(fā)

26、。4） 成對約束：一個客戶需求的裝貨點 和其對應(yīng)的卸貨點 必須被同一輛車訪問。5） 次序約束：客戶需求的裝貨點 必須在對應(yīng)的卸貨點 之前被訪問。6） 容量約束：任何時刻車輛所裝貨物量之和不能超過車輛的最大容量。上述約束是PDPTW問題中常見的幾種約束條件。另外還會根據(jù)實際情況的要求增加一些附加約束，如車輛類型與貨物類型之間的類型匹配約束，司機的最大工作時間約束等。PDPTW問題的優(yōu)化目標也是總運輸成本最小。一般來說，與總運輸成本有關(guān)的費用包括：車輛的固定代價，是運輸代價中最重要的部分，要最大可能的減少使用的車輛數(shù)；與車輛行駛距離有關(guān)的代價。3.2 配送問題的求解算法車輛配送問題的求解算法有很多

27、種，但究其本質(zhì)來講，基本分為最優(yōu)化算法和啟發(fā)式算法兩大類。3.2.1最優(yōu)化算法最優(yōu)化算法，也稱之為精確算法，就是指能夠通過有限的計算和推理得到優(yōu)化問題的最優(yōu)解的算法。在配送問題中，所謂最優(yōu)化算法就是找到一組路徑集合，使得其目標函數(shù)值比其它任何一組可行路徑集合的目標函數(shù)值更好。常用的最優(yōu)化算法主要有：分枝定界算法、動態(tài)規(guī)劃算法和整數(shù)規(guī)劃。通常情況下，NP-hard問題的精確解法的計算量較大，而且隨著問題規(guī)模的增大計算量會呈爆炸式的增長，因此在實際問題中最優(yōu)化算法的應(yīng)用范圍有限。3.2.2啟發(fā)式算法啟發(fā)式算法是通過對過去經(jīng)驗的歸納推理以及實驗分析來解決問題的方法，即借助于某種直觀推斷或試探的方法。

28、啟發(fā)式方法要求分析人員必須運用自己的感知和洞察力，從與研究問題有關(guān)而比較具體的模型及算法中尋求其間的聯(lián)系，從中得到啟發(fā)，去發(fā)現(xiàn)適于解決該問題的思路和途徑。用啟發(fā)式方法求解問題時強調(diào)“滿意”。常常是得到滿意解，決策者就認為可以了，而不去追求最優(yōu)解。之所以這樣是因為：(1) 很多問題不存在嚴格的最優(yōu)解（如目標之間存在矛盾的多目標問題），此時對目標的滿意性比最優(yōu)性更能描述人們的選擇行為。(2) 得到某些問題最優(yōu)解的成本太大。(3) 從實際出發(fā)，有時探求問題的最優(yōu)解沒有意義。對于NP-Hard問題，人們自然會想到啟發(fā)式的算法。啟發(fā)式的算法就是根據(jù)某種啟發(fā)式的信息對已知的可行解進行改善，通過若干次的迭代

29、獲得相對滿意的解。和精確算法相比，啟發(fā)式的算法不能保證得到全局最優(yōu)解，但是實現(xiàn)起來相對簡單。由于車輛運輸調(diào)度問題是NP-hard問題，而現(xiàn)實中該問題規(guī)模一般很大，因此想以能夠接受的運算速度找到最優(yōu)解是不可能的。而啟發(fā)式算法可以在相對短時間內(nèi)找到“滿意”解，為此研究人員把精力主要放在構(gòu)造高質(zhì)量的啟發(fā)式算法上。目前已提出的求解車輛運輸調(diào)度問題的啟發(fā)式算法很多，主要分為經(jīng)典啟發(fā)式算法和現(xiàn)代啟發(fā)式算法兩類。3.2.3節(jié)約算法利用節(jié)約法確定配送線路的主要出發(fā)點是，根據(jù)配送中心的運輸能力（包括車輛的多少和載重量）和配送中心到各個用戶以及各個用戶之間的距離來制訂使總的車輛運輸?shù)膖.km（噸數(shù)乘上公里數(shù)）數(shù)最

30、小的配送方案。為了便于介紹節(jié)約法的基本思想，設(shè)：配送的是一種貨物；各用戶的坐標（x，y）及需求量均為已知；配送中心有足夠的運輸能力。利用節(jié)約法制訂出的配送方案除了送總 t.km 數(shù)最小外，還滿足以下條件：方案能滿足所有用戶的要求；不使任何一輛車超載；每輛車每天的總運行時間或行駛里程不超過規(guī)定的上限；能滿足用戶到貨時間要求。（2）節(jié)約法的基本思想如圖3-1所示，設(shè)A 點為配送中心，它分別向用戶B 和C送貨。設(shè)A 到B 和C 的距離為a和b，兩個用戶B、C 之間的距離為c，送貨方案只有兩種，如圖中（a）和（b）所示。BBCCB(a)（b）節(jié)約法的送貨方案AA圖3-1 節(jié)約法配送方案圖圖中（a）方案

31、是從配送中心A 向用戶B、C分別單獨送貨，配送路線為：ABA，ACA；總的配送距離為：Da=2a + 2b圖（b）方案是從配送中心向用戶，A 依次送貨，配送線路為：ABC；總的配送距離為：Db=a + b + c對比這兩個方案，哪個更合理呢？這就要看 Da 和Db 哪個最小，配送距離月小則說明方案越合理，由總距離公式可得出：Da Db =2a + 2b a b c = a + b c如果把圖中的A、B、C看成為一個三家性的三個頂點，那么a、b、 c 則是這個三角形三條邊的長度。由三角形的幾何性質(zhì)可知，任意兩條邊之和均大于第三邊(即a + b c)，有a + b c 0 。因此，可以認定Da D

32、b的結(jié)果是大于零的，即：Da Db可以看出，（b）方案優(yōu)于（a）方案，這種分析方案優(yōu)劣的思想就是節(jié)約法的基本思想。根據(jù)節(jié)約法的基本思想，如果有一個配送中心分別向 N 個用戶配送貨物，在汽車載重能力允許的前提下，每輛汽車的配送線路上經(jīng)過的用戶個數(shù)越多，則配送線路越合理，總配送距離越小。第四章基于節(jié)約算法的配送路線優(yōu)化聯(lián)華連鎖便利店在桂林市的分布具體如下圖所示：圖4-1 桂林市聯(lián)華便利超市分布圖從上圖可看出聯(lián)華便利店在市區(qū)內(nèi)分布較為均勻，在環(huán)城路上零星分布著幾家，結(jié)合桂林市實際城區(qū)分布特點以及費用考慮，聯(lián)華便利店的配送中心定在桂林市七星路高新區(qū)附近，這里既有良好的倉庫設(shè)備，交通情況也非常便利，同時

33、又靠近桂林市區(qū)，配送方便，費用合理。以下是每個分店（一年365天）平均每天的需求量情況表：表4-1 聯(lián)華便利店分店平均每天需求量表分店123456需求量(KG)302295292333289354分店789101112需求量(KG)337349361336306314現(xiàn)有路線是固定不變且為已知,每條線路行駛距離見下表所示：表4-2 聯(lián)華便利店距聯(lián)華配送中心最短距離（公里）PP11P1P21.62.4P2PP3P41.80.7532.7P4P2.5P5PP6P73.42.71.6P7P0.731.4P8P1.20.82P9P0.731.61.32P10P1.93.4P11PP12設(shè)每個車輛的運輸

34、能力是2噸，根據(jù)案例可知，聯(lián)華平均每天所用車輛數(shù)為2輛?，F(xiàn)在用節(jié)約算法對該配送線路問題進行求解。根據(jù)配送中心與分店之間,分店與分店之間的距離距離表，計算出用戶間的節(jié)約里程。表4-3 節(jié)約值矩陣表302P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P5P5354P3.45.9P6337P71.705.3P7349P74.8P8361P91.704.54.28P9336P765.74.5P10306P4P11314P121.70從表3-2中選出節(jié)約值最大值為7.1，其對應(yīng)的兩點為P10、P12。P10、P12兩處的需求量之和為650kg，未超過一輛車的運

35、輸能力2t，因此，連接P10、P12成回路，即P-P10-P12-P。再將頂點P10和P12的節(jié)約值賦為0。結(jié)果如表3-3所示。表4-4 除P10與P12連接點節(jié)約值表302P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P5P5354P3.45.9P6337P71.705.3P7349P74.8P8361P91.704.54.28P9336P765.74.5P10306P4P11314P121.704.605.2從表3-3中選出節(jié)約值最大為6.97，如果連接P6和P10 ，則與上述線路合并，其總需求量為986kg，未超過一輛車的運輸能力2t，因此，連

36、接P6形成回路，即P-P6-P10-P12-P。再將頂點P6和P10的節(jié)約值賦為0。繼續(xù)選出節(jié)約值最大為6.8，其對應(yīng)兩個頂點為P7、P12。如果連接P7和P12 ，則與上述線路合并，其總需求量為1323kg，未超過一輛車的運輸能力2t，因此，連接P7形成回路，即P-P6-P10-P12-P7-P。再將頂點P7和P12的節(jié)約值賦為0。由以上連接過程可看出P10點分別與P6、P12兩點連接形成回路，P12點也分別與P7、P10兩點連接形成回路，因此將所有與P10點、P12點的連接的節(jié)約值賦為0。見下表：表4-5 剩余節(jié)約值表（一）302P1295P20.2P2292P30.20.2P3333P4

37、2.050.40.4P4289P5P5354P3.45.9P6337P71.705.3P7349P74.8P8361P91.704.54.28P9336P10000000000P10306P0P11314P1200000000000繼續(xù)選出節(jié)約值最大為5.9，其對應(yīng)兩個頂點為P5、P6。如果連接P5和P6 ，則與上述線路合并，其總需求量為1612kg，未超過一輛車的運輸能力2t，因此，連接P5形成回路，即P-P5-P6-P10-P12-P7-P。此后，P6兩端連接點也已確定，因此將P6點與其他連接點的節(jié)約值賦值為0。見表3-5：表4-6 剩余節(jié)約值表（二）302P1295P20.2P2292P

38、30.20.2P3333P42.050.40.4P4289P5P5354P600000P6337P71.700P7349P3.34.804.8P8361P91.7012.93.504.54.28P9336P10000000000P10306P2.12.500P11314P1200000000000繼續(xù)選出節(jié)約值最大為4.8，其對應(yīng)的頂點為P5、P8和P7、P8以及P7、P11三對頂點。綜合考慮，連入回路的應(yīng)為P5、P8和P7、P11兩對頂點。連接P5、P8和P7、P11，則與上述線路合并，其總需求量為2207kg，超過一輛車的運輸能力2t，因此，結(jié)合店鋪分布情況考慮，將P11編入回路中，即形成

39、P-P5-P6-P10-P12-P7-P11-P回路，此時該回路的運輸總量為1918kg。因為只有兩輛運輸車，因此剩下的六點將形成另外一條回路，因為剩余點的總需求量為1932kg，小于運輸車輛的額定載重，因此下面將不再考慮是否超過載重。將第一條回路所包含的點與其他點連接所節(jié)約的節(jié)約值賦為0，得到的剩余點的節(jié)約值表如下：表4-7 除回路1剩余點節(jié)約值表302P1295P20.2P2292P30.20.2P3333P42.050.40.4P4289P50000P5354P600000P6337P7000000P7349P3.3000P8361P91.7012.90004.28P9336P10000

40、000000P10306P110000000000P11314P1200000000000從上表可看出節(jié)約值最大值為4.28，其對應(yīng)的兩點為P8、P9，因此，連接P8、P9成回路，即P-P8-P9-P。再將頂點P8和P9的連接點節(jié)約值賦為0。重復回路1的操作，得到回路2的連接狀況為：P-P1-P4-P8-P9-P3-P2-P，運輸量為1932kg。兩條回路節(jié)約的里程為：回路1（P-P5-P6-P10-P12-P7-P11-P）：5.9+6.97+7.1+6.8+4.8=31.57km回路2（P-P1-P4-P8-P9-P3-P2-P）：2.05+3.3+4.28+1+0.2=10.83km所以

41、配送線路優(yōu)化后，聯(lián)華超市配送線路總節(jié)約里程為42.4公里。具體線路圖如下：圖4-2 聯(lián)華超市優(yōu)化后配送線路圖第五章方案綜合評價5.1 算法的適用度評價配送運輸通常是一種短距離、小批量、高頻率的運輸形式。如果單從運輸?shù)慕嵌葋砜矗菍Ω删€運輸?shù)囊环N補充和完善，屬于末端運輸、支線運輸，以高質(zhì)量的服務(wù)為目標，以盡可能滿足客戶要求。從配送中心把貨物送到所需的各個分店，有很多種不同的路線選擇方案。合理的選擇配送線路，對企業(yè)和社會都具有很重要的意義。為將貨物送給分店，需要從一個或多個配送中心組織配送運輸。一般地一個或多個配送中心目的地存在一個道路網(wǎng)，如何在這張道路網(wǎng)上綜合考慮各線路車流量、道路狀況、客戶的

42、分布狀況、配送中心的選址、車輛額定載重量及其他車輛運行限制等因素，找出一條最佳的運輸線路解決方案，達到節(jié)省運行距離、運輸時間和運行費用的目的就是線路設(shè)計的意義所在。進行配送線路優(yōu)化時，必須要有明確的目標，遵循基本的原則。配送路線方案目標的選擇可以從以下幾個方面來考慮。（1）配送效益最高或配送成本最低（2）配送里程最短（3）配送服務(wù)水準最優(yōu)（4）配送勞動的消耗最小求解最短路徑的配送路線的方法很多，結(jié)合具體的要求，在此設(shè)計中采用了節(jié)約里程法來求解。啟發(fā)式算法是從尚未安排的車輛、運輸任務(wù)或行駛路徑中按照構(gòu)造算法進行選擇，知道所有任務(wù)和車輛均被調(diào)度為止。構(gòu)造的每一步，根據(jù)某個判別函數(shù)，把當前的線路構(gòu)形

43、和另外的構(gòu)形進行比較并加以改進，以最小代價把一個不在當前構(gòu)形上的需求對象插入進構(gòu)形，最后得到一個較好的可行構(gòu)形。我們根據(jù)啟發(fā)式算法中的節(jié)約里程法得到優(yōu)化后的線路。通過兩種方法的比較我們可以發(fā)現(xiàn)在此設(shè)計中用節(jié)約里程法計算出來的配送路線算出來的配送路線有實用性。通過對物流配送線路的優(yōu)化，可以派出更少的車輛來滿足裝貨的要求，使車輛完成配送任務(wù)的同時行駛的距離最少。一方面可以緩解交通擁堵，另一方面可以減少汽車造成的污染。為廣大人民造福。配送線路的優(yōu)化產(chǎn)生了一定的經(jīng)濟效益和社會效益。同時，我們雖然計算出了比較合理的配送路線，但模型也存在著一定的缺陷。在計算過程中也將一些因素理想化了，與實際情況不完全相符

44、。所以在實際中，我們可以將更多的因素考慮進去，設(shè)計出更加合理的配送路線。5.2加強線路管理水平隨著配送中要求成本費用要盡可能降低，特別是目前多批次、小批量配送的發(fā)展，要求配送中心采用效率化的配送方法。聯(lián)華超市為實現(xiàn)效率化的配送，應(yīng)越來越重視配車計劃管理、提高裝載率以及車輛運行管理。從總體上看，降低配送成本的措施就是追求車輛運行的效率化，提高車輛運行效率，這就需要建立有效的火車追蹤系統(tǒng)，即在車輛上配置一個全球定位系統(tǒng)（GPS），通過這種終端一方面對貨物的在途情況進行控制。5.3 公司采用該方案的整體評價在此設(shè)計中，我們針對聯(lián)華便利店以桂林市為例，對桂林市配送中心的配送區(qū)域進行配送路線的設(shè)計。通過

45、節(jié)約里程法計算出的配送路線。在此配送線路中，避免了各個節(jié)點的重復配送，使車輛的運載率得到了一定的提高。同時我們也意識到在此模型中沒有考慮配送時間，運價等問題，所以在以后的研究以及方法的改進中，我們可以將更多的影響因素考慮進去，為公司制定出更加合理的配送方案。第六章 總結(jié)通過對比可以看出，通過節(jié)約算法的優(yōu)化之后，該配送中心的配送線路得到了改進，節(jié)約了里程42.4km，減少了運輸車輛的數(shù)目，從而降低了運輸成本，提高了利潤。這只是節(jié)約里程算法的簡單運用，我們也應(yīng)看到，在現(xiàn)實的企業(yè)配送過程中，要考慮的配送點會更多、分布更廣，線路會更復雜，同時還要綜合考慮配送時間的限制、車輛的保養(yǎng)維修、人力成本、交通路

46、況等諸多因素。因此節(jié)約法簡便易行,但也有一些弊端，一是過于強調(diào)節(jié)約里程，沒有考慮時間。路況等因素，二是不能對客戶需求作出靈活多變的處理。在配送路 線選擇決策時,通?？紤]較優(yōu)的原則,而不是最優(yōu)化原則. 我們還應(yīng)做到深入了解客戶,加強與客戶的信息交流， 通過對客戶需求的時間變化對其進行分類,以增加配送的靈活性，路線決策過程中實施多路線同步?jīng)Q策，節(jié)約法的實施過程,要綜合考慮路程長短和時間因素，配送的總體過程實際上還會受商品分揀、裝卸、搬運設(shè)備和貨物組裝的共同影響。物資管理工作的好壞直接影響到施工企業(yè)的生產(chǎn)、技術(shù)、財務(wù)等多方面的經(jīng)營活動和經(jīng)濟效益；在現(xiàn)代社會，物流的概念被炒作的十分熱門，但這不僅僅是一

47、種炒作，現(xiàn)代物流管理思想確實是有相當?shù)目茖W基礎(chǔ)和成熟的技術(shù)，也不乏成功的例證。隨著我國社會主義市場經(jīng)濟的建立和完善，建筑企業(yè)必須改變過去計劃經(jīng)濟模式下的管理思想，采用先進的物流管理方式，建立高效的物流管理組織機構(gòu)已成為必然的趨勢。所以，施工企業(yè)引入現(xiàn)代物流管理思想，加強企業(yè)的物流管理，對于企業(yè)降低工程成本，實現(xiàn)工程項目效益最大化，提高企業(yè)競爭力具有重要的現(xiàn)實意義.隨著社會生產(chǎn)分工細化，許多企業(yè)開始注重業(yè)務(wù)外包，將自身不擅長的業(yè)務(wù)外包給第三方企業(yè)完成，自己把精力集中到核心業(yè)務(wù)上來，提高企業(yè)競爭力。建筑企業(yè)應(yīng)該將物流業(yè)務(wù)外包給合適的第三方物流企業(yè)，減少自身服務(wù)，將精力集中在施工建設(shè)上來。第三方物流

48、企業(yè)具有專業(yè)化的物流管理人員、技術(shù)人員、物流設(shè)備和信息系統(tǒng)等，充分發(fā)揮專業(yè)化的物流運作的管理經(jīng)驗，達到整體最優(yōu)化的效果。物流業(yè)務(wù)的外包大大降低了企業(yè)物流成本，減少了物流人員，借助信息平臺與第三方物流公司緊密溝通，同時利用其廣泛的配送網(wǎng)絡(luò)，不僅提高了物資的運送效率，降低運輸成本，而且降低了建筑企業(yè)庫存，削減了存儲成本。企業(yè)還可以將企業(yè)信息系統(tǒng)建設(shè)轉(zhuǎn)嫁給第三方物流公司，有利于提高信息系統(tǒng)的專業(yè)性、可靠性，且減少了建設(shè)投資和運營成本。物流外包可以更加明晰企業(yè)物流成本費用，降低了計算難度，提高了核算精確性，為運作的改進及決策的實施提供了有力保障。 建筑施工企業(yè)與供應(yīng)商缺乏長期有效的信息溝通，建立長期、穩(wěn)定的合作伙伴關(guān)系可以簡化之間的交易環(huán)節(jié)，提高材料的優(yōu)惠程度，從而縮短了談判費用和時間，降低了采購成本。建立長期合作關(guān)系對于企業(yè)的長期發(fā)展具有重要意義。同時，除企業(yè)自身與供應(yīng)商保持合作外，還可以利用第三方物流企業(yè)的業(yè)務(wù)關(guān)系擴大自身的供應(yīng)選擇范圍。通過第三方物流公司與其他供應(yīng)企業(yè)的合作關(guān)系以及相互之間的優(yōu)惠，選擇成本較低的供應(yīng)商，由物流公司承擔采購計劃，這樣不僅可以降低采購成本，而且可以進一步減少自身服務(wù)范圍，進一步提高企業(yè)競爭力。在現(xiàn)代的企業(yè)物流管理系統(tǒng)中，“信息化