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

閆會姝

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

閆會姝

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

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

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

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

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

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

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

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

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

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

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

（一）基本假設(shè)

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

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

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

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

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

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

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

（7）每個客戶只能被一輛車進(jìn)行服務(wù)一次。

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

假設(shè)配送中心最多可以用k輛車（k=1，2，…，K）對L個客戶（i=1，2，…，l）進(jìn)行服務(wù)。

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

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

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

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

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

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

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

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

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

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

目標(biāo)函數(shù)：

約束條件：

三、算例仿真

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

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

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

表2 車輛的送貨量和取貨

四、結(jié)語

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

[1]馬祖軍.產(chǎn)品回收逆向物流網(wǎng)絡(luò)優(yōu)化設(shè)計模型[J].管理工程學(xué)報，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]吳斌，蔡紅，樊樹海，蔣南云.雙倍體差分進(jìn)化粒子群算法在VRPSDP中的應(yīng)用研究[J].系統(tǒng)工程理論與實踐，2010（3）.

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

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

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

（編輯：唐龍）

F252.81

A

1673-1999（2015）05-0045-03

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

2015-04-04

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