基于聚類的城市共同配送海量訂單調(diào)度問題研究①

謝天保, 趙 萌, 雷西玲

1(西安理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院, 西安 710054)

2(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 西安 710054)

基于聚類的城市共同配送海量訂單調(diào)度問題研究①

謝天保1, 趙 萌1, 雷西玲2

1(西安理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院, 西安 710054)

2(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 西安 710054)

針對(duì)云物流環(huán)境下城市共同配送海量訂單調(diào)度難的問題, 本文提出基于訂單聚類的調(diào)度算法. 首先針對(duì)單中心多車輛調(diào)度問題, 提出基于單親遺傳的優(yōu)化調(diào)度算法; 在此基礎(chǔ)上綜合考慮城市配送中心的地理位置、車輛及配送點(diǎn)的地理位置、貨物的種類、需求量, 提出采用蟻群算法構(gòu)建基于配送中心的海量訂單聚類、優(yōu)化調(diào)度算法.

共同配送; 海量訂單; 聚類; 蟻群算法; 調(diào)度

1 引言

隨著信息技術(shù)的高速發(fā)展, 我國(guó)的城市物流配送正在進(jìn)行著變革, 傳統(tǒng)的物流配送已經(jīng)不能滿足現(xiàn)代城市物流發(fā)展的需求, 加快物流信息的共享互通、降低物流成本、統(tǒng)籌優(yōu)化社會(huì)物流資源、提高城市物流配送效率是新環(huán)境下城市物流配送亟需解決的問題.而云物流是基于云計(jì)算強(qiáng)大的通信能力、運(yùn)算能力和匹配能力[1], 建立物流信息共享平臺(tái), 實(shí)現(xiàn)智能匹配、智能組合、智能管理物流服務(wù)等先進(jìn)功能[2]. 基于云物流的物流信息共享平臺(tái), 是對(duì)整個(gè)物流網(wǎng)絡(luò)中的信息進(jìn)行收集、處理、傳遞、共享的集中地, 其主要思想就是: 在物流信息充分共享的前提下, 對(duì)供貨方和收貨方之間交易的海量物流訂單、各類企業(yè)和第三方物流企業(yè)現(xiàn)有的零散物流資源進(jìn)行整合, 依靠云計(jì)算技術(shù)對(duì)這些信息進(jìn)行處理和挖掘, 實(shí)行科學(xué)合理的訂單規(guī)劃和車輛調(diào)度進(jìn)行管理, 實(shí)施共同配送, 使得共同配送信息平臺(tái)的各方參與者都能獲取更多的利益, 從而吸引更多企業(yè)的物流訂單和物流資源加入到平臺(tái)中, 形成一個(gè)平臺(tái)開放、資源共享、終端無限的網(wǎng)絡(luò). 因此,研究云物流下城市共同配送海量訂單調(diào)度問題, 有效緩解城市交通壓力、減少城市污染, 對(duì)提高城市物流管理水平、改善城市居民的生存環(huán)境具有重要的意義,也對(duì)云物流信息共享平臺(tái)的實(shí)際建設(shè)與應(yīng)用具有推進(jìn)作用.

物流配送車輛優(yōu)化調(diào)度問題最早由DnaZtig和Ramser于1959年首次提出[3]. 車輛優(yōu)化調(diào)度問題根據(jù)時(shí)間特征的差異可分為車輛路徑規(guī)劃問題VRP(Vehicle Routing Problem)、車輛調(diào)度問題VSP (Vehicle Scheduling Problem)以及有時(shí)間窗的車輛路徑問題VRPTW(Vehicle Routing Problem with Time Windows)[4], 屬于一個(gè)NP-hard問題, 其模型建立針對(duì)一個(gè)配送中心而且只有當(dāng)其規(guī)模較小時(shí), 才能求其精確解. 而對(duì)于多中心協(xié)同配送調(diào)度問題, 在以往的國(guó)內(nèi)外研究中[5-11], 文獻(xiàn)[5-6]首先將多車場(chǎng)問題轉(zhuǎn)化為單車場(chǎng)問題, 用分解算法處理多車場(chǎng)配送問題; 文獻(xiàn)[7]提出了一種基于網(wǎng)絡(luò)流模型最優(yōu)解的啟發(fā)式算法, 來探討多車場(chǎng)滿載貨運(yùn)車輛的優(yōu)化調(diào)度問題; 文獻(xiàn)[8]運(yùn)用了禁忌搜尋法解決車輛配送路線問題; 文獻(xiàn)[9]采用了C-W節(jié)約算法對(duì)有時(shí)間窗約束的非滿載車輛調(diào)度進(jìn)行路線安排; 文獻(xiàn)[10]提出用神經(jīng)網(wǎng)絡(luò)算法來求解車輛配送路線優(yōu)化問題; 文獻(xiàn)[11]建立了一種基于最小配送費(fèi)用的數(shù)學(xué)模型來研究多車場(chǎng)多車型車輛調(diào)度問題, 并借助遺傳算法對(duì)模型進(jìn)行求解. 云物流模式下城市共同配送涉及到海量訂單、眾多配送中心以及各種類型車輛調(diào)度, 再加上多種約束條件(時(shí)間窗約束、類別), 顯然是一個(gè)復(fù)雜的NP-Hard問題, 同時(shí)考慮到云物流模式下的訂單配送具有多頻次、少批量、多品種、零散化、個(gè)性化、訂單動(dòng)態(tài)性、時(shí)效性高、隨機(jī)性強(qiáng)等特點(diǎn), 這些特點(diǎn)無疑增加了云物流海量訂單調(diào)度模型求解的復(fù)雜性,為此本文提出基于多中心聚類結(jié)合單中心多車輛調(diào)度算法實(shí)現(xiàn)海量訂單的優(yōu)化調(diào)度, 根據(jù)物流訂單的特性(物流中心空間距離、貨物類型等)采用聚類分析[12], 分別計(jì)算各中心(類)的配送成本, 以上過程結(jié)合改進(jìn)蟻群算法對(duì)海量訂單反復(fù)迭代聚類分析, 最終可求取城市海量物流訂單的最優(yōu)調(diào)度方案, 便于云物流分布式調(diào)度的實(shí)現(xiàn).

2 基于聚類的海量訂單共同配送調(diào)度模型

假設(shè)某城市現(xiàn)有物流中心M個(gè), 用變量m(m=1, 2,…, M)表示, 考慮到城市居民需求的動(dòng)態(tài)性, 這些物流配送中心在城市區(qū)域均勻分布, 其坐標(biāo)為(Xm, Ym), 每個(gè)物流中心擁有多個(gè)不同類型的運(yùn)輸車輛, 平均車速V, 物流中心的地理信息、及車輛信息通過云服務(wù)收集于城市共同配送云物流平臺(tái). 在某一時(shí)刻(通常周期性處理), 城市物流平臺(tái)收集到N個(gè)訂單, 貨物配送點(diǎn)隨機(jī)分布于城市覆蓋區(qū)域, 根據(jù)M個(gè)配送中心的地理位置信息、各自的車輛信息、配送點(diǎn)地理位置信息, 如何從M個(gè)配送中心選擇出若干個(gè)配送中心及車輛負(fù)責(zé)海量訂單的配送任務(wù), 合理調(diào)度車輛資源、提高運(yùn)輸車輛的配載率, 緩解城市交通擁堵, 降低城市物流配送成本是本文研究的目標(biāo).

2.1 問題分析及變量說明

在云物流城市共同配送模式下, 配送的總成本主要包括固定成本和運(yùn)輸成本. 固定成本包括車輛動(dòng)用成本和人力資源成本等, 在基于時(shí)間窗約束車輛調(diào)度[13]的數(shù)學(xué)模型中, 這里采用硬時(shí)間窗, 即必須在規(guī)定時(shí)間段送達(dá). 下面首先對(duì)模型中的變量進(jìn)行說明, 然后分析城市共同配送活動(dòng)的成本.

(1) 配送中心信息描述:

m(m=1, 2, …, M)表示配送中心編號(hào);

(Xm, Ym)(m=1, 2, …, M)表示配送中心m的地理坐標(biāo);

f(m, k)(m=1, 2, …, M, k=1, 2, …, K)表示配送中心m的車輛編號(hào);

g(f(m, k))(m=1, 2, …, M, k=1, 2, …, K)表示m配送中心第k輛車的最大載重量;

C(f(m, k))(m=1, 2, …, M, k=1, 2, …, K)表示m配送中心第k輛車固定成本(包括人力成本);

UC(f(m, k))(m=1, 2, …, M, k=1, 2, …, K)表示m配送中心第k輛車每公里消耗成本.

(2) 配送點(diǎn)信息描述:

n(n=1, 2, …, N, N＞＞M)表示配送點(diǎn)編號(hào);

(Xn, Yn)(n=1, 2, …, N)表示配送點(diǎn)n的地理坐標(biāo);

Pg(n)(n=1, 2, …, N)表示配送點(diǎn)n所需貨物的重量;

Tp(n)(n=1, 2, …, N)表示配送點(diǎn)n所需貨物的類別,不同類別的貨物不能同車, 例如蔬菜和農(nóng)藥;

st(n)(n=1, 2, …, N)表示配送點(diǎn)n要求送貨的最早時(shí)間;

et(n)(n=1, 2, …, N)表示配送點(diǎn)n要求送貨的最遲時(shí)間;

tt(n)(n=1, 2, …, N)表示配送點(diǎn)n卸貨消耗時(shí)間;

D(i, j)(i=1, 2, …, N, j=1, 2, …, N)表示配送點(diǎn)i和配送點(diǎn)j之間的距離;

DHS(i, m)表示配送點(diǎn)i和配送中心m之間的距離.

(3) 決策變量:

a) 配送點(diǎn)i是否為配送中心M的第k車輛f(m, k)的第一個(gè)配送點(diǎn).

b) 配送點(diǎn)i是否為配送中心M的第k車輛f(m, k)的最后一個(gè)配送點(diǎn).

c) 緊前配送點(diǎn)i是和緊后配送點(diǎn)j是否由配送中心M的第k車輛f(m, k)完成.

(4) 中間變量: 決策變量確定后, 即可計(jì)算出中間變量.

Sst(f(m, k), i)表示m中心的車輛k到達(dá)配送點(diǎn)i的實(shí)際時(shí)間:

SD(f(m, k))表示m中心車輛k行使的總路程:

U(f(m, k))用于判別m中心的車輛k是否被調(diào)用:

2.2 模型目標(biāo)函數(shù)的確定

首先分析動(dòng)用車輛的固定成本, 固定成本主要包括人力成本(駕駛員和裝卸工)、車輛管理成本和折舊成本等. VFC表示完成整個(gè)物流訂單所有物流中心動(dòng)用車輛的固定成本:

其次分析貨物配送的運(yùn)輸成本, 運(yùn)輸成本主要包括車輛的燃油費(fèi)、路橋費(fèi)用等, 其中SD(f(m, k))表示m中心第k輛車的行駛距離, UC(f(m, k))表示該輛車單位行使距離的消耗成本. VTC表示總的運(yùn)輸成本:

模型的目標(biāo)函數(shù)為總成本SUMC=VFC+VTC最小.

約束條件:

(1) 任一配送點(diǎn)i, 只能由一輛車完成配送. 由2.1中的(3)節(jié)內(nèi)容看出, 任一配送點(diǎn)i只能由某配送中心m第k輛車完成, 如為車輛的第一個(gè)配送點(diǎn)時(shí), 決策變量HS(i, f(m, k))=1; 如為車輛的最后一個(gè)配送點(diǎn)時(shí), 決策變量HE(i, f(m, k))=1; 否則為中間節(jié)點(diǎn), 只能為某一個(gè)節(jié)點(diǎn)j的緊前節(jié)點(diǎn), 因此

(2) 每個(gè)客戶服務(wù)時(shí)間必須在約束的時(shí)間窗內(nèi).lt(i)和ut(i)為配送節(jié)點(diǎn)i所要求的貨物到達(dá)的最早時(shí)間和最遲時(shí)間, Sst(f(m, k), i)為車輛實(shí)際達(dá)到節(jié)點(diǎn)i的時(shí)間點(diǎn).

(3) 保證配送中心的車輛經(jīng)過一系列的配送任務(wù)最終回到原點(diǎn). 對(duì)任一車輛k, 如其承擔(dān)某配送點(diǎn)i為出發(fā)點(diǎn)時(shí), 必有另一配送點(diǎn)j為其最終配送點(diǎn), 完成最終配送任務(wù)后, 返回配送中心.

(4) 對(duì)于m中心任一車輛k, 其負(fù)責(zé)的配送點(diǎn)的需求貨物總重量之和不能超出車輛k的最大載重量g(f(m,k)).

(5) 假如配送點(diǎn)i和配送點(diǎn)j由同車配送, 貨物類別差級(jí)應(yīng)不大于L, 即同車貨物類別不沖突, 例如食物和農(nóng)藥、或帶刺激性的氣味貨物不能同車, L的取值取決于貨物具體的編碼方案.

3 基于聚類分析的海量訂單共同配送調(diào)度模型求解

在實(shí)際的配送過程中, 考慮到車輛的載重限制、行駛距離最小、返回原配送中心等約束條件, 可以斷定配送車輛負(fù)責(zé)完成的配送點(diǎn)必將分布配送的周圍附近, 這就提示我們針對(duì)眾多物流中心、海量訂單的配送問題可以通過聚類劃分成多個(gè)單中心的物流配送問題, 降低問題的求解規(guī)模, 然后啟發(fā)式優(yōu)化算法各個(gè)求解, 最后通過反復(fù)迭代聚類分析結(jié)合優(yōu)化算法可求出全局最優(yōu)解.

3.1 基于單親遺傳的單中心車輛調(diào)度問題求解

假設(shè)某城市均勻分布著m個(gè)物流中心, 要獲取整個(gè)城市海量訂單優(yōu)化調(diào)度方案(多中心配送), 首先解決單中心車輛調(diào)度優(yōu)化問題, 下面以單配送中心多配送點(diǎn)車輛調(diào)度問題為例, 采用單親遺傳算法求解進(jìn)行說明.

定義1. 虛擬配送點(diǎn), 形式類同于一般配送點(diǎn), 其貨物需求量為零, 與配送中心及其他配送點(diǎn)的距離為零,僅為染色體基因交叉而定義.

(1) 染色體編碼采用整數(shù)編碼, 染色體中基因由配送點(diǎn)編號(hào)、配送中心編號(hào)和虛擬配送點(diǎn)組成. 如圖1所示, 圖中的s為配送中心編號(hào), v為虛擬配送點(diǎn), 相鄰兩個(gè)s節(jié)點(diǎn)代表一輛車的運(yùn)輸路徑.

圖1 染色體編碼示意圖

這個(gè)編碼方案優(yōu)點(diǎn)是染色體確定后, 很容易計(jì)算出決策變量HS(i, f(m, k))、HE(i, f(m, k))、HIJ(i, j, f(m,k)), 并根據(jù)公式(4)、(5)、(6)計(jì)算出中間變量Sst(f(m,k), i)和SD(f(m, k)).

(2) 初始染色體的生成, 針對(duì)類中的配送點(diǎn), 可隨機(jī)生成若干組染色體.

(3) 計(jì)算染色體中各基因的換位概率, 虛擬配送點(diǎn)的換位概率為1, 其他配送節(jié)點(diǎn)換位概率以配送節(jié)點(diǎn)3為例說明.

(4)針對(duì)種群中染色體, 隨機(jī)產(chǎn)生兩個(gè)換位節(jié)點(diǎn)及隨機(jī)數(shù)p(0, 1), 如果兩個(gè)節(jié)點(diǎn)的換位概率均大于p, 實(shí)施基因換位; 否則重新產(chǎn)生換位節(jié)點(diǎn)和隨機(jī)數(shù)p.

(5)根據(jù)車輛時(shí)間窗約束條件公式(10)和載重約束條件(12)檢查每條路徑的可行性、, 剔出不滿足約束條件的染色體.

(6)根據(jù)公式(7)和(8)計(jì)算配送中心總成本SUMC,包括車輛固定成本VFC和車輛運(yùn)輸成本VTC, 及m中心的總成本Z(m).

(7)如果連續(xù)幾次最優(yōu)總成本SUMC不再降低, 即獲取最優(yōu)解, 算法結(jié)束. 否則轉(zhuǎn)(8).

(8)選擇出種群中總成本SUMC最少的若干染色體最為新種群, 轉(zhuǎn)步驟(3).

3.2 基于聚類分析的海量訂單調(diào)度算法

配送中心的運(yùn)輸能力決定了它能夠負(fù)責(zé)周圍配送點(diǎn)的多少, 因此可根據(jù)配送中心的運(yùn)輸能力, 選擇周圍配送點(diǎn)的聚類半徑, 結(jié)合蟻群算法[15]實(shí)施海量訂單的優(yōu)化調(diào)度. 具體算法如下:

(1) 初始化參數(shù)α, β, 準(zhǔn)備N組螞蟻, 每組m個(gè)螞蟻隨機(jī)分布于m個(gè)配送中心(聚類中心).

(2) 針對(duì)每個(gè)聚類中心i, 按照搜索半徑r范圍, 確定范圍內(nèi)的配送點(diǎn)Vi, 要求Vi的并集為所有需求點(diǎn). 初始化螞蟻的禁忌表Tubai=Vi, 令ηij=1/dhs(i, j), dhs(i, j)為配送點(diǎn)j到配送中心i的距離.

(3) 針對(duì)每只螞蟻k, 隨機(jī)選取搜索范圍內(nèi)的配送點(diǎn)j, 按照概率最大轉(zhuǎn)移規(guī)則, 分配配送點(diǎn)j于配送中心i中, 令s(i, j)=1, 并將配送點(diǎn)j輸入禁忌表Tubai.

其中: τij(t)為t時(shí)刻, 配送點(diǎn)j到配送中心i路徑的信息素.

(4) 當(dāng)一組螞蟻搜索完成后, 所有的配送點(diǎn)分配完畢, 按照3.1節(jié)的算法, 計(jì)算各配送中心的配送成本Z(m), 然后計(jì)算總成本SumC=∑Z(m).

(5) 記錄螞蟻k經(jīng)過配送點(diǎn)j和配送中心i路徑的信息增量.

(6) 當(dāng)N組螞蟻全部完成搜索, 轉(zhuǎn)(7), 否則轉(zhuǎn)(3).

(7) 更新螞蟻分組配送點(diǎn)到配送中心路徑上的信息量, 并記錄最好的分類結(jié)果.

(8) 如連續(xù)幾次SumC不再降低, 算法結(jié)束; 否則轉(zhuǎn)(2), 直至總成本不再降低.

4 實(shí)驗(yàn)分析

云物流城市共同配送車輛調(diào)度問題優(yōu)化研究過程中, 為了節(jié)省計(jì)算資源, 且更加清晰直觀的說明所要研究的問題, 選取了37個(gè)配送點(diǎn)和6個(gè)配送中心作為研究對(duì)象, 針對(duì)配送點(diǎn)訂單信息的三個(gè)屬性進(jìn)行聚類調(diào)度分析, 包括: 橫坐標(biāo)、縱坐標(biāo)、訂單類別(共包含十個(gè)等級(jí), 不同等級(jí)代表不同種類的貨物; 級(jí)別相差越大,種類差別越大, 本文假定相差2個(gè)級(jí)別, 不能同車裝載),車輛行駛單公里成本1元. 假定這些訂單和配送中心分布在100*100的區(qū)域內(nèi), 具體訂單數(shù)據(jù)和配送中心信息如表1, 表2所示.

針對(duì)3.2節(jié)中的聚類算法, α=1.9反映了配送點(diǎn)被聚類到任一配送中心的歷史信息強(qiáng)度, α過小, 歷史信息重視不夠, 算法收斂較慢; α過大, 容易陷入局部最優(yōu)化.β=1.2表示啟發(fā)式信息(配送點(diǎn)到配送中心的距離DHS)受重視的程度, 顯然β過大, 聚類結(jié)果受距離DHS影響較大, 容易陷入局部最優(yōu). 共設(shè)置50組螞蟻,每組螞蟻數(shù)37只, 經(jīng)過239次迭代獲取調(diào)度方案如表3和圖2所示.

表1 訂單信息表

表2 配送中心信息表

表3 車輛調(diào)度最優(yōu)路徑

圖2 聚類及車輛優(yōu)化調(diào)度路線圖

分析表3不難看出, 6個(gè)配送中心經(jīng)聚類優(yōu)化后, 選擇其中四個(gè)參與配送任務(wù). 配送中心1, 3和4各出2輛車,中心6出1輛車, 車輛行駛路徑、配載率、行使距離見表3, 各車配載率較高, 均在75%以上.

如上所示, 圖2展示了6個(gè)配送中心、37個(gè)配送點(diǎn)的空間位置、以及7輛車的負(fù)責(zé)配送的行駛路徑. 配送中心②和⑤不參與配送任務(wù). 經(jīng)過實(shí)心點(diǎn)(配送中心①③④⑥)的封閉曲線為各車輛的行駛路線. 配送中心③和⑥負(fù)責(zé)的配送點(diǎn)不存在運(yùn)送貨物種類沖突問題,車輛路徑基本符合路徑最短原則, 配送中心①和④負(fù)責(zé)配送點(diǎn)存在物品類別沖突, 類別沖突的貨物不能同車配送, 同時(shí)為了滿足各配送點(diǎn)時(shí)間窗約束, 車輛路徑出現(xiàn)交叉, 并未滿足路徑最短原則, 這與實(shí)際情況相符,并不影響總體配送成本降低.

5 結(jié)語

針對(duì)云物流環(huán)境下城市共同配送海量訂難以調(diào)度問題, 本文提出基于訂單聚類結(jié)合單中心多車輛優(yōu)化調(diào)度的迭代算法, 對(duì)海量訂單調(diào)度問題進(jìn)行了探討研究. 單中心多車輛調(diào)度模塊由各中心服務(wù)器完成, 物流訂單聚類分析由云物流中心系統(tǒng)已完成, 實(shí)現(xiàn)分布式調(diào)度, 以便快速求出車輛調(diào)度最優(yōu)解.

1貢祥林, 楊蓉. “云計(jì)算”與“云物流”在物流中的應(yīng)用. 中國(guó)流通經(jīng)濟(jì), 2012, 26(10): 29–33. [doi: 10.3969/j.issn.1007-8266.2012.10.006]

2張水旺, 胡小建. 云物流概念模型及其運(yùn)作機(jī)理研究. 科技管理研究, 2015, 35(19): 186–190, 196. [doi: 10.3969/j.issn.1000-7695.2015.19.035]

3田冉, 孫林夫, 唐慧佳, 等. 多車場(chǎng)物流協(xié)同運(yùn)輸調(diào)度問題研究. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(21): 230–236. [doi:10.3778/j.issn.1002-8331.1408-0158]

4王天成. 物流配送車輛優(yōu)化調(diào)度問題概述. 物流工程與管理, 2013, 35(8): 29–30.

5杭省策, 李懷祖. 多車場(chǎng)車流分配的廣義指派模型及其分解算法. 西安交通大學(xué)學(xué)報(bào), 1997, (12): 111–116.

6郭耀煌, 李軍. 車輛優(yōu)化調(diào)度問題的研究現(xiàn)狀評(píng)述. 西南交通大學(xué)學(xué)報(bào), 1995, 30(4): 376–382.

7張明善, 唐小我. 多車場(chǎng)滿載貨運(yùn)車輛優(yōu)化調(diào)度的網(wǎng)絡(luò)流算法. 系統(tǒng)工程學(xué)報(bào), 2002, 17(3): 216–220.

8Bianchessi N, Righini G. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery.Computers & Operations Research, 2007, 34(2): 578–594.

9李作秋, 王國(guó)林. 一種有時(shí)間窗約束的非滿載車輛調(diào)度問題中的啟發(fā)式算法研究 .公路交通科技 ,2006 ,23(7) :147–149.

10Golden BL, Raghavan S, Wasil EA. The Vehicle Routing Problem: Latest Advances and New Challenges. US:Springer, 2008.

11馬宇紅, 姚婷婷, 張芳芳. 多車場(chǎng)多車型車輛調(diào)度問題及其遺傳算法. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2014, 44(2): 107–114.

12王駿, 王士同, 鄧趙紅. 聚類分析研究中的若干問題. 控制與決策, 2012, 27(3): 321–328.

13張建強(qiáng), 方衛(wèi)國(guó). 有時(shí)間窗約束車輛路徑問題的改進(jìn)遺傳算法. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(32): 228–231. [doi:10.3778/j.issn.1002-8331.2010.32.063]

Research on Massive Orders Scheduling Problem of Urban Joint Distribution Based on Clustering

XIE Tian-Bao1, ZHAO Meng1, LEI Xi-Ling2

1(School of Economics and Management, Xi’an University of Technology, Xi’an 710054, China)
2(School of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710054, China)

In order to solve the problem of massive orders scheduling in the cloud logistics environment, this paper proposes a scheduling algorithm based on orders clustering. Firstly, aiming at the single center multi vehicle scheduling problem, an optimal scheduling algorithm based on the single parent genetic algorithm is proposed. On this foundation,considering the location of the city distribution centers, the vehicles and the distribution points, the type and the demand of goods, an order clustering model based on distribution center is built by using the ant colony algorithm.

joint distribution; massive orders; clustering; ant colony algorithm; scheduling

謝天保,趙萌,雷西玲.基于聚類的城市共同配送海量訂單調(diào)度問題研究.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(7):232–237. http://www.c-sa.org.cn/1003-3254/5837.html

陜西省教育廳人文社科重點(diǎn)研究基地科研計(jì)劃項(xiàng)目(15JZ039)

2016-10-28; 收到修改稿時(shí)間: 2016-11-30