物流配送車輛優(yōu)化調(diào)度的綜述

《物流配送車輛優(yōu)化調(diào)度的綜述》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第33卷增刊東南大學(xué)學(xué)報(自然科學(xué)版)Vol133Sup.2003年9月JOURNALOFSOUTHEASTUNIVERSITY(NaturalScienceEdition)Sept.2003物流配送車輛優(yōu)化調(diào)度的綜述楊弋顧幸生(華東理工大學(xué)自動化研究所,上海200237)摘要:物流配送車輛優(yōu)化調(diào)度問題是一類具有廣泛應(yīng)用的強(qiáng)NP難題,本文綜合國內(nèi)外多種參考文獻(xiàn),闡述了該問題的定義和分類,具體介紹了不同情況下的常見模型和主要算法,并就目前該問題的研究發(fā)展情況做了簡要分析和進(jìn)一步的展望.關(guān)鍵詞:物流;配送;車輛調(diào)度;調(diào)度中圖分類號:F252文獻(xiàn)標(biāo)識碼:A文章編號:1001-05

2、05(2003)增刊20105207AsurveyoflogisticsdeliveryvehicleschedulingYangYiGuXingsheng(ResearchInstituteofAutomation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)Abstract:LogisticdeliveryvehicleschedulingproblemisawidelyusedstronghardNPproblem.Inthispa2per,therecentdevelopmentoft

3、hestudyonlogisticdeliveryvehicleschedulingproblemisintroduced,itsdefi2nitionandclassificationareanalyzed,alsoitsmainmathematicsmodelandalgorithmarediscussedaftercon2sultinglotsofreference.Finallyitsapplicationsaregivenanddevelopmenttendencyismadefurtherestimate.Keywords:logistics;delivery;

4、VSP;scheduling1物流配送車輛調(diào)度問題的提出111物流配送車輛優(yōu)化調(diào)度問題的提出[1]最初的物流概念(physicaldistribution)是美國學(xué)者克拉克在20世紀(jì)20年代提出的.隨著社會經(jīng)濟(jì)的發(fā)展,物流已從傳統(tǒng)的運輸服務(wù)發(fā)展成為以信息技術(shù)和管理為核心的綜合物流系統(tǒng).因此,美國物流管理協(xié)會[1]于1984年正式將物流概念改為了logistics.[2]現(xiàn)代物流配送流程可見圖1,其中存儲環(huán)節(jié)的要求日益趨向弱化,配送成為最重要的環(huán)節(jié),直接為用戶服務(wù).配送的核心部分是配送車輛的集貨、貨物配裝及送貨過程,而車輛配送路線的合理優(yōu)化,對于整個物流運輸速度、成本、效益影

5、響至關(guān)重要.根據(jù)中國倉儲協(xié)會對146個企業(yè)的調(diào)查顯示,用于運輸?shù)馁M用占整個物流費用的比例分別為:在生產(chǎn)企業(yè)原料物流中占58%,在生產(chǎn)企業(yè)成品物流中占73%,在商業(yè)物流中占[3]52%.所以進(jìn)行配送系統(tǒng)優(yōu)化,最主要是對配送車輛的優(yōu)化調(diào)度,包括集貨線路優(yōu)化、貨物配裝及送貨線路優(yōu)化.圖1配送流程圖[4]物流配送車輛優(yōu)化調(diào)度問題最早是由學(xué)者Dantzig和Ramser于1959年首次提出的,國外一般稱之為vehicleroutingproblem或vehicleschedulingproblem.一般以為,不考慮時間要求,僅根據(jù)空間位置安排線路時稱[5]為車輛線路安排問題VRP;考

6、慮時間要求,安排線路時稱為車輛調(diào)度問題VSP.對VRP與VSP,也有學(xué)者不收稿日期:2003205215.作者簡介:楊弋(1972—),男,碩士生;顧幸生(聯(lián)系人),教授,博士生導(dǎo)師,xsgu@ecust.edu.cn.106東南大學(xué)學(xué)報(自然科學(xué)版)第33卷區(qū)分兩者,只是加上具體約束定語,例如,將有時間要求的車輛調(diào)度問題稱為vehicleroutingproblemwithtimewindows,等等.由于大多數(shù)國外文獻(xiàn)習(xí)慣采用VRP表述車輛調(diào)度問題,本文循例稱之為VRP.物流配送車輛優(yōu)化調(diào)度問題一般可定義為:對于一系列裝貨點和(或)卸貨點,組織合適的行車線路,使載貨車輛

7、有序地通過它們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等)下,達(dá)到一定的目標(biāo)(如路程最短,費用最少,時間盡量少,使用車輛數(shù)量盡量少[3]等).112車輛優(yōu)化調(diào)度問題的分類VRP被提出后,國內(nèi)外各學(xué)科的學(xué)者從不同角度,不同方向?qū)λM(jìn)行了各種研究,并各自按不同的標(biāo)準(zhǔn)[6,7]對VRP進(jìn)行了分類,綜合起來可分為以下幾種.按任務(wù)目標(biāo)區(qū)分,有純裝問題或純卸問題(purepickuporpuredelivery,車輛在所有任務(wù)點裝貨或卸貨,即集貨或送貨問題)及裝卸混合問題(