基于遺傳算法的帶有時間窗的配送方案設(shè)計

劉曉扣 程金洋（劉曉扣，青島理工大學(xué)管理工程學(xué)院；程金洋，青島理工大學(xué)信息與控制工程學(xué)院）

隨著人們生活方式的改變，外賣成為生活中不可缺少的一部分。訂餐配送又面臨著諸多問題，例如配送超時、訂單分批不合理等，因此制定合理的配送規(guī)劃是非常重要的。

■ 模型的建立

（一）基本假設(shè)

（1）假設(shè)商家的位置已知而且唯一，且位于服務(wù)范圍的中心點(diǎn)處。所有的需求點(diǎn)均位于商家的配送范圍內(nèi)。（2）假設(shè)在一個時間周期內(nèi)，外賣員從整點(diǎn)時刻在商家出發(fā)，完成配送任務(wù)后，必在下一個整點(diǎn)時刻前返回商家，以不影響下一周期的配送任務(wù)。（3）每個需求點(diǎn)都有一定的訂單數(shù)，且僅由一名外賣員為其服務(wù)；同一個需求點(diǎn)的任務(wù)不可由多名外賣員完成。（4）外賣人員的單次攜帶量有最大限制，即有上限。（5）所有的外賣人員的配送車輛相同，行駛速度相同。6.假設(shè)兩點(diǎn)之間的距離為歐氏距離。

（二）符號的定義

1.qi：需求點(diǎn)i 的訂單數(shù)。2.Q：外賣員單次最大攜帶量。3.ai：需求點(diǎn)允許的最遲送達(dá)時間。4.Sik：第k 個外賣員配送需求點(diǎn)i 的開始時間。5.ti 服務(wù)第i 個需求點(diǎn)所需要的時間。6.tij：外賣員從節(jié)點(diǎn)i 到節(jié)點(diǎn)j 的行駛時間，與節(jié)點(diǎn)ij 之間的距離成正比。

（三）最優(yōu)配送路線模型

Step1：設(shè)置0-1 決策變量：

Step2：根據(jù)外賣配送要求，當(dāng)外賣員完成一單的平均時間最小時，此時的求解為最優(yōu)的配送路徑，因此目標(biāo)函數(shù)與約束條件為：

Step3.滿足的約束條件為：

式（1）表示由每個需求點(diǎn)只能被一個外賣人員服務(wù)；式（2）表示外賣員配送完一個需求點(diǎn)后，必須馬上離開，保持路徑的連貫性；式（3）表示每個外賣員攜帶的包裹量不能超過最大攜帶量；式（4）表示所有外賣員于整點(diǎn)時刻必須從餐廳商家出發(fā)；式（5）表示所有的外賣員完成配送后，在下一個整點(diǎn)時刻前，必須返回商家；式（6）表示外賣員k 經(jīng)過點(diǎn)j，則必從其他唯一節(jié)點(diǎn)駛來；式（7）表示外賣員k 經(jīng)過點(diǎn)i，則必向其他唯一節(jié)點(diǎn)駛?cè)ィ皇剑?）表示對路上行駛時間、外賣交接時間、外賣員開始服務(wù)客戶的實(shí)際需要進(jìn)行約束，為避免出現(xiàn)延誤情況，外賣配送需要滿足服務(wù)第i 個需求點(diǎn)的總時間早于開始服務(wù)下一個需求點(diǎn)j 的時間；式（9）表示外賣員k 開始服務(wù)第i 個需求點(diǎn)的時間要早于需求點(diǎn)i 允許的最遲開始服務(wù)時間。

■ 模型的求解

（一）數(shù)據(jù)的處理

1.需求點(diǎn)的位置

在直角坐標(biāo)系的第一象限中，選定配送范圍為邊長為50 的正方形區(qū)域。假定中心點(diǎn)（25,25）為餐館，利用MATLAB 在配送范圍內(nèi)隨機(jī)生成20 個需求點(diǎn)，且這些需求點(diǎn)在范圍內(nèi)均勻分布。

2.需求量的確定

本文研究11 點(diǎn)-12 點(diǎn)這個時間段，共有20 個訂單數(shù)，利用MATLAB 在[1,10]內(nèi)隨機(jī)生成20 個訂單數(shù)，且所有的訂單量服從正態(tài)分布。

3.每個需求點(diǎn)的要求最遲送達(dá)時間

在每個時間段的開始的時候，所有的外賣員出發(fā)配送。在11:00-12:00 該周期內(nèi)，商家接到上一周期內(nèi)產(chǎn)生的訂單，積攢到11 點(diǎn)，統(tǒng)一配送。分配好配送路線的外賣人員在11 點(diǎn)出發(fā)，嚴(yán)格按照路徑行駛，并在12 點(diǎn)前返回餐館，以便完成下一周期的配送任務(wù)。每個時間段內(nèi)的需求點(diǎn)要求的最遲送達(dá)時間，以該時間段的左時間窗為0 點(diǎn)，在[1,60]內(nèi)隨機(jī)生成。

（二）外賣人員數(shù)、配送路線的求解

外賣人數(shù)不受限制，外賣員每次的最大攜帶量為20 份，根據(jù)不同的時間段，外賣人員數(shù)有所變化，以滿足每個時段的配送需求。在11:00-12:00 時間段內(nèi)，由生成的隨機(jī)數(shù)據(jù)并利用遺傳算法求解，配送路線圖如圖1。

該時間段的最佳配送方案見表1。

表1 11:00-12:00的最佳配送方案

■ 模型的改進(jìn)

在以上的分析中，本文建立了外賣人員最大化、餐廳的制作能力無限大理想狀況下的配送路線模型，并求解給出最大數(shù)量的外賣人員數(shù)和配送路線。

研究模型一情況下的外賣配送路線，我們發(fā)現(xiàn)外賣人員過多，致使餐館的運(yùn)營成本較高，同時餐廳的外賣能力在實(shí)際中也是有限度的。因此本文對模型進(jìn)行了改進(jìn)，加入外賣人員人數(shù)限制與餐廳外賣制作能力限制條件。

（1）配送路線仍滿足模型一的目標(biāo)函數(shù)以及約束條件。

（2）餐館配備的外賣員是固定的，設(shè)為六人。

（3）若餐廳的外賣提供能力為110 份/時，一小時內(nèi)的累積訂單數(shù)超過110，就詢問該周期內(nèi)最晚的訂單顧客是否同意延單，即將顧客的訂單安排在下一周期配送；若不同意，則舍棄該訂單。延單后，若延單數(shù)量過多，則在下一周期內(nèi)考慮停止接單。為了保證餐廳最大化收益、提高顧客滿意度，盡可能地減少延單甚至停單情況的發(fā)生。所以建議在發(fā)生該情況時增加外賣人員的數(shù)量同時提高餐廳制作能力，以滿足顧客需求。

■ 總結(jié)

通過對外賣配送方案的研究，本文給出了理想狀態(tài)下的配送路線模型，并在此基礎(chǔ)上考慮餐廳外賣提供能力，對模型進(jìn)行了改進(jìn)，使模型更具有實(shí)用性。本文建立的外賣配送路線模型，可以很好地給出每個商家的最佳外賣配送方案，從而節(jié)省人力成本、物力成本、時間成本，進(jìn)行資源的合理配置。