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

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

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

■ 模型的建立

（一）基本假設(shè)

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

（二）符號(hào)的定義

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

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

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

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

Step3.滿(mǎn)足的約束條件為：

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

■ 模型的求解

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

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

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

2.需求量的確定

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

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

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

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

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

該時(shí)間段的最佳配送方案見(jiàn)表1。

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

■ 模型的改進(jìn)

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

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

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

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

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

■ 總結(jié)

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