轉運問題

轉運問題是運輸問題的一個子類，其中允許轉運。在轉運中，運輸可以或必須經過中間節點，並可能改變運輸方式。

轉運問題起源於中世紀，當時貿易開始成為一種大眾現象。獲得最低成本的路線是當時的主要優先考量。然而，隨著技術發展，最短時間的運輸問題逐漸受到重視。

概觀

轉運（Transshipment 或 Transhipment）是將貨物或貨櫃運送至一個中間目的地，再從該地運往另一個目的地的過程。其中一個可能的原因是在旅途中改變運輸方式（例如從海運轉為陸運），這被稱為換裝（transloading）。另一個原因則是將小型貨物合併為大型貨物（集貨），並在另一端將大型貨物拆分（分貨）。轉運通常在運輸樞紐進行。許多國際轉運也在指定的關稅區進行，從而避免了海關檢查或關稅，否則這將是高效運輸的主要障礙。

問題的建構

為了完整地建構轉運問題，需要一些初始假設：

系統包含 m 個起點和 n 個終點，其索引分別為： <math>i=1,\ldots, m</math>，<math>j=1,\ldots, n</math>
存在一種需要被運送的單一商品
終點所需的商品數量等於起點可提供的產出數量
運輸同時從所有起點開始，且可從任一節點運至任何其他節點（包括運至另一起點或從某一終點運出）
運輸成本與運送數量無關
轉運問題是一種獨特的線性規劃問題 (LLP)，其特殊之處在於它考慮了所有源點與匯點皆可同時接收和分配貨物（雙向運作）的假設

符號說明

<math>t_{r,s}</math>：從節點 r 到節點 s 的運輸時間
<math>a_i</math>：節點 i 的可供應商品量
<math>b_{m+j}</math>：節點 (m+j) 的商品需求量
<math>x_{r,s}</math>：從節點 r 到節點 s 的實際運輸量

問題的數學模型

目標是最小化 <math>\sum\limits_{i=1}^m \sum\limits_{j=1}^n t_{i,j} x_{i,j} </math>，其限制條件為：

<math> x_{r,s}\geq 0 </math>; <math>\forall r=1\ldots m </math>, <math>s=1\ldots n</math>
<math>\sum_{s=1}^{m+n}{x_{i,s}}-\sum_{r=1}^{m+n}{x_{r,i}}=a_i</math>; <math>\forall i=1\ldots m</math>
<math>\sum_{r=1}^{m+n}{x_{r,m+j}}-\sum_{s=1}^{m+n}{x_{m+j,s}}=b_{m+j}</math>; <math>\forall j=1\ldots n</math>
<math>\sum_{i=1}^{m}{a_i}=\sum_{j=1}^{n}{b_{m+j}}</math>

解法

由於在大多數情況下，目標函數不存在顯式表達式，Rajeev 和 Satya 提出了一種替代方法。此方法使用連續兩個階段來找出從起點到終點的最短時間路徑。第一階段旨在解決 <math>n\cdot m</math> 個時間最小化問題，在每種情況下，都使用剩餘的 <math>n+m-2</math> 個中間節點作為轉運點。這也導出了所有起點與終點之間的最短時間運輸。在第二階段，需要解決一個標準的時間最小化問題。此時間最小化轉運問題的解，是這兩個階段的聯合求解結果。

第一階段

由於成本與運送數量無關，在每個獨立問題中，可以將運送數量標準化為 1。問題現在簡化為一個從 i 到 m+j 的指派問題。設 <math>x'_{r,s}=1</math> 表示在最佳化過程中使用了節點 r 和 s 之間的邊，否則為 0。現在的目標是確定所有的 <math>x'_{r,s}</math>，以最小化目標函數：

<math>T_{i,m+j}=\sum_{r=1}^{m+n}\sum_{s=1}^{m+n}{t_{r,s}\cdot x'_{r,s}}</math>,

滿足以下條件

<math>\sum_{s=1}^{m+n}{x'_{r,s}}=1</math>
<math>\sum_{r=1}^{m+n}{x'_{r,s}}=1</math>
<math>x'_{m+j,i}=1</math>
<math>x'_{r,s}=0,1</math>.

推論

<math>x'_{r,r}=1</math> 和 <math>x'_{m+j,i}=1</math> 需要從模型中排除；另一方面，若沒有 <math>x'_{m+j,i}=1</math> 的限制，最佳路徑將只包含 <math>x'_{r,r}</math> 型的循環，這顯然不是一個可行解。
可以不使用 <math>x'_{m+j,i}=1</math>，而改寫為 <math>t_{m+j,i}=-M</math>，其中 M 是一個任意大的正數。透過此修改，上述的數學模型可簡化為標準指派問題的形式，並能使用匈牙利演算法求解。

第二階段

在第二階段，解決一個包含 m 個起點和 n 個終點且無轉運的時間最小化問題。此階段與原始設定有兩個主要不同之處：

運輸僅能從起點到終點
從 i 到 m+j 的運輸時間是在第一階段計算出的最佳路徑的時間總和。為與第一階段引入的時間區分，可將其記為 <math>t'_{i,m+j}</math>。

數學形式

目標是找到 <math>x_{i,m+j}\geq 0</math> 以最小化

<math>z=max\left\{t'_{i,m+j}: x_{i,m+j}>0\;\; (i=1\ldots m,\; j=1\ldots n)\right\}</math>,
滿足以下條件

<math>\sum_{i=1}^{m}{x_{i,m+j}}=a_i</math>
<math>\sum_{j=1}^{n}{x_{i,m+j}}=b_{m+j}</math>
<math>\sum_{i=1}^{m}{a_i}=\sum_{j=1}^{n}{b_{m+j}}</math>

這個問題可以輕易地用 Prakash 所開發的方法解決。集合 <math>\left\{t'_{i,m+j}, i=1\ldots m,\; j=1\ldots n\right\}</math> 需要被分割成子群組 <math>L_k, k=1\ldots q</math>，其中每個 <math>L_k</math> 包含所有數值相同的 <math>t'_{i,m+j}</math>。序列 <math>L_k</math> 的組織方式為：<math>L_1</math> 包含數值最大的 <math>t'_{i,m+j}</math>，<math>L_2</math> 包含次大的，以此類推。此外，將正的優先因子 <math>M_k</math> 指派給子群組 <math>\sum_{L_k}{x_{i,m+j}}</math>，規則如下：

<math>\alpha M_k-\beta M_{k+1}=\left\{\begin{array}{cc}-ve, & if\; \alpha<0\\ ve, & if\; \alpha>0 \end{array}\right.</math>

對所有的 <math>\beta</math>。使用此符號，目標是找到所有 <math>x_{i,m+j}</math> 以最小化目標函數

滿足以下條件

<math>\sum_{i=1}^{m}{x_{i,m+j}}=a_i</math>
<math>\sum_{j=1}^{n}{x_{i,m+j}}=b_{m+j}</math>
<math>\sum_{i=1}^{m}{a_i}=\sum_{j=1}^{n}{b_{m+j}}</math>
<math>\alpha M_k-\beta M_{k+1}=\left\{\begin{array}{cc}-ve, & if\; \alpha<0\\ ve, & if\; \alpha>0 \end{array}\right.</math>

延伸

部分學者如 Das 等人 (1999) 和 Malakooti (2013) 曾探討過多目標轉運問題。

參考資料