□文/于 斌 謝振華 劉伯超

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

一、匯集式路線概述

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

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

（1）貨運量Q：

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

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

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

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

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

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

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

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

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

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

某倉庫K擬采用一輛中型載貨汽車（Q0=4噸），將瓶裝氧氣分送給 B1、B2、B3、B4四個貨運點，各點之間的距離如圖2所示。（圖2）

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

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

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

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

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

（4）計算各路插入貨運點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最小值的路段作為插入貨運點的路段。因為Δ2，1=1是三個路段增量中的最小值，所以選擇B2→B1路段作為點x的插入位置，組成新的回路：B0→B2→B3→B1→B0。因為現(xiàn)有循環(huán)回路的貨運點數(shù)為4，即R

表1 各貨運點的里程矩陣（單位：公里）

Δ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

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

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

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

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