基于節約算法的車輛路徑問題研究

張頤穎

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

[關鍵詞]車輛調度；路徑優化；節約算法

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

1 背 景

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

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

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

2 案例分析

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

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

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

3 研究方法

3.1 節約算法簡述

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

3.2 節約算法具體應用

3.2.1 模型的建立

3.2.2 節約算法的步驟

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

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

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

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

4 優化方案

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

5 結 論

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

參考文獻：

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

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

[3]張學志，陳功玉.車輛路線安排的改進節約算法[J].系統工程，2008，26（11）：67-70.