閆會姝

基于集送貨需求的車輛路徑優(yōu)化問題研究

閆會姝

車輛在服務過程中，既可能面對集貨需求，也可能面對送貨需求。在國內(nèi)外學者研究的基礎上，提出一種新的解決VRPSDP問題的方法。在系統(tǒng)分析同時具有集送貨需求的物流網(wǎng)絡機構(gòu)與要素的基礎上，構(gòu)建基于集送貨需求的車輛路徑優(yōu)化模型，利用lingo軟件進行優(yōu)化求解。實例仿真結(jié)果表明，通過該模型的建立及軟件的應用，能夠?qū)囕v的路徑進行優(yōu)化，能夠有效地減少車輛的運輸成本，提高物流運作的效率。

集送貨需求；路徑優(yōu)化；實例仿真；lingo軟件

隨著人們的環(huán)保意識逐漸加強，各企業(yè)根據(jù)自身可持續(xù)發(fā)展的需要，原材料、半成品、制成品、廢舊品的回收和再利用越來越受到關(guān)注，逆向物流的問題得到了越來越多學者的關(guān)注。在逆向物流運作過程中涉及很多復雜的規(guī)劃問題，逆向物流的車輛路徑優(yōu)化就是其中之一，由此延伸出很多不同類型的VRP［1］，如VRPB（Vehicle Routing Problem with Backhauls）、VRPBM（Vehicle Routing Problem with Backhauls of Mixed Loads）等［2］。在實際的生活中，顧客可能會有配送和回收的需求，如飲料供應商在給零售商店送飲料的同時，店主可能會要求廠家回收空瓶子。由于將送貨和回收單獨進行會增加成本，因此將正向物流和逆向物流同時加以考慮成為解決問題的有效途徑。該問題是經(jīng)典VRP問題的一個拓展，是帶有同時取貨和送貨功能的車輛路徑優(yōu)化問題（Vehicle Routing Problem with Simultaneous Delivery and pickup，VRPDP）。

一、集送貨需求車輛路徑的優(yōu)化問題概述

（一）研究現(xiàn)狀

目前，各界學者將集送貨需求的逆向物流車輛路徑優(yōu)化問題［3］分為三類：第一類是Anily、Toth和Vigo、Brandao等，研究的主題是帶回程載貨的車輛路徑問題（VRPB），這類問題適用于每個客戶要求服務的內(nèi)容不一樣，有的是對貨物的需求，有的是要將貨物運到倉庫。通過將該問題分成先送貨再集貨兩個階段，只有將所有的需求點送完后才對集貨客戶服務。第二類是Casco、Salhi和Nagy［4］等，研究的主題是混合集送貨需求的車輛路徑問題（VRPMPD）。這類問題在需求方面假設與第一個問題一致，但是放寬了配送的約束條件，不再要求配貨必須在集貨前，可以混合進行。第三類問題是同時具有集送貨需求的車輛路徑優(yōu)化問題（VRPSDP）。對于VRPSDP的求解通常采用啟發(fā)式算法和元啟發(fā)式算法，同時遺傳算法、蟻群算法、模擬退火算法［4］都有研究，但是對于求解質(zhì)量還有待進一步改進（見圖1）。

圖1 集送貨車輛路線問題分類

（二）本文研究的數(shù)據(jù)來源及創(chuàng)新點

筆者以重慶一家集啤酒生產(chǎn)和啤酒瓶回收一體的公司為背景，數(shù)據(jù)來源于圖書館、互聯(lián)網(wǎng)和文獻資料等多種途徑。筆者首先分析專家學者關(guān)于集送貨車輛路徑優(yōu)化問題的研究思路和研究方法，然后提出基于集送貨需求的車輛路徑優(yōu)化問題研究的基本假設，定義參數(shù)、變量和確定目標函數(shù)，建立VRPDP車輛路徑優(yōu)化問題的模型。筆者主要是采用lingo軟件，以滿足相應的約束條件為前提，最終實現(xiàn)運輸成本最小化的目標。創(chuàng)新點在于對模型的建立，同時考慮了運輸距離變動成本、啟動車輛數(shù)量成本及總的車輛貨損成本，對于提高企業(yè)的物流運作效率具有重要的現(xiàn)實意義［5］。

二、VRPSDP車輛路徑優(yōu)化問題的模型構(gòu)建

VRPSDP（Vehicle Routing Problem with Simultaneous Delivery and Pickup）是VRP問題的延伸，可以描述為：有一個配送中心或者倉庫，有K輛相同型號，相同最大載重量的貨車從起始站點出發(fā)，服務于沿途的各個客戶點；這些客戶點包括只有需求，只有供給，既有需求又有供給三種情況，各類客戶被服務完成后車輛最終返回到配送中心。車輛在運輸過程中，需要滿足每輛車的實際載重量不大于車輛的最大載重量，每個服務點有接近被賦予一次的約束條件，最終求出車輛的行車路線使得總的行駛路程最低的方案，實現(xiàn)總的運輸效率最高和總的消耗成本最少的目標。

（一）基本假設

（1）客戶的位置、需求量和時間窗在集送貨過程中完全已知，且車輛的最大裝載量應小于單個客戶點的需求量、貨物回收量。

（2）在倉儲中心的貨物數(shù)量充足，貨物的配送過程中不會出現(xiàn)缺貨的現(xiàn)象。

（3）集送貨過程中貨物只考慮重量的約束，不考慮體積、形狀的限制。

2）調(diào)研階段：在設計前期，沒有進行現(xiàn)場調(diào)研，僅根據(jù)地形圖確認管線位置，施工單位進入現(xiàn)場開挖后，發(fā)現(xiàn)設計與現(xiàn)場情況不符，需要重新調(diào)整設計，在一定程度上影響了施工進度。

（4）在任何時候車輛的最大載重量應大于所裝載的貨物量。

（5）每輛車輛均以倉庫作為出發(fā)點，對各客戶點服務完成后重新返回到倉庫。

（6）服務車輛的行駛速度在集送貨過程中為恒定值，不考慮其他物理因素，不考慮交通堵塞等現(xiàn)象［6］。

（7）每個客戶只能被一輛車進行服務一次。

（二）參數(shù)和變量的定義

假設配送中心最多可以用k輛車（k=1，2，…，K）對L個客戶（i=1，2，…，l）進行服務。

M代表節(jié)點集合。

N代表客戶點集合。N={i}，i=0表示配送中心，i= 1，2，…，n為客戶節(jié)點。

α代表單位運輸距離的運輸成本。

β代表單位車輛的啟用成本。

T代表車輛的最大載重能力。

C代表客戶點i與客戶點j之間的距離。

di代表客戶點i的送貨需求。

pi代表客戶點i的取貨需求。

（三）模型構(gòu)建

車輛路徑優(yōu)化的目標是在滿足所有客戶集送貨需求及車輛負載能力等約束條件下找出運輸成本最低的行駛路線。成本包括運輸距離變動成本、啟動車輛數(shù)量成本及貨損成本。之前大量學者的研究只考慮了運輸距離的變動成本，筆者在建模過程中將考慮運輸距離變動成本、啟動車輛數(shù)量成本及貨損成本，建立改進的VRPSDP模型［6］。

目標函數(shù)：

約束條件：

三、算例仿真

重慶某企業(yè)是一家集啤酒生產(chǎn)和啤酒瓶回收為一體的公司，公司會定期派車輛對啤酒的銷售商進行送貨并且根據(jù)銷售商的需求將啤酒瓶回收。筆者主要以該公司在重慶主城的集送貨群為研究對象，將主要的6個銷售商點通過Google地圖進行投影，各銷售點到配送中心的距離及銷售點之間的距離見表1，銷售點對啤酒的需求量以及啤酒瓶的取貨量見表2。假定所使用的貨車的最大容量為240，固定使用成本為80。為了軟件計算方便，將銷售商編號從小到大設置成X1—X6，配送中心設為X0。Xij表示連接ij這兩個供應商的那條路，節(jié)點分別代表配送中心，石橋鋪銷售點，渝北銷售點，南岸銷售點，璧山銷售點，九龍坡銷售點，北碚銷售點。

表1 配送中心與客戶間的距離/km

使用Lingo軟件在MS Windows XP、Pentium 43.06GHz、1.00GB內(nèi)存的環(huán)境下對上述模型進行求解。計算結(jié)果是為了完成所有顧客的集送貨需求，需要使用三條循環(huán)去獲得路線。其中，路線一為X0-X1-X3-X4；路線二為X0-X2-X5-X0；路線三為X0-X6-X0。三條路線總的路程為262 km，達到局部最優(yōu)。該模型是解決整數(shù)非線性規(guī)劃的模型。Lingo軟件能在較短的時間內(nèi)取得局部最優(yōu)解。

表2 車輛的送貨量和取貨

四、結(jié)語

本文通過構(gòu)建基于集送貨需求的車輛路徑優(yōu)化問題模型對車輛路徑進行優(yōu)化，同時運用lingo軟件對該模型進行了優(yōu)化計算與算例仿真，進一步證實了車輛路徑優(yōu)化對于提高物流企業(yè)的運營效率，降低物流企業(yè)的運營成本，具有重要的實踐意義。

[1]馬祖軍.產(chǎn)品回收逆向物流網(wǎng)絡優(yōu)化設計模型[J].管理工程學報，2005（4）.

[2]Christian S.Efficient Local Search on the GPU：Investigations on the Vehicle Routing Problem[J].Journal of Parallel and Distributed Computing，2013（7）.

[3]Melián-Batista B，Santiago A，AngelBello F，et al.A Biobjective Vehicle Routing Problem with Time Windows：A Real Case in Tenerife[J].Applied Soft Computing Journal，2014（17）.

[4]吳斌，蔡紅，樊樹海，蔣南云.雙倍體差分進化粒子群算法在VRPSDP中的應用研究[J].系統(tǒng)工程理論與實踐，2010（3）.

[5]殷佳林，蔣泰.具有同時送貨和取貨需求的車輛路徑問題的蟻群禁忌混合優(yōu)化算法[J].廣西科學院學報，2008（4）.

[6]王科峰，葉春明，李永林.同時送取貨車輛路徑問題算法研究綜述[J].計算機應用研究，2013（2）.

[7]陳久梅，曾波.兩級定位—路徑問題的路徑重連變鄰域搜索人工蜂群算法[J].計算機集成制造系統(tǒng)，2014（5）.

（編輯：唐龍）

F252.81

A

1673-1999（2015）05-0045-03

閆會姝（1992—），女，重慶工商大學（重慶南岸400067）商務策劃學院2014級碩士研究生，研究方向為物流與供應鏈管理。

2015-04-04

電子商務及供應鏈系統(tǒng)重慶市重點實驗室開放基金項目（2013ECSC0101）。