遺傳算法、節(jié)約法在物流配送中應(yīng)用 - 副本

1、摘要配送是物流活動(dòng)中直接與消費(fèi)者相連的環(huán)節(jié)。配送成本占物流的各項(xiàng)成本的比例相當(dāng)高。配送線路合理與否影響到配送速度、成本和效益，特別是多用戶配送線路的確定是一項(xiàng)復(fù)雜的系統(tǒng)工程。因此，物流車輛路線問(wèn)題(VRP)成為國(guó)內(nèi)研究的熱點(diǎn)。運(yùn)籌學(xué)，用定量化方法了解和解釋運(yùn)行系統(tǒng)、為管理決策提供科學(xué)依據(jù)的學(xué)科。它把有關(guān)的運(yùn)行系統(tǒng)首先歸結(jié)成數(shù)學(xué)模型，然后用數(shù)學(xué)方法進(jìn)行定量分析和比較，求得合理運(yùn)用人力、物力和財(cái)力的系統(tǒng)運(yùn)行最優(yōu)方案。運(yùn)籌學(xué)有廣闊的應(yīng)用領(lǐng)域，是軟科學(xué)中“硬度”較大的一門學(xué)科，兼有邏輯的數(shù)學(xué)和數(shù)學(xué)的邏輯的性質(zhì)，是系統(tǒng)工程學(xué)和現(xiàn)代管理科學(xué)中的一種基礎(chǔ)理論和不可缺少的方法、手段和工具。在運(yùn)籌學(xué)中有解決物流

2、配送問(wèn)題的有效方法。本文主要介紹了節(jié)約法、遺傳算法并用這些方法解決實(shí)際物流配送問(wèn)題。關(guān)鍵字：物流配送，節(jié)約法，遺傳算法AbstractDistribution logistics activities directly connected with the consumer segment. The costs of logistics and distribution costs account for a very high proportion. Distribution line is reasonable or not affect the distribution of speed

3、, cost and efficiency, especially multi-user distribution lines to determine is a complex system engineering. Therefore, the logistics vehicle routing problem (VRP) has become a hot domestic research.Operations research, using quantitative methods to understand and explain the operating system, to p

4、rovide a scientific basis for management decisions disciplines. It related to the operation of the system is due to a mathematical model first, and then use mathematical methods for quantitative analysis and comparison, and seek the rational use of human, material and financial resources of the syst

5、em to run the optimal solution. Operations research has broad applications, the soft science of "hardness" of the larger one discipline, the nature of the logic of both mathematics and mathematical logic, is a basic theory of system engineering and modern management science and not lack of

6、 methods, means and tools.There are effective ways to solve the logistics problems in operations research. This paper describes the conservation law, scanning method, tabu search, genetic algorithm and use these methods to solve practical problems of logistics and distribution.Keywords: logistics, s

7、aving, scanning method, tabu search, genetic algorithm現(xiàn)代運(yùn)籌學(xué)算法在物流配送中的應(yīng)用1緒論1.1發(fā)達(dá)國(guó)家和地區(qū)物流配送現(xiàn)狀 理解物流配送概念離不開(kāi)對(duì)物流概念的分析。物流概念最早是在美國(guó)形成的，被稱為“physiealDistribution”(即Pn)，譯成漢語(yǔ)是“實(shí)物分配”或“貨物配送”。1963年被引入日本，物流被定義為“在連接生產(chǎn)和消費(fèi)間對(duì)物資履行保管、運(yùn)輸、裝卸、包裝、加工等功能，以及作為控制這類功能后援的信息功能,，在物資銷售中起了橋梁作用”。因此，現(xiàn)代物流是以滿足消費(fèi)者的需求為目標(biāo)，把制造、運(yùn)輸、銷售等市場(chǎng)情況統(tǒng)一起來(lái)思考的一

8、個(gè)產(chǎn)業(yè)概念。配送是物流系統(tǒng)的核心環(huán)節(jié)之一，配送在英語(yǔ)中的原語(yǔ)是“delivery”，是交貨送貨的意思。在日本工業(yè)標(biāo)準(zhǔn)Jis中，將配送定義為“將貨物從物流結(jié)點(diǎn)送交收貨人”強(qiáng)調(diào)了送貨的含義?？梢哉f(shuō)，物流配送是連接生產(chǎn)與消費(fèi)之間的一種中介服務(wù)，是物資供應(yīng)的種重要形式。配送是“配”和“送”有機(jī)結(jié)合的形式，它利用有效的分揀、配貨等理貨工作，使送貨達(dá)到一定的規(guī)模，以利用規(guī)模優(yōu)勢(shì)取得較低的送貨成本。 推行配送制有利于合理配置資源。由于實(shí)施配送可以做到以配送企業(yè)的庫(kù)存取代社會(huì)上千家萬(wàn)戶的零散庫(kù)存，或者說(shuō)，可以使庫(kù)存相對(duì)集中，因此，有條件也有可能按照統(tǒng)一計(jì)劃合理分配和使用資源，做到物盡其用。推行配送制可以降低物

9、流成本，促進(jìn)生產(chǎn)快速發(fā)展。這是因?yàn)楦鞣N流通要素相對(duì)集中，有益于開(kāi)展規(guī)模經(jīng)營(yíng)活動(dòng)；流通的物質(zhì)要素相對(duì)集中，也便于合理安排各環(huán)節(jié)上的物流活動(dòng)，使總體運(yùn)動(dòng)協(xié)調(diào)一致，最終會(huì)減少物流領(lǐng)域內(nèi)的勞動(dòng)消耗和費(fèi)用支出。推行配送制能夠充分發(fā)揮專業(yè)流通組織的綜合優(yōu)勢(shì)。推行配送很容易使不同的流通組織聯(lián)系在一起，從而構(gòu)成多功能的、一體化的物流運(yùn)動(dòng)。這種以配送作為媒介而形成的一體化運(yùn)作較之各個(gè)專業(yè)企業(yè)獨(dú)立運(yùn)作更能發(fā)揮流通組織的整體優(yōu)勢(shì)和綜合優(yōu)勢(shì)。 從20世紀(jì)60年代起，商品配送的合理化在美國(guó)普遍得到重視。為了在流通領(lǐng)域產(chǎn)生效益，美國(guó)企業(yè)采取了以下措施：一是將老式的倉(cāng)庫(kù)改為配送中心；二是引進(jìn)電腦管理網(wǎng)絡(luò)，對(duì)裝卸、搬運(yùn)、保管

10、實(shí)行標(biāo)準(zhǔn)化操作，提高作業(yè)效率；三是連鎖店共同組建配送中心，促進(jìn)連鎖店效益的增長(zhǎng)。美國(guó)連鎖店的配送中心有多種，主要有批發(fā)型、零售型和倉(cāng)儲(chǔ)型三種類型。首先是批發(fā)型。該類型配送中心主要靠計(jì)算機(jī)管理。業(yè)務(wù)部通過(guò)計(jì)算機(jī)獲取會(huì)員店的訂貨信息，及時(shí)向生產(chǎn)廠家和儲(chǔ)運(yùn)部發(fā)出訂貨指示單。其次是零售型。以美國(guó)沃爾瑪商品公司的配送中心為典型。該類型配送中心一般為某零售商獨(dú)資興建，專為本公司的連鎖店按時(shí)提供商品，確保各店穩(wěn)定經(jīng)營(yíng)。第三是倉(cāng)儲(chǔ)型。美國(guó)福來(lái)明公司的食品配送中心是典型的倉(cāng)儲(chǔ)式配送中心。它的主要任務(wù)是接受獨(dú)立雜貨商聯(lián)盟的委托業(yè)務(wù)，為該聯(lián)盟在該地區(qū)的若干家加盟店負(fù)責(zé)商品配送。 在日本，零售業(yè)是首先建立先進(jìn)物流系統(tǒng)

11、的行業(yè)之一。便利店作為一種新的零售業(yè)態(tài)迅速成長(zhǎng)，現(xiàn)己遍及日本，正影響著日本其他的零售商業(yè)形式。這種新的零售商業(yè)業(yè)態(tài)需要利用新的物流技術(shù)，以保證店內(nèi)各種商品的供應(yīng)順暢。因此，日本的物流配送具有以下特點(diǎn)；第一，分銷渠道發(fā)達(dá)。許多日本批發(fā)商過(guò)去常常把自己定位為某特定制造商的專門代理商，只允許經(jīng)營(yíng)一家制造商的產(chǎn)品。為了保證有效地供應(yīng)商品,日本許多物流公司不得不對(duì)原有的分銷渠道進(jìn)行合理化改造,更好地做到與上游或下游公司的分銷一體化。第二，頻繁、小批量進(jìn)貨。日本的物流配送企業(yè)的很大一部分服務(wù)需求來(lái)自便利店，便利店依靠的是小批量的頻繁進(jìn)貨，只有利用先進(jìn)的物流系統(tǒng)才有可能發(fā)展連鎖便利店，因?yàn)樗剐∨康念l繁進(jìn)

12、貨得以實(shí)現(xiàn)。第三，物流配送體現(xiàn)出共同化、混載化的趨勢(shì)。共同化、混載化的商品配送使原來(lái)按照不同生產(chǎn)廠、不同商品種類劃分開(kāi)來(lái)的分散的商品物流轉(zhuǎn)變?yōu)閷⒉煌瑥S家的產(chǎn)品和不同種類的商品混合起來(lái)運(yùn)送的聚合的商品物流，從而得以發(fā)揮商品物流的批量效益，大大提高了運(yùn)貨車輛的裝載率。第四,合作型物流配送。在日本,生產(chǎn)企業(yè)、零售企業(yè)與綜合商社、綜合物流公司之間基本上都存在一種長(zhǎng)期的物流合作關(guān)系。并且，這種合作關(guān)系還隨著日本工業(yè)生產(chǎn)的國(guó)際化延伸到國(guó)外。第五，政府規(guī)劃在現(xiàn)代物流配送發(fā)展過(guò)程中具有重要作用。臺(tái)灣地區(qū)的配送中心多為中小規(guī)模、平房倉(cāng)庫(kù),并采用適合本地區(qū)特點(diǎn)的設(shè)施設(shè)備。臺(tái)灣地區(qū)創(chuàng)造了自己的“本土化物流”。他們認(rèn)

13、為“自動(dòng)化”不一定適應(yīng)所有國(guó)家和地區(qū)的物流產(chǎn)業(yè)發(fā)展，引進(jìn)技術(shù)必須考慮企業(yè)的財(cái)力規(guī)模、土地成本、建筑成本、設(shè)備成本等條件。因此，臺(tái)灣地區(qū)沒(méi)有完全照搬美國(guó)和日本的發(fā)展經(jīng)驗(yàn),而是融合這些國(guó)家物流現(xiàn)代化的經(jīng)驗(yàn)，根據(jù)自己的需求，盡量完善自己的物流薄弱環(huán)節(jié)。另外，物流人才的培養(yǎng)也是臺(tái)灣物流企業(yè)形成自己特色的重要原因之一，他們認(rèn)為物流現(xiàn)代化不僅在于逐步實(shí)現(xiàn)物流設(shè)施的現(xiàn)代化更重要的是在于人才素質(zhì)的提高。目前，臺(tái)灣的物流配送發(fā)展趨勢(shì)是從整合到聚集；在物流配送的發(fā)展初期，企業(yè)是憑借自身力量與外部競(jìng)爭(zhēng)；在發(fā)展的階段，則是通過(guò)若干企業(yè)間的互助合作與其他企業(yè)競(jìng)爭(zhēng)。而在聯(lián)合的階段則是通過(guò)資源共享的結(jié)盟來(lái)與其他企業(yè)競(jìng)爭(zhēng)，也

14、就是使自己的競(jìng)爭(zhēng)對(duì)手通過(guò)聚集成為自己的一部分。這樣就達(dá)到了高層次競(jìng)爭(zhēng)的階段,即通過(guò)提供有差異的服務(wù)進(jìn)行競(jìng)爭(zhēng)，而并非僅通過(guò)硬件進(jìn)行競(jìng)爭(zhēng)。1.2我國(guó)的物流配送發(fā)展現(xiàn)狀 物流配送是現(xiàn)代流通的重要組成部分。近年來(lái)，我國(guó)物流配送發(fā)展出現(xiàn)了積極趨勢(shì)，主要體現(xiàn)在以下幾個(gè)方面： 各級(jí)政府部門采取措施積極推動(dòng)物流配送的發(fā)展。不少省市己經(jīng)把發(fā)展現(xiàn)代物流列入了日程，例如，上海、天津、深圳都把物流作為支柱產(chǎn)業(yè)。還有許多省市開(kāi)始制定物流規(guī)劃。國(guó)家有關(guān)部門對(duì)商品物流和配送采取了積極鼓勵(lì)和支持的政策，在我國(guó)流通領(lǐng)域?qū)ν忾_(kāi)放政策中，鼓勵(lì)國(guó)外資本投資于物流和配送設(shè)施等。目前國(guó)內(nèi)物流和配送服務(wù)己有較快的發(fā)展，物流配送己經(jīng)成為許多

15、企業(yè)降低成本，提高競(jìng)爭(zhēng)力的重要手段。例如，相當(dāng)多實(shí)行連鎖經(jīng)營(yíng)的零售企業(yè)建立了自己的配送中心，為企業(yè)內(nèi)部的連鎖網(wǎng)點(diǎn)提供物流配送服務(wù)，一些連鎖企業(yè)配送商品比例己經(jīng)超過(guò)企業(yè)經(jīng)營(yíng)品種的50%。 在生活資料領(lǐng)域和生產(chǎn)資料領(lǐng)域出現(xiàn)了各具特色的不同類型的現(xiàn)代物流企業(yè)。一些傳統(tǒng)的流通企業(yè)，包括運(yùn)輸和倉(cāng)儲(chǔ)業(yè)通過(guò)改造成為物流企業(yè)，如中遠(yuǎn)集團(tuán)、中外運(yùn)集團(tuán)和中儲(chǔ)集團(tuán)等；一些國(guó)有商業(yè)批發(fā)企業(yè)和大型零售企業(yè)正在積極探索和嘗試開(kāi)展社會(huì)化物流配送服務(wù)；一些生產(chǎn)企業(yè)開(kāi)始介入現(xiàn)代物流，如青島海爾集團(tuán)；一批專業(yè)化的物流企業(yè)得到較快發(fā)展，物流配送的社會(huì)化、專業(yè)化發(fā)展趨勢(shì)日益明顯，如深圳中海物流都是比較成功的第三方物流公司。外資在物流

16、配送服務(wù)領(lǐng)域的發(fā)展也十分迅速，如中國(guó)儲(chǔ)運(yùn)總公司與日本崗谷鋼機(jī)株式會(huì)社合資組建了天津崗谷物流公司，是集配送、加工、倉(cāng)儲(chǔ)、寄售、租賃、修理、展銷和技術(shù)咨詢?yōu)橐惑w的新型流通組織。像這樣的合資物流公司，在北京、天津、上海等地已有10家之多，它們主要是為在中國(guó)投資的跨國(guó)公司提供物流配送服務(wù)。這些企業(yè)根據(jù)各自特點(diǎn)，發(fā)揮特長(zhǎng)優(yōu)勢(shì)，積極開(kāi)拓物流服務(wù)領(lǐng)域，形成了服務(wù)模式多樣、多種經(jīng)濟(jì)成份并存的現(xiàn)代物流企業(yè)群體。連鎖企業(yè)內(nèi)部的配送中心在硬件設(shè)施、管理水平、管理信息系統(tǒng)等方面的建設(shè)，獲得較大發(fā)展，有些己經(jīng)達(dá)到較先進(jìn)的水平。 現(xiàn)代物流技術(shù)的開(kāi)發(fā)研究取得一定進(jìn)展。一些物流配送企業(yè)在研究開(kāi)發(fā)物流信息技術(shù)和物流配送管理技術(shù)

17、上取得了許多成果，對(duì)于推動(dòng)我國(guó)現(xiàn)代物流發(fā)展發(fā)揮了積極作用。目前已有相當(dāng)多的物流和配送技術(shù)開(kāi)始進(jìn)入中國(guó)，并在企業(yè)中得到越來(lái)越廣泛的應(yīng)用，例如條形碼技術(shù)、計(jì)算機(jī)支持的信息管理技術(shù)、EDI、MRP等。 盡管我國(guó)物流配送業(yè)近幾年發(fā)展很快，但與發(fā)達(dá)國(guó)家相比還處在起步階段，不可避免地會(huì)遇到這樣或那樣的問(wèn)題。當(dāng)前，主要存在以下幾個(gè)方面的問(wèn)題： (l)物流配送市場(chǎng)化程度低，第三方物流配送發(fā)展滯后。目前我國(guó)大多數(shù)物流配送企業(yè)技術(shù)裝備和管理手段比較落后，服務(wù)網(wǎng)絡(luò)和信息系統(tǒng)不健全，物流配送市場(chǎng)化程度低，影響了物流服務(wù)的準(zhǔn)確性與時(shí)效性。其主要表現(xiàn)是：?。ㄎ锪髋渌推髽I(yè)數(shù)量小，經(jīng)營(yíng)規(guī)模小)、少(物流配送市場(chǎng)份額少、服務(wù)功

18、能少，大多數(shù)企業(yè)還只是被動(dòng)地按照用戶的要求，從事單一功能的運(yùn)輸、倉(cāng)儲(chǔ)和配送，很少能提供物流策劃、組織及深入到供應(yīng)鏈的全過(guò)程管理，物流增值少)、散(網(wǎng)絡(luò)分割、經(jīng)營(yíng)秩序不規(guī)范，不能為客戶提供包括物流網(wǎng)絡(luò)設(shè)計(jì)、預(yù)測(cè)、訂貨管理、存貨管理等系統(tǒng)物流服務(wù))、弱(競(jìng)爭(zhēng)力弱和發(fā)展滯后，專業(yè)化、信息化、標(biāo)準(zhǔn)化還沒(méi)跟上，還沒(méi)有真正了解國(guó)際物流企業(yè)的運(yùn)作方式和真正意義上的“第三方物流”)。 （2）物流基礎(chǔ)設(shè)施落后，物流配送的整體功能低。一是交通運(yùn)輸設(shè)施建設(shè)與物流配送的需要不相適應(yīng)，即交通運(yùn)輸能力仍不能滿足運(yùn)輸需求，主要運(yùn)輸通道供需矛盾依然突出：二是技術(shù)裝備水平落后；三是物流系統(tǒng)標(biāo)準(zhǔn)化程度低。 （3）物流配送管理體制

19、和相關(guān)制度不完善。一方面，市場(chǎng)競(jìng)爭(zhēng)機(jī)制和市場(chǎng)管理法規(guī)不健全，發(fā)展物流配送所需的產(chǎn)業(yè)政策和產(chǎn)業(yè)規(guī)劃尚未出臺(tái)，物流市場(chǎng)的進(jìn)入與退出、競(jìng)爭(zhēng)規(guī)則基本上無(wú)統(tǒng)一法律法規(guī)可循，對(duì)社會(huì)性的物流缺乏有效的外部約束，致使不正當(dāng)競(jìng)爭(zhēng)較為嚴(yán)重。另一方面，物流配送市場(chǎng)至今仍被人為地按照部門、地區(qū)和行業(yè)的行政壁壘分割，物流配送市場(chǎng)管理和行業(yè)管理還沒(méi)有理順，各地商委、經(jīng)貿(mào)委、交通局、鐵路局、外經(jīng)貿(mào)委等都各自承擔(dān)了一部分物流管理職能，各部門間分工又有交叉，造成了物流管理中條塊分割、重復(fù)建設(shè)等問(wèn)題，統(tǒng)一、競(jìng)爭(zhēng)、有序的物流配送市場(chǎng)沒(méi)有建立起來(lái)，嚴(yán)重影響了物流配送渠道的暢通和高效運(yùn)轉(zhuǎn),使物流配送很難達(dá)到規(guī)模經(jīng)濟(jì)和預(yù)期回報(bào)。 （4）

20、專業(yè)的物流配送管理和技術(shù)人才短缺。1.3發(fā)展物流配送的意義 隨著經(jīng)濟(jì)全球化和網(wǎng)絡(luò)信息技術(shù)發(fā)展的加快，物流及配送業(yè)作為一個(gè)新的經(jīng)濟(jì)增長(zhǎng)點(diǎn)引起了國(guó)人的注意。上海、天津、北京等城市紛紛將物流產(chǎn)業(yè)作為支柱產(chǎn)業(yè)，中儲(chǔ)、中遠(yuǎn)、中外運(yùn)等大型企業(yè)都把現(xiàn)代物流作為重點(diǎn)發(fā)展領(lǐng)域。我國(guó)證券市場(chǎng)己經(jīng)形成了由幾十家企業(yè)構(gòu)成的“物流板塊”，許多商貿(mào)流通部門紛紛介入現(xiàn)代物流配送業(yè)務(wù)中，物流及配送業(yè)的發(fā)展在全國(guó)方興未艾。 2011年我國(guó)社會(huì)物流總費(fèi)用為8.4萬(wàn)億元，從構(gòu)成情況看，運(yùn)輸費(fèi)用4.4萬(wàn)億元，占社會(huì)物流總費(fèi)用的比重為52.4%，保管費(fèi)用2.9萬(wàn)億元，占社會(huì)物流總費(fèi)用的比重是34.5%，管理費(fèi)用1萬(wàn)億元，占社會(huì)物流總費(fèi)

21、用的比重為11.9%。運(yùn)輸成本占物流成本的50%左右，是影響物流總費(fèi)用的主要因素，調(diào)查顯示，美國(guó)的運(yùn)輸成本僅占到其GDP的不到6%，日本也僅為6.5%。而我國(guó)運(yùn)輸成本占到GDP 的11%。中國(guó)倉(cāng)儲(chǔ)協(xié)會(huì)對(duì)146家生產(chǎn)企業(yè)的調(diào)查結(jié)果表明，運(yùn)輸費(fèi)用占整個(gè)物流費(fèi)用的比例分別為：生產(chǎn)企業(yè)原材料物流中運(yùn)輸費(fèi)用占到58%，生產(chǎn)企業(yè)成品物流中運(yùn)輸費(fèi)用占到73%，商業(yè)物流中運(yùn)輸費(fèi)用占到 52%。 由以上數(shù)據(jù)可以看出運(yùn)輸費(fèi)用在總物流費(fèi)用中所占比重最大，因此節(jié)約運(yùn)輸費(fèi)用可以極大的降低物流成本。在物流活動(dòng)中，配送是很重要的一個(gè)環(huán)節(jié)，運(yùn)輸成本在配送成本中占有很大的一部分，因此在配送管理中，有效的使用車輛并確定配送車輛經(jīng)

22、濟(jì)行駛路線，在最短的時(shí)間內(nèi)把商品送到顧客手中，提高顧客的滿意度，是配送作業(yè)的重點(diǎn)。顯然，為了實(shí)現(xiàn)以上幾點(diǎn)目標(biāo)，必須對(duì)配送過(guò)程進(jìn)行合理規(guī)劃，這一點(diǎn)可以通過(guò)改進(jìn)運(yùn)輸方式、進(jìn)行線路規(guī)劃等來(lái)實(shí)現(xiàn)。近年來(lái)，配送車輛路線的確定問(wèn)題是物流配送領(lǐng)域的重點(diǎn)研究對(duì)象，它是指利用科學(xué)的、合理的手段來(lái)制定配送線路，對(duì)其進(jìn)行研究可以提高配送效益、有利于實(shí)現(xiàn)配送科學(xué)化。 為實(shí)現(xiàn)運(yùn)輸成本的降低，必須對(duì)運(yùn)輸?shù)倪M(jìn)行合理規(guī)劃。運(yùn)輸?shù)暮侠硪?guī)劃涉及到時(shí)間、財(cái)務(wù)、環(huán)境三方面的因素，首先從時(shí)間要考慮準(zhǔn)時(shí)性、快速響應(yīng)；財(cái)務(wù)上要考慮運(yùn)輸涉及的各種開(kāi)支(車輛購(gòu)置成本和消耗、司機(jī)薪酬、油耗等)；環(huán)境上要盡可能減少不必要的行駛,避免交通擁擠、空氣

23、以及噪音等污染。這些可以通過(guò)改進(jìn)運(yùn)輸方式、線路規(guī)劃等交通管理來(lái)加以改善。其中運(yùn)輸方式屬于“硬”技術(shù)的問(wèn)題。是可以通過(guò)設(shè)施的完善和提高運(yùn)輸?shù)男?降低相應(yīng)成本。運(yùn)輸?shù)木€路規(guī)劃主要是利用各種先進(jìn)的信息技術(shù)對(duì)車輛及其路線進(jìn)行規(guī)劃，實(shí)現(xiàn)對(duì)車輛合理有效的利用，從而節(jié)省大量的時(shí)間和成本。而物流中心配送作業(yè)的重點(diǎn)就是如何將車輛有效的使用并決定其最經(jīng)濟(jì)的行駛路線圖，使商品能在最短的時(shí)間內(nèi)送到顧客的手中。該問(wèn)題為；從配送中心(物流據(jù)點(diǎn))用多輛車向多個(gè)需求點(diǎn)(顧客)送貨，每個(gè)需求點(diǎn)的位置和需求量一定,每輛車的載重量一定，要求合理安排車輛路線，使總運(yùn)距最短，并滿足以下條件：(1)每條配送路徑上各需求點(diǎn)的需求量之和不

24、超過(guò)車輛載重量；(2)每條配送路徑的長(zhǎng)度不超過(guò)車輛一次配送的最大行駛距離；(3)每個(gè)需求點(diǎn)必須滿足,且只能由一輛車送貨。達(dá)到一定的目標(biāo)(如路程最短、費(fèi)用最少、時(shí)間盡量少、使用車輛數(shù)盡量少等)。此即為VRP問(wèn)題。 通過(guò)科學(xué)合理的手段制定配送路線，在配送活動(dòng)中是很重要的一個(gè)環(huán)節(jié)。合理的選擇配送路線，對(duì)于社會(huì)和企業(yè)具有重要意義。對(duì)于企業(yè)，配送路線的優(yōu)化，可以簡(jiǎn)化配送程序、提高配送效率，充分利用配送車輛運(yùn)力、降低空載率、減少配送次數(shù)、盡量使配送成本降低；同時(shí)優(yōu)化配送路線可以加快企業(yè)對(duì)客戶需求的響應(yīng)速度，準(zhǔn)時(shí)、快速的把物品送達(dá)客戶，提高客戶滿意程度。對(duì)于社會(huì)，配送路線優(yōu)化可以節(jié)省作業(yè)車輛，進(jìn)而緩解交通擁

25、堵?tīng)顩r，減少噪聲、尾氣的排放，為保護(hù)生態(tài)環(huán)境做出貢獻(xiàn)。所以研究配送車輛路線優(yōu)化問(wèn)題及算法具有重要的現(xiàn)實(shí)意義。1.4物流配送路線優(yōu)化研究現(xiàn)狀 國(guó)內(nèi)外相關(guān)領(lǐng)域?qū)RP問(wèn)題的研究始于50年代，在理論研究和實(shí)際應(yīng)用兩方面都已取得了非常顯著的成果。隨著研究的深入發(fā)展,如何使研究的理論模型更貼近現(xiàn)實(shí)中的運(yùn)輸規(guī)劃問(wèn)題開(kāi)始成為研究者們關(guān)注的焦點(diǎn)。車輛路線問(wèn)題(VRP問(wèn)題)是組合優(yōu)化領(lǐng)域中著名的NP難題，近二十年來(lái)，無(wú)論在國(guó)內(nèi)還是國(guó)外，VRP問(wèn)題都是一個(gè)非?；钴S的研究領(lǐng)域。目前國(guó)內(nèi)外用于解決該問(wèn)題的現(xiàn)代數(shù)學(xué)方法主要分為以下幾類： （1）精確算法 精確算法是采用嚴(yán)密的數(shù)學(xué)手段進(jìn)行計(jì)算的方法，在能夠求得可行解的情況

26、下，其求得的結(jié)果一般要好于啟發(fā)算法。常見(jiàn)的精確算法有以下幾種：分枝定界法、割平面法、動(dòng)態(tài)規(guī)劃法等。 分支定界法是一種應(yīng)用范圍很廣的搜索算法，它的基本思想是把給定問(wèn)題分解為若干個(gè)較小的子問(wèn)題，每個(gè)子問(wèn)題又可繼續(xù)分解，直到子問(wèn)題不能再分解或不能產(chǎn)生最優(yōu)解。根據(jù)問(wèn)題的特點(diǎn)和不同的策略，把問(wèn)題分解為子問(wèn)題的過(guò)程稱之為分支。在分支過(guò)程，為每一子問(wèn)題估算其對(duì)應(yīng)的目標(biāo)值的界限稱之為定界。定界的目的是為了測(cè)定界的趨勢(shì)，留下有價(jià)值的或尚不能判定的分支。刪除肯定不存在的最優(yōu)解的分支，稱之為剪支，以達(dá)到加速收斂、簡(jiǎn)化運(yùn)算的目的。對(duì)為題進(jìn)行分解，確定子問(wèn)題的解值界限，減去非優(yōu)的子問(wèn)題，在進(jìn)行新的分支，這樣一個(gè)分支到定

27、界到剪支再到分支等反復(fù)的過(guò)程是分支定界法的基本算法步驟。不同的分支規(guī)則與定界方法，形成了同一問(wèn)題的不同分支定界方法。 割平面法是由高莫瑞1958年提出的，故又稱為Gomory的割平面法。它的基本思想是：不斷增加線性約束條件（幾何術(shù)語(yǔ)稱為割平面）將原規(guī)劃問(wèn)題的可行域切割掉一部分，使其切割掉的部分只包含非整數(shù)解，沒(méi)有切割掉任何整數(shù)可行解，直到切割后得到的可行域有一個(gè)整數(shù)坐標(biāo)的極點(diǎn)恰好是問(wèn)題的最優(yōu)解為止。針對(duì)求解的決策變量是全部取整還是部分取整問(wèn)題，割平面算法中就分成了兩種計(jì)算方法，前者稱為分?jǐn)?shù)算法，后者稱為混合整數(shù)算法。 動(dòng)態(tài)規(guī)劃法是20世紀(jì)50年代由貝爾曼（R. Bellman）等人提出,用來(lái)解

28、決多階段決策過(guò)程問(wèn)題的一種最優(yōu)化方法。所謂多階段決策過(guò)程,就是把研究問(wèn)題分成若干個(gè)相互聯(lián)系的階段,由每個(gè)階段都作出決策,從而使整個(gè)過(guò)程達(dá)到最優(yōu)化。許多實(shí)際問(wèn)題利用動(dòng)態(tài)規(guī)劃法處理,常比線性規(guī)劃法更為有效,特別是對(duì)于那些離散型問(wèn)題。實(shí)際上,動(dòng)態(tài)規(guī)劃法就是分多階段進(jìn)行決策,其基本思路是：按時(shí)空特點(diǎn)將復(fù)雜問(wèn)題劃分為相互聯(lián)系的若干個(gè)階段,在選定系統(tǒng)行進(jìn)方向之后,逆著這個(gè)行進(jìn)方向,從終點(diǎn)向始點(diǎn)計(jì)算,逐次對(duì)每個(gè)階段尋找某種決策,使整個(gè)過(guò)程達(dá)到最優(yōu),故又稱為逆序決策過(guò)程。 精確式算法領(lǐng)域的研究主要是針對(duì)某一特定問(wèn)題而設(shè)計(jì)，實(shí)際應(yīng)用范圍有限，基本是在傳統(tǒng)物流配送模式下來(lái)考慮問(wèn)題、改進(jìn)模型和設(shè)計(jì)算法。該方法不能保

29、證所得出的最終解是最優(yōu)整數(shù)解，但其一定是非常接近最優(yōu)解的。隨著車輛運(yùn)輸調(diào)度系統(tǒng)的復(fù)雜化和調(diào)度目標(biāo)的增加，問(wèn)題的數(shù)據(jù)量會(huì)變得越來(lái)越大，利用精確算法求解問(wèn)題就會(huì)變得十分困難，于是研究者們開(kāi)始考慮利用啟發(fā)算法來(lái)解決這類問(wèn)題。啟發(fā)方法是指人們根據(jù)經(jīng)驗(yàn)規(guī)則來(lái)發(fā)現(xiàn)問(wèn)題的滿意解的方法。用啟發(fā)式方法求解問(wèn)題時(shí)往往注重求得滿意解而非最優(yōu)解。啟發(fā)式算法分為傳統(tǒng)啟發(fā)式算法和現(xiàn)代啟發(fā)式算法兩種。 （2）傳統(tǒng)啟發(fā)式算法 傳統(tǒng)的啟發(fā)式算法主要有節(jié)約法、掃描法等。 節(jié)約里程法又稱節(jié)約算法或節(jié)約法，是指用來(lái)解決運(yùn)輸車輛數(shù)目不確定的VRP問(wèn)題的最有名的啟發(fā)式算法。節(jié)約里程法基本規(guī)定，利用節(jié)約法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配

30、送中心的運(yùn)輸能力和配送中心到各個(gè)用戶以及各個(gè)用戶之間的距離來(lái)制定使總的車輛運(yùn)輸?shù)膰嵐飻?shù)最小的配送方案。另還需滿足以下條件；1）所有用戶的要求；2）不使任何一輛車超載；3）每輛車每天的總運(yùn)行時(shí)間或行駛里程不超過(guò)規(guī)定的上限；4）用戶到貨時(shí)間要求?；舅枷胧牵瑸檫_(dá)到高效率的配送，使配送的時(shí)間最小距離最短成本最低，而尋找的最佳配送路線。近年來(lái)，由于小批量、多批次的及時(shí)配送方式的發(fā)展,運(yùn)輸費(fèi)用正在逐年提升，許多企業(yè)的運(yùn)費(fèi)己經(jīng)超越了庫(kù)存費(fèi)用。選擇有效的配送路線，己成為控制物流成本的主要措施。那么如何選擇有效的配送路線呢？現(xiàn)代企業(yè)已經(jīng)普遍接受了一種觀點(diǎn)，即有效的配送路線實(shí)際上是在保證商品準(zhǔn)時(shí)到達(dá)客戶指定點(diǎn)

31、的前提下，盡可能地減少運(yùn)輸?shù)能嚧魏瓦\(yùn)輸?shù)目偮烦?。在這種思想的指導(dǎo)下，節(jié)約法已成為選擇配送路線的主要方法，并受到國(guó)內(nèi)外物流界的青睞。 掃描法是Gillett和Miller于1974年所提出的求解車輛路線問(wèn)題（Vehicle Routing Problem,VRP）的方法，此方法屬于先分群再排路線的方式。該方法采用極坐標(biāo)來(lái)表示各需求點(diǎn)的區(qū)位，然后任取一需求點(diǎn)為起始點(diǎn)，定其角度為零度，以順時(shí)鐘或逆時(shí)鐘方向，以車容量為限制條件進(jìn)行服務(wù)區(qū)域之分割，再借由Lin與Kernighan的交換法進(jìn)行需求點(diǎn)的排序，建構(gòu)車輛排程路線。一般情況下，制定從一個(gè)物流中心向多個(gè)用戶運(yùn)送貨物的配送計(jì)劃時(shí)，必須考慮每輛車的運(yùn)載

32、能力和行駛距離及時(shí)間等的限制。其中掃描法是一種能較好地解決配送路線問(wèn)題的有效方法，它的基本思路是采用逐次逼近的方法來(lái)解決問(wèn)題。 （3）現(xiàn)代啟發(fā)式算法 現(xiàn)代啟發(fā)式算法主要有禁忌搜索算法、遺傳算法、蟻群算法、粒子群算法等。用現(xiàn)代啟發(fā)算法對(duì)問(wèn)題的求解是通過(guò)大規(guī)模的迭代來(lái)實(shí)現(xiàn)的，現(xiàn)代啟發(fā)算法自身具有一套獨(dú)特的搜索規(guī)則。為了求得滿意解，算法在迭代中要不斷采納和分析新信息，必要情況下需要變更原來(lái)的策略，建立新的搜索規(guī)則，同時(shí)要注意從失敗的搜索中取得經(jīng)驗(yàn)教訓(xùn)，逐漸減小搜索的范圍。隨后從多個(gè)可行解中找出滿意解。 1）禁忌搜索法 Gendreaut 等人（1991）最先將禁忌搜索法應(yīng)用于車輛路徑優(yōu)化問(wèn)題。先構(gòu)造

33、一系列的解，然后對(duì)所得到的結(jié)果不斷地改進(jìn)。該算法所得到的解不一定是可行解，它們對(duì)可行性的偏離程度體現(xiàn)在目標(biāo)函數(shù)里的懲罰函數(shù)值的大小。禁忌搜索法是針對(duì)車輛路線優(yōu)化問(wèn)題的較好的現(xiàn)代啟發(fā)式算法，在許多經(jīng)典的車輛路線優(yōu)化問(wèn)題的求解中都已經(jīng)被成功地運(yùn)用。 2）遺傳算法 近年來(lái)，一類基于生物學(xué),物理學(xué)和人工智能的具有全局優(yōu)化能力、魯棒性強(qiáng)、通用性強(qiáng)且適于并行處理的現(xiàn)代啟發(fā)式算法得到了發(fā)展。因其高效的優(yōu)化性能、無(wú)需問(wèn)題特殊信息等優(yōu)點(diǎn)，廣泛用于計(jì)算機(jī)科學(xué)、優(yōu)化調(diào)度、運(yùn)輸問(wèn)題、組合優(yōu)化、工程優(yōu)化等領(lǐng)域。遺傳算法是其中具有代表性的一種現(xiàn)代啟發(fā)式方法。 3）蟻群算法 蟻群算法蟻群算法（ant colony opti

34、mization,，ACO）又稱螞蟻算法，是一種用來(lái)尋找最優(yōu)解決方案的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。螞蟻在路徑上前進(jìn)時(shí)會(huì)根據(jù)前邊走過(guò)的螞蟻所留下的分泌物選擇其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強(qiáng)度成正比。因此，由大量螞蟻組成的群體的集體行為實(shí)際上構(gòu)成一種學(xué)習(xí)信息的正反饋現(xiàn)象：某一條路徑走過(guò)的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個(gè)體間通過(guò)這種信息的交流尋求通向食物的最短路徑。蟻群算法就是根據(jù)這一特點(diǎn)，通過(guò)模仿螞蟻的行為，從而實(shí)現(xiàn)尋優(yōu)。這種算法有別于傳統(tǒng)編程模式，其優(yōu)勢(shì)在于，

35、避免了冗長(zhǎng)的編程和籌劃，程序本身是基于一定規(guī)則的隨機(jī)運(yùn)行來(lái)尋找最佳配置。也就是說(shuō)，當(dāng)程序最開(kāi)始找到目標(biāo)的時(shí)候，路徑幾乎不可能是最優(yōu)的，甚至可能是包含了無(wú)數(shù)錯(cuò)誤的選擇而極度冗長(zhǎng)的。但是，程序可以通過(guò)螞蟻尋找食物的時(shí)候的信息素原理，不斷地去修正原來(lái)的路線，使整個(gè)路線越來(lái)越短，也就是說(shuō)，程序執(zhí)行的時(shí)間越長(zhǎng)，所獲得的路徑就越可能接近最優(yōu)路徑。這看起來(lái)很類似與我們所見(jiàn)的由無(wú)數(shù)例子進(jìn)行歸納概括形成最佳路徑的過(guò)程。實(shí)際上好似是程序的一個(gè)自我學(xué)習(xí)的過(guò)程。 4）粒子群算法 Kennedy 和 Eberhart 在 1995 年首次提出了粒子群算法，該算法基于對(duì)鳥(niǎo)類飛行覓食行為的模擬，群體達(dá)到最優(yōu)目標(biāo)是通過(guò)鳥(niǎo)群個(gè)

36、體之間的協(xié)作行為實(shí)現(xiàn)的。粒子群算法與遺傳算法類似，它們的共同點(diǎn)是運(yùn)算方式基于群體的迭代，但粒子群算法沒(méi)有變異、交叉和算子的復(fù)制，群體在解可行域中追逐最優(yōu)粒子不斷搜索直到找到滿意解。粒子群算法的優(yōu)點(diǎn)為：個(gè)體數(shù)量少、計(jì)算簡(jiǎn)單、魯棒性好、容易實(shí)現(xiàn)，并有著深刻的智能背景，適合于科學(xué)研究及工程應(yīng)用。粒子群算法源于對(duì)鳥(niǎo)群捕食行為的研究。鳥(niǎo)群捕食場(chǎng)景為：鳥(niǎo)群在一片固定區(qū)域內(nèi)尋找食物，但在這個(gè)區(qū)域內(nèi)食物只有一塊，群內(nèi)的每一只鳥(niǎo)的搜索行為都具有隨機(jī)性。鳥(niǎo)群中的所有個(gè)體都不清楚在哪里可以找到食物，但個(gè)體知道自身位置與食物間的距離。對(duì)于這個(gè)群體來(lái)說(shuō)尋找食物的最簡(jiǎn)單有效的策略就是搜尋目前離食物最近的個(gè)體周圍的區(qū)域，粒

37、子群算法正是基于上述方式解決優(yōu)化問(wèn)題的。粒子群算法求解優(yōu)化問(wèn)題時(shí)，每一個(gè)潛在解可以被看做是空間中進(jìn)行搜索的一只鳥(niǎo)，我們將之稱為“粒子”。所有的粒子與相關(guān)優(yōu)化函數(shù)之間都有適應(yīng)值，這個(gè)適應(yīng)值由優(yōu)化函數(shù)決定，粒子自身具有速度，粒子的速度決定粒子本身的飛行距離和方向。所有的粒子追隨目前的最優(yōu)粒子在可行區(qū)域內(nèi)搜尋最優(yōu)解。粒子群算法隨機(jī)初始化一定數(shù)量的粒子，它尋找最優(yōu)解的方式是通過(guò)多次迭代。每次迭代粒子追逐個(gè)體極值（粒子自身在所經(jīng)歷的位置中找到的最優(yōu)解）及全局極值（整個(gè)群體到目前為止找到的最優(yōu)解）來(lái)更新自己。2理論基礎(chǔ)2.1物流配送問(wèn)題的基本理論2.1.1配送路線問(wèn)題模型 采用科學(xué)的、合理的方法來(lái)確定配送

38、線路，成為提高物流配送車輛效益、實(shí)現(xiàn)物流配送科學(xué)化的重要途徑。在滿足客戶配送需求的前提下，如何選擇配送路線，是一項(xiàng)很重要的工作。配送作業(yè)的時(shí)效性和高效性主要受車輛路線的安排與調(diào)度方案優(yōu)化情況的影響。配送路線優(yōu)化問(wèn)題由來(lái)已久，其可以描述如下，見(jiàn)圖 2-1?？蛻酎c(diǎn)配送中心圖2-1 配送路線優(yōu)化問(wèn)題原理圖 有一個(gè)（或者多個(gè)）配送中心，共有配送車輛 K 輛（一種或者多種車型），車輛載重量為Q1，Q2，Qk共有 I 位客戶等待被服務(wù)，每位客戶都有各自需求量G1，G2，Gi。從配送中心出發(fā)的配送車輛對(duì)等待服務(wù)的客戶進(jìn)行配送，以滿足客戶的要求（物品品種、數(shù)量、規(guī)格的要求，配送時(shí)間的要求），最后返回配送中心。

39、要求所有客戶都被服務(wù)到，同時(shí)配送車輛不能超載。最終求出車輛配送路線方案，并達(dá)到一定的優(yōu)化目標(biāo)（如路程最短、費(fèi)用最少、時(shí)間盡量少等）。車輛路線優(yōu)化問(wèn)題是 NP 難題。自從它被提出以來(lái)，由于其應(yīng)用的廣泛性和在經(jīng)濟(jì)上的價(jià)值，一直受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。配送路線優(yōu)化問(wèn)題的主要構(gòu)成要素為：配送車輛、貨物、客戶、配送中心、路網(wǎng)。各要素具體說(shuō)明如下。 （1）車輛，其主要屬性有：車輛類型、裝載量、最大行駛距離、配送開(kāi)始前與完成后所在的配送中心。 （2）貨物，其主要屬性有：重量、送達(dá)時(shí)間和送達(dá)地點(diǎn)等。貨物能否裝在同一配送車輛上取決于貨物屬性。 （3）客戶，其主要屬性有：需求(或供應(yīng))貨物的種類、接受服務(wù)的時(shí)間

40、等。 （4）配送中心，其主要是用來(lái)進(jìn)行集貨、分貨、配貨、送貨等物流作業(yè)，在不同的路線優(yōu)化問(wèn)題中，配送中心的個(gè)數(shù)為一個(gè)或者多個(gè)。 （5）運(yùn)輸網(wǎng)絡(luò)，其組成部分有配送中心、客戶點(diǎn)和車輛行駛路線等。2.1.2物流配送路線的優(yōu)化目標(biāo) 對(duì)車輛配送路線問(wèn)題進(jìn)行優(yōu)化時(shí)，必須要有明確的目標(biāo)和遵循的基本原則。配送路線優(yōu)化問(wèn)題的優(yōu)化目標(biāo)可以從以下幾個(gè)方面考慮： （1）配送效益最高或配送成本最低。 物流企業(yè)是以追求效益為主要目標(biāo)的，通常用企業(yè)利潤(rùn)來(lái)表示，即企業(yè)通常以利潤(rùn)的最大化作為自身經(jīng)營(yíng)的目的。配送成本對(duì)物流企業(yè)利潤(rùn)有直接的影響，以成本最低作為優(yōu)化目標(biāo)與物流企業(yè)利潤(rùn)的最大化有直接的聯(lián)系。當(dāng)與成本及利潤(rùn)相關(guān)的數(shù)據(jù)容易

41、得到和計(jì)算時(shí)，就可以用利潤(rùn)最大或以成本最低作為優(yōu)化目標(biāo)。 （2）配送里程最短。 當(dāng)配送成本與配送里程具有較強(qiáng)的相關(guān)特性，與除此之外的其它因素相關(guān)特性較弱時(shí)，配送里程最短就近似等同于配送成本最低。這時(shí)可以考慮用配送里程最短作為優(yōu)化目標(biāo)，這樣就可以大大簡(jiǎn)化配送路線優(yōu)化方法。當(dāng)配送成本與配送里程的相關(guān)性不明顯優(yōu)于其它因素的時(shí)候，如考慮車輛載重情況、道路運(yùn)行條件等因素，單以路線最短作為優(yōu)化目標(biāo)就變得不適宜。 （3）配送服務(wù)水平最優(yōu)。 當(dāng)準(zhǔn)時(shí)性成為配送的第一要求，或當(dāng)出現(xiàn)某些特殊情況需要確保服務(wù)水平而忽略配送成本時(shí)，則應(yīng)盡量在成本不出現(xiàn)失控的情況下，以服務(wù)水平最優(yōu)為優(yōu)化目標(biāo)。優(yōu)質(zhì)的服務(wù)可以采用較高的服務(wù)

42、價(jià)格，從而保證企業(yè)的合理利潤(rùn)。 （4）配送勞動(dòng)的消耗最小。 它是以物化勞動(dòng)和活勞動(dòng)消耗最小為優(yōu)化目標(biāo)，在許多情況下，如人員緊張、燃料緊張、車輛設(shè)備緊張等，限制了配送作業(yè)，這時(shí)就可以考慮以配送所需要的人員、車輛或其它相關(guān)資源消耗最小作為優(yōu)化目標(biāo)。實(shí)際上，配送路線優(yōu)化問(wèn)題的優(yōu)化目標(biāo)是多元的，但是考慮到優(yōu)化目標(biāo)的目標(biāo)值應(yīng)當(dāng)符合實(shí)際情況，一般要盡可能取得實(shí)用性較強(qiáng)的目標(biāo)值。因此，本文采用成本最低作為優(yōu)化目標(biāo)。2.1.3配送車輛路線優(yōu)化問(wèn)題的約束條件 現(xiàn)實(shí)中，配送車輛路線優(yōu)化問(wèn)題存在著很多方面的約束條件，這些約束條件使得該問(wèn)題在研究和應(yīng)用上產(chǎn)生了許多不同的方向和型態(tài)，基于前文所述的分類標(biāo)準(zhǔn)，一些最重要的

43、約束條件包括： （1）容量約束。任意配送車輛所搭載的貨物總量不能超過(guò)該車輛的載重能力。 （2）配送中心數(shù)目約束。配送中心有一個(gè)或者多個(gè)。 （3）優(yōu)先約束。客戶之間服務(wù)的次序存在著限制。 （4）車型約束。不同客戶的配送要求需要由不同車型來(lái)滿足。 （5）時(shí)間窗約束。包括硬時(shí)間窗約束和軟時(shí)間窗約束。 （6）隨機(jī)約束?？蛻魯?shù)量、配送需求、行駛路線等隨機(jī)出現(xiàn)。 （7）車速約束。車速是否穩(wěn)定。 （8）相容性約束。客戶是否可以被不同配送車輛（配送中心）服務(wù)。 通過(guò)以上分析，本文所要研究的配送車輛路線優(yōu)化問(wèn)題所采用的約束條件為：每個(gè)客戶只能被一輛車服務(wù)，每個(gè)被服務(wù)客戶沒(méi)有優(yōu)先次序，配送車輛的載重情況不超過(guò)自身

44、的載重能力，每個(gè)客戶對(duì)其被服務(wù)的時(shí)間窗的要求為軟時(shí)間窗模式。2.1.4配送路線優(yōu)化問(wèn)題的分類 對(duì)配送車輛路線問(wèn)題類型分析是進(jìn)一步對(duì)問(wèn)題進(jìn)行建模和求解的基礎(chǔ)。現(xiàn)有的對(duì)配送路線優(yōu)化問(wèn)題的分類大致有以下八種：分類依據(jù)分類具體分類說(shuō)明按任務(wù)特征分只送貨問(wèn)題只送貨問(wèn)題的特征為：配送車輛僅考慮從配送中心向客戶送貨；只取貨問(wèn)題的特征為：配送車輛僅考慮從各客戶處把供應(yīng)的貨物取到配送中心；取送貨混合問(wèn)題的特征為：既考慮將客戶需求的貨物從配送中心送到各個(gè)客戶只取貨問(wèn)題混合問(wèn)題按配送中心數(shù)目分單一車場(chǎng)問(wèn)題單一車場(chǎng)問(wèn)題的特征為：配送系統(tǒng)中只有一個(gè)車場(chǎng)、貨場(chǎng)或配送中心；多個(gè)車場(chǎng)問(wèn)題的特征為：配送系統(tǒng)中有多個(gè)車場(chǎng)、貨場(chǎng)或

45、配送中心多個(gè)車場(chǎng)問(wèn)題按配送車輛類型數(shù)目分單一車型問(wèn)題單一車型問(wèn)題的特征為：配送作業(yè)所用車輛都是同一類型，即車輛的參數(shù)如：載重能力、最長(zhǎng)行駛時(shí)間和單次作業(yè)的最大行駛距離等相同；反之多種車型問(wèn)題的特征為配送作業(yè)所用的車輛類型不完全相同多個(gè)車型問(wèn)題按配送車輛路線分車輛開(kāi)放問(wèn)題車輛封閉問(wèn)題車輛開(kāi)放問(wèn)題的特征為：車輛完成其配送任務(wù)后可以不返回出發(fā)點(diǎn)；車輛封閉問(wèn)題的特征為：車輛完成其配送任務(wù)后必須返回出發(fā)點(diǎn)按配送車輛卸載狀況分滿載問(wèn)題滿載問(wèn)題是指當(dāng)客戶的需求量或提供量大于或者等于配送車輛的載重能力時(shí)，需要用一輛或者多輛車來(lái)完成一項(xiàng)配送作業(yè)，其中大多數(shù)配送車輛要滿載運(yùn)行；非滿載問(wèn)題是指當(dāng)客戶的需求量或提供量

46、小于配送車輛的載重能力時(shí)，多個(gè)客戶的配送需求都可以由同一配送車輛來(lái)滿足，整個(gè)配送過(guò)程中配送車輛處于非滿載狀態(tài)；滿載和非滿載混合問(wèn)題是指當(dāng)一部分客戶的需求量或提供量大于或者等于配送車輛的載重能力，而一部分客戶的需求量或提供量小于配送車輛的載重能力時(shí)非滿載問(wèn)題混合問(wèn)題按客戶時(shí)間需求分無(wú)時(shí)間窗問(wèn)題無(wú)時(shí)間窗問(wèn)題的特點(diǎn)是客戶對(duì)服務(wù)時(shí)間無(wú)具體要求；有時(shí)間窗問(wèn)題的特點(diǎn)是客戶要求配送車輛必須在規(guī)定的時(shí)間范圍內(nèi)將貨物送達(dá)或取走。有時(shí)間窗問(wèn)題又可以分為硬時(shí)窗問(wèn)題和軟間窗問(wèn)題，其中硬時(shí)窗是指，客戶要求必須在指定的時(shí)間范圍內(nèi)進(jìn)行配送作業(yè)，不能提前也不能拖后否則需要等待或者不能為其服務(wù)，軟時(shí)窗是指，客戶要求配送車輛盡可

47、能在規(guī)定的時(shí)間范圍為其服務(wù)但也可以提前或拖后，只是要受到一定的懲罰，如交罰金有時(shí)間床問(wèn)題按優(yōu)化目標(biāo)數(shù)分單目標(biāo)問(wèn)題單目標(biāo)問(wèn)題是指選擇某一最優(yōu)或較優(yōu)指標(biāo)作為優(yōu)化目標(biāo)，如配送路線最短。多目標(biāo)問(wèn)題則是指同時(shí)選擇多個(gè)最優(yōu)或較優(yōu)的指標(biāo)作為優(yōu)化目標(biāo)，如同時(shí)要求配送路線最短和成本最低。路線優(yōu)化模型的指標(biāo)一般包括：配送時(shí)間最短、配送路線最短、成本最低。一般情況下這三個(gè)目標(biāo)是統(tǒng)一的：距離最短，也就意味著時(shí)間最短，成本也最低，但是很多情況下，也有出現(xiàn)多目標(biāo)不統(tǒng)一、甚至互相矛盾的可能多目標(biāo)問(wèn)題按客戶和路網(wǎng)特點(diǎn)分靜態(tài)問(wèn)題靜態(tài)問(wèn)題的特征為：客戶的位置、數(shù)目、需求，以及天氣、路況等因素是確定的和已知的；動(dòng)態(tài)問(wèn)題的特征為：客

48、戶的位置數(shù)目、需求，以及天氣、路況等因素是隨機(jī)變化的。動(dòng)態(tài)問(wèn)題表2-12.2典型配送車輛路線優(yōu)化問(wèn)題的數(shù)學(xué)模型 本文此處以經(jīng)典的帶時(shí)間窗配送車輛路線優(yōu)化問(wèn)題為例，來(lái)說(shuō)明配送車輛路線優(yōu)化問(wèn)題的一般模型及表達(dá)方式。帶時(shí)間窗配送車輛路線優(yōu)化問(wèn)題的一般描述為：有一個(gè)配送中心（含車場(chǎng)），擁有的配送車輛數(shù)為 K 輛，容量分別為 Qk（k=1，2，K）。有 I 個(gè)客戶點(diǎn)需要被服務(wù)，客戶點(diǎn) i 的作業(yè)量為 Gi，配送車輛 k 到達(dá)客戶點(diǎn) i 的時(shí)刻為kis ，并且客戶點(diǎn) i 的配送作業(yè)需要在規(guī)定的時(shí)間窗ETi，LTi內(nèi)完成，其中 ETi表示客戶點(diǎn) i 允許配送作業(yè)開(kāi)始的最早時(shí)間，LTi表示客戶點(diǎn) i 允許配送

49、作業(yè)開(kāi)始的最遲時(shí)間。如果配送車輛到達(dá)客戶點(diǎn) i 的時(shí)間早于 ETi，則配送車輛需要在客戶點(diǎn) i 處等待，如果配送車輛到達(dá)客戶點(diǎn) i 的時(shí)間晚于 LTi，則客戶點(diǎn) i 的配送作業(yè)將被延遲進(jìn)行，同時(shí)配送車輛需要接受處罰。 一般情況下帶時(shí)間窗路線優(yōu)化問(wèn)題需要考慮以下幾個(gè)約束條件： （1）各客戶點(diǎn)只可以由一輛車配送且只能被配送一次，不考慮多輛車同時(shí)為一個(gè)客戶點(diǎn)服務(wù)的情況； （2）配送中心（或車場(chǎng)）只有一個(gè)，所有車輛從配送中心出發(fā)，車輛在完成所有作業(yè)之后需要回到配送中心； （3）各配送線路上客戶點(diǎn)的作業(yè)總量不應(yīng)大于該線路上作業(yè)車輛的載重量； （4）每個(gè)客戶點(diǎn)的配送作業(yè)量必須小于為其服務(wù)的車輛的最大載重量

50、，即只需一臺(tái)配送車輛即可滿足該客戶點(diǎn)的配送作業(yè)需求。對(duì)模型參數(shù)定義如下：客戶i由k車來(lái)服務(wù)其他車輛k由i到j(luò)其他表示客戶點(diǎn) i 到客戶點(diǎn) j 的運(yùn)輸成本；表示配送車輛由于等待失去的機(jī)會(huì)成本；表示配送車輛由于遲到需要支付的罰金。在僅考慮裝載約束和時(shí)間窗約束的條件下，帶時(shí)間窗的配送車輛路線優(yōu)化模型可以表示為： 任意的k i=1，2，I j=1，2，I，任意的k i=1，2，I，任意的k=0或1i，j=1，2，,I，任意的k=0或1 i=1，2，I，任意的k 其中式中的目標(biāo)函數(shù)，表示為各客戶點(diǎn)配送的目標(biāo)是使配送成本最小。目標(biāo)函數(shù)由兩部分組成，前半部分為車輛在線路上進(jìn)行配送時(shí)所消耗的運(yùn)輸成本，后半部分

51、為車輛在為各個(gè)客戶點(diǎn)進(jìn)行配送的過(guò)程中，由早到所損失的機(jī)會(huì)成本及遲到所支付的罰金之和。這一目標(biāo)函數(shù)的具體意義為：要在滿足配送路線最短的條件下，盡量考慮車輛配送的時(shí)間窗約束，以使得配送車輛運(yùn)輸成本及時(shí)間成本兩者所代表的配送成本最低。該模型的不足是忽略了配送車輛載重情況及道路等級(jí)情況對(duì)車輛運(yùn)輸成本的影響。3現(xiàn)代運(yùn)籌學(xué)方法在物流配送路線優(yōu)化中的實(shí)際應(yīng)用3.1傳統(tǒng)啟發(fā)式節(jié)約法及其應(yīng)用3.1.1節(jié)約法描述 利用里程節(jié)約法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配送方的運(yùn)輸能力及其到客戶之間的距離和各客戶之間的相對(duì)距離來(lái)制定使配送車輛總的周轉(zhuǎn)量達(dá)到或接近最小的配送方案。假設(shè)條件： （1）配送的是同一種或相類似的貨物

52、； （2）各用戶的位置及需求量已知； （3）配送方有足夠的運(yùn)輸能力； （4）設(shè)狀態(tài)參數(shù)為tij, tij是這樣定義的： tij=1,表示客戶I，J在同一送貨路線上；0，表示客戶I，J不在同一送貨線路上。 t0j =2表示由送貨點(diǎn)p0向客戶J單獨(dú)派車送貨。 且所有狀態(tài)參數(shù)應(yīng)滿足下式： 式中：N-客戶數(shù) 利用節(jié)約法制定出的配送方案除了使總的周轉(zhuǎn)量最小外，還應(yīng)滿足： （1）方案能滿足所有客戶的到貨時(shí)間要求； （2）不使車輛超載； （3）每輛車每天的總運(yùn)行時(shí)間及里程滿足規(guī)定的要求。 如圖3-1所示，設(shè)p0為配送中心，分別向用戶pi和pj送貨。p0到pi和pj的距離分別為d0i和d0j，兩個(gè)用戶pi和p

53、j之間的距離為dij，送貨方案只有兩種即配送中心p0向用戶pi, pj分別送貨和配送中心p0向用戶pi, pj同時(shí)送貨，如圖11-7a)和b)。比較兩種配送方案： 方案a）的配送路線為p0pip0pjp0,配送距離為da=d0i+d0j 方案b)配送路線p0pipjp0,配送距離為db=. d0i+d0j+dij 顯然，da不等于db，我們用sij表示里程節(jié)約量，即方案b)比方案a)節(jié)約的配送里程： 根據(jù)節(jié)約法的基本思想，如果一個(gè)配送中心p0分別向N個(gè)客戶pj(j=1.2n)配送貨物，在汽車載重能力允許的前提下，每輛汽車的配送線路上經(jīng)過(guò)的客戶個(gè)數(shù)越多，里程節(jié)約量越大，配送線路越合理。圖3-13

54、.1.2節(jié)約法應(yīng)用實(shí)例 例：某一配送中心p0向10個(gè)客戶pj(j=1,2,10)配送貨物，其配送網(wǎng)絡(luò)如圖3-2所示。圖中括號(hào)內(nèi)的數(shù)字表示客戶的需求量（T），線路上的數(shù)字表示兩節(jié)點(diǎn)之間的距離。配送中心有2t和4t兩種車輛可供使用，試制定最優(yōu)的配送方案。 圖3-2 解：第一步：計(jì)算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計(jì)算配送中心與客戶及客戶之間的最短距離，結(jié)果見(jiàn)表3-3。 P010P194P2795P3814105P48181496P58181715137P6313121011106P74141311121282P810111517181817119P97481315151510118P10表3-

55、3 第二步：計(jì)算節(jié)約里程sij,結(jié)果見(jiàn)表3-4。P115P2811P34710P403610P500039P6000015P70000045P894000125P91381000009P10表3-4 第三步：將節(jié)約sij,進(jìn)行分類，按從大到小的順序排列，得表3-5。節(jié)約里程項(xiàng)目分類表序號(hào)路線節(jié)約里程序號(hào)路線節(jié)約里程1p1p21513p6p752p1p101313p7p853p2p31113p8p954p3p41016p1p444p4p51016p2p946p1p9916p6p846p5p6919p2p536p9p10919p4p639p1p3821p7p929p2p10822p3p10111p2p4722p5p7112p3p6622p6p91表3-5 第四步：確定配送線路。從分類表中，按節(jié)約里程大小順序，組成線路圖。 （1）初始方案：對(duì)每一客戶分別單獨(dú)派車送貨，結(jié)果如圖3-6