基于最近插入法的X公司物流配送路線(xiàn)優(yōu)化方案研究

【文章摘要】

高效合理的配送作業(yè)是物流系統(tǒng)順利運(yùn)行的保證，配送線(xiàn)路的合理安排對(duì)配送速度、配送成本以及配送效益影響很大。本文首先對(duì)物流配送的相關(guān)理論進(jìn)行概述，然后以X公司的配送現(xiàn)狀為例，運(yùn)用改進(jìn)后的最近插入法對(duì)配送線(xiàn)路進(jìn)行優(yōu)化，提出優(yōu)化的配送方案。

【關(guān)鍵詞】

配送；配送路線(xiàn)優(yōu)化；最近插入法

1 物流配送概述

1.1配送的概念

配送位于物流活動(dòng)的最末端，是直接與消費(fèi)者相連的環(huán)節(jié)，在整個(gè)的物流成本中，占有相當(dāng)高的比例。按照國(guó)家質(zhì)量技術(shù)監(jiān)督局發(fā)布的中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)“物流術(shù)語(yǔ)”（GB/T 18354—2001），配送是指在經(jīng)濟(jì)合理區(qū)域范圍內(nèi)根據(jù)用戶(hù)要求，對(duì)物品進(jìn)行揀選、加工、包裝、分割、貼標(biāo)簽、組配等作業(yè)，并按時(shí)送達(dá)指定地點(diǎn)的物流活動(dòng)。

1.2配送路線(xiàn)優(yōu)化的意義

配送路線(xiàn)優(yōu)化是指對(duì)多個(gè)發(fā)貨點(diǎn)和收貨點(diǎn)，組織適當(dāng)?shù)男熊?chē)路線(xiàn)，使車(chē)輛有序的到達(dá)并通過(guò)，在滿(mǎn)足一定的條件下，實(shí)現(xiàn)最終目標(biāo) 。

對(duì)企業(yè)和社會(huì)來(lái)說(shuō)，選擇合理的配送路線(xiàn)具有很重要的意義：

（1）優(yōu)化配送路線(xiàn)，可以減少配送時(shí)間，縮短配送里程，提高配送效率，增加車(chē)輛利用率，降低配送成本。

（2）優(yōu)化配送路線(xiàn)，可以加快物流速度，更快速地將貨物送到，提高客戶(hù)滿(mǎn)意度。

（3）優(yōu)化配送路線(xiàn)，可以使配送作業(yè)合理，提高企業(yè)運(yùn)營(yíng)效率.

（4）優(yōu)化配送路線(xiàn)，可以節(jié)省運(yùn)輸車(chē)輛，減少車(chē)輛空駛率，降低社會(huì)物流成本。

（5）優(yōu)化配送路線(xiàn)，可以緩解交通壓力，減少噪音、尾氣排放等運(yùn)輸污染。

1.3配送路徑問(wèn)題的描述

一般的物流配送路徑問(wèn)題可描述為：

有N個(gè)客戶(hù)點(diǎn)，每個(gè)客戶(hù)點(diǎn)的需求量和位置確定，用T輛汽車(chē)從配送中心運(yùn)輸貨物，分別到達(dá)這些客戶(hù)點(diǎn)，完成任務(wù)后返回物流中心，要求合理安排行駛路線(xiàn)。同時(shí)還要滿(mǎn)足：

（1）每條線(xiàn)路上的客戶(hù)點(diǎn)總需求量不超過(guò)汽車(chē)的載重量；

（2）每條配送路線(xiàn)總長(zhǎng)度不超過(guò)汽車(chē)一次配送的最大行駛距離；

（3）每個(gè)客戶(hù)點(diǎn)的需求由一輛汽車(chē)來(lái)完成。

目的是總成本（距離、時(shí)間）最小。

2 最近插入法

2.1最近插入法

最近插入法是Rosenkrantz和Stearns等人在1977年提出的，共有四個(gè)步驟：

（1）找到c0i最小的節(jié)點(diǎn)vi，形成一個(gè)子回路（subtour），T={V0，VK，VO}；

（2）在剩下的節(jié)點(diǎn)中，尋找一個(gè)距離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)VK；

（3）在子回路中找到一條?。╥，j），使得Cik+Ckj-Cij最小，然后將節(jié)點(diǎn)V i插入到節(jié)點(diǎn)vi，vj之間，用兩條新的?。╥，k），（k，j）代替原來(lái)的?。╥，j），并 將 節(jié)點(diǎn)vk加入到子回路中；

（4）重復(fù)步驟（2）、（3），直到所有的節(jié)點(diǎn)都加入到子回路中。

這樣，子回路就演變?yōu)榱艘粋€(gè)TSP的解。因?yàn)樽罱迦敕ń鉀Q的是單回路運(yùn)輸問(wèn)題，所以需要在此方法基礎(chǔ)上進(jìn)行改進(jìn)和修正，使其能解決多回路運(yùn)輸VRP問(wèn)題。

2.2改進(jìn)的最近插入法

（1）找到c0i最小的節(jié)點(diǎn)vi，形成一個(gè)子回路（subtour），T={V0，VK，VO}。

（2）在剩下的節(jié)點(diǎn)中，尋找一個(gè)距離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)vk。若此時(shí)回路的總貨運(yùn)量未超過(guò)車(chē)的載重限制，則繼續(xù)步驟（3）。否則，轉(zhuǎn)（1）尋找新的一條回路。

（3）在子回路中找到一條?。╥，j）使得Cik+Ckj-Cij最小，然后將節(jié)點(diǎn)vi插入到節(jié)點(diǎn)vi，vj之間，用兩條新的?。╥，k），（k，j）代替原來(lái)的?。╥，j），并 將節(jié)點(diǎn)vk加入到子回路中。若此時(shí)該回路的總路程為未超過(guò)車(chē)輛的行程限制，則繼續(xù)步驟（4），否則轉(zhuǎn)步驟（1），尋找新的一條回路。

（4）重復(fù)步驟（2）和（3），直到每一個(gè)節(jié)點(diǎn)都被歸入某一個(gè)子回路中。

3 X公司的配送路線(xiàn)優(yōu)化研究

3.1 X公司簡(jiǎn)介

X公司是位于西安的一家生產(chǎn)密度板的企業(yè)，技術(shù)力量雄厚，工藝設(shè)備先進(jìn)。公司的客戶(hù)分為需求量穩(wěn)定的大客戶(hù)和需求量隨機(jī)的小客戶(hù)兩種。

大客戶(hù)在時(shí)間和地點(diǎn)上的需求都不確定，但是需求量大，一般采用租賃車(chē)輛的方法進(jìn)行點(diǎn)對(duì)點(diǎn)運(yùn)輸，有時(shí)也由客戶(hù)自己運(yùn)輸。小客戶(hù)地點(diǎn)確定，主要位于西安的周邊縣市，但需求量不大，不過(guò)公司為推廣產(chǎn)品，每周用專(zhuān)車(chē)送貨上門(mén)。公司現(xiàn)擁有兩輛11噸的貨車(chē)，一輛7噸的貨車(chē)，如果車(chē)輛不夠時(shí)，采取租賃車(chē)輛的辦法。

目前，對(duì)小客戶(hù)公司采用的配送線(xiàn)路如圖2-1所示。

該 配 送 線(xiàn) 路 的 弊 端 在于：配 送 路 線(xiàn)選擇不合理，運(yùn)距過(guò)長(zhǎng)，消耗作業(yè)時(shí)間多，不能充分利用車(chē)輛配載容積，浪費(fèi)人力和物力資源，影響公司的收益。

3.2 X公司的配送線(xiàn)路分析與優(yōu)化

基本條件：X公司需給9個(gè)客戶(hù)送貨，客戶(hù)依次為1，2，3，…，9，現(xiàn)有車(chē)輛為1輛7T的貨車(chē)（百公里油耗21L），2輛11T的貨車(chē)（每百公里油耗27L），柴油每升7.14元，司機(jī)每天工資150元。目標(biāo)：確定所需要的車(chē)輛數(shù)目、車(chē)輛類(lèi)型、司機(jī)數(shù)量以及各車(chē)行走的路徑，并指派這些車(chē)輛到一個(gè)回路中，同時(shí)包括回路內(nèi)的路徑安排和調(diào)度，使得運(yùn)輸總費(fèi)用最小。

限制條件：（1）運(yùn)輸里程超過(guò)350公里時(shí)，需配備兩名司機(jī)，減去由于裝卸貨等影響因素，各車(chē)最大運(yùn)輸距離為600公里。

（2）為預(yù)防突發(fā)事件，每輛車(chē)完成任務(wù)之后都要回到源點(diǎn)0處。

（3）不能超過(guò)車(chē)輛的容量限制。7噸的貨車(chē)最多可裝300張密度板，11噸的最多可裝500張密度板。

設(shè)各點(diǎn)間的距離為，9節(jié)約距離為Cij。每輛車(chē)的載貨量為ri，各點(diǎn)需求量為，每輛車(chē)的行駛里程為，公里，西安為0點(diǎn)，客戶(hù)點(diǎn)1，2，?，9。

各個(gè)配送點(diǎn)的運(yùn)距和運(yùn)量見(jiàn)表3-1。

3.2.1原配送線(xiàn)路基本數(shù)據(jù)分析

各配送線(xiàn)路總里程，所需運(yùn)輸車(chē)輛型號(hào)、數(shù)量以及所需司機(jī)數(shù)量見(jiàn)表3-2。

由上表可知，公司每周需7噸貨車(chē)進(jìn)行5次 配 送，需要司機(jī)6人，工資支出900元，總里程為1262.8KM，，消耗柴油265.2L，所需燃油費(fèi)1894元，加上司機(jī)工資，一共花費(fèi)2794元。

3.2.2基于改進(jìn)的最近插入法的企業(yè)配送路線(xiàn)優(yōu)化

令T={0}，N={0，1，2??，10}，比較從0出發(fā)的所有路徑大小。因?yàn)?，所以就有顧客點(diǎn)0，1構(gòu)成一個(gè)子回路，，此時(shí)。

然后在剩余顧客點(diǎn)（1，2，3，4，6，7，8，9）中尋找到0和5中某一點(diǎn)的最小距離，且。

因?yàn)樗栽谧踊芈凡迦朦c(diǎn)1，由于對(duì)稱(chēng)性，無(wú)論將1插入到0和5之間往返路徑中，結(jié)果都是一樣的，這樣，構(gòu)成了一個(gè)新的子回路。

再次尋找剩余顧客點(diǎn)到0，1， 5中某一點(diǎn)的最小距離：可知最小距離為，此時(shí)，因?yàn)閞1+ r2=260+120380<500，所以在子回路插入點(diǎn)2.將點(diǎn)2分別插入（0，1），（1，5），（5，0）中，比較得：插入到（1，5）增量最小，。

，此時(shí)構(gòu)成了一個(gè)新的子回路。

再次對(duì)剩余的顧客點(diǎn)按照上訴方法進(jìn)行優(yōu)化，可構(gòu)成另子回路T1={0，3，4，6，0}和子回路利用改進(jìn)后的最近插入法得到公司優(yōu)化結(jié)果。（表3-3）

由此得出，公司每周需要11噸貨車(chē)配送3次，配送總里程939.7 km.，燃油費(fèi)用1811元，司機(jī)4人次，工資600元，總共的配送費(fèi)用為2411元。

3.2.3優(yōu)化方案比較分析

本文將從所需車(chē)輛數(shù)，行駛總里程，總油耗，人力資源和總費(fèi)用這些指標(biāo)，對(duì)優(yōu)化后的方案進(jìn)行評(píng)價(jià)分析，從對(duì)比中可知，優(yōu)化后的方案需要使用的車(chē)次更少，減少了X公司用車(chē)緊張的情況，使車(chē)輛安排使用上有了更大的彈性。因此，在用車(chē)角度上考慮，優(yōu)化后的方案比優(yōu)化前的方案合理。從總運(yùn)輸里程角度考慮，優(yōu)化后的總運(yùn)輸里程為939.7千米，與原方案的1262.8千米相比較，減少了車(chē)輛行駛的里程數(shù)，減少了公司車(chē)輛的損耗和資源的浪費(fèi)，帶來(lái)更多效益。

從燃油消耗的角度考慮，優(yōu)化后的方案的消耗為254升，與原方案的265.2升相比較，降低了油耗量。不僅減少X公司燃油費(fèi)用的支出，還能降低社會(huì)資源的浪費(fèi)。

從公司人力資源消耗角度來(lái)考慮，優(yōu)化后的方案所需司機(jī)人數(shù)為4人，減少人力的消耗為2人次，使公司在人員安排上將更具有彈性，還能降低公司費(fèi)用的支出。從支出的總費(fèi)用角度來(lái)考慮，優(yōu)化后的方案的費(fèi)用支出為2413元，與原方案的為2794元相比較，節(jié)省了總費(fèi)用的支出。

【參考文獻(xiàn)】

[1]高曉亮，伊俊敏，甘衛(wèi)華.倉(cāng)儲(chǔ)與配送管理[M].清華大學(xué)出版社，2006.

[2]Elliot Rabinovich， Manus Rungtusanatham and Timothy M. Laseter. Physical distribution service performance and Internet retailer margins： The drop-shipping context[J].Journal of Operations Management，2008（6）：767-780.

[3]孔少?gòu)兀和P.商品物流配送優(yōu)化策略探討[J].市場(chǎng)論壇，2009（7）：94-95

[4]Gianpaolo Ghiani. Gilbert Laporte. Roberto Musmanno. Introduction to Logistics Systems Planning and Control [M]. T&T Productions Ltd， London，2004（1）：3-15.

【作者簡(jiǎn)介】

張瑜，女，1981年，講師，研究方向，物流管理。