魏遠(yuǎn)晗

(重慶交通大學(xué) 重慶 400074)

一、引言

眾所周知，車輛路徑問題(VRP)是一個(gè)NP-hard問題，為了有效地解決VRP問題，過去開展了大量的研究[1-3]。Novoa和Storer[4]從再優(yōu)化的角度提出了需求隨機(jī)的單車輛路徑問題的近似動(dòng)態(tài)規(guī)劃方法。Fuellerer等[5]在前人研究的基礎(chǔ)上，進(jìn)一步研究了具有裝載能力的三維車輛路徑問題，并利用蟻群算法解決了該問題。Marinakis等[6]提出了一種混合粒子群優(yōu)化算法來解決車輛路徑問題，并在較短的計(jì)算時(shí)間內(nèi)取得了非常滿意的結(jié)果。在大型物流網(wǎng)絡(luò)中，VRP的成功實(shí)施應(yīng)包括客戶聚類和車輛路徑優(yōu)化[7]。然而，近二十年來，傳統(tǒng)的車輛路徑問題的客戶聚類優(yōu)化過程很少涉及客戶和產(chǎn)品的特點(diǎn)。近年來，逆向物流和冷鏈物流研究的興起促進(jìn)了集群客戶和產(chǎn)品研究的深入。每個(gè)客戶的特點(diǎn)可以用周邊交通條件、地理環(huán)境、需求要求、貨物相容性等來表征。然而，這些特性中有一部分是不能直接用數(shù)字測(cè)量的。分區(qū)交付基于異構(gòu)客戶特點(diǎn),有必要將這些特征作為輸入，然后進(jìn)行車輛路徑優(yōu)化,再結(jié)合運(yùn)輸成本尋找最優(yōu)路線。

綜上所述，上述VRP的變化反映了客戶的實(shí)際交付要求。例如，許多零售商為顧客提供退貨服務(wù)，顧客可能會(huì)選擇將自己不滿意的商品退貨。這也被稱為逆向物流。在這種情況下，每個(gè)客戶的交貨和取貨活動(dòng)可以同時(shí)進(jìn)行，從而使車輛路徑優(yōu)化問題變得更加困難。另一個(gè)例子是送貨上門，送貨人員需要配送客戶的順序，客戶貨物的體積大小，合理安排車輛的裝箱方案，優(yōu)化配送路徑。以上例子說明帶時(shí)間窗的城市大件物流車輛路徑優(yōu)化問題應(yīng)該考慮不同顧客的相同類型的需求，并把它們裝載在車輛的同一個(gè)區(qū)域，這樣就會(huì)提高裝載率，減少車輛數(shù)，降低配送成本。

二、案例分析

在本文中，我們用的是智能啟發(fā)式算法，為了驗(yàn)證算法的有效性，本文選取重慶部分地區(qū)的30個(gè)客戶，他們的經(jīng)緯度坐標(biāo)和需求如表1所示。

(一)案例相關(guān)數(shù)據(jù)

車廂的大小為420*180*200，每個(gè)區(qū)域的大小分別為：第1個(gè)區(qū)域大小為120*30*200，在這個(gè)區(qū)域里放置的是第一種類型的貨物，貨物的大小為120*30*50，每個(gè)貨物的重量為40kg；第2個(gè)區(qū)域大小為150*120*200，在這個(gè)區(qū)域里放置的是第2種類型的貨物，貨物的大小為120*50*100，每個(gè)貨物的重量為70kg；第3個(gè)區(qū)域大小為300*30*200，在這個(gè)區(qū)域里放置的是第3種類型的貨物，貨物的大小為150*30*65，每個(gè)貨物的重量為60kg；第4個(gè)區(qū)域大小為300*150*200，在這個(gè)區(qū)域里放置的是第4種類型的貨物，貨物的大小為150*75*185，每個(gè)貨物的重量為80kg。

車輛的額定載重是1300kg，配送車輛車廂里最多容納的第1種類型貨物的個(gè)數(shù)為4個(gè)，貨車最多容納的第2種類型貨物的個(gè)數(shù)為6個(gè)，貨車最多容納的第3種類型貨物的個(gè)數(shù)為4個(gè)，貨車最多容納的第4種類型貨物的個(gè)數(shù)為4個(gè)。車子的配送速度為40km/h，配送中心擁有的車子的數(shù)目為6輛，每一輛車子的固定配送費(fèi)用為100元，車輛單位運(yùn)輸成本為10元，早到的懲罰成本是5元/小時(shí)，晚到的懲罰成本為10元/小時(shí)。

表1 客戶及其具體的需求

(二)優(yōu)化結(jié)果分析

本文采用智能啟發(fā)式算法來求解優(yōu)化帶有時(shí)間窗的城市大件物流車輛路徑優(yōu)化問題。優(yōu)化結(jié)果如下所示：

第1條路線的配送順序是：22,17,7,16,25,12，裝載重量是1040kg，車廂里固定區(qū)域裝載的貨物的情況分別是：第1個(gè)區(qū)域里裝載的第1種類型的貨物的個(gè)數(shù)為3個(gè)，第2個(gè)區(qū)域里裝載的第2種類型的貨物的個(gè)數(shù)為6個(gè)，第3個(gè)區(qū)域里裝載的第3種類型的貨物的個(gè)數(shù)為3個(gè)，第4個(gè)區(qū)域里裝載的第4種類型的貨物的個(gè)數(shù)為4個(gè)。路線總長(zhǎng)度為34.70km。

第2條路線的配送順序是：18,15，裝載重量是520kg，車廂里固定區(qū)域裝載的貨物的情況分別是：第1個(gè)區(qū)域里裝載的第1種類型的貨物的個(gè)數(shù)為0個(gè)，第2個(gè)區(qū)域里裝載的第2種類型的貨物的個(gè)數(shù)為0個(gè)，第3個(gè)區(qū)域里裝載的第3種類型的貨物的個(gè)數(shù)為6個(gè)，第4個(gè)區(qū)域里裝載的第4種類型的貨物的個(gè)數(shù)為2個(gè)。路線總長(zhǎng)度為16.26km。

第3條路線的配送順序是：10,20,6,14,13,11，裝載重量是1070kg，車廂里固定區(qū)域裝載的貨物的情況分別是：第1個(gè)區(qū)域里裝載的第1種類型的貨物的個(gè)數(shù)為3個(gè)，第2個(gè)區(qū)域里裝載的第2種類型的貨物的個(gè)數(shù)為5個(gè)，第3個(gè)區(qū)域里裝載的第3種類型的貨物的個(gè)數(shù)為6個(gè)，第4個(gè)區(qū)域里裝載的第4種類型的貨物的個(gè)數(shù)為3個(gè)。路線總長(zhǎng)度為45.74km。

第4條路線的配送順序是：1,4,19,9,26,28，裝載重量是900kg，車廂里固定區(qū)域裝載的貨物的情況分別是：第1個(gè)區(qū)域里裝載的第1種類型的貨物的個(gè)數(shù)為4個(gè)，第2個(gè)區(qū)域里裝載的第2種類型的貨物的個(gè)數(shù)為2個(gè)，第3個(gè)區(qū)域里裝載的第3種類型的貨物的個(gè)數(shù)為6個(gè)，第4個(gè)區(qū)域里裝載的第4種類型的貨物的個(gè)數(shù)為3個(gè)。路線總長(zhǎng)度為29.70km。

第5條路線的配送順序是：24,3,5,29,27，裝載重量是1180kg，車廂里固定區(qū)域裝載的貨物的情況分別是：第1個(gè)區(qū)域里裝載的第1種類型的貨物的個(gè)數(shù)為2個(gè)，第2個(gè)區(qū)域里裝載的第2種類型的貨物的個(gè)數(shù)為6個(gè)，第3個(gè)區(qū)域里裝載的第3種類型的貨物的個(gè)數(shù)為6個(gè)，第4個(gè)區(qū)域里裝載的第4種類型的貨物的個(gè)數(shù)為4個(gè)。路線總長(zhǎng)度為26.32km。

第6條路線的配送順序是：8,30,23,21,2，裝載重量是1120kg，車廂里固定區(qū)域裝載的貨物的情況分別是：第1個(gè)區(qū)域里裝載的第1種類型的貨物的個(gè)數(shù)為4個(gè)，第2個(gè)區(qū)域里裝載的第2種類型的貨物的個(gè)數(shù)為4個(gè)，第3個(gè)區(qū)域里裝載的第3種類型的貨物的個(gè)數(shù)為6個(gè)，第4個(gè)區(qū)域里裝載的第4種類型的貨物的個(gè)數(shù)為4個(gè)。路線總長(zhǎng)度為32.27km。

經(jīng)計(jì)算，總的配送成本為2833.98元。

本文首先介紹了車輛路徑問題，根據(jù)閱讀文獻(xiàn)，發(fā)現(xiàn)車輛路徑研究的變化反映了客戶的實(shí)際交付要求。所以引出在帶時(shí)間窗的城市大件物流的配送上，送貨人員需要考慮配送客戶的順序，客戶貨物的體積大小，合理安排車輛的裝箱方案，優(yōu)化配送路徑。接著本文選取了重慶某地區(qū)的30個(gè)客戶點(diǎn)，基于它們的需求運(yùn)用智能啟發(fā)式算法進(jìn)行求解，結(jié)果證明了該算法的有效性。希望對(duì)相關(guān)的研究有一定的參考意義。