美國郵政公路運輸?shù)膬?yōu)化研究節(jié)選一

1、美國郵政公路運輸?shù)膬?yōu)化研究（節(jié)選一）摘要：美國郵政每年投遞超過2000億件包裹，如何在規(guī)定的時間內(nèi)和節(jié)約成本的前提下運送這些包裹，這是美國郵政面臨的一個重要課題。HCAP模型協(xié)助美國郵政進行公路運輸分析，尋找成本節(jié)約空間。通過HCAP模型，美國郵政目前每年已經(jīng)實現(xiàn)過百萬美元的成本節(jié)約。 背景 美國郵政的運輸系統(tǒng)是世界上最大最復(fù)雜的物流系統(tǒng)之一，每年運送超過2000億件郵件。它的陸路運輸網(wǎng)絡(luò)由多個不同的部分組成，每個部分都有其獨特的功能。美國郵政每年運送的郵件類型多樣，包括信函、扁平件（例如專門放文件的超大信封）、包裹和期刊。每種類型的郵件都有其特性，從尺寸、形狀到重量都各不相同，從而對分揀處理

2、提出不同的要求。美國郵政對不同的郵件進行了分類，包括優(yōu)先郵件、一類郵件（時限包括次日達(dá)、兩日達(dá)、三日達(dá)）和標(biāo)準(zhǔn)郵件，每一類郵件都有明確的服務(wù)和時限要求。為滿足不同類型郵件的服務(wù)要求，美國郵政建立了相應(yīng)的轉(zhuǎn)運中心，比如標(biāo)準(zhǔn)包裹和期刊在大宗（大體積）郵件處理中心進行處理，優(yōu)先郵件用卡車運至優(yōu)先郵件處理中心，對時限要求高的特快及部分一類和優(yōu)先郵件用卡車從處理分發(fā)中心運送至航空郵件處理中心，進入航空運輸網(wǎng)絡(luò)。 雖然美國郵政每一個郵件處理中心都有其獨特的使命，但在實際使用中仍存在著明顯的交叉和重復(fù)的情況。比如貨車在兩個處理及分發(fā)中心之間進行運輸?shù)臅r候可能會在大宗郵件處理中心停留裝卸；同時，本屬 STC之

3、間的運輸也可能會在處理及分發(fā)中心裝卸郵件。這些重復(fù)交錯的網(wǎng)絡(luò)運行明顯增加了美國郵政的運輸規(guī)劃的復(fù)雜性和挑戰(zhàn)性。平均每個工作日，美國郵政要在30000個終端（包括處理中心、郵局和其他終端）之間安排75000條路向。因此美國郵政采用了一系列先進的分析工具和技術(shù)去管理其龐大而復(fù)雜的運輸網(wǎng)絡(luò)。大宗郵件處理中心區(qū)間郵件處理中心處理及分發(fā)中心圖1：美國東北部郵政運輸網(wǎng)絡(luò)概況 目標(biāo) 作為一個分析工具，高速公路運輸分析系統(tǒng)模型（簡稱HCAP模型）的作用在于減少公路運輸成本的同時保證了投遞的及時性。這套系統(tǒng)協(xié)助美國郵政分析運輸網(wǎng)絡(luò)的路徑和日程安排，同時它具有足夠的靈活性，能夠應(yīng)用于不同層次的網(wǎng)絡(luò)，比如說可以應(yīng)用

4、于全國各大轉(zhuǎn)運中心、或者東北部的郵件處理中心，還可以專門用于全國的大宗郵件處理中心（詳見模型解決方案章節(jié)）。 HCAP模型除了能夠應(yīng)用于不同類型和層次的網(wǎng)絡(luò)之外，更重要的是為了解決一個標(biāo)志性問題，這個問題是由不同處理中心之間的郵件收發(fā)需求以及各種可靈活運用的運輸資源所共同產(chǎn)生的。HCAP模型能夠優(yōu)化這些由郵件收發(fā)需求帶來的各種運輸問題，同時尋求潛在的能夠?qū)崿F(xiàn)滿足這些郵件收發(fā)需求的路徑選擇。因此在模型處理問題的過程中，非常有必要明確所有的郵件收發(fā)需求以及各種潛在的運輸路徑選擇。這里講的郵件收發(fā)需求指涉及不同類型郵件在各個處理中心之間的接收與投遞。 HCAP模型的目標(biāo)是優(yōu)化現(xiàn)存的運輸網(wǎng)絡(luò)，也就是說

5、，降低網(wǎng)絡(luò)運行成本。模型的目標(biāo)不是為了打造一個全新的運輸網(wǎng)絡(luò)，而是去分析各種潛在的運輸路徑選擇。該模型運用探索法和業(yè)務(wù)洞察力生成新的運輸路徑，以供模型在優(yōu)化運輸網(wǎng)絡(luò)的過程中進行選擇。HCAP模型能夠在現(xiàn)存和各種新的運輸路徑選擇的基礎(chǔ)上明確指出最優(yōu)的運輸資源組合。 模型解決方案 HCAP模型優(yōu)化了美國郵政運輸網(wǎng)絡(luò)各個組成部分的綜合利用。該模型尤其著力于解決同時收發(fā)運輸路徑問題（VRP/PD）。Bodin和Golden在1981年對各種運輸路徑問題（VRP）進行了分類。VRP模型明確了在各個終端進行路徑運輸?shù)膬?yōu)化方案。以下是模型三大基礎(chǔ)組成部分： 終端：指在運輸網(wǎng)絡(luò)中所有的實體場所。在HCAP模型

6、中，終端指的是像處理分發(fā)中心、STC、航空郵件和大宗郵件處理中心等進行郵件接收與分發(fā)的場所。 總包：指的是在各個終端之間進行分發(fā)運輸?shù)泥]件。在HCAP模型中，它指的是在特定時間窗內(nèi)從出發(fā)地運至目的地的郵件量，同時也可以表示具有特定服務(wù)標(biāo)準(zhǔn)的某一類郵件（例如一類郵件、從紐約至三藩市的三日達(dá)郵件）。模型中的總包分為兩類：可分割總包與不可分割總包。 路向：在HCAP模型中，路向指的是在特定時間窗內(nèi)把總包從出發(fā)地運至目的地所采用的各條路徑。路徑可能是一站式的，也可能中途作多次停留，每次停留都可能在某個郵件處理中心收發(fā)郵件。路向的定義包含以下幾個方面：貨車的運能、每一站到達(dá)和離開的時間以及成本。需要注意

7、的是路向的定義在HCAP模型的應(yīng)用中具有十分重要的意義。路向集合的產(chǎn)生基于由美國郵政的合約承包運輸商組成的高速公路網(wǎng)絡(luò)。 對于模型中出現(xiàn)的多站式路向，我們運用另外一個概念來描述： 路徑：每個路向可以由一系列連續(xù)站點之間的路徑來組成。直接路向可以只有一條路徑，直接從出發(fā)地達(dá)到目的地。多站式路向可以有不同的路徑，每條路徑連接著兩個處理中心。 美國郵政的每一個處理中心既可以作為出發(fā)地又可以作為目的地，因此在實際情況中每一個處理中心都可以同時接收和分發(fā)郵件。HCAP中的同時收發(fā)運輸路徑模型（VRP/PD）在分派收發(fā)任務(wù)的過程中經(jīng)常會運用到以下約束： 分派約束：每次的郵件收發(fā)量必須被安排在一條或多條可實

8、現(xiàn)的路向之中，路向要讓郵件的收發(fā)任務(wù)在特定的時間窗內(nèi)從出發(fā)地到達(dá)目的地。 容量約束：對于路向中的每一條路徑，每一次的郵件收發(fā)量必須小于或等于路徑的容量。HCAP模型允許每一條路向中路徑擁有不同的容量，因此在模型的應(yīng)用中，美國郵政可以把一些原本不在模型計算范圍內(nèi)的郵件量列入模型的其它路向路徑當(dāng)中。 最小成本：可同時滿足分派約束和容量約束，成本包括在確定路向時所發(fā)生的固定成本，以及在計算某一條特定路徑郵件投遞總量時所發(fā)生的變動成本。在的同時收發(fā)運輸路徑問題（VRP/PD）中尋求最優(yōu)和次優(yōu)解決方案的方法有很多，這些方法包括使用各種商業(yè)軟件和軟件庫。在這些方法之中選擇的時候，可以運用以下要求進行評估：（1） 解決時間：HCAP模型計算最優(yōu)或次優(yōu)方案的時間是非?？斓?，通常的解決時間都不會超過幾分鐘（簡單一點的問題甚至幾十秒就可以了），次優(yōu)方案的解決時間一般只占最優(yōu)方案的百分之一左右。（2） 最優(yōu)性：方案必須是最優(yōu)或次優(yōu)的。如果不是的話，方案將不會對現(xiàn)狀帶來任何“明顯的”改善，這種改善只需簡單的檢查就能發(fā)現(xiàn)。（3） 可擴展性：模型當(dāng)初的設(shè)計容量大概是幾千條路向，未來要擴展至上百萬條路向。（4） 靈活性：由于同時收發(fā)運輸路徑問題（VRP/PD）是模型的核心組成部分，因此對模型的要求額外增加了的這種情況將無可避免