基于遺傳算法的快遞配送路徑優(yōu)化問題研究

楊粟涵　于蕾

摘? 要：以數(shù)字型基礎(chǔ)設(shè)施為代表的“新基建”目前處在起步階段，面對經(jīng)濟(jì)下行的壓力，夯實(shí)物流產(chǎn)業(yè)基礎(chǔ)，可合理規(guī)劃配送路線來提高物流配送效率。以合肥市某知名快遞企業(yè)配送路徑優(yōu)化問題為研究對象，分析該企業(yè)配送問題，建立以配送網(wǎng)絡(luò)成本最小為優(yōu)化目標(biāo)的數(shù)學(xué)模型，采用基本遺傳算法的流程為模型設(shè)計算法，仿真運(yùn)行得出結(jié)論。

關(guān)鍵詞：配送路徑;遺傳算法;優(yōu)化模型

中圖分類號：TP18;F252? ? ? ?文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2020）09-0099-03

Research on Optimization of Express Delivery Route Based on Genetic Algorithm

YANG Suhan，YU Lei

（Hefei Technology College，Hefei? 230011，China）

Abstract：“New infrastructure” represented by digital infrastructure currently in its infancy. In face of economic downward pressure，laying solid foundation of logistics industry，a reasonable planning route can be distributed to improve the efficiency of logistics distribution. A famous express enterprises in Hefei distribution route optimization problem as the research object，analyzing the enterprise distribution problems，establishing a distribution network，and the mathematical model of objective function is minimum cost，using the basic process of genetic algorithm for the model to design algorithm，and simulation in order to draw the conclusion.

Keywords：delivery route;genetic algorithm;optimal model

0? 引? 言

電商產(chǎn)業(yè)的蓬勃興盛及O2O商業(yè)模式的不斷成熟，促進(jìn)了物流行業(yè)的飛速發(fā)展，物流業(yè)的發(fā)展程度已然成為衡量我國現(xiàn)代化程度的重要指標(biāo)之一。特別是目前新冠肺炎疫情時期，基于人工智能的物流網(wǎng)絡(luò)展現(xiàn)出驚人的效率，避免了災(zāi)難性的物資短缺。打贏疫情防控阻擊戰(zhàn)，物流產(chǎn)業(yè)基礎(chǔ)是重要因素，不僅依賴于物流快遞業(yè)的個體擔(dān)當(dāng)、企業(yè)情懷，也要依賴國家的產(chǎn)業(yè)支撐、政策扶持。面對日前經(jīng)濟(jì)下行的壓力，我國多次提出加快“新基建”、培育新動能，然而以數(shù)字型基礎(chǔ)設(shè)施為代表的“新基建”卻處在起步階段。因此加快“新基建”可以對沖疫情不利影響，為應(yīng)對經(jīng)濟(jì)下行壓力、推動高質(zhì)量發(fā)展提供著力點(diǎn)。

在物流行業(yè)的“最后一公里”物流配送環(huán)節(jié)上，數(shù)字化智能化水平不盡如人意，配送成本居高不下，而配送安全性和時效性又是影響客戶滿意度的重要因素，因此關(guān)于物流配送的路徑優(yōu)化問題一直受到不少學(xué)者的關(guān)注并取得一定成效。如趙娜研究餐飲領(lǐng)域的配送問題，設(shè)計配送路線，在車輛路徑優(yōu)化的基礎(chǔ)上加入時間窗，建立了VRPTW問題模型，并且設(shè)計遺傳算法進(jìn)行優(yōu)化求解[1];詹斌等借助云計算和大數(shù)據(jù)對電商物流末端配送進(jìn)行分析，提出可視化配送服務(wù)一系列創(chuàng)新思路[2];涂漢江針對TSP問題（Travelling Salesman Problem）對外賣配送路徑優(yōu)化進(jìn)行建模，用分支限界法求解，建立一個外賣訂餐系統(tǒng)[3]。針對我市蜀山區(qū)某知名快遞企業(yè)的現(xiàn)狀，文章用遺傳算法研究其轄區(qū)配送路徑優(yōu)化問題。

1? 快遞企業(yè)配送路徑優(yōu)化問題分析

1.1? 問題描述

以安徽省合肥市蜀山區(qū)某知名快遞企業(yè)的直營站點(diǎn)配送路徑優(yōu)化為對象進(jìn)行研究。通過調(diào)研得知，該企業(yè)在蜀山區(qū)設(shè)1個配送中心、15個站點(diǎn)，主營業(yè)務(wù)范圍為末端配送，依據(jù)轄區(qū)顧客電子訂單的物品種類、規(guī)格、數(shù)量、時間、地點(diǎn)等顧客信息需求來進(jìn)行掃描、分類、裝卸搬運(yùn)、調(diào)度等，最終將物品送往各站點(diǎn)。由于該企業(yè)并未形成完善的配送體系網(wǎng)絡(luò)，物流裝備的標(biāo)準(zhǔn)化程度低，極大地影響了配送效率，并且合理配送計劃的缺乏造成配送成本虛高，因此亟需建立數(shù)字化智能化的物流網(wǎng)絡(luò)。

該企業(yè)的一個配送中心處在蜀山區(qū)各站點(diǎn)的中心區(qū)域，占地面積大，配送業(yè)務(wù)主要集中在各類網(wǎng)購的快遞包裹，并且具備一定數(shù)目的配送員和配送車輛，一名配送員駕駛一輛車給若干個站點(diǎn)送貨，每名配送員根據(jù)分配到的目標(biāo)執(zhí)行配送任務(wù)，且都是從配送中心出發(fā)，完成配送任務(wù)后返回配送中心。15個站點(diǎn)的門店分布不均，處在不同的地理位置，具有不同的經(jīng)營狀況，送貨時間和貨物需求量也不盡相同，所有物流點(diǎn)的地理位置和貨物需求量都是已知的，如表1所示。配送到達(dá)站點(diǎn)的停滯時間忽略不計，主要考慮的是配送過程所消耗的時間，配送員配送時也需要完成退貨等逆向物流貨物的處理，并且?guī)Щ嘏渌椭行?。各個配送員的工作內(nèi)容不交叉，可以看作是MTSP多旅行商問題（Multiple Traveling Salesman Problem）或者分成M個TSP問題[4]。

1.2? 模型建立