張頤穎

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

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

[中圖分類號]F224 [文獻標識碼]A [文章編號]1005-6432（2014）27-0130-02

1 背 景

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

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

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

2 案例分析

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

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

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

3 研究方法

3.1 節(jié)約算法簡述

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

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

3.2.1 模型的建立

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

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

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

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

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

4 優(yōu)化方案

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

5 結(jié) 論

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

參考文獻：

[1]范潔，曹俊琴.改進節(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]張學志，陳功玉.車輛路線安排的改進節(jié)約算法[J].系統(tǒng)工程，2008，26（11）：67-70.