王旭坪，張珺，易彩玉
關鍵詞:
生產配送聯合調度,在線訂餐,多車多任務配送,三階段啟發式算法
摘要:
隨著聯通互聯網的普及和生活節奏的推動，網上訂餐因其獨有的方便性和多樣性，成為諸多下班族和中學生的新興生活形式。截至2021年末，我國網上外賣用戶規模達54416千人，環比下降29.92%。以“美團”為例，2021年餐飲外賣業務交易筆數144億筆，環比下降41.6%，外賣市場潛力巨大。在實際運作中，線下酒樓對外賣訂單的生產和配送環節常常分開調度，可使訂單所需生產時間和配送時間最短。但是，外賣送達時間由開始生產時間、生產時長，開始配送時間和配送時長等誘因共同決定；同時，外賣訂單信息提早未知、下單集中、配送地點分散等特性，致使外賣訂單延誤情況普遍。為此，有必要考慮外賣訂單相關特點，研究外賣訂單的生產和配送聯合調度問題。
本文研究問題屬于生產與配送聯合調度（and，IPDS）的一類特殊問題。根據Chen[1]對IPDS通用表達式的定義，本文研究問題可敘述為。圖1展示了外賣訂單履行過程示意圖：外賣訂單實時下達；生產調度為多個面點師的并行機生產；配送汽車數和車容量有限，屬于多車多任務汽車路徑問題（Multi-Trips，MTVRP）；客戶數有多個；目標函數為最小化所有訂單的服務時間跨徑之和。本文以所有訂單的服務時間跨徑之和為優化目標，建立并行機生產多車多任務配送聯合優化物理模型。所需決策關鍵問題：（1）開始生產已下達的訂單還是繼續等待更多訂單下達；（2）對已下達訂單怎么委派給有限的面點師；（3）已完成的訂單怎樣生成配送批次及路徑；（4）配送批次怎樣分配給有限的汽車。
圖1.外賣訂單履行過程示意圖
本文建立三階段啟發式在線調度算法對模型進行求解。總體設計思路：基于配送區域界定的混和時間窗分批策略對實時訂單進行分批；同一批次內訂單連續安排生產；將生產完批次委派配送汽車，并用遺傳算法進行路徑優化。采用數值實驗將本文算法與傳統生產配送在線調度算法進行對比剖析。研究表明：（1）當訂單抵達率很小，飯店生產和配送能力充足時，可采用傳統生產配送在線調度算法進行次序調度；當訂單抵達率較大，飯店生產和配送能力受限制網上外賣訂餐系統，適合采用三階段啟發式在線調度算法進行聯合調度。（2）隨著的減小，三階段啟發式在線調度算法對服務時間跨徑之和的改進幅度越來越大。（3）三階段啟發式在線調度算法優勢在于減短配送時間和配送等待時間網上外賣訂餐系統，劣勢在于引起了訂單批次生成之前生產能力的空閑。（4）隨著的減小，三階段啟發式在線調度算法的劣勢漸漸減小，同時對于配送時間和配送等待時間的改進幅度也平緩減少。
本文構建模型及設計算法對網上訂餐平臺進行外賣訂單調度具有較大應用價值，尤其適用于訂單抵達率較高的外賣場景。生成的訂單生產配送調度方案能幫助飯店優化生產配送資源，節省配送成本，提升配送效率。隨著電子商務新業態的迅猛發展，網上商場、網購花束等新興訂單履行場景也符合生產配送在線聯合調度問題的特點，本文構建的模型和算法同樣適用于解決電商新業態中的訂單履行問題。
基金捐助:
國家自然科學基金項目（，，，）
文章刊發:
《系統管理學報》2020,29(01):159-167.
作者介紹
免責聲明：部分文章信息來源于網絡以及網友投稿，本站只負責對文章進行整理、排版、編輯，出于傳遞更多信息之目的，并不意味著贊同其觀點或證實其內容的真實性，如本站文章和轉稿涉及版權等問題，請作者在及時聯系本站，我們會盡快為您處理。
