多時(shí)間窗的物流配送中心-配送路徑選取模型研究

重慶市市政設(shè)計(jì)研究院

0 引 言

正確選擇物流節(jié)點(diǎn)和配送服務(wù)方式，合理確定物流配送流程，對(duì)提升物流效率、提高物流企業(yè)經(jīng)濟(jì)效益有著非常重要的意義。羅耀波等[1]在考慮倉(cāng)庫(kù)容量約束和車輛容量約束的基礎(chǔ)上，結(jié)合送取貨一體化的配送模式和客戶服務(wù)時(shí)間要求，建立帶退貨和軟時(shí)間窗的多倉(cāng)庫(kù)選址-路徑問(wèn)題數(shù)學(xué)模型。Wu等[2]考慮多場(chǎng)站情景，將原問(wèn)題分為兩個(gè)子問(wèn)題，運(yùn)用模擬退火算法和迭代的方式進(jìn)行求解。劉虹等[3]研究帶時(shí)間窗約束的越庫(kù)選址-路徑問(wèn)題，采用時(shí)間窗模糊化處理方法定義客戶滿意度函數(shù)，在能力和載重等約束下，建立多目標(biāo)規(guī)劃模型。Ko?等[4]考慮帶有時(shí)間窗約束的多車型選址-路徑問(wèn)題，提出混合整數(shù)規(guī)劃模型與一組有效不等式。羅耀波等[5]針對(duì)帶倉(cāng)庫(kù)容量約束和路徑容量約束的選址-路徑問(wèn)題，提出一種結(jié)合模擬退火算法的混合遺傳算法進(jìn)行整體求解。Winkenbach等[6]將城市物流過(guò)程中貨物整合、配送外包、運(yùn)輸方式選擇等因素考慮在兩級(jí)網(wǎng)絡(luò)選址-路徑問(wèn)題中，構(gòu)建帶時(shí)間約束的混合整數(shù)線性規(guī)劃模型。Pichka等[7]研究含有開放路徑的兩級(jí)網(wǎng)絡(luò)選址-路徑問(wèn)題，提出混合整數(shù)規(guī)劃模型與混合啟發(fā)式算法。

以上研究，都未考慮配送中心開放成本與多時(shí)間窗口。本文在綜合考慮配送中心選址、配送中心開放成本、配送車輛使用成本、服務(wù)時(shí)效需求等因素的基礎(chǔ)上，引入配送時(shí)間窗口，即要求配送車輛僅能在規(guī)定時(shí)間窗內(nèi)到達(dá)客戶點(diǎn)，且在時(shí)間窗關(guān)閉前駛離客戶點(diǎn)，并以總成本最小化為目標(biāo)，建立多時(shí)間窗的多配送中心選址-配送路徑選取模型，并利用商業(yè)化運(yùn)算軟件Cplex（版本12.4）對(duì)模型進(jìn)行精確求解。

1 問(wèn)題及數(shù)學(xué)模型

1.1 問(wèn)題描述

問(wèn)題具體特征如下：

（1）運(yùn)輸網(wǎng)絡(luò)中包含兩類節(jié)點(diǎn)：配送中心及配送中心輻射范圍內(nèi)若干有配送需求的客戶點(diǎn)。所有節(jié)點(diǎn)的位置已知，配送中心是否開放需結(jié)合配送中心開放成本、配送距離、客戶點(diǎn)需求等各種因素綜合權(quán)衡而定。配送中心是配送卡車的始發(fā)/終到點(diǎn)。

（2）每一個(gè)配送中心均保有足夠數(shù)量的配送卡車，車輛類型相同，且其額定載重、行駛速度等均為已知。

（3）客戶點(diǎn)的貨物需求已知且不可拆分，每個(gè)客戶點(diǎn)只能由一輛配送卡車服務(wù)，且只能被服務(wù)一次。

（4）所有客戶點(diǎn)均有服務(wù)時(shí)間窗限制，每個(gè)客戶點(diǎn)有多個(gè)時(shí)間窗，對(duì)于每個(gè)客戶點(diǎn)，其服務(wù)時(shí)間窗之間相互不重疊。配送卡車對(duì)客戶點(diǎn)的服務(wù)必須在相應(yīng)的時(shí)間窗開啟后才能開始，在時(shí)間窗關(guān)閉前完成服務(wù)，即配送卡車不能在非時(shí)間窗的時(shí)間段到達(dá)客戶點(diǎn)。

1.2 參數(shù)及變量

上述問(wèn)題所涉及參數(shù)及變量含義如表1所示。

1.3 目標(biāo)函數(shù)

目標(biāo)函數(shù)為總成本最小化，目標(biāo)函數(shù)式（1）包含三部分：第一部分為配送卡車的行駛成本；第二部分為配送卡車的使用成本；第三部分為配送中心的開放成本。

表1 參數(shù)及變量

1.4 約束條件

約束（2）表示配送卡車進(jìn)出配送中心次數(shù)相同。約束（3）表示對(duì)于任意車輛只能使用一次。約束（4）表示對(duì)于任一客戶點(diǎn)，只能被一輛配送卡車服務(wù)一次。約束（5）表示配送卡車進(jìn)出節(jié)點(diǎn)次數(shù)相等，且每輛配送卡車對(duì)同一節(jié)點(diǎn)服務(wù)一次。約束（6）表示客戶點(diǎn)貨物由某個(gè)配送中心進(jìn)行配送。約束（7）和（8）表示某配送中心是否開放。約束（9）和（10）確定變量zmhi的取值，表示客戶點(diǎn)貨物由某輛配送卡車從某配送中心進(jìn)行配送。約束（11）和（12）表示若配送中心下的配送卡車被使用，則該配送卡車一定從該配送中心出發(fā)。約束（13）表示配送卡車載重限制。約束（14）和（15）表示配送卡車從配送中心到客戶點(diǎn)的時(shí)間連續(xù)性。約束（16）和（17）表示配送卡車在客戶點(diǎn)間的到達(dá)時(shí)間連續(xù)性。約束（18）表示配送卡車到達(dá)客戶點(diǎn)的基本時(shí)間約束，并對(duì)未使用配送卡車進(jìn)行取值的輔助約束。約束（19）和（20）確定變量sciht的取值，表示配送卡車在客戶點(diǎn)某個(gè)時(shí)間窗開啟后到達(dá)。約束（21）和（22）確定變量eciht的取值,表示配送卡車在客戶點(diǎn)某個(gè)時(shí)間窗關(guān)閉前到達(dá)。約束（23）和（24）確定變量gciht的取值，表示配送卡車在哪個(gè)時(shí)間窗到達(dá)客戶點(diǎn)。約束（25）表示配送卡車到達(dá)客戶點(diǎn)的時(shí)間約束。約束（26）和（27）表示配送卡車離開客戶點(diǎn)的時(shí)間限制，即配送卡車在哪個(gè)時(shí)間窗對(duì)客戶點(diǎn)進(jìn)行服務(wù)，就需要在該時(shí)間窗內(nèi)完成服務(wù)并離開該點(diǎn)。

2 模型求解

為驗(yàn)證所構(gòu)建模型的可用性，利用Matlab軟件生成一系列隨機(jī)算例，并結(jié)合物流配送企業(yè)實(shí)踐，選定混合整數(shù)規(guī)劃模型所涉及主要參數(shù)的具體取值。

2.1 條件設(shè)定及主要參數(shù)選取

網(wǎng)絡(luò)節(jié)點(diǎn)坐標(biāo)采用隨機(jī)生成的方式，以1 km為單位，建立笛卡爾坐標(biāo)系。首先指定配送中心的位置，假定配送中心分布在邊長(zhǎng)為90 km的正方形區(qū)域內(nèi)，其坐標(biāo)為在該范圍內(nèi)生成的若干個(gè)點(diǎn)，且任意兩點(diǎn)間的距離應(yīng)大于15 km。接著在各配送中心的輻射范圍（服務(wù)半徑）內(nèi)，生成相應(yīng)的客戶點(diǎn)坐標(biāo)，且任意兩個(gè)客戶點(diǎn)之間的距離應(yīng)大于300 m。鑒于客戶點(diǎn)的多時(shí)間需求，設(shè)定客戶點(diǎn)在一個(gè)工作日內(nèi)的所有時(shí)間窗均位于區(qū)間[5,18]，針對(duì)每個(gè)客戶點(diǎn)都在該區(qū)間內(nèi)隨機(jī)生成多個(gè)沒(méi)有交集的時(shí)間窗，且任意時(shí)間窗的長(zhǎng)度至少大于配送卡車在該點(diǎn)的服務(wù)時(shí)間。

算例中主要參數(shù)取值如表2所示。

2.2 求解與結(jié)果分析

運(yùn)用Cplex軟件對(duì)不同規(guī)模的隨機(jī)算例進(jìn)行精確求解，計(jì)算結(jié)果如表3所示。

以算例7為例，網(wǎng)絡(luò)中包含3個(gè)配送中心（D1，D2，D3），9個(gè)客戶點(diǎn)，設(shè)定配送中心開放成本分別為0、50、100元/d。當(dāng)pm=0元/d時(shí)，即不考慮配送中心開放成本，精確求解結(jié)果中的選址與車輛路徑方案如表4所示，選擇開放2個(gè)配送中心，目標(biāo)函數(shù)值為315.56元；當(dāng)pm=50元/d時(shí)，求解結(jié)果中的選址與車輛路徑方案不變，目標(biāo)函數(shù)值為415.56，新增成本即為配送中心成本；當(dāng)pm=100元/d時(shí)，求解方案如表5所示，此時(shí)僅選擇開放1個(gè)配送中心，相應(yīng)配送路徑方案也發(fā)生變化，目標(biāo)函數(shù)值為466.54元。由此可以看出，當(dāng)參數(shù)取值不同時(shí)，所得選址-路徑方案與目標(biāo)函數(shù)值也有所差別。

表2 主要參數(shù)取值

表3 算例的精確算法求解結(jié)果

表4 算例7精確解的選址-路徑方案（pm=0元/d）

表5 算例7精確解的選址-路徑方案（pm=100元/d）

求解結(jié)果表明，隨著算例規(guī)模增大，目標(biāo)函數(shù)值呈上升趨勢(shì)，且當(dāng)參數(shù)取值（m、n、pm）相同時(shí)，不同算例的運(yùn)算結(jié)果也相對(duì)平穩(wěn)。針對(duì)同一算例，配送中心的開放成本若取不同的值，將對(duì)結(jié)果產(chǎn)生較大影響，若不考慮配送中心開放成本，在選址方案中會(huì)選擇開放更多的配送中心，盡可能減少運(yùn)輸過(guò)程中的配送成本；而當(dāng)配送中心的開放成本逐漸增大時(shí)，將會(huì)減少配送中心的開放數(shù)量，使得總成本最小。

3 結(jié) 語(yǔ)

面向帶多時(shí)間窗的多配送中心選址-路徑規(guī)劃問(wèn)題，構(gòu)建混合整數(shù)規(guī)劃模型，利用Cplex軟件對(duì)隨機(jī)生成的算例進(jìn)行精確求解，通過(guò)對(duì)選址方案與車輛路徑的優(yōu)化實(shí)證，驗(yàn)證所建模型的有效性。在實(shí)踐中，應(yīng)合理權(quán)衡選址中心開放成本與運(yùn)輸成本之間的關(guān)系，做出最優(yōu)決策。本研究豐富了選址-路徑問(wèn)題的建模手段，算例運(yùn)算試驗(yàn)可為決策者提供參考。