基于啟發(fā)式算法的匯集式行駛路線選擇

□文/于 斌 謝振華 劉伯超

（常州機(jī)電職業(yè)技術(shù)學(xué)院 江蘇·常州）

一、匯集式路線概述

匯集式路線是指按照單程進(jìn)行貨運(yùn)生產(chǎn)組織的車輛行駛路線。車輛由起點(diǎn)出發(fā)，在貨運(yùn)任務(wù)規(guī)定的各貨運(yùn)點(diǎn)依次進(jìn)行裝貨或卸貨，并且每次裝貨或卸貨都小于一個(gè)整車，車輛完成各貨運(yùn)點(diǎn)運(yùn)輸任務(wù)以后，最終返回原出發(fā)點(diǎn)。因此，一般情況下，匯集式路線為封閉路線。車輛可能沿著一條環(huán)形式的路線行駛，也可能在一條直線形路線上往返行駛。

匯集式的運(yùn)輸形式一般可分為三種形式：（1）分送式：車輛從起點(diǎn)裝車完成后，沿著運(yùn)行路線上的各個(gè)貨運(yùn)點(diǎn)依次進(jìn)行卸貨，最終可返回起點(diǎn)；（2）收集式：車輛從起點(diǎn)空車出發(fā)，沿著運(yùn)行路線上的各個(gè)貨運(yùn)點(diǎn)進(jìn)行裝貨，最終達(dá)到目的地；（3）分送——收集式：車輛沿著運(yùn)行路線上的各個(gè)貨運(yùn)點(diǎn)分別或者同時(shí)進(jìn)行裝貨以及卸貨。如為分送式路線，其主要日運(yùn)行指標(biāo)如下：

（1）貨運(yùn)量Q：

Qj—第j次周轉(zhuǎn)車輛完成的貨運(yùn)量。

（2）周轉(zhuǎn)量 P：

Pj—第j次周轉(zhuǎn)車輛完成的貨物周轉(zhuǎn)量。

當(dāng)車輛按照匯集式路線完成運(yùn)輸工作時(shí)，由于周轉(zhuǎn)貨物周轉(zhuǎn)量的大小與車輛沿路線上各個(gè)貨運(yùn)點(diǎn)的繞行次序有關(guān)。如果繞行次序不同，即使完成同樣的貨運(yùn)任務(wù)，其周轉(zhuǎn)量也會(huì)不大相同。在這種情況下，按照總行程最短的原則來(lái)組織車輛進(jìn)行運(yùn)輸顯然最為經(jīng)濟(jì)。因此，選擇匯集式路線應(yīng)以總行程最短為最佳準(zhǔn)則。

二、匯集式行駛路線求解流程

前已述及，選擇匯集式路線，即選擇車輛在各貨運(yùn)點(diǎn)間繞行次序，應(yīng)以每個(gè)單程后者周轉(zhuǎn)總行程最短為最佳準(zhǔn)則。據(jù)此，可以將匯集式路線選擇問(wèn)題歸結(jié)為運(yùn)籌學(xué)中的貨郎擔(dān)問(wèn)題，我們可以采用啟發(fā)式算法進(jìn)行近似求解。

行駛路線最短問(wèn)題有很多種算法，在這里啟發(fā)式指的是在一個(gè)搜尋樹(shù)的節(jié)點(diǎn)上定義的函數(shù)h（n），用于評(píng)估從此節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最便宜的路徑。啟發(fā)式通常用于資訊充分的搜尋算法，例如最好優(yōu)先貪婪算法與A*。最好優(yōu)先貪婪算法會(huì)為啟發(fā)式函數(shù)選擇最低代價(jià)的節(jié)點(diǎn)；A*則會(huì)為 g（n）+h（n）選擇最低代價(jià)的節(jié)點(diǎn)，此 g（n）是從起始節(jié)點(diǎn)到目前節(jié)點(diǎn)的路徑的確實(shí)代價(jià)。如果 h（n）是可接受的，也即 h（n）未曾付出超過(guò)達(dá)到目標(biāo)的代價(jià)，則A*一定會(huì)找出最佳解。

現(xiàn)仍以分送式路線選擇為例，其計(jì)算程序如圖1所示。（ 圖 1）其中：Lj－貨運(yùn)點(diǎn)j的里程系數(shù)；R－組成循環(huán)回路的貨運(yùn)點(diǎn)數(shù)；f－貨運(yùn)點(diǎn)總數(shù)；i，j－貨運(yùn)點(diǎn)序號(hào)。

圖1 啟發(fā)式算法選擇車輛繞行次序程序圖

三、基于啟發(fā)式算法的匯集式路線選擇

某倉(cāng)庫(kù)K擬采用一輛中型載貨汽車（Q0=4噸），將瓶裝氧氣分送給 B1、B2、B3、B4四個(gè)貨運(yùn)點(diǎn)，各點(diǎn)之間的距離如圖2所示。（圖2）

圖2 各節(jié)點(diǎn)之間的距離（單位：公里）

下面，用圖2所述的啟發(fā)式算法確定分送式的最佳行駛路線。

（1）根據(jù)圖1所示，編制里程矩陣，求貨運(yùn)點(diǎn)的里程系數(shù)，即Lj，如表1。（表1）

（2）確定初選循環(huán)回路。按Lj值的從大到小，依次選取三個(gè)貨運(yùn)點(diǎn)（B0，B2，B1）組成最初循環(huán)回路：B0→B2→B1→B0，其貨運(yùn)點(diǎn)數(shù)R=3。

（3）確定插入貨運(yùn)點(diǎn)。在剩余的貨運(yùn)點(diǎn)中，選取Lj較大的B3（L3>L4）為待插入貨運(yùn)點(diǎn)，即x=3。

（4）計(jì)算各路插入貨運(yùn)點(diǎn)x后的里程增量 Δij：

Δ0，2=L0，3+L3，2-L0，2=10+6-11=5

Δ2，1=L2，3+L3，1-L2，1=6+4-9=1

Δ1，0=L3，1+L3，0-L1，0=4+10-8=6

（5）確定插入位置，組織新的回路。選取Δij最小值的路段作為插入貨運(yùn)點(diǎn)的路段。因?yàn)棣?，1=1是三個(gè)路段增量中的最小值，所以選擇B2→B1路段作為點(diǎn)x的插入位置，組成新的回路：B0→B2→B3→B1→B0。因?yàn)楝F(xiàn)有循環(huán)回路的貨運(yùn)點(diǎn)數(shù)為4，即R

表1 各貨運(yùn)點(diǎn)的里程矩陣（單位：公里）

Δ0，2=L0，4+L4，2-L0，2=0.5

Δ2，3=L2，4+L4，3-L2，3=2.5

Δ3，1=L3，4+L4，1-L3，1=6.5

Δ1，0=L1，4+L4，0-L1，0=6

因?yàn)棣?，2值最小，所以選擇B0→B2作為B4的插入點(diǎn)，得到最終的循環(huán)回路 ：B0→B4→B2→B3→B1→B0。按照此循環(huán)回路的繞行次序，車輛的總行程為∑ L=L0，4+L4，2+L2，3+L3，1+L1，0=29.5（公里）。這里需要說(shuō)明的是，啟發(fā)式算法求得的解是近似求解，并不一定是最優(yōu)解，但一般也是令人較為滿意的解。

匯集式的運(yùn)輸線路的組織工作較為復(fù)雜，但有利于做到“取貨上門，送貨到家”，可有效滿足客戶需求，在配送運(yùn)輸中被廣泛應(yīng)用，在匯集式運(yùn)輸線路的選擇中，以運(yùn)輸費(fèi)用最低為原則。運(yùn)用啟發(fā)式算法，可以較為準(zhǔn)確地確定最佳行駛路線。

[1]孫媛.企業(yè)物流網(wǎng)絡(luò)規(guī)劃研究.同濟(jì)大學(xué)學(xué)位論文，2008.

[2]李靜.基于道路網(wǎng)絡(luò)影響的物流運(yùn)輸成本研究.合肥工業(yè)大學(xué)學(xué)位論文，2009.