“最后一公里”路徑規(guī)劃模型研究

鄧宇　徐靖翔　劉玉婷

摘要：末端物流配送主要是以學(xué)校、住宅區(qū)、辦公寫字樓為主要場景，當(dāng)前物流配送沒有系統(tǒng)地對路徑進(jìn)行規(guī)劃，配送期長，導(dǎo)致無法高效對客戶進(jìn)行服務(wù)。首先通過利用單機(jī)模型模擬單個(gè)快遞員的工作流程，以最小化配送時(shí)間為目標(biāo)建立路徑規(guī)劃模型，然后采集成都市某配送中心的數(shù)據(jù)，接著使用遺傳算法求解，驗(yàn)證了模型的有效性。

關(guān)鍵詞：最后一公里;快遞派送;路徑規(guī)劃模型

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）09-0279-02

1 引言

城市中的學(xué)校、住宅區(qū)、辦公區(qū)域相對集中，從四面八方而來的快遞首先送達(dá)當(dāng)?shù)氐目爝f集散中心，為了運(yùn)輸車輛的通行方便，集散點(diǎn)一般設(shè)立在城市的郊區(qū)，而“最后一公里”的實(shí)現(xiàn)途徑則需要通過快遞員的配送來實(shí)現(xiàn)門到門的服務(wù)。隨著快遞的發(fā)展，同城即時(shí)配送逐漸興起，客戶對商品派送時(shí)間的要求也越來越高，既要保證物品不損壞，又要保證準(zhǔn)時(shí)送達(dá)，因此，配送順序和路徑就顯得尤為重要[1]。

在產(chǎn)業(yè)界，目前的快遞配送業(yè)務(wù)呈現(xiàn)出粗放式擴(kuò)張的特點(diǎn)，現(xiàn)代路徑規(guī)劃方法遠(yuǎn)未得到有效而深入的應(yīng)用。通過配送車輛路徑的規(guī)劃，實(shí)現(xiàn)低成本、高效率、集約化的配送服務(wù)是每一個(gè)配送公司都難以逾越、且影響到其生死存亡的關(guān)鍵問題。該問題的研究無論對于單個(gè)配送公司的降本增效，還是整個(gè)社會(huì)的即時(shí)配送水平的提高，乃至現(xiàn)代電子商務(wù)的持續(xù)健康發(fā)展都具有重要的現(xiàn)實(shí)意義[2]。

然而，理論界現(xiàn)有的研究成果，在面對四散分布的菜鳥驛站，郵箱，以及具體小區(qū)的門牌，要想做到快速、低成本的即時(shí)配送也絕非易事。該問題具有傳統(tǒng)的長時(shí)間送達(dá)的物流所無法比擬的復(fù)雜性與特殊性，具體體現(xiàn)在：①問題的動(dòng)態(tài)性與時(shí)間緊迫性極強(qiáng);②每一訂單都有包裹放置地點(diǎn)的要求（如：某菜鳥驛站，某小區(qū)，某郵箱，某具體門牌號(hào)）;③快件有大小之分，配送車輛的大小，如何合理的規(guī)劃每次配送的貨物會(huì)對配送時(shí)間有影響;④各個(gè)快遞的送達(dá)時(shí)間，以及在之前配送中用去的時(shí)間，也將影響每個(gè)物件配送的順序[3]。

為此，本文在綜述理論界已有相關(guān)研究的基礎(chǔ)上，根據(jù)“最后一公里”配送問題的特點(diǎn)，針對不同客戶不同的配送需求會(huì)增加配送員的往返次數(shù)，降低效率的問題，合理考慮時(shí)間、距離等因素，通過對配送路線的合理規(guī)劃，來減少配送員的配送用時(shí)。提出一種最小化配送時(shí)間的路徑規(guī)劃模型，并運(yùn)用成都市某配送中心的真實(shí)數(shù)據(jù)，對提出的模型進(jìn)行模擬仿真。

2 問題描述

隨著社會(huì)經(jīng)濟(jì)的飛速發(fā)展，物流運(yùn)輸?shù)膹?qiáng)度和效率就顯得格外重要。車輛運(yùn)輸?shù)姆绞?、成本很難在短時(shí)間內(nèi)優(yōu)化，因此最簡單減少運(yùn)輸成本的方式就是對快遞員派件進(jìn)行規(guī)劃。由于當(dāng)前的物流末端配送點(diǎn)主要設(shè)置在人口聚集處，因此就會(huì)導(dǎo)致因未對當(dāng)?shù)匚锪髋渌瓦M(jìn)行路線優(yōu)化而導(dǎo)致的快遞運(yùn)輸配送期長，無法高效對客戶進(jìn)行配送服務(wù)等物流問題。

2.1 模型假設(shè)

假設(shè)一：車輛速度恒定，不考慮路況，紅綠燈影響。假設(shè)二：配送區(qū)域范圍固定。假設(shè)三：一個(gè)區(qū)域有一位快遞員配送。假設(shè)四：即送即走，無須等待。

2.2 基于α/β/γ三元組描述模型

α域：本文研究的調(diào)度問題機(jī)器環(huán)境為單機(jī)問題，單一派送員上按順序。個(gè)訂單，每個(gè)客戶的地理位置已知。β域：配送員應(yīng)該在客戶要求的時(shí)間窗內(nèi)進(jìn)行完成派送。γ域：目標(biāo)函數(shù)為最短配送時(shí)間。

3 建立“最后一公里”調(diào)度規(guī)劃模型

3.1 符號(hào)說明

3.2 模型建立

以最小化為：

（1）為目標(biāo)函數(shù)，表示最短配送時(shí)間，（2）一（3）保證每個(gè)派送點(diǎn)僅被服務(wù)一次;式（4）一（5）表示車輛從末端配送中心出發(fā)最后到達(dá)配送中心。

4 數(shù)值算例

4.1數(shù)據(jù)收集

以成都市某順豐速運(yùn)的到戶配送為例進(jìn)行仿真實(shí)驗(yàn)，收集該配送中心2019年12月27日的到戶配送信息，包括：配送地點(diǎn)，配送交貨期。在對數(shù)據(jù)進(jìn)行預(yù)處理之后，得到各配送點(diǎn)之間的距離，以及各客戶要求的時(shí)間窗，某位快遞員的數(shù)據(jù)如表1所示：

4.2 基于遺傳算法求解算例

遺產(chǎn)算法是一種通過模擬種群的進(jìn)化過程搜索最優(yōu)解的啟發(fā)式算法，借助遺傳算子進(jìn)行交叉、變異等操作機(jī)制，在經(jīng)過迭代后得到最優(yōu)或近似最優(yōu)解。本文選取遺傳算法求解模型。

4.2.1 染色體編碼

本文將染色體定義為由快遞員的配送路徑，基因用十六進(jìn)制與二進(jìn)制編碼，用0表示配送中心，用1-9與A-F表示客戶，客戶后接的數(shù)字0與1表示客戶的實(shí)時(shí)位置。如染色體“0 A120 91 31 0”中，“0 A120 91310”代表快遞員的配送路徑為0-10-2-9-3-4-0。

4.2.2 適應(yīng)度函數(shù)

個(gè)體的適應(yīng)度是指種群中個(gè)體對環(huán)境的適應(yīng)能力，可由適應(yīng)度函數(shù)來評(píng)估。個(gè)體的適應(yīng)度越高，則表示個(gè)體越能在環(huán)境中生存下來并進(jìn)行繁殖。本研究目標(biāo)是最小化快遞員的配送里程。

4.2.3 求解結(jié)果

求解得到以下排序：金林俊景、麗景華庭、西藏花園、紅運(yùn)花園、晉陽社區(qū)、成都花園、綠城花園、雙景秀庭、龍文教育。與實(shí)際配送路徑比較，優(yōu)化后的配送路徑使用的時(shí)間更少。

5 總結(jié)

快遞作為服務(wù)行業(yè)，在考慮運(yùn)輸成本的同時(shí)，更需要注重客戶的滿意程度，在客戶規(guī)定的時(shí)間窗內(nèi)送達(dá)。本文以單個(gè)派送員的配送為研究目標(biāo)，建立最小化配送時(shí)間的路徑規(guī)劃模型，并以真實(shí)數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了模型的有效性，為“最后一公里”路徑規(guī)劃研究提供了新思路。

參考文獻(xiàn)：

[1]王征，李婷玉，岳彩凡.同城即時(shí)配送問題基于多預(yù)測場景的在線調(diào)度[J].系統(tǒng)工程理論與實(shí)踐，2018，38（12）：3197-3211.

[2]王旭坪，詹林敏，張珺，考慮碳稅的電子商務(wù)物流最后一公里不同配送模式的成本研究[Jl.系統(tǒng)管理學(xué)報(bào)，2018，27（4）：776-782.

[3）楊鑰，李樹雪，劉玉利.“最后一公里”校園物流配送平臺(tái)系統(tǒng)設(shè)計(jì)[J].電腦知識(shí)與技術(shù)，2019，15 （21）：278-279.

【通聯(lián)編輯：光文玲】