基于節(jié)約算法的車輛路徑問(wèn)題研究

張頤穎

[摘 要]車輛路徑問(wèn)題是物流配送中的決策難題，配送成本的減少成為優(yōu)化的主要目的，而科學(xué)家們對(duì)車輛調(diào)度優(yōu)化采用的方法層出不窮。本文針對(duì)節(jié)約算法做了簡(jiǎn)單的概述與研究，并以飛馬快運(yùn)公司為例，采用節(jié)約算法對(duì)該公司的車輛調(diào)度進(jìn)行簡(jiǎn)單的調(diào)整。

[關(guān)鍵詞]車輛調(diào)度；路徑優(yōu)化；節(jié)約算法

[中圖分類號(hào)]F224 [文獻(xiàn)標(biāo)識(shí)碼]A [文章編號(hào)]1005-6432（2014）27-0130-02

1 背 景

在物流配送領(lǐng)域，配送成本費(fèi)用是配送運(yùn)輸成本、分揀成本、配裝成本以及流通加工成本的總和。配送運(yùn)輸成本是成本費(fèi)用中較大開(kāi)支，尤其是配送點(diǎn)多、路線較長(zhǎng)時(shí)，配送路徑的選擇直接決定運(yùn)輸成本的大小。因此，在配送點(diǎn)及配送點(diǎn)需求量已知的情況下，如何通過(guò)科學(xué)的方法選擇最優(yōu)路徑是物流配送中最關(guān)鍵的抉擇[1]。

車輛路徑問(wèn)題（Vehicle Routing Problem，簡(jiǎn)稱 VRP）[2]，又稱為車輛調(diào)度問(wèn)題，通常是在配送中心及配送點(diǎn)之間，選擇適當(dāng)?shù)穆肪€，使車輛有序地通過(guò)，在滿足一定的約束條件（如貨物需求量、發(fā)送量、交貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等）下，達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用最少、時(shí)間盡量少、使用車輛數(shù)盡量少等），并返回配送中心。

配送車輛路徑問(wèn)題是世界公認(rèn)的 NP 難題，國(guó)內(nèi)外很多學(xué)者都進(jìn)行了研究，并提出了多種路線選擇及路徑優(yōu)化方法。本文采用了節(jié)約算法對(duì)飛馬公司的車輛調(diào)度問(wèn)題進(jìn)行研究與分析。

2 案例分析

飛馬快運(yùn)是依托邯運(yùn)集團(tuán)邯鄲汽車客運(yùn)網(wǎng)絡(luò)發(fā)展起來(lái)的快遞企業(yè)，2005年成立，主要開(kāi)展無(wú)人跟隨的小件快遞業(yè)務(wù)。目前客運(yùn)網(wǎng)絡(luò)日發(fā)班車1838次，營(yíng)運(yùn)線路126條，營(yíng)運(yùn)里程13107公里，沿途經(jīng)過(guò)站點(diǎn)1270個(gè)，班車輻射16個(gè)省市、78個(gè)大中城市，聯(lián)系晉冀魯豫四省的經(jīng)濟(jì)文化中心。目前的服務(wù)項(xiàng)目有同城快遞、省內(nèi)外貨物快遞、零擔(dān)貨物快遞，包裝服務(wù)、對(duì)方付費(fèi)、代收貨款，上門(mén)接貨、送貨上門(mén)、倉(cāng)儲(chǔ)分揀，貨物到達(dá)、受理一條龍服務(wù)，異地貨物中轉(zhuǎn)、異地貨物派送上門(mén)，代購(gòu)親情速遞物品，箱式專線運(yùn)輸?shù)取?/p>

飛馬快運(yùn)承運(yùn)的貨物主要放在客車底艙隨車運(yùn)輸。邯鄲客運(yùn)網(wǎng)絡(luò)能覆蓋的地區(qū)，由該客運(yùn)網(wǎng)絡(luò)的班車運(yùn)輸。該客運(yùn)網(wǎng)絡(luò)不能覆蓋的地區(qū)，與其他省市的運(yùn)輸公司合作，由合作的運(yùn)輸公司代為送達(dá)。目前，飛馬快運(yùn)與省內(nèi)外50余家汽車站、企業(yè)以及個(gè)體配貨點(diǎn)建立了業(yè)務(wù)合作關(guān)系。同時(shí)，公司現(xiàn)擁有130多部1.5噸以下廂式貨車，其中邯鄲客運(yùn)總站內(nèi)停17部，其余116部車平時(shí)分布在邯鄲市內(nèi)各業(yè)務(wù)網(wǎng)點(diǎn)，包括商場(chǎng)、批發(fā)點(diǎn)等。這116部貨車主要負(fù)責(zé)市內(nèi)配送業(yè)務(wù)，同時(shí)提供上門(mén)取貨業(yè)務(wù)、送貨業(yè)務(wù)，不提供長(zhǎng)途運(yùn)輸業(yè)務(wù)。站內(nèi)17部貨車可以提供出省運(yùn)輸業(yè)務(wù)。至今，飛馬快運(yùn)的服務(wù)范圍包括：同城快遞，市內(nèi)所有區(qū)、街、巷及市郊各縣（市），省內(nèi)快遞含河北省所有地、市、縣，全國(guó)快運(yùn)含北京、天津、上海、遼寧、河北、河南、山西、山東、陜西、江蘇、江西、湖南、湖北、浙江等省市。貨運(yùn)起步價(jià)90元，每公里2.5元。

在本案例中，主要研究邯鄲客運(yùn)站的發(fā)車量以及發(fā)車的路徑，針對(duì)不同的路徑做調(diào)整，以達(dá)到運(yùn)輸成本最低。邯鄲客運(yùn)站可以看作是一個(gè)配送中心，研究由該配送中心負(fù)責(zé)整個(gè)配送網(wǎng)絡(luò)客戶需求的車輛調(diào)度問(wèn)題，正常情況下由客戶提前提出需求計(jì)劃（包含需求量和需求時(shí)間）后，由配送中心負(fù)責(zé)配送。而配送中心考慮到自身運(yùn)營(yíng)成本的因素，采用循環(huán)式配貨方式對(duì)多個(gè)需求客戶配送。

3 研究方法

3.1 節(jié)約算法簡(jiǎn)述

本文采用了節(jié)約算法。節(jié)約算法是由 Clarke 和 Wright 提出的一種經(jīng)典啟發(fā)式算法，節(jié)約法求解路線安排問(wèn)題采用的是典型的啟發(fā)式思路。首先，以所有配送點(diǎn)均采用直接往返的送貨作為初始的可行安排。計(jì)算每?jī)蓚€(gè)配送點(diǎn)連接帶來(lái)的節(jié)約量，按節(jié)約量由大到小的順序，尋找節(jié)約量最大的兩個(gè)配送點(diǎn)：①如果它們連接后，所在線路上的貨運(yùn)量之和不超過(guò)車輛的載重限制，連接這兩個(gè)配送點(diǎn)；并進(jìn)一步尋找與這兩個(gè)配送點(diǎn)進(jìn)行連接帶來(lái)節(jié)約量最大的配送點(diǎn)，把這個(gè)配送點(diǎn)也連接到這條線路上，直到該線路上的所有配送點(diǎn)的貨運(yùn)量之和等于或超過(guò)車輛的載重限制，連接使總貨運(yùn)量超過(guò)車輛載重的最后一個(gè)配送點(diǎn)，本線路為該配送點(diǎn)提供的貨運(yùn)量剛好使車輛滿載。②如果它們連接后，所在線路上的貨運(yùn)量之和等于車輛的載重限制，連接這兩個(gè)配送點(diǎn)。③如果它們連接后，所在線路上的貨運(yùn)量之和超過(guò)車輛的載重限制，連接這兩個(gè)配送點(diǎn)，并使車輛剛好滿載。將剩余的配送點(diǎn)和配送向量組成一個(gè)新的配送線路規(guī)劃問(wèn)題，重復(fù)采用上述方法，直到所有可能連接的配送點(diǎn)全部連接完成后，結(jié)果作為路線安排的最優(yōu)解[3]。

3.2 節(jié)約算法具體應(yīng)用

3.2.1 模型的建立

3.2.2 節(jié)約算法的步驟

1）取最大節(jié)約值1012，即天津到廊坊，此時(shí)載重量為1.2t，不能再增加一個(gè)地方的載重量。

2）除去到天津與廊坊的節(jié)約值，在剩余的節(jié)約值中取最大值658，即北京到滄州，此時(shí)載重量為1.2t，也不能再增加一個(gè)地方的載重量。

3）在前面的基礎(chǔ)上再挑選最大節(jié)約值391，即衡水到保定，此時(shí)載重量為0.8t，剩余的節(jié)約值為349，石家莊到衡水，載重量變成1.4t。

4）7個(gè)地區(qū)都有路線經(jīng)過(guò)，即得到路線的最小值，也就是從邯鄲派三輛車，路徑分別為：邯鄲——天津——廊坊——邯鄲；邯鄲——北京——滄州——邯鄲；邯鄲——石家莊——衡水——保定——邯鄲。

4 優(yōu)化方案

通過(guò)應(yīng)用節(jié)約算法討論該問(wèn)題，最后得出的結(jié)果為：邯鄲應(yīng)該派三輛車，分別派往邯鄲——天津——廊坊——邯鄲，載重量為1.2t，運(yùn)費(fèi)為1700元；邯鄲——北京——滄州——邯鄲，載重量為1.2t，運(yùn)費(fèi)為1665元；邯鄲——石家莊——衡水——保定——邯鄲，載重量為1.4t，運(yùn)費(fèi)為1132.5元。最后得出的總運(yùn)費(fèi)為4497.5元。因此該公司可以根據(jù)本文中提供的方法解決該問(wèn)題。

5 結(jié) 論

本文通過(guò)分析研究實(shí)際生活中存在的問(wèn)題，通過(guò)運(yùn)用節(jié)約算法提出解決方法。C-W節(jié)約算法思想簡(jiǎn)單，在解決旅行商問(wèn)題時(shí)是一種很好的算法，可以快速得到問(wèn)題的滿意解。

參考文獻(xiàn)：

[1]范潔，曹俊琴.改進(jìn)節(jié)約算法在電表配送路線選擇中的應(yīng)用[J].物流工程與管理，2012，34（214）：102-105.

[2]Dantzing G，Ramser J.The truck dispatching problem[J].Management Science，1959，10（6）：80-91.

[3]張學(xué)志，陳功玉.車輛路線安排的改進(jìn)節(jié)約算法[J].系統(tǒng)工程，2008，26（11）：67-70.