基于Trans CAD的定位路線問(wèn)題解決方案

江 偉

（江蘇省交通技師學(xué)院車輛工程系 江蘇 鎮(zhèn)江 212006）

0 前言

Trans CAD擁有一套車輛路徑和物流程序模塊，能以表格和地圖的形式輸出Trans CAD軟件系統(tǒng)計(jì)算出的最優(yōu)選址、最優(yōu)路徑和車輛調(diào)度時(shí)刻表。Trans CAD的這些程序可以解決諸多復(fù)雜的物流問(wèn)題。本文使用Trans CAD軟件系統(tǒng)解決物流系統(tǒng)LRP，目的是為了說(shuō)明采用先進(jìn)的信息技術(shù)能更高效、直觀地為現(xiàn)代物流規(guī)劃提供最優(yōu)解決方案。

1 定位路線問(wèn)題

定位路線問(wèn)題(Location Routing Problem，LRP)是物流規(guī)劃中定位配給問(wèn)題（LAP）和車輛路線（VRP）問(wèn)題的集成，是物流系統(tǒng)優(yōu)化的難題。LRP可描述為：給定一組符合實(shí)際情況的客戶點(diǎn)集合和備選設(shè)施點(diǎn)集合，從這些備選設(shè)施點(diǎn)中選出一組新的設(shè)施位置集合作為規(guī)劃設(shè)施點(diǎn)，同時(shí)還要確定出一套從各個(gè)設(shè)施到其服務(wù)客戶點(diǎn)的運(yùn)輸路線，解決該問(wèn)題的目的是使總費(fèi)用最小。LRP通常作如下假定：（1）客戶位置和客戶需求量已知；（2）備選設(shè)施點(diǎn)位置已知；（3）貨物由一個(gè)或多個(gè)設(shè)施供應(yīng)；（4）每個(gè)客戶只接收來(lái)自一個(gè)設(shè)施的一個(gè)車輛送來(lái)的貨物。

2 基于Trans CAD的LRP方案優(yōu)化

2.1 在Trans CAD中創(chuàng)建LRP地圖

2.1.1 路網(wǎng)層及相關(guān)數(shù)據(jù)庫(kù)的建立

將DXF格式的路網(wǎng)文件導(dǎo)入Trans CAD中，選取我們所需要的CAD圖層，導(dǎo)入線地理文件。

為了防止輸出矩陣時(shí)也很可能會(huì)出現(xiàn)空白矩陣單元，需對(duì)路網(wǎng)中的所有路段節(jié)點(diǎn)都和緊鄰路段節(jié)點(diǎn)實(shí)現(xiàn)無(wú)間隔性連接的檢驗(yàn)，斷開(kāi)的節(jié)點(diǎn)需用地圖編輯工具來(lái)連接。

當(dāng)路網(wǎng)層導(dǎo)入后，Trans CAD會(huì)自動(dòng)生成與此圖層相關(guān)的一些屬性字段，再添加本文所需的屬性字段SPEED和TIME，再為每條記錄填充相應(yīng)的字段值，這樣就建立了路網(wǎng)層數(shù)據(jù)庫(kù)。

2.1.2 設(shè)施點(diǎn)和客戶點(diǎn)圖層及數(shù)據(jù)庫(kù)的創(chuàng)建

以城市道路網(wǎng)作為底圖層，建立設(shè)施點(diǎn)層和客戶點(diǎn)層。本文假定A市共有9個(gè)設(shè)施點(diǎn)，其中有1個(gè)已存在設(shè)施點(diǎn)和8個(gè)備選設(shè)施點(diǎn)，選址階段需選出2個(gè)新建設(shè)施點(diǎn)。

（1）設(shè)施點(diǎn)圖層及設(shè)施數(shù)據(jù)庫(kù)的創(chuàng)建

新建地理文件Facility，添加到當(dāng)前圖層窗口，設(shè)置屬性字段，再在圖層中添加設(shè)施點(diǎn)。本文將設(shè)施點(diǎn)分為原有設(shè)施點(diǎn)和備選設(shè)施點(diǎn)兩類，所以我們需要在地圖圖層中進(jìn)行分類。在設(shè)施選擇集中新建原有設(shè)施點(diǎn)Exsisting和備選設(shè)施點(diǎn)Candidate兩個(gè)選擇集，再到設(shè)施點(diǎn)數(shù)據(jù)窗分別點(diǎn)選兩個(gè)選擇集。

（2）客戶點(diǎn)圖層及客戶數(shù)據(jù)庫(kù)的創(chuàng)建

客戶點(diǎn)圖層的建立方法同設(shè)施點(diǎn)圖層。本文假定有46個(gè)客戶點(diǎn)分布在城市路網(wǎng)中，客戶點(diǎn)層數(shù)據(jù)庫(kù)需增加的屬性字段有NAME，OPEN TIME， CLOSE TIME， FIXED SERVICE TIME， TIME PER UINT，DEMAND，NODE_ID。創(chuàng)建設(shè)施點(diǎn)層和客戶點(diǎn)層后，需將所有設(shè)施點(diǎn)、客戶點(diǎn)和路網(wǎng)節(jié)點(diǎn)連接起來(lái)，以實(shí)現(xiàn)設(shè)施點(diǎn)和客戶點(diǎn)在路網(wǎng)上的通達(dá)性，查找出基于現(xiàn)實(shí)路網(wǎng)的最短路徑。在Endpoints屬性表中為設(shè)施點(diǎn)和客戶點(diǎn)分別添加索引字段INDEX 01和INDEX 02，以便連接后自動(dòng)生成節(jié)點(diǎn)ID和設(shè)施點(diǎn)ID、客戶點(diǎn)ID的對(duì)應(yīng)關(guān)系。

3 網(wǎng)絡(luò)

創(chuàng)建網(wǎng)絡(luò)文件并使之成為當(dāng)前激活的網(wǎng)絡(luò)。使用命令Networks/Paths>Multiple Paths創(chuàng)建的以時(shí)間為權(quán)值的最短路徑陣。本文數(shù)據(jù)輸入需要一個(gè)服務(wù)成本矩陣，所以需要在最小時(shí)間矩陣的基礎(chǔ)上創(chuàng)建一個(gè)服務(wù)成本矩陣COST。本文在選址階段的目標(biāo)就是在保證設(shè)施到客戶的平均服務(wù)成本最小的前提下確定待建設(shè)施點(diǎn)的位置。每個(gè)候選設(shè)施向客戶提供物流服務(wù)都會(huì)產(chǎn)生相應(yīng)的服務(wù)成本，本文構(gòu)建服務(wù)成本公式[1]：C=F+P*t。式中，C—服務(wù)成本；F—固定投資成本；P—運(yùn)營(yíng)成本相關(guān)系數(shù)；T—車輛運(yùn)營(yíng)時(shí)間，單位：min。

本文給定固定投資成本為320/60，運(yùn)營(yíng)成本相關(guān)系數(shù)為80，因此服務(wù)成本公式為C=320/60+80*時(shí)間/60（以上數(shù)據(jù)僅供本文測(cè)試用），輸出服務(wù)成本矩陣。服務(wù)成本矩陣用于查找基于路網(wǎng)層的設(shè)施點(diǎn)到客戶點(diǎn)的最短路徑，該矩陣中的索引為路網(wǎng)節(jié)點(diǎn)層的ID，這與原設(shè)施點(diǎn)ID和客戶點(diǎn)ID不一致，因此必須使服務(wù)成本矩陣索引ID與設(shè)施點(diǎn)ID和客戶點(diǎn)ID相一致。

3.1 基于Trans CAD的物流設(shè)施選址與配送路線解決方案

3.1.1 物流設(shè)施選址

本文進(jìn)行物流設(shè)施選址所需要的材料包括：（1）A市的城市道路網(wǎng)圖層；（2）包含所有備選設(shè)施點(diǎn)的點(diǎn)圖層；（3）包含所有客戶點(diǎn)的點(diǎn)圖層；（4）客戶點(diǎn)需求，表示客戶點(diǎn)重要程度的權(quán)重量；（5）成本矩陣。每個(gè)設(shè)施都有與之相關(guān)的固定投資成本和運(yùn)營(yíng)成本。我們可以以此來(lái)建立物流服務(wù)的成本矩陣，行代表候選點(diǎn)列代表客戶。

利用上述三個(gè)圖層來(lái)輸出作為選址程序基本輸入的服務(wù)成本矩陣，它包括所有設(shè)施點(diǎn)和客戶點(diǎn)，是通過(guò)計(jì)算候選點(diǎn)到客戶點(diǎn)的運(yùn)行時(shí)間來(lái)創(chuàng)建最短時(shí)間矩陣，然后利用時(shí)間矩陣求出成本矩陣。

在設(shè)施定位對(duì)話框進(jìn)行相應(yīng)設(shè)置，打開(kāi)設(shè)施選擇集對(duì)話框，就會(huì)看到Trans CAD自動(dòng)生成了一個(gè)名為New Facilities的選擇集，它包含兩個(gè)點(diǎn)。設(shè)施數(shù)據(jù)窗中也會(huì)顯示出選擇集，最后Trans CAD生成一個(gè)設(shè)施選址結(jié)果圖。

3.1.2 車輛路線安排

本文需要解決的是受車輛類型、容量及成本約束、帶時(shí)間窗的車輛路線安排問(wèn)題，需要事先準(zhǔn)備好以下材料：（1）帶有服務(wù)時(shí)間限制的設(shè)施數(shù)據(jù)庫(kù)；（2）帶有營(yíng)業(yè)時(shí)間、車輛固定服務(wù)時(shí)間限制的客戶數(shù)據(jù)庫(kù)；（3）基于路網(wǎng)的包含所有設(shè)施點(diǎn)到客戶間的距離和出行時(shí)間的路線矩陣文件；（4）各設(shè)施車輛信息數(shù)據(jù)庫(kù)。[2]

本文在設(shè)施選址的基礎(chǔ)上進(jìn)行車輛路線安排。首先需要建立一個(gè)“規(guī)劃后設(shè)施”的選擇集以便后續(xù)程序調(diào)用，此選擇集包括已經(jīng)存在的1個(gè)設(shè)施和2個(gè)新設(shè)施。

在VRPTW對(duì)話框進(jìn)行相應(yīng)設(shè)置并輸出路線矩陣，還可輸出一個(gè)文本形式的車輛行程安排記錄。點(diǎn)擊演示路線命令，地圖中就會(huì)增加路線圖層并產(chǎn)生一個(gè)stops表格，顯示設(shè)施點(diǎn)和客戶點(diǎn)的對(duì)應(yīng)關(guān)系。

3.2 結(jié)果分析

本文規(guī)劃的三個(gè)設(shè)施中“F2”、“F8”為新規(guī)劃設(shè)施，“F5”為原有設(shè)施。對(duì)比設(shè)施定位結(jié)果和車輛路線安排結(jié)果可知，在設(shè)施定位模型中由設(shè)施“F5”為客戶“C10”提供配送服務(wù)，設(shè)施“F8”為客戶“C43、C44”服務(wù)，而在車輛路線模型中客戶“C10”是由設(shè)施“F2”服務(wù)的，客戶“C43、C44”由設(shè)施“F5”服務(wù)。為了實(shí)現(xiàn)物流設(shè)施定位和配送路線的整體優(yōu)化，本文要使用輛路線編輯工具箱對(duì)車輛路線安排方案進(jìn)行調(diào)整，將客戶點(diǎn) “C10”添加到設(shè)施“F5”的配送路線Route 7中，再點(diǎn)擊重新計(jì)算站點(diǎn)順序按鈕，系統(tǒng)將自動(dòng)調(diào)整該路線時(shí)間順序。另外，需為設(shè)施點(diǎn)“F8”和客戶點(diǎn)“C43”、“C44”創(chuàng)建新路線。[3]

3.3 A市物流設(shè)施選址與配送路線解決方案

圖1 A市物流系統(tǒng)LRP解決方案圖

在本文案例的解決方案中，從8個(gè)備選設(shè)施點(diǎn)選出“F2”、“F8”兩個(gè)規(guī)劃設(shè)施，這兩個(gè)設(shè)施和原有設(shè)施“F5”一起為46個(gè)客戶提供物流配送服務(wù)。一共形成12條配送路線。其中設(shè)施“F2”派出3輛車，形成Route 9、Route 10、Route 11 共 3 條配送路線。 設(shè)施“F5”派出 5 輛車，形成 Route 4、Route 5、Route 6、Route 7、Route8 共 5 條配送路線。 設(shè)施“F8”派出 4 輛車，形成 Route 1、Route 2、Route 3、Route 12 共 4 條配送路線。

Trans CAD路線系統(tǒng)顯示A市物流系統(tǒng)LRP解決方案（如圖1所示），還能為每一輛車制定了詳細(xì)的出行路徑和出行時(shí)間表。

4 結(jié)論

本文對(duì)基于Trans CAD軟件系統(tǒng)的物流系統(tǒng)LRP解決方案進(jìn)行了研究，對(duì)如何運(yùn)用Trans CAD中的物流模塊解決物流系統(tǒng)LRP進(jìn)行了闡述，解決了基于Trans CAD的物流系統(tǒng)LRP，最后對(duì)方案結(jié)果進(jìn)行分析，并用路線編輯工具對(duì)物流配送方案進(jìn)行調(diào)整，為非計(jì)算機(jī)專業(yè)的人員提供了一個(gè)解決LRP的平臺(tái)。

［1］Caliper Corporation.Trans CAD 中文用戶手冊(cè)[M].America，2002：215-220.

［2］楊寧，尚新春，韋獻(xiàn)蘭，李海峰.利用Trans CAD軟件包解決基于時(shí)間窗的車輛路徑問(wèn)題[J].交通與計(jì)算機(jī)，2007，1(25)：113-114.

［3］Caliper Corporation.Trans CAD 中文用戶手冊(cè)[S].America，2002：177-181.