基于量子粒子群算法的城市物流配送路徑研究

□文/周 媛 解翠杰 高田娟

（河北交通職業(yè)技術(shù)學(xué)院 河北·石家莊）

一、引言

配送路線的合理優(yōu)化屬于NP（Non-deterministic Polynomial）問題，是車輛路徑優(yōu)化問題（VRP）中的典型問題，由Dantzig和Ramser于1959年首次提出，歷經(jīng)數(shù)十年的研究，已經(jīng)成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的研究熱點(diǎn)課題。

二、追求共贏的配送路徑系統(tǒng)模型

（一）客戶滿意度模型。傳統(tǒng)的車輛路徑問題用時(shí)間窗口作為運(yùn)輸服務(wù)的時(shí)間約束。結(jié)合實(shí)際，客戶傾向于某一時(shí)間段內(nèi)得到服務(wù)，［τ1i，τ2i］表示客戶可容忍的服務(wù)時(shí)間范圍，［ai，bi］為客戶期望的服務(wù)時(shí)間范圍，對(duì)于圖中所描述的客戶i其滿意度函數(shù)可表示為:

（二）配送中心配送運(yùn)輸經(jīng)濟(jì)效益模型。配送中心的配送運(yùn)輸任務(wù)總是圍繞經(jīng)濟(jì)效益，根據(jù)Fisher市場(chǎng)均衡價(jià)格的計(jì)算模型，設(shè)用m（m=1，2，…，m）輛配送車對(duì)i（i=1，2，…，n）個(gè)客戶進(jìn)行運(yùn)輸配送，每個(gè)客戶持有的現(xiàn)金數(shù)額分別是A=｛e1，e2，…，en｝，必須支付配送車輛的服務(wù) B=｛q1，q2，…，qm｝的費(fèi)用，考慮如下一類對(duì)數(shù)收益函數(shù):

應(yīng)用Lagrange乘子法，求解方程組后得:

這就可以得到配送中心的配送運(yùn)輸?shù)淖畲笫杖霝?

其等同于:

三、量子粒子群優(yōu)化求解

（一）初始化種群。直接采用量子位的概率幅作為粒子（即配送車輛）當(dāng)前位置的編碼，其初始化編碼的方案:

（二）解空間變換。量子位的每個(gè)概率幅對(duì)應(yīng)解空間的優(yōu)化變量，記粒子 Pj上第 i個(gè)量子位為［αij，βij］T，則相應(yīng)的解空間變量為:

（三）粒子狀態(tài)更新。粒子狀態(tài)更新規(guī)則為:

（四）變異處理。由量子非門實(shí)現(xiàn)變異操作過程。

其中 j∈｛1，2，…，m｝，i∈｛1，2，…，n｝。

（五）粒子群的適應(yīng)度。基于共贏的配送路徑量子粒子群優(yōu)化的適應(yīng)度定義為:

圖1 量子粒子群優(yōu)化適應(yīng)度進(jìn)化曲線

其中，VN表示使用的車輛數(shù)，VNmin表示已知使用的最小車輛數(shù)，VNmax表示已知使用的最大車輛數(shù)，D表示車輛行駛的總距離，Dmin表示車輛最小行駛距離，Dmax表示車輛最大行駛距離，WT表示總等待時(shí)間，WTmin表示前種群中最小等待時(shí)間，WTmax表示前種群中最大等待時(shí)間，而 ρ1，ρ2，ρ3，ρ4，ρ5表示權(quán)重，且 ρ1+ρ2+ρ3+ρ4+ρ5＝1。

四、求解優(yōu)化算例

石藥樂仁堂醫(yī)藥物流配送中心，其主要的業(yè)務(wù)是從事藥品的零售配送。配送技術(shù)指標(biāo)為:年工作時(shí)間為251天（每周五日工作制），每天工作8小時(shí)（一班制），藥品預(yù)計(jì)年銷量40萬大箱，全省內(nèi)零售戶數(shù)為28，000戶，一周配送一次，即平均每個(gè)工作日將配送4，800個(gè)零售戶，用戶提供詳細(xì)零售戶的布局情況。用基于共贏配送路徑模型進(jìn)行優(yōu)化，進(jìn)行了為期3個(gè)月的優(yōu)化計(jì)算，圖1是其適應(yīng)度函數(shù)的進(jìn)化曲線圖。（圖1）優(yōu)化結(jié)果:優(yōu)化前原配送車輛為70輛，優(yōu)化后使用56輛；優(yōu)化后的路徑圍繞配送中心成“花瓣形”，配送中心的綜合運(yùn)營成本大幅度下降，單件藥品的綜合運(yùn)行成本降至0.16元，與實(shí)際運(yùn)行的效果接近。

本文基于共贏機(jī)理去思考配送路徑的優(yōu)化問題，兼顧對(duì)顧客、對(duì)商家的利益，可以提高配送中心建設(shè)的科學(xué)性以及提高配送中心運(yùn)營質(zhì)量。

［1］G.B.Dantzig，J.H.Ramser，The Truck Dispatching Problem.1959.

［2］賈永基.車輛調(diào)度問題優(yōu)化算法研究.上海交通大學(xué)博士學(xué)位論文，2004.

［3］Ning Chen，Xiaotie Deng，Xiaoming Sun.Andrew Chi-Chih Yao:Fisher Equil ibrium Price with a Class of Concave Uti lity Functions，ESA 2004.