城市物流配送訂單分配排序優化研究

師嘉欣，高更君

（上海海事大學 物流研究中心，上海 201306）

0 引言

隨著經濟的快速發展，城市物流配送已經成為城市經濟發展與居民生活的重要支撐系統，需求日趨旺盛。為提高城市物流配送的整體效率、滿足客戶的多種差異化需求，如何對大量客戶訂單進行合理分配使配送時間最短已成為國內外學者研究的熱點問題之一，典型的研究有：朱孟高[1]等面對龐大的客戶規模，將同一路段的客戶點和末梢客戶點進行合并，提出集束式算法解決城市物流配送問題；王雪萍[2]在考慮車輛有容量約束的情況下，以配送時間最短為目標，運用節約算法對城市配送問題進行求解；Anna Franceschettia[3]等把城市配送問題轉化為城市區域劃分的問題，用動態規劃算法求得時間最短的配送方案。這些研究通過對訂單配送時間的優化為解決城市物流配送問題提供了思路，但都未考慮訂單裝載時間對整體配送效率的影響。訂單貨物的裝載和配送是物流系統的重要環節，它們相互聯系、制約，影響訂單的整體配送效率。基于此，本文嘗試綜合考慮訂單裝載時間與配送時間對整體配送效率的影響，利用成組分批排序的理論和方法對解決資源和任務分配問題的優勢來解決城市物流配送訂單分配排序優化問題，以實現配送過程整體最優，從而提高整體配送效率和客戶滿意度。

1 城市物流配送訂單分配排序問題描述

城市物流配送依托城配中心來完成客戶的訂單配送任務，在運營過程中城配中心面臨著大量的訂單配送需求，需要通過集貨、分揀、裝載和配送等物流作業，按客戶的要求對訂單貨物有計劃的運輸并送到指定地點以完成訂單配送服務[4]。本文研究的是一個城市配送中心為多個客戶需求點提供配送服務的訂單分配排序問題，具體可以描述為城市配送中心在滿足客戶訂單需求及車載量限制等約束條件下，對客戶訂單進行分配，每批訂單開始配送前有一個批訂單貨物裝載時間，訂單貨物裝載完成后，每輛車從配送中心出發對客戶點完成服務后回到配送中心。要求確定合適的訂單分配和客戶服務順序，使訂單貨物裝載和配送的總完工時間最短，提高整體配送效率。

2 城市物流配送訂單分配排序模型建立

2.1 排序論概述

排序論作為運籌學的一個分支，對提高效率、資源的開發和配置、工程進展的安排以及經濟運行等方面都能起到輔助科學決策的作用，是解決資源和任務分配組合優化問題的一種理論和方法[4]。其中，成組分批排序理論是排序論中的一個組成部分，在成組分批排序理論中，每組工件在開始加工前，都需要一定的安裝時間，而且安裝時間會影響工件加工順序，在加工過程中工件不允許中斷，并且同一客戶的工件不可以分批進行加工，與本文研究的裝載和配送組合優化的訂單分配排序問題比較相似。并且對于制造系統中多品種、多頻次、小批量的工件加工需求，運用成組分批排序理論可以提高加工效率，實現資源最優調配，因此用成組分批排序理論解決本文研究的問題有一定的優勢。

2.2 模型假設及參數設定

2.2.1 模型假設

為了便于建模，作出假設：

1）車輛型號相同，在配送過程中勻速行駛，不考慮道路擁堵問題；

2）客戶的商品需求量和地點是已知的；

3）車輛的載貨量有限，任何一個客戶訂單需求的物品總量不能超過車輛的載貨量限制，訂單物品可以混裝；

4）不考慮車輛在客戶需求點停留的時間，即到即卸；

5）每輛車從配送中心出發并返回配送中心；

6）一輛車可以為多個客戶服務，但是一個客戶不能由多輛車服務。

2.2.2 參數設定

參數設定如下：

1）N表示需要配送的訂單集合，N=（N1，N2，…，Nn）；

2）M表示需要配送的車輛數，M=（M1，M2，…，Mm）；

3）X表示配送中心和客戶需求點編號X=（0，1，2，…，x），其中0表示配送中心，其余的點為客戶需求點x；

4）B表示訂單的分批批數，B=（1，2，…，b）；

5）Q為車輛的最大載貨量，以t為單位；

7）Yi表示在客戶點i需要配送的貨物量，以t為單位；

8）α表示車輛行駛速度；β表示裝貨的效率；

2.3 模型建立

根據本文提出的問題，將城市物流配送訂單中的每個貨物視為工件，車輛視為機器，將車輛在配送中心裝載貨物的時間視為工件的批安裝時間，將車輛行駛到每個客戶需求點的時間視為工件的標準加工時間，將車輛從一個客戶需求點行駛到另一個客戶需求點的時間視為工件的實際加工時間，以總完工時間最短作為目標，建立模型如下：

式(1)表示目標函數即總完工時間最短，T1為在配送中心裝載貨物的時間，即工件的安裝時間之和；T2為車輛的總行駛時間，即所有工件的加工時間之和；式(2)、式(3)表示每批訂單的配送路徑都形成一個哈密頓回路，即每批工件在一個機器上加工完后機器停止工作；式(4)表示任意訂單需要貨物量都不能超過車輛最大載貨量，即任意工件都可以在一臺機器上完成加工；式(5)表示任意批次訂單所需貨物量都要低于該批次車輛的最大載貨量，即車間每臺機器的加工容量有限；式(6)、式(7)表示客戶訂單不可以分割，一個客戶只能由一輛車服務，即同一客戶的工件不能分批加工。

3 模型算法設計

啟發式算法求解整數規劃模型可以降低計算難度，提高計算效率，所以本文用啟發式算法對模型進行求解，本文的啟發式算法原理是首先把所有工件依次分配給機器得到初始可行解，然后再重復互換最大完工時間最大和最大完工時間最小的兩臺機器的工件，直到沒有可改進的解，從而得到最優排序[6]。工件的交換方法和算法的具體步驟如下：

以M1和M2兩臺機器為例，如圖1所示，則工件交換方法如下：

圖1 工件交換圖示

表1 配送地理位置及需求分布

通過上述交換方法，對于工件N1最多需要進行兩次交換，使算法復雜度降低，提高了計算效率。

2）算法步驟

（1）將工件和機器依次編號，令N1為M1上的第一個工件。

（2）把剩下的工件依次分配給最先空閑下來的機器，當多臺機器同時空閑下來時，優先選擇編號小的機器，得到初始可行解。

（3）根據（2）中得到的工件順序計算每批的安裝時間和加工時間之和求得總完工時間，尋找互換后能使當前總完工時間變小的工件，若存在，轉（4），否則轉（5）。

（4）按照（1）中的交換方法將工件進行交換，交換完成后把兩臺機器上的工件順序重新排列使總完工時間最小。

（5）尋找可互換的工件，若存在，則轉（4）；否則，停止。

根據本文建立的城市物流配送訂單分配排序模型，在LINGO11.0上進行程序設計，運用上述啟發式算法求解可以得到總完工時間最小的訂單分配排序方案。

4 算例模擬

為了驗證模型和算法的有效性，假設有一個配送中心向七個客戶送桶裝水，配送中心與各個客戶的地理位置和每個客戶的需求如表1所示。已知配送中心有三輛型號相同的車，每輛車的最大載重量為10t，每桶水為0.02t，裝貨效率為12t/h，車輛的行駛速度為50km/h，車輛完成配送后返回配送中心[2]，通過合理的訂單分配排序方案，使總完工時間最短。

運用LINGO 11.0對算例求解，得到最優訂單分配排序方案如圖2所示，客戶訂單的分配排序方案為：第一批0-7-1-0；第二批0-2-6-0；第三批0-3-4-5-0，總完工時間為4.798h，則每個訂單的平均完工時間為（0.778+1.1 48+0.741+1.149+0.789+1.027+1.133）/7=0.966h。

圖2 訂單分配排序方案

由文獻[2]的研究成果可知若加上每批訂單貨物的裝載時間，則通過節約算法對訂單分配優化的總完成時間為2.678+1.249+1.125=5.052h，每個訂單的平均完工時間為（1.09+1.196+1.708+0.825+0.977+1.127+1.249+0.729）/7=1.272h?？傻贸霰疚难芯康膶蛻粲唵窝b載時間和配送時間組合優化所得到的總完工時間小于只對訂單配送時間優化所得到的總完工時間，同時可以降低每個訂單的平均完工時間，減少城市配送中心車輛的占用和其余客戶訂單的等待時間，實現資源的最優調配，提高整體配送效率和客戶滿意度。

5 結論

城市物流配送問題的解決能夠促進城市經濟健康快速發展，提高居民生活水平。通過本文的研究，建立了城市物流訂單配送總完工時間最短的目標函數模型，運用啟發式算法對算例進行求解，結果表明對客戶訂單的裝載時間和配送時間組合優化可以提高訂單整體配送效率，減少城市配送中心車輛的占用和其余訂單的等待時間，實現資源的最優調配，希望為以后城市物流訂單配送問題提供新思路。