畢業(yè)設(shè)計(jì)物流運(yùn)輸

1、石家日和更松術(shù)手陸畢業(yè)設(shè)計(jì)物流運(yùn)輸，配送效率提高及方案設(shè)計(jì)明李瑞論文作者:指導(dǎo)教師：肖揚(yáng)管理物流業(yè)：專 理：系（院）管系2016答辯日期：36年 月曰目錄摘要 I第1章緒論 11.1 課題背景 11.2 21.2.1 31.2.2 61.2.3 71.2.4 101.2.5 151.3 181.3.1 201.3.2 211.4 本文主要研究?jī)?nèi)容 221.5 本文結(jié)構(gòu) 23早 242.1242.5 30結(jié)論 獻(xiàn) 42致謝摘要高效率合理的配送是物流系統(tǒng)順利運(yùn)行的保證，配送線路安排的合理與否對(duì)配送 速度、成本、效益影響很大。正確合理地安排車輛的配送線路，實(shí)現(xiàn)合理的線路 運(yùn)輸，可以有效地節(jié)約運(yùn)輸時(shí)間

2、，增加車輛利用率，從而降低運(yùn)輸成本，提高企 業(yè)經(jīng)濟(jì)效益與客戶服務(wù)水平，使企業(yè)達(dá)到科學(xué)化的物流管理，這也是企業(yè)提高自 身競(jìng)爭(zhēng)力的有效途徑之一。物流配送路徑優(yōu)化問(wèn)題具有很高的計(jì)算復(fù)雜性，屬于NP完全難問(wèn)題，高效的精確算法存在的可能性不大，但可根據(jù)啟發(fā)算法求得近似最優(yōu)解。本文首先對(duì)物流配送進(jìn)行概述，并運(yùn)用節(jié)約算法、掃描算法以及改進(jìn) 后的最近插入法對(duì)配送線路進(jìn)行優(yōu)化，提出最優(yōu)配送方案。.緒論隨著社會(huì)主義市場(chǎng)經(jīng)濟(jì)的不斷發(fā)展，作為“第三利潤(rùn)源泉”的物流對(duì)經(jīng)濟(jì)活動(dòng)的 影響日益明顯，引起了人們?cè)絹?lái)越多的重視，成為當(dāng)前“最重要的競(jìng)爭(zhēng)領(lǐng)域”。配送是現(xiàn)代物流的一個(gè)重要環(huán)節(jié)，隨著物流的全球化、信息化及一體化，配送在整

3、個(gè)物流系統(tǒng)中的作用變得越來(lái)越重要。 配送是連接生產(chǎn)與消費(fèi)之間的一種中介 服務(wù)。它是指按客戶（包括零售商店、用戶等）的訂貨要求（包括貨物種類、數(shù)量和 時(shí)間等方面的要求），在物流中心（包括配送中心、倉(cāng)庫(kù)、車站、港口等）進(jìn)行分貨、 配貨工作，并將配好的貨物及時(shí)送交收貨人的物流活動(dòng)。配送不是單純的運(yùn)輸或送貨，而是運(yùn)輸與其他活動(dòng)（集貨，分貨，配貨）的組合， 是“配”與“送”的有機(jī)結(jié)合。因此對(duì)于配送問(wèn)題的研究可分為對(duì)“配”和“送”兩方面的研究?！芭洹敝饕獮榕渌椭行倪x址問(wèn)題，“送”包括旅行商問(wèn)題（TSP）、 車輛路線優(yōu)化問(wèn)題（VRP）。由于選址的外部因素（經(jīng)濟(jì)，基礎(chǔ)設(shè)施，環(huán)境等）及 內(nèi)部因素（企業(yè)戰(zhàn)略，勞動(dòng)

4、力成本和素質(zhì)等）的影響，單純考慮距離問(wèn)題的選址 是不合理的，因此在本文中不對(duì)“配”進(jìn)行研究，主要對(duì)“送”進(jìn)行研究。配送路線的優(yōu)化，是配送優(yōu)化中的一個(gè)關(guān)鍵環(huán)節(jié)。 在配送過(guò)程中，配送線路合理 與否對(duì)配送速度、成本、效益影響很大。設(shè)計(jì)合理、高效的配送路線方案，不僅 可以減少配送時(shí)間，降低作業(yè)成本，提高企業(yè)的效益，而且可以更好地為客戶服 務(wù)，提高客戶的滿意度，維護(hù)企業(yè)良好的形象。配送線路優(yōu)化是指對(duì)一系列的發(fā)貨點(diǎn)和收貨點(diǎn)， 組織適當(dāng)?shù)男熊嚶肪€使車輛有序 的通過(guò)它們，在滿足一定的約束條件下（貨物需求量與發(fā)送量，車輛容量限制， 行駛里程限制），力爭(zhēng)實(shí)現(xiàn)一定的目標(biāo)（行駛里程最短，使用車輛盡可能少）。但 配送作

5、業(yè)情況復(fù)雜多變，不僅存在配送點(diǎn)多、貨物種類多、道路網(wǎng)復(fù)雜、路況多 變等情況，而且運(yùn)輸服務(wù)地區(qū)內(nèi)需求網(wǎng)點(diǎn)分布也不均勻， 使得線路優(yōu)化問(wèn)題是一 個(gè)無(wú)確定解多項(xiàng)式難題，需要啟發(fā)算法去求得近似最優(yōu)解。1.1 物流配送的概念配送（distribution）起源于“送貨上門”。20世紀(jì)60年代初期，生產(chǎn)企業(yè)或中轉(zhuǎn) 倉(cāng)庫(kù)根據(jù)客戶的需求，將貨物準(zhǔn)確的運(yùn)送到客戶手中，形成了配送的雛形一一“普 通送貨。隨著客戶對(duì)產(chǎn)品多樣化和差異化的要求，為了滿足客戶的需求，原始的普通送貨開(kāi)始轉(zhuǎn)向分揀、配貨、送貨一體化。因此產(chǎn)生了配送。按照國(guó)家質(zhì)量技術(shù)監(jiān)督局發(fā)布的中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)“物流術(shù)語(yǔ)”（GB/T18354-2001），

6、配送是指在經(jīng)濟(jì)合理區(qū)域范圍內(nèi)根據(jù)用戶要求， 對(duì)物品進(jìn)行揀選、 加工、包裝、分割、組配等作業(yè)，并按時(shí)送達(dá)指定地點(diǎn)的物流活動(dòng) 1。1.2 物流配送的功能配送作為一種新型的物流手段，伴隨著生產(chǎn)的不斷發(fā)展而日趨成熟。發(fā)展配送， 無(wú)論對(duì)于物流系統(tǒng)的完善，企業(yè)的發(fā)展，還是整個(gè)經(jīng)濟(jì)社會(huì)效益的提高，都具有 重要的作用。)配送完善和優(yōu)化了物流系統(tǒng)。第二次世界大戰(zhàn)后，高水平的干線運(yùn)輸呼喚1(. 支線運(yùn)輸和小搬運(yùn)配套，但支線運(yùn)輸和小搬運(yùn)在適應(yīng)性、靈活性、服務(wù)性上的欠 缺，致使運(yùn)力不合理、運(yùn)輸成本過(guò)高。配送的出現(xiàn)使干線運(yùn)輸、支線運(yùn)輸及小搬 運(yùn)統(tǒng)一，輸送過(guò)程得以優(yōu)化和完善。(2)配送提高了末端物流的效益。配送通過(guò)大批量

7、進(jìn)貨，集中發(fā)貨，以及將多 個(gè)小批量集中一起大批量發(fā)貨，都能有效的節(jié)省運(yùn)力，實(shí)現(xiàn)經(jīng)濟(jì)運(yùn)輸，降低成本， 使末端的物流經(jīng)濟(jì)效益得到提高。(3)配送通過(guò)集中庫(kù)存使企業(yè)實(shí)現(xiàn)低庫(kù)存或零庫(kù)存。 采取準(zhǔn)時(shí)制配送方式之后， 生產(chǎn)企業(yè)完全可以依靠配送中心的準(zhǔn)時(shí)配送而不需保持自己的庫(kù)存或保持少量 安全庫(kù)存而不必留有經(jīng)常庫(kù)存。(4)配送簡(jiǎn)化事物，方便客服。采用配送的方式，客戶只需向一處訂購(gòu)，或一 個(gè)進(jìn)貨單位聯(lián)系就可以訂購(gòu)到以往需要去許多地方才能頂?shù)降呢浳铮虼舜蟠蟮臏p輕了客戶的工作量和負(fù)擔(dān)，也節(jié)省了事務(wù)的開(kāi)支。(5)配送可以降低整個(gè)社會(huì)物資的庫(kù)存水平。發(fā)展配送，實(shí)行集中庫(kù)存，整個(gè) 社會(huì)物資的庫(kù)存總量必然低于各企業(yè)分散

8、的庫(kù)存總量。同時(shí)，配送有利于靈活高 度，有利于發(fā)揮物資的作用。止匕外，集中庫(kù)存可以發(fā)揮規(guī)模經(jīng)濟(jì)優(yōu)勢(shì)，降低庫(kù)存 成本。1.3 配送路線優(yōu)化的意義配送合理化與否是配送決策系統(tǒng)的重要內(nèi)容，配送線路的合理與否又是配送合理 化的關(guān)鍵。選擇合的理配送路線，對(duì)企業(yè)和社會(huì)都具有很重要的意義。對(duì)企業(yè)來(lái)說(shuō)，(1)優(yōu)化配送路線，可以減少配送時(shí)間和配送里程，提高配送 效率，增加車輛利用率，降低配送成本。(2)可以加快物流速度，能準(zhǔn)時(shí)、快速 地把貨物送到客戶的手中，提高客戶滿意度。(3)使配送作業(yè)安排合理化，提高 企業(yè)作業(yè)效率，有利于企業(yè)提高競(jìng)爭(zhēng)力與效益 30對(duì)社會(huì)來(lái)說(shuō)，它可以節(jié)省運(yùn)輸車輛，減少車輛空載率，降低了社會(huì)物

9、流成本， 對(duì)其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。 與此同時(shí)，還能緩解交通緊張狀況，減少 噪聲、尾氣排放等運(yùn)輸污染，對(duì)民生和環(huán)境也有不容忽視的作用。1.4 國(guó)內(nèi)外有物流管理發(fā)展研究狀況物流業(yè)的發(fā)展水平反映了一個(gè)國(guó)家的綜合國(guó)力和企業(yè)市場(chǎng)競(jìng)爭(zhēng)能力。當(dāng)今，全球經(jīng)濟(jì)新秩序正在建立和調(diào)整，世界各國(guó)以及區(qū)域經(jīng)濟(jì)組織都非常重視物流水平 對(duì)于本國(guó)經(jīng)濟(jì)發(fā)展、國(guó)民生活素質(zhì)和軍 事勢(shì)力的影響。國(guó)內(nèi)因?yàn)楝F(xiàn)代信息技術(shù) 飛速發(fā)展的，物流業(yè)也依托這個(gè)大的環(huán)境快速發(fā)展。 一些大型企業(yè)的物流管理信 息系統(tǒng)具備了以下幾點(diǎn)特點(diǎn)。信息化：網(wǎng)絡(luò)時(shí)代物流信息化必然要求。物流信息化表現(xiàn)為物流信息的商品化、 物流信息收集的數(shù)據(jù)庫(kù)化和代碼化、

10、物流信息處理的電子化和計(jì)算機(jī)化、 物流信 息傳遞的標(biāo)準(zhǔn)化和實(shí)時(shí)化、物流信息存儲(chǔ)的數(shù)字化等。自動(dòng)化：自動(dòng)化的基礎(chǔ)是信息化，自動(dòng)化的核心是機(jī)電一體化，自動(dòng)化的外在表 現(xiàn)是無(wú)人化，自動(dòng)化的效果是省力化，另外還可以擴(kuò)大物流作業(yè)能力、 提高勞動(dòng) 生產(chǎn)力、減少物流作業(yè)的差錯(cuò)等。網(wǎng)絡(luò)化：物流領(lǐng)域的網(wǎng)絡(luò)化有兩層含義：一是物流配送系統(tǒng)的計(jì)算機(jī)通信網(wǎng)絡(luò)， 包括物流配送中心與供應(yīng)商或制造商的聯(lián)系要通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)，另外與下游顧客之間的聯(lián)系也要通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)通信，；二是組織的網(wǎng)絡(luò)化，即所謂的組織內(nèi)部 網(wǎng)（Intranet）?？梢?jiàn)，物流的網(wǎng)絡(luò)化成為現(xiàn)代物流活動(dòng)的主要特征。智能化：這是物流自動(dòng)化、信息化的一種高層次應(yīng)用，物

11、流作業(yè)過(guò)程大量的運(yùn)籌 和決策，為了提高物流現(xiàn)代化的水平，物流的智能化已成為現(xiàn)代物流發(fā)展的一個(gè) 新趨勢(shì)。國(guó)外物流的發(fā)展趨勢(shì)，隨著經(jīng)濟(jì)全球化步伐的加快，科學(xué)技術(shù)尤其是信息技術(shù)、 通訊技術(shù)的發(fā)展，跨國(guó)公司的出現(xiàn)所導(dǎo)致的本土化生產(chǎn)、全球采購(gòu)、全球消費(fèi)趨 勢(shì)的加強(qiáng)，現(xiàn)代物流的發(fā)展呈現(xiàn)出新的特點(diǎn)：（一）,電子物流的興起。絡(luò)的電子商務(wù)的迅速發(fā)展促使了電子物流的興起。電子物流可以在線,追蹤發(fā)出的貨物，在線規(guī)劃投遞路線，在線進(jìn)行物流調(diào)度，在線進(jìn)行貨運(yùn)檢查?？梢哉f(shuō)電 子物流將是21世紀(jì)物流發(fā)展的大趨勢(shì)。（二）.物流規(guī)模和物流活動(dòng)的范圍進(jìn)一步擴(kuò)大，物流企業(yè)將向集約化與協(xié) 同,21世紀(jì)是一個(gè)物流全球化的時(shí)代，企業(yè)之間

12、的競(jìng)爭(zhēng)將十分激烈?；l(fā)展。 要滿足全球化或區(qū)域化的物流服務(wù)，企業(yè)規(guī)模必須擴(kuò)大形成規(guī)模效益。規(guī)模的擴(kuò) 大可以是企業(yè)合并，也可以是企業(yè)間的合作與聯(lián)盟，主要表現(xiàn)在兩個(gè)方面： 和不同類型的物流企業(yè)在空.問(wèn)上集中布局的場(chǎng)所，是具有一定規(guī)模和綜合服務(wù) 功能的物流集結(jié)點(diǎn)。物流園區(qū)的建設(shè)，有利于實(shí)現(xiàn)物流企業(yè)的專業(yè)化和規(guī)?；?， 發(fā)揮它們的整體優(yōu)勢(shì)和互補(bǔ)優(yōu)勢(shì)。帶動(dòng)國(guó)際物流業(yè)加速向全球化方向發(fā)展， 而物流全球化的發(fā)展走勢(shì)，又必然推動(dòng) 和促進(jìn)各國(guó)物流企業(yè)的聯(lián)合和并購(gòu)活動(dòng)。（三）物流服務(wù)的優(yōu)質(zhì)化和全球化。服務(wù)的要求越來(lái)越高；物流脹勢(shì)的優(yōu)質(zhì)化是物流今后發(fā)展的重要趨勢(shì)。5個(gè)亮點(diǎn)“Right”的服務(wù)，即把好的產(chǎn)品（The r

13、ight porduct）在規(guī)定白向時(shí)間（At the right time）;規(guī)定的地點(diǎn)（In the right place）,以適當(dāng)?shù)臄?shù)量（In the right quantity）,合 適的價(jià)格（At the right Price）提供給客戶將成為物流企業(yè)優(yōu)質(zhì)服務(wù)的共同標(biāo)準(zhǔn)。物流成本己不再是客戶選擇物流服務(wù)的唯一標(biāo)準(zhǔn)，人們更多的是注重物流服務(wù)的質(zhì)量。同時(shí)物流服務(wù)的全球化是今后發(fā)展的又一重要趨勢(shì)。（四）第三方物流的快速發(fā)展。Third party logistics）是指在物流渠道中由中間商提供的服務(wù)。,中間商以合同的 形式在一定期限內(nèi)，提供企業(yè)所需的全部或部分物流服務(wù)、 第三方物流

14、提供者是 一個(gè)為外部客戶管理、控制和提供物流服務(wù)作業(yè)的公司；他們并不在供應(yīng)鏈中占有一席之地，僅是第三 方，但通過(guò)提供一整套物流活動(dòng)來(lái)服務(wù)于供應(yīng)鏈。（五）綠色物流是物流發(fā)展的又一趨勢(shì)。發(fā)展，但是物流的發(fā)展同時(shí)也會(huì)給城市環(huán)境帶來(lái)不利 的影響，如運(yùn)輸工具的噪 聲、污染排放、對(duì)交通的阻塞等，以及生產(chǎn)及生活中的廢棄物的不當(dāng)處理所造成 的對(duì)環(huán)境的影響。綠色物流的另一方面就是建立工業(yè)和生活廢料處理的物流系統(tǒng)。（六）不斷采用新的科學(xué)技術(shù)改造物流裝備和提高管理水平。.為核心，以信息技術(shù)、運(yùn)輸技術(shù)、配送技術(shù)、裝卸搬運(yùn)技術(shù)、自動(dòng)化倉(cāng)儲(chǔ)技術(shù)、庫(kù)存控制技術(shù)、包裝技術(shù)等專業(yè)技術(shù)為支撐的現(xiàn)代化物流裝備技術(shù)格局。今后進(jìn)一步的

15、發(fā)展方向是：一一自動(dòng)導(dǎo)引小車（AGV）,技術(shù)，搬運(yùn)機(jī)器人（Robot Systemj）技術(shù)等。 電子識(shí)別和電子跟 .蹤技術(shù)，智能運(yùn)輸系統(tǒng)（ITS）。一一信息化、機(jī)械化、自動(dòng)化、智，能化于一 體。信息化一一采用無(wú)線互聯(lián)網(wǎng)技術(shù)，衛(wèi)星定位技術(shù)（GPS）,地理信息系統(tǒng)（GIS）, 射頻標(biāo)識(shí)技術(shù)（RF）等。物流配送模型及方法描述3.1多回路運(yùn)輸一VRP模型多回路運(yùn)輸問(wèn)題是現(xiàn)實(shí)中很普遍的一種調(diào)配問(wèn)題，特別對(duì)于有大量服務(wù)對(duì)象的實(shí)體，例如擁有一個(gè)上千客戶的企業(yè)。此類調(diào)配的核心問(wèn)題是如何對(duì)車輛進(jìn)行調(diào)度。 因此，VRP （Vehicle Routing Problem）模型也應(yīng)運(yùn)而生，成了解決多回路問(wèn)題的 一個(gè)相

16、當(dāng)成功的模型。該問(wèn)題研究目標(biāo)是：對(duì)一系列顧客需求點(diǎn)設(shè)計(jì)適當(dāng)?shù)穆肪€， 使車輛有序地通過(guò)他 們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里 程限制等），達(dá)到一定的優(yōu)化目標(biāo)（如里程最短，費(fèi)用最小，時(shí)間盡量少等）。它 涉及了多輛交通工具的服務(wù)對(duì)象的選擇和路徑確定兩方面問(wèn)題6。一個(gè)典型的VRP模型可以如下表述：（1）基本條件 現(xiàn)有m輛相同的車輛停在一個(gè)共同的源點(diǎn) 0v,它需給n個(gè)客戶 提供貨物，顧客為12n,vvv、，。（2）模型目標(biāo) 確定所需的車輛數(shù)N,并指派這些車輛到一個(gè)回路中，同時(shí)包括 回路內(nèi)的路徑安排和調(diào)度，使總費(fèi)用最小。（3）限制條件：N不大于m；每一個(gè)訂單都要完成；每

17、輛車完成任務(wù)后都要回 到源點(diǎn)0v;車輛的容量限制不能超過(guò)；特殊問(wèn)題還需考慮時(shí)窗限制；運(yùn)輸規(guī)章 限制。3.2節(jié)約算法問(wèn)題，它VRP）是用來(lái)解決運(yùn)輸車輛數(shù)目不確定的 Saving Algorithm節(jié)約算法（. 是目前用來(lái)解決VRP模型最有名的啟發(fā)式算法。3.2.2節(jié)約里程算法主要步驟已知條件：需求點(diǎn)集RN=1,2,?, n,各點(diǎn)需求量iR,各點(diǎn)間最短距離ijc。第一步， 形成一個(gè)初始解。確定各車輛配送點(diǎn)集令j=1,2,?,n （先 采取單點(diǎn)配送）。第二步，進(jìn)行節(jié)約度的計(jì)算。計(jì)算所有點(diǎn)對(duì)的節(jié)約度錯(cuò)誤！未找到引用源。，然后 對(duì)計(jì)算結(jié)果進(jìn)行升序排列。第三步，進(jìn)行回路的合并。從升序排列的節(jié)約度序列中的最

18、上面的值開(kāi)始，直到節(jié)約里程的隊(duì)列空為止，重復(fù)下列步驟：按照節(jié)約里程隊(duì)列從大到小的順序，分析客戶i和j之間合并的可能性（是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并 次數(shù)不超過(guò)2）,將i, j連接起來(lái)，即可令。如果不是這樣，則從節(jié),約里程隊(duì)列中去除 當(dāng)前的節(jié)約里程，分析下一個(gè)客戶對(duì)9。3.3掃描算法掃描算法（Sweep Algorithm）也是用于求解車輛數(shù)目不限制的 VRP問(wèn)題，與節(jié) 約算法不同的是，它屬于亞啟發(fā)式算法，而節(jié)約算法屬于構(gòu)造算法。3.3.1掃描算法的基本原理掃描算法是一種“先分組后路線”的算法。所謂分組，即指派給每輛車一組點(diǎn)。一種簡(jiǎn)單的分組方法是將以配送中心為原點(diǎn)的坐標(biāo)平面劃分為

19、多個(gè)扇形區(qū)域，并初步將每個(gè)扇形區(qū)域的點(diǎn)分派給一輛車，然后擴(kuò)充路線。如果在進(jìn)行了一次“分 組-路線”的路線構(gòu)造后，還存在未分配點(diǎn)，則再進(jìn)行“分組 -路線”程序。如此 反復(fù)，直到所有的點(diǎn)均已分配為止10。3.3.2掃描算法的主要步驟（1）以起始點(diǎn)0點(diǎn)作為極坐標(biāo)系的原點(diǎn)，并一連通圖中的任意一顧客點(diǎn)和原點(diǎn) 的連線定義為角度零，建立極坐標(biāo)系。然后對(duì)所有的顧客所在的位置，進(jìn)行極坐 標(biāo)變換。（2）分組 從最小角度的顧客開(kāi)始建立一個(gè)組，按逆時(shí)針?lè)较?，將?客逐個(gè)加入到組中，直到顧客的需求總量超出了負(fù)載的限制。然后繼續(xù)建立一個(gè)新的組，繼續(xù)按逆時(shí)針?lè)较?，將客戶加入組中。（3）重復(fù)（2）中的過(guò)程，直到所有客戶都被分

20、類為止。（4）路徑優(yōu)化對(duì)各個(gè)組內(nèi)的單回路進(jìn)行路徑優(yōu)化。3.4改進(jìn)后的最近插入法TSP模型是單回路運(yùn)輸問(wèn)題的最為典型的一個(gè)模型，它的全稱是TravelingSalesman Problem1中文叫做旅行商問(wèn)題。它是一個(gè)典型的NP-Hard問(wèn)題，對(duì)于 大規(guī)模的線路優(yōu)化問(wèn)題，無(wú)法獲得最優(yōu)解。最近插入法就是一種解決此問(wèn)題的啟 發(fā)式算法。3.4.1最近插入法最近插入法是Rosenkrantz和Stearns等人在1977年提出的一種用于解決TSP（旅行商）問(wèn)題的算法。最近插入法由四步完成：（1）找到0ic最小的節(jié)點(diǎn)iv,形成一個(gè)子回路（subtour）,。（2）在剩下的節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)

21、最近的節(jié)點(diǎn) kvo（3）在子回路中找到一條?。╥, j）,使得ikc+kjc-ijc最小，然后將節(jié)點(diǎn)iv插入到 節(jié)點(diǎn)iv, jv之間，用兩條新的?。╥, k）, （k, j）代替原來(lái)的?。╥, j）,并將節(jié)點(diǎn) kv加入到子回路中。這樣，子回路,直到所有的節(jié)點(diǎn)都加入到子回路中。）3 （、）2）重復(fù)步驟（4 就演變?yōu)榱艘粋€(gè)TSP的解由于最近插入法解決的是單回路運(yùn)輸問(wèn)題， 故筆者在此方法基礎(chǔ)上進(jìn)行改進(jìn)和修 正，使其能解決多回路運(yùn)輸 VRP問(wèn)題。有改進(jìn)的方法如下：3.4.2改進(jìn)的最近插入法（1）找到0ic最小的節(jié)點(diǎn)iv,形成一個(gè)子回路（subtour）,。（2）在剩下的節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn) kvo若此時(shí)回路的 總貨運(yùn)量未超過(guò)車的載重限制，則繼續(xù)步驟（3）。否則，轉(zhuǎn)（1）尋找新的一條 回路。（3）在子回路中找到一條?。╥, j）,使得ikc+kjc-ijc最小，然后將節(jié)點(diǎn)iv插入 到節(jié)點(diǎn)iv, jv之間，用兩條新的?。╥, k）, （k, j）代替原來(lái)