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

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

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

2、中圖分類號(hào):F252文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1001-0505(2003)增刊20105207AsurveyoflogisticsdeliveryvehicleschedulingYangYiGuXingsheng(ResearchInstituteofAutomation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)Abstract:Logisticdeliveryvehicleschedulingproblemisawidelyus

3、edstronghardNPproblem.Inthispa2per,therecentdevelopmentofthestudyonlogisticdeliveryvehicleschedulingproblemisintroduced,itsdefi2nitionandclassificationareanalyzed,alsoitsmainmathematicsmodelandalgorithmarediscussedaftercon2sultinglotsofreference.Finallyitsappli

4、cationsaregivenanddevelopmenttendencyismadefurtherestimate.Keywords:logistics;delivery;VSP;scheduling1物流配送車輛調(diào)度問題的提出111物流配送車輛優(yōu)化調(diào)度問題的提出[1]最初的物流概念(physicaldistribution)是美國(guó)學(xué)者克拉克在20世紀(jì)20年代提出的.隨著社會(huì)經(jīng)濟(jì)的發(fā)展,物流已從傳統(tǒng)的運(yùn)輸服務(wù)發(fā)展成為以信息技術(shù)和管理為核心的綜合物流系統(tǒng).因此,美國(guó)物流管理協(xié)會(huì)[1]于1984年正式將物流概念改為了l

5、ogistics.[2]現(xiàn)代物流配送流程可見圖1,其中存儲(chǔ)環(huán)節(jié)的要求日益趨向弱化,配送成為最重要的環(huán)節(jié),直接為用戶服務(wù).配送的核心部分是配送車輛的集貨、貨物配裝及送貨過程,而車輛配送路線的合理優(yōu)化,對(duì)于整個(gè)物流運(yùn)輸速度、成本、效益影響至關(guān)重要.根據(jù)中國(guó)倉(cāng)儲(chǔ)協(xié)會(huì)對(duì)146個(gè)企業(yè)的調(diào)查顯示,用于運(yùn)輸?shù)馁M(fèi)用占整個(gè)物流費(fèi)用的比例分別為:在生產(chǎn)企業(yè)原料物流中占58%,在生產(chǎn)企業(yè)成品物流中占73%,在商業(yè)物流中占[3]52%.所以進(jìn)行配送系統(tǒng)優(yōu)化,最主要是對(duì)配送車輛的優(yōu)化調(diào)度,包括集貨線路優(yōu)化、貨物配裝及送貨線路優(yōu)化.圖1配送流程

6、圖[4]物流配送車輛優(yōu)化調(diào)度問題最早是由學(xué)者Dantzig和Ramser于1959年首次提出的,國(guó)外一般稱之為vehicleroutingproblem或vehicleschedulingproblem.一般以為,不考慮時(shí)間要求,僅根據(jù)空間位置安排線路時(shí)稱[5]為車輛線路安排問題VRP;考慮時(shí)間要求,安排線路時(shí)稱為車輛調(diào)度問題VSP.對(duì)VRP與VSP,也有學(xué)者不收稿日期:2003205215.作者簡(jiǎn)介:楊弋(1972—),男,碩士生;顧幸生(聯(lián)系人),教授,博士生導(dǎo)師,xsgu@ecust.edu.cn.106東南大

7、學(xué)學(xué)報(bào)(自然科學(xué)版)第33卷區(qū)分兩者,只是加上具體約束定語,例如,將有時(shí)間要求的車輛調(diào)度問題稱為vehicleroutingproblemwithtimewindows,等等.由于大多數(shù)國(guó)外文獻(xiàn)習(xí)慣采用VRP表述車輛調(diào)度問題,本文循例稱之為VRP.物流配送車輛優(yōu)化調(diào)度問題一般可定義為:對(duì)于一系列裝貨點(diǎn)和(或)卸貨點(diǎn),組織合適的行車線路,使載貨車輛有序地通過它們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等)下,達(dá)到一定的目標(biāo)(如路程最短,費(fèi)用最少,時(shí)間盡量少,使用車輛

8、數(shù)量盡量少[3]等).112車輛優(yōu)化調(diào)度問題的分類VRP被提出后,國(guó)內(nèi)外各學(xué)科的學(xué)者從不同角度,不同方向?qū)λM(jìn)行了各種研究,并各自按不同的標(biāo)準(zhǔn)[6,7]對(duì)VRP進(jìn)行了分類,綜合起來可分為以下幾種.按任務(wù)目標(biāo)區(qū)分,有純裝問題或純卸問題(purepickuporpuredelivery,車輛在所有任務(wù)點(diǎn)裝貨或卸貨,即集貨或送貨問題)及裝卸混合問題(