基于變鄰域搜索算法的物流配送系統(tǒng)集成優(yōu)化研究

孫 琦戢守峰劉 旭

1（東北大學(xué)，沈陽 110169）2（國(guó)網(wǎng)遼陽供電公司，遼陽 110099）

基于變鄰域搜索算法的物流配送系統(tǒng)集成優(yōu)化研究

孫 琦1戢守峰1劉 旭2

1（東北大學(xué)，沈陽 110169）2（國(guó)網(wǎng)遼陽供電公司，遼陽 110099）

本文針對(duì)物流配送系統(tǒng)集成優(yōu)化問題，考慮取貨和送貨兩種業(yè)務(wù)的配送情形下倉庫和車輛的容量上限約束，構(gòu)建包括倉庫的開放成本、配送成本以及容量溢出成本的非線性混合整數(shù)優(yōu)化模型，設(shè)計(jì)變鄰域搜索啟發(fā)式算法對(duì)模型進(jìn)行求解。算法通過泰森多邊形確定位置上的初始訂單分配，再通過掃描半徑及消費(fèi)者數(shù)據(jù)結(jié)構(gòu)標(biāo)識(shí)實(shí)現(xiàn)鄰域搜索，改進(jìn)算法對(duì)解決方案進(jìn)行迭代更新，完成優(yōu)化求解。最后通過對(duì)遼寧宅急送取/送一體化物流配送案例進(jìn)行數(shù)值分析，驗(yàn)證算法可行性和有效性。

變鄰域搜索算法 取貨和送貨 非線性混合整數(shù)優(yōu)化模型 集成優(yōu)化

引 言

“互聯(lián)網(wǎng)+流通”促使物流行業(yè)系統(tǒng)升級(jí)，一地多倉和異地多倉問題日益凸顯，行業(yè)發(fā)展具有新模式和新特點(diǎn)，如京東、當(dāng)當(dāng)?shù)葹樘嵘?wù)水平自建配送系統(tǒng)，既為消費(fèi)者提供配送服務(wù)，又要滿足售后退貨的收取服務(wù)。物流系統(tǒng)優(yōu)化問題亟待解決，以滿足新時(shí)代的行業(yè)需求。物流系統(tǒng)的位置/路徑集成優(yōu)化問題研究大體可以分為3個(gè)階段：基礎(chǔ)的車輛/路徑問題 （Vehicle-Routing Problems，VRP）源自Dantzig等 （1959）的研究，即配送中心為規(guī)模有限而需求量不同的消費(fèi)者提供配送服務(wù) ，滿足一定假設(shè)約束情況下對(duì)有限的配送車輛進(jìn)行訂單分配及路徑規(guī)劃［1］；傳統(tǒng)的位置/配給問題 （Location-Allocation Problems，LAP）首次由Cooper（1963）提出，即依據(jù)消費(fèi)者的配送量和交付地點(diǎn)的位置分布關(guān)系，規(guī)劃得出配送區(qū)域內(nèi)配送站的位置和數(shù)量規(guī)模［2］；近代消費(fèi)模式的發(fā)展促使位置/路徑問題 （Location-Routing Problems，LRP）的研究日益顯現(xiàn)［3］。如Marinakis （2015）考慮了3種不同的拓?fù)浣Y(jié)構(gòu)改進(jìn)粒子群算法優(yōu)化求解隨機(jī)需求下固定容量的位置路徑問題［4］；Macedo等 （2015）指出構(gòu)建倉庫開放、配送路徑和車輛調(diào)度的集成問題總成本優(yōu)化模型，并闡明和標(biāo)準(zhǔn)LRP的主要區(qū)別是：每部配送車輛是否可以分配多條路徑 ，即車輛和路徑之間是否存在一一對(duì)應(yīng)的關(guān)系［5］；Torfi等 （2015）針對(duì)包含工廠、倉庫和客戶的三層位置路徑集成問題提出采用梯形模糊數(shù)來確定評(píng)價(jià)標(biāo)準(zhǔn)的相對(duì)權(quán)重，通過工廠和中央倉庫的位置選擇和客戶訂單的分配規(guī)劃，減少物流網(wǎng)絡(luò)總成本［6］；Vincent等（2014）提出一種改進(jìn)的模擬退火算法求解開放位置路徑問題，并通過數(shù)值算例證明改進(jìn)算法比CPLEX在求解質(zhì)量和求解時(shí)間方面表現(xiàn)更優(yōu)［7］。Nagy等 （2005）對(duì)經(jīng)典車輛路徑問題進(jìn)行擴(kuò)展，考慮客戶取貨和送貨情況下的單一倉庫和多倉庫集成模型 （Vehicle Routing Problem with Pickups and Deliveries，VRP-PD），并用交替啟發(fā)式算法進(jìn)行了近似求解［8］；Polat等 （2015）基于擾動(dòng)的鄰域搜索算法求解VRP-PD問題［9］；Wang等 （2015）指出帶時(shí)間窗的取貨和送貨車輛路徑問題 （VRPSPDTW）為NP-hard問題 ，并用p-SA元啟發(fā)式算法求解［10］；Liu等 （2013）構(gòu)建醫(yī)療系統(tǒng)的車輛路徑物流調(diào)度模型 ，設(shè)計(jì)兩個(gè)元啟發(fā)算法 （禁忌搜索和遺傳算法）進(jìn)行求解，配送系統(tǒng)總成本得到優(yōu)化［11］；Li等 （2015）設(shè)計(jì)自適應(yīng)鄰域搜索算法求解同時(shí)取貨和送貨的多倉庫車輛路徑問題［12］。

近年，國(guó)內(nèi)學(xué)者對(duì)物流配送系統(tǒng)集成問題也做出探索。如李群霞等 （2015）研究了二級(jí)供應(yīng)鏈聯(lián)合優(yōu)化問題，并設(shè)計(jì)了解決方案［13］。唐金環(huán)等 （2015）考慮時(shí)間和碳排放約束下的車輛路徑優(yōu)化問題，構(gòu)建了非線性混合整數(shù)規(guī)劃模型，并用粒子群算法對(duì)物流配送系統(tǒng)進(jìn)行決策求解［14］；唐金環(huán)等 （2014）設(shè)計(jì)BFA-PSO算法求解選址——路徑——庫存集成問題［15］；李富昌 （2016）研究了庫存運(yùn)輸聯(lián)合優(yōu)化模型，決策中心聯(lián)合做出訂貨量、零售價(jià)和營(yíng)銷成本的決策，再給出庫存運(yùn)輸聯(lián)合優(yōu)化最優(yōu)策略的求解方法［16］；王超等（2014）提出模擬退火算法求解帶時(shí)間窗的取貨和送貨車輛路徑問題 （VRPSPDTW）［17］。

綜上所述 ，迄今為止的研究表明：對(duì)于車輛路徑經(jīng)典問題的研究，隨著時(shí)代發(fā)展具有新的特點(diǎn)；VRP問題的研究成果日益顯現(xiàn)，而對(duì)于LRP問題擴(kuò)展成果還很鮮見；車輛位置路徑問題往往采用啟發(fā)式算法進(jìn)行求解，對(duì)于智能算法的研究有待豐富。本文在LRP問題基礎(chǔ)上進(jìn)行擴(kuò)展，考慮取/送一體化的訂單分配與物流配送集成優(yōu)化問題 （Location Routing Problem with Pickups and Deliveries，LRP-PD）模型構(gòu)建，并設(shè)計(jì)啟發(fā)式算法進(jìn)行求解。

1 問題描述與符號(hào)說明

1.1 問題描述

LRP-PD可抽象為一個(gè)完全有向圖G=｛N，E｜Nw∈N，Np∈N，Nd∈N；｛i→j｝∈E｝，其中Nw表示已知庫存容量的倉庫結(jié)點(diǎn)，需求不確定的消費(fèi)者分為兩類結(jié)點(diǎn)Np表示取貨消費(fèi)者結(jié)點(diǎn)，Nd表示送貨消費(fèi)者結(jié)點(diǎn)；車輛結(jié)點(diǎn)M=｛Mp，Md｝。集成配送系統(tǒng)中，每個(gè)車輛完成取貨和送貨服務(wù)之后，返回到相同的開放倉庫。消費(fèi)者在一個(gè)訂單周期內(nèi)僅分配一輛車提供服務(wù)，車輛完成服務(wù)后返回倉庫。決策者對(duì)集成配送系統(tǒng)進(jìn)行優(yōu)化時(shí)，需選擇開放哪些倉庫，確定車輛的配送路徑，以降低整個(gè)系統(tǒng)的運(yùn)作成本。

一般情況下，消費(fèi)者需求是不確定的，決策者為配送系統(tǒng)預(yù)先設(shè)計(jì)先驗(yàn)路線方案，以便選擇最佳配送路線降低成本 ，而車輛容量是決定規(guī)劃方案中路線數(shù)量的主要因素。消費(fèi)者隨機(jī)需求符合泊松分布特征，因此將取貨和送貨的先驗(yàn)路線方案分別表示為兩組時(shí)間序列：θ=｛θ0，θ1，θ2，…，θκ，… ，θn，θ0｝和θ=｛θ0，θ1，θ2，…，θκ，…，θn，θ0｝，其中θκ表示組成配送路徑結(jié)點(diǎn)的時(shí)間序列結(jié)點(diǎn)，車輛從初始開放倉庫θ0=n出發(fā)，最后返回起點(diǎn)倉庫交車。為了簡(jiǎn)化問題 ，定義v和v為消費(fèi)者隨機(jī)需求變量產(chǎn)生的貨物容量，參數(shù)λp和λd分別為取貨和送貨上限概率，即P（v＞V）≤λp和P（v＞V）≤λd。消費(fèi)者取/送貨物β的均值路徑序列｛μ，μ，… ，μ｝和｛μ，μ，… ，μ｝，則v和v的均值分別為

1.2 符號(hào)與參數(shù)

模型中所用參數(shù)變量和決策變量總結(jié)如表1：

表1 符號(hào)說明

2 成本優(yōu)化數(shù)學(xué)模型

系統(tǒng)優(yōu)化的目標(biāo)是總成本最小化。本文將集成系統(tǒng)的總成本模型分解為3個(gè)子問題進(jìn)行構(gòu)建：倉庫開放成本，配送運(yùn)輸成本和容量損失成本。系統(tǒng)優(yōu)化的數(shù)據(jù)結(jié)構(gòu)表示為：LRP-PD=｛xw，yiw，z｜C｝。隨機(jī)需求到達(dá)后，系統(tǒng)根據(jù)消費(fèi)者總需求情況進(jìn)行訂單分配，規(guī)劃配送倉庫完成訂單交付，產(chǎn)生倉庫運(yùn)營(yíng)成本。而配送運(yùn)輸成本和容量損失成本之間存在交集，因此將容量損失過程分為車輛運(yùn)輸容量溢出和倉庫容量溢出。

2.1 配送運(yùn)輸成本

由于消費(fèi)者需求是不確定的，當(dāng)發(fā)貨需求相對(duì)車輛固定容量溢出時(shí)，每輛車遍歷消費(fèi)者結(jié)點(diǎn)數(shù)受取貨上限概率約束。取貨配送路徑θκ上，容量溢出結(jié)點(diǎn)的數(shù)量小于等于1時(shí)，單輛車取貨容量溢出成本。其中C和C分別表示取貨時(shí)車輛容量溢出，車輛從倉庫n到溢出點(diǎn)θκ之間的往返成本。進(jìn)一步地，得到所有車輛整條取貨路徑上發(fā)生容量溢出的預(yù)期成本；同理 ，可推導(dǎo)出配送系統(tǒng)送貨過程的容量溢出成本。

2.2 倉庫容量溢出成本

由于需求的不確定性，倉庫發(fā)生容量溢出的情況可能存在，一旦這種情況發(fā)生，物流配送系統(tǒng)就會(huì)產(chǎn)生額外轉(zhuǎn)運(yùn)成本。貨物β存入倉庫每超出一單位容量記為ρ，產(chǎn)生額外處理倉庫存儲(chǔ)過剩的單位成本cβ。由此，得到倉庫溢出成本：

其中，任何一類貨物β對(duì)于倉庫w存在一個(gè)超過倉庫容量的概率，消費(fèi)者需求是一個(gè)隨機(jī)變量，同時(shí)每單位產(chǎn)生額外倉庫容量溢出費(fèi)cβ。進(jìn)而得到每批貨物β的所有預(yù)期倉庫容量溢出成本總額。

2.3 配送集成系統(tǒng)的非線性混合整數(shù)規(guī)劃模型綜上，成本優(yōu)化數(shù)學(xué)模型表示為：

其中，式 （1）是考慮取貨和送貨一體化的物流配送集成系統(tǒng)優(yōu)化的目標(biāo)函數(shù)，等式右邊求和分量分別表示倉庫運(yùn)營(yíng)成本、路徑運(yùn)輸成本、車輛取貨固定成本、車輛送貨固定成本、取貨車輛容量溢出成本、送貨車輛容量溢出成本、取貨造成的倉庫容量溢出成本和送貨造成的倉庫容量溢出成本。

約束部分：由于每位消費(fèi)者需求的不確定性，取貨和送貨車輛荷載的概率分別不超過車輛容量上限概率λp和λd，得到式 （2）和式 （3）的車輛容量約束。式 （4）和式 （5）確保每位消費(fèi)者都被規(guī)劃一條配送路徑，并且只有一個(gè)前端配送路徑結(jié)點(diǎn)。式 （6）～式 （9）表示每條路徑連續(xù)性的約束 ，保持起止倉庫為同一倉庫。式 （10）和式（11）表示消除子回路。式 （12）和式 （13）表示路徑上的倉庫是開放的 ，可進(jìn)行訂單分配滿足消費(fèi)者需求。式 （14）～式 （16）表示決策變量為0 ～1變量。

綜上所述，LRP-PD是LAP和VRP的組合變體，二者均為NP-hard，因此LRP-PD也是一個(gè)NP-hard問題。然而，由于其涉及 FLP、VRP、不確定需求和取/送貨路線的物流配送系統(tǒng)集成問題，使得LRP-PD更為復(fù)雜。本文針對(duì)這一問題，提出一種近似求解的啟發(fā)式算法。

3 變鄰域搜索算法過程設(shè)計(jì)

以遼寧宅急送在一個(gè)訂單周期內(nèi)15個(gè)配送倉庫構(gòu)成的取/送一體化物流配送系統(tǒng)為研究案例，優(yōu)化流程如圖1所示。將LRP-PD分解成3個(gè)子問題：倉庫分配問題，訂單分配問題和車輛路徑規(guī)劃問題。倉庫開放后，分配消費(fèi)者訂單，確定車輛配送路徑。下面研究各個(gè)子問題的解決方案如下。

3.1 倉庫分配

圖1 取/送一體化物流配送系統(tǒng)集成優(yōu)化過程圖

首先需要確定開放倉庫的數(shù)量。對(duì)于傳統(tǒng)的LRP問題，根據(jù)消費(fèi)者總需求可估算出開放倉庫的數(shù)量，而本文研究的是消費(fèi)者需求不確定情形。一般情況，總?cè)?送貨容量超出的配送系統(tǒng)容量上限時(shí)，額外增加倉庫容量溢出成本，因此有必要分配更多的倉庫。另一方面，倉庫和車輛未被利用的容量增加了機(jī)會(huì)損失成本，開放倉庫的數(shù)量越少則成本越低。為解決這個(gè)問題，引入?yún)?shù)γpβ和γdβ分別表示取/送貨物β時(shí)，配送系統(tǒng)分配的倉庫數(shù)量；ξpβ和ξdβ表示所有需要取/送貨物β的隨機(jī)需求。配送系統(tǒng)分配的開放倉庫數(shù)量κpβ和κdβ取值范圍受到倉庫容量上限概率常量λw及倉庫平均容量Vw的限制，即對(duì)貨物β的最低配送量P （ξpβ＞Vwgγpβ）≤λw和P（ξdβ＞Vwgγdβ）≤λw。配送貨物的數(shù)量按容量大小分類記為η，記配送系統(tǒng)開放倉庫κ=max｛κp1，κd1，κp2，κd2，… ，κpη，κdη｝是最優(yōu)解集中的最大值，開放倉庫的數(shù)量應(yīng)該在κ值附近。

如圖1（a）所示，初始種群集合（w1，w3，w6，w10）為開放倉庫的初始解，確定開放的倉庫數(shù)量及初始值。如果w3被w8代替，開放倉庫更新分配為（w1，w8，w6，w10）。為了搜索到更好的開放倉庫組合，確定倉庫替換算子為兩個(gè)倉庫之間位置距離相等的倉庫。替換算子可以替代產(chǎn)生得到兩個(gè)分組。例如，圖中的倉庫w9位于與w3和w10等距點(diǎn)，所以它可以代替這兩組，即（w1，w9，w6，w10）和（w1，w3，w6，w9）是解決方案過程中開放倉庫組合的一個(gè)有效組合。

3.2 訂單分配

一般情況，開放的倉庫可以為與其距離相對(duì)最近的客戶提供較好的服務(wù)，運(yùn)輸成本相對(duì)較低。消費(fèi)者收貨過程需得到一個(gè)開放倉庫提供的服務(wù)，LRP-PD可視為一個(gè)集合覆蓋問題。

初始分配能夠把客戶分成s組，而容量和運(yùn)輸路徑的約束會(huì)使訂單分配情況改變。因此，依據(jù)模型特點(diǎn)設(shè)計(jì)更新方法如下：消費(fèi)者被分為兩個(gè)集群，即靠近倉庫集和遠(yuǎn)離倉庫集。如果一個(gè)消費(fèi)者到一個(gè)倉庫的距離小于r，則分配和初始分配保持不變，被稱為分配確定；否則，消費(fèi)者被標(biāo)記為分配不確定，這意味著它的分配是可以改變的。圖1（b）說明了分配確定和分配不確定組的邊界。因此，當(dāng)搜索半徑越小的時(shí)候，更多的分配不確定的消費(fèi)者會(huì)出現(xiàn)，這會(huì)使自由度和解域更大。更新算子通過調(diào)整訂單分配，使模型滿足倉庫容量約束，相對(duì)擴(kuò)大搜索解域的范圍。

3.3 車輛路徑分配

由于車輛訂單交付地點(diǎn)具有散亂性，本文改進(jìn)變鄰域搜索 （Variable Neighborhood Search，VNS）算法以解決VRP。Mladenovic＇等人 （1997）提出的變鄰域搜索是一種用于優(yōu)化求解的鄰域搜索元啟發(fā)式算法［20］。Jarboui等 （2013）［21］，Hemmelmayr 等 （2015）［22］和Coelho等 （2015）［23］研究并擴(kuò)展了變鄰域搜索求解位置路徑問題，改進(jìn)鄰域搜索規(guī)則使得搜索過程盡可能高效地靠近解域。

圖1（c）顯示了標(biāo)記為w3、w6、w10和w12的4個(gè)開放倉庫的擬解決方案。每個(gè)倉庫標(biāo)記兩列標(biāo)識(shí)：左列為需取貨消費(fèi)者，右列為需送貨消費(fèi)者。數(shù)字標(biāo)記車輛的配送服務(wù)順序，進(jìn)而形成配送路徑。根據(jù)車輛的容量約束，如前文所述，訂單分配確定消費(fèi)者集合是不變的；不確定消費(fèi)者可以被任何倉庫提供服務(wù)。因此，在本文中構(gòu)建了一個(gè)初始的解決方案，通過在分配倉庫的數(shù)字序列中插入分配確定消費(fèi)者來表示；同時(shí)隨機(jī)插入分配不確定消費(fèi)者到任意的序列中。

引入短期記憶數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)鄰域搜索半徑r的控制，避免指針?biāo)阉饕苿?dòng)到一個(gè)循環(huán)周期內(nèi)已經(jīng)訪問過的解決方案。同時(shí)，設(shè)計(jì)一個(gè)中長(zhǎng)期記憶的數(shù)據(jù)結(jié)構(gòu)，即一個(gè)線性鏈表，為實(shí)現(xiàn)搜索空間更靠近最優(yōu)可行領(lǐng)域，標(biāo)記不可行鄰域，提高效率。在解鄰域搜索中，本文的改進(jìn)算法引入交換和移動(dòng)算子：交換算子，即在同一個(gè)操作 （取貨/送貨）下，兩個(gè)消費(fèi)者結(jié)點(diǎn)的交換，一個(gè)分配確定的消費(fèi)者不能與屬于不同倉庫的消費(fèi)者交換，則只有分配不確定消費(fèi)者可以在不同的倉庫之間進(jìn)行交換；移動(dòng)算子，即一個(gè)消費(fèi)者訂單從當(dāng)前位置轉(zhuǎn)移到另一個(gè)位置。只有分配到不確定消費(fèi)者的訂單才允許移動(dòng)到當(dāng)前序列外的位置 ，則分配確定消費(fèi)者的訂單只能在當(dāng)前序列中移動(dòng)。

圖2描述改進(jìn)的鄰域搜索算法實(shí)現(xiàn)流程圖。由配送量下界確定初始開放倉庫的數(shù)量，進(jìn)而確定初始解決方案，即搜索的起始集，通過交換算子和移動(dòng)算子擴(kuò)大搜索域。κ=max｛κp1，κd1，κp2，κd2，…，κpη，κdη｝是對(duì)解決方案的放松，因此倉庫的數(shù)量可能被放大。在流程圖中，為了獲得開放倉庫的最佳數(shù)量，求解過程被執(zhí)行κ-1次，直到無可行的解決方案。

4 實(shí)驗(yàn)結(jié)果

案例配送系統(tǒng)架構(gòu)如圖3所示，實(shí)驗(yàn)平臺(tái)Matlab6.0。隨機(jī)抽取100個(gè)消費(fèi)者訂單樣本，成本參數(shù)范圍：Cw∶U［2000，8000］，w∈［1，15］，C～U［200，500］，C～U［200，500］，C～U［0，5000］，C～U［0，500］；容量范圍：V～U［10t，30t］，V～U［20t，50t］，V～U［0，5t］，V～U［0，5t］。

圖2 集成系統(tǒng)優(yōu)化的鄰域搜索算法流程圖

圖3 宅急送系統(tǒng)功能模塊圖

由于各子倉庫分布在省內(nèi)各地，倉庫開放成本受當(dāng)?shù)亟?jīng)濟(jì)因素影響呈現(xiàn)均勻分布，具有梯度變化，如表2所示。

表2 消費(fèi)者規(guī)模與倉庫開放成本變化梯度表 元

配送車輛按照載重與耗油量特征，分為大型車、中型車和小型車。為更好滿足消費(fèi)者訂單需求，充分利用已有數(shù)據(jù)資源，提高配送系統(tǒng)集成優(yōu)化程度，依據(jù)訂單樣本密集程度選擇車輛類型。路徑優(yōu)化結(jié)果如圖4所示。

圖4 訂單樣本配送路徑優(yōu)化結(jié)果

由圖4（a）可見，經(jīng)過有限次的迭代，變鄰域搜索得到最優(yōu)的訂單分配路線。圖4（b）所示當(dāng)前最優(yōu)解值靠近最優(yōu)解。

將樣本集進(jìn)行4種情形優(yōu)化效果對(duì)比，如表3所示，以測(cè)試本文改進(jìn)的變鄰域搜索算法。對(duì)比樣本集合在沒有考慮集成優(yōu)化、單一倉庫分配成本優(yōu)化、倉庫——訂單分配集成及倉庫——訂單——路徑集成情況下，運(yùn)作總成本、誤差率和運(yùn)行時(shí)間的差異隨著模型復(fù)雜度增加，運(yùn)算時(shí)間增加及總成本降低程度明顯。

表3 算法測(cè)試情形設(shè)計(jì)

5 結(jié)束語

本文考慮了物流配送系統(tǒng)從訂單接收到訂單交付的整個(gè)運(yùn)營(yíng)過程，構(gòu)建了隨機(jī)需求下物流系統(tǒng)成本優(yōu)化模型。為優(yōu)化系統(tǒng)的總成本，模型從3個(gè)運(yùn)作階段進(jìn)行成本核算：倉庫開放過程，運(yùn)輸過程和容量損失過程，并對(duì)各子階段的運(yùn)營(yíng)成本進(jìn)一步細(xì)化建模。

配送集成系統(tǒng)優(yōu)化模型的求解過程分成以下步驟：（1）倉庫分配：確定集成系統(tǒng)分配倉庫的數(shù)量；（2）訂單分配：確定消費(fèi)者訂單配送的范圍；（3）車輛路徑分配：控制搜索半徑，對(duì)消費(fèi)者結(jié)點(diǎn)進(jìn)行變鄰域擴(kuò)充。數(shù)值案例的實(shí)驗(yàn)結(jié)果表明，通過有限次的迭代計(jì)算，系統(tǒng)總成本優(yōu)化顯著，節(jié)省成本約占未優(yōu)化成本的13%，充分證明了本文優(yōu)化模型的可行性和算法的有效性。

進(jìn)一步地，在模型構(gòu)建與求解中得到經(jīng)濟(jì)管理學(xué)啟示如下：（1）在數(shù)據(jù)資源日益豐富的環(huán)境下，企業(yè)對(duì)自建物流體系的優(yōu)化決策過程應(yīng)充分利用互聯(lián)網(wǎng)和智能技術(shù)降低運(yùn)營(yíng)成本，進(jìn)而提升物流行業(yè)的流通效率；（2）對(duì)復(fù)雜物流系統(tǒng)的優(yōu)化過程，采用適當(dāng)?shù)难芯渴侄芜M(jìn)行問題分解與集成，能夠?yàn)闆Q策者提供更精確的計(jì)算結(jié)果和更有價(jià)值的決策參考；（3）車輛和倉庫的容量動(dòng)態(tài)影響配送系統(tǒng)成本優(yōu)化，因此在實(shí)踐中挖掘有效的問題影響因素可以提升模型的優(yōu)化效果。

本文研究尚有改進(jìn)之處，如在未來研究中擴(kuò)大系統(tǒng)集成要素和問題規(guī)模，優(yōu)化預(yù)處理過程和算法設(shè)計(jì)過程，以提高算法的運(yùn)行時(shí)間和運(yùn)行精度。

［1］Dantzig G B，Ramser J H.The Truck Dispatching Problem ［J］.Management Science，1959，6（1）：80～91

［2］Cooper L.Location-allocation Problems ［J］.Operations Research，1963，11（3）：331～343

［3］Min H，Jayaraman V，Srivastava R.Combined Location-routing Problems：A Synthesis and Future Research Directions ［J］.European Journal of Operational Research，1998，108（1）：1～15

［4］Marinakis Y.An Improved Particle Swarm Optimization Algorithm for the Capacitated Location Routing Problem and for the Location Routing Problem with Stochastic Demands ［J］.Applied Soft Computing，2015，37（C）：680～701

［5］Macedo R，Alves C，Hanafi S，et al.Skewed General Variable Neighborhood Search for the Location Routing Scheduling Problem ［J］.Computers&Operations Research，2015，61：143～152

［6］Torfi F，F(xiàn)arahani R Z，Mahdavi I.Fuzzy MCDM for Weight of Object's Phrase in Location Routing Problem ［J］.Applied Mathematical Modelling，2016，40：526～541

［7］Vincent F Y，Lin S Y.A Simulated Annealing Heuristic for the Open Location-routing Problem ［J］.Computers&Operations Research，2015，62：184～196

［8］Macedo R，Alves C，Hanafi S，et al.Skewed General Variable Neighborhood Search for the Location Routing Scheduling Problem ［J］.Computers&Operations Research，2015，61：143～152

［8］Nagy G，Salhi S.Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries［J］.European Journal of Operational Research，2005，162（1）：126～141

［9］Polat O，Kalayci C B，Kulak O，et al.A Perturbation Based Variable Neighborhood Search Heuristic for Solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit［J］.European Journal of Operational Research，2015，242（2）：369～382

［10］Wang C，Mu D，Zhao F，et al.A Parallel Simulated Annealing Method for the Vehicle Routing Problem with Simultaneous Pickupdelivery and Time Windows［J］.Computers&Industrial Engineer－ing，2015，83：111～122

［11］Liu R，Xie X，Augusto V，et al.Heuristic Algorithms for a Vehicle Routing Problem with Simultaneous Delivery and Pickup and Time Windows in Home Health Care［J］.European Journal of Operational Research，2013，230（3）：475～486

［12］Li J，Pardalos P M，Sun H，et al.Iterated Local Search Embedded Adaptive Neighborhood Selection Approach for the Multi-depot Vehicle Routing Problem with Simultaneous Deliveries and Pickups ［J］.Expert Systems with Applications，2015，42（7）：3551～3561

［13］李群霞 ，馬風(fēng)才，張群.供應(yīng)鏈提前期供需聯(lián)合優(yōu)化庫存模型研究 ［J］.中國(guó)管理科學(xué)，2015，23（4）：117～122

［14］唐金環(huán) ，戢守峰，沈貴財(cái).時(shí)變網(wǎng)絡(luò)下考慮碳排放的車輛路徑優(yōu)化 ［J］.系統(tǒng)工程，2015，33（9）：37～44

［15］唐金環(huán) ，戢守峰 ，朱寶琳.考慮碳配額差值的選址-路徑-庫存集成問題優(yōu)化模型與算法 ［J］.中國(guó)管理科學(xué) ，2014，22（9）：114～122

［16］李富昌.考慮營(yíng)銷成本的庫存與運(yùn)輸聯(lián)合優(yōu)化三階段決策模型研究 ［J］.工業(yè)技術(shù)經(jīng)濟(jì)，2016，（2）：39～44

［17］王超，穆東.基于模擬退火算法求解VRPSPDTW問題 ［J］.系統(tǒng)仿真學(xué)報(bào) ，2014，26（11）：2618～2623

［18］郭慶軍，等.制造業(yè)與物流業(yè)種群生態(tài)系統(tǒng)協(xié)同演化實(shí)證研究 ［J］.工業(yè)技術(shù)經(jīng)濟(jì) ，2014，（7）：9～17

［19］Park S J，Cachon G P，Lai G，et al.Supply Chain Design and Carbon Penalty：Monopoly vs.Monopolistic Competition ［J］.Production and Operations Management，2015，24（9）：1494～1508

［20］Mladenovic＇N，Hansen P.Variable Neighborhood Search ［J］.Computers&Operations Research，1997，24（11）：1097～1100

［21］Jarboui B，Derbel H，Hanafi S，et al.Variable Neighborhood Search for Location Routing［J］.Computers&Operations Research，2013，40（1）：47～57

［22］Hemmelmayr V C.Sequential and Parallel Large Neighborhood Search Algorithms for the Periodic Location Routing Problem ［J］.European Journal of Operational Research，2015，243（1）：52～60

［23］Coelho I M，Munhoz P L A，Ochi L S，et al.An Integrated CPU-GPU Heuristic Inspired on Variable Neighbourhood Search for the Single Vehicle Routing Problem with Deliveries and Selective Pickups ［J］.International Journal of Production Research，2015：1～18

A Logistics System Integrated Optimization with Variable Neighborhood Search Algorithm

Sun Qi1Ji Shoufeng1Liu Xu2
（1.Northeastern University，Shenyang 110169，China；2.State Grid Liaoyang Electric Power Supply Company，Liaoyang 110099，China）

In order to optimize logistics integration system by the action plan for“Internet Plus Circulation”，a nonlinear mixed integer model is proposed to reduce total cost including open warehouse cost，distribution cost and capacity overflow cost，which contains two kinds of trade business：pickup and delivery for consumers.Variable neighborhood search heuristic algorithm is designed to solve the model and Tyson polygon is used to determine the initial order allocation in pretreatment process from the perspective of geographical space.Then it also designs some of the data structures to record the result and running attributes of the neighborhood searching by scanning radius so that the improved algorithm can update iterative solutions and get the optimal solution.In the end，the effectiveness of the models and algorithms are testified through the numerical example from the project of an express delivery company in China's Liaoning province.The research results show that reasonable use of big data planning can improve operational efficiency of the traditional logistics mode.

variable neighborhood search algorithm；pickups and deliveries；mixed integer nonlinear optimizationmodel；integrated optimization

（責(zé)任編輯：史 琳）

10.3969/j.issn.1004-910X.2016.08.006

F224

A

2016—04—14

國(guó)家自然科學(xué)基金資助項(xiàng)目 “碳限制與行為約束下多源選址——路徑——庫存集成模型研究”（項(xiàng)目編號(hào)：71572031），遼寧省教育廳人文社科基地項(xiàng)目 “低碳化多源選址——路徑——庫存問題聯(lián)合優(yōu)化模型與算法研究”（項(xiàng)目編號(hào) ：ZJ2013014）。

孫琦，東北大學(xué)工商管理學(xué)院博士研究生。研究方向：物流系統(tǒng)建模與優(yōu)化、復(fù)雜網(wǎng)絡(luò)分析。戢守峰，東北大學(xué)工商管理學(xué)院教授 ，博士生導(dǎo)師。研究方向：物流系統(tǒng)建模與優(yōu)化、物流與供應(yīng)鏈管理。劉旭，國(guó)網(wǎng)遼陽供電公司碩士研究生。研究方向 ：企業(yè)標(biāo)準(zhǔn)化管理、管理創(chuàng)新、品牌管理。