城市物流配送訂單分配排序優(yōu)化研究

師嘉欣，高更君

（上海海事大學(xué) 物流研究中心，上海 201306）

0 引言

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

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

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

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

2.1 排序論概述

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

2.2 模型假設(shè)及參數(shù)設(shè)定

2.2.1 模型假設(shè)

為了便于建模，作出假設(shè)：

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

2）客戶的商品需求量和地點(diǎn)是已知的；

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

4）不考慮車輛在客戶需求點(diǎn)停留的時(shí)間，即到即卸；

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

6）一輛車可以為多個(gè)客戶服務(wù)，但是一個(gè)客戶不能由多輛車服務(wù)。

2.2.2 參數(shù)設(shè)定

參數(shù)設(shè)定如下：

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

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

3）X表示配送中心和客戶需求點(diǎn)編號(hào)X=（0，1，2，…，x），其中0表示配送中心，其余的點(diǎn)為客戶需求點(diǎn)x；

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

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

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

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

2.3 模型建立

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

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

3 模型算法設(shè)計(jì)

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

以M1和M2兩臺(tái)機(jī)器為例，如圖1所示，則工件交換方法如下：

圖1 工件交換圖示

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

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

2）算法步驟

（1）將工件和機(jī)器依次編號(hào)，令N1為M1上的第一個(gè)工件。

（2）把剩下的工件依次分配給最先空閑下來的機(jī)器，當(dāng)多臺(tái)機(jī)器同時(shí)空閑下來時(shí)，優(yōu)先選擇編號(hào)小的機(jī)器，得到初始可行解。

（3）根據(jù)（2）中得到的工件順序計(jì)算每批的安裝時(shí)間和加工時(shí)間之和求得總完工時(shí)間，尋找互換后能使當(dāng)前總完工時(shí)間變小的工件，若存在，轉(zhuǎn)（4），否則轉(zhuǎn)（5）。

（4）按照（1）中的交換方法將工件進(jìn)行交換，交換完成后把兩臺(tái)機(jī)器上的工件順序重新排列使總完工時(shí)間最小。

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

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

4 算例模擬

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

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

圖2 訂單分配排序方案

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

5 結(jié)論

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