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

□文/周 媛 解翠杰 高田娟

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

一、引言

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

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

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

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

應用Lagrange乘子法，求解方程組后得:

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

其等同于:

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

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

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

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

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

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

（五）粒子群的適應度?；诠糙A的配送路徑量子粒子群優(yōu)化的適應度定義為:

圖1 量子粒子群優(yōu)化適應度進化曲線

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

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

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

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

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

［2］賈永基.車輛調度問題優(yōu)化算法研究.上海交通大學博士學位論文，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.