夏賢康，盧星儒XIA Xian-kang, LU Xing-ru（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）(School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China)

基于價值函數(shù)的運輸規(guī)劃模型設(shè)計

夏賢康，盧星儒
XIA Xian-kang, LU Xing-ru
（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）
(School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China)

在闡述運輸規(guī)劃模型建模思路和算法的基礎(chǔ)上，針對物流網(wǎng)絡(luò)中的運輸配送問題對運輸規(guī)劃模型進行設(shè)計，通過引入價值函數(shù)，構(gòu)建運輸品類數(shù)量和到達時間價值函數(shù)的雙層目標規(guī)劃模型，采用遺傳算法對上述模型的最優(yōu)近似解進行求解。經(jīng)過實例分析，根據(jù)各需求點運輸品類需求情況計算各個需求點之間的行駛時間及各條路線到達需求點的時間，得到相應的最佳運輸路線，結(jié)果表明該算法可行。

運輸規(guī)劃；價值函數(shù)；遺傳算法

隨著經(jīng)濟全球化的發(fā)展，不同形式、不同層次的區(qū)域物流和國際物流等逐漸發(fā)展起來，迫切需要一種高效完善的物流網(wǎng)絡(luò)系統(tǒng)作技術(shù)支撐。物流企業(yè)需要在全球范圍內(nèi)建立物流網(wǎng)絡(luò)系統(tǒng)，實現(xiàn)對整個物流網(wǎng)絡(luò)的效用最高和總費用最低的優(yōu)化，運輸配送作為物流網(wǎng)絡(luò)的中心環(huán)節(jié)，對運輸規(guī)劃模型進行設(shè)計是物流網(wǎng)絡(luò)優(yōu)化的重點，考慮在價值函數(shù)理論的基礎(chǔ)上，對以運輸量和到達時間為雙目標的運輸規(guī)劃問題進行研究[1-4]。

1 建模與算法設(shè)計

1.1 建模思路

（1）運輸路網(wǎng)。假設(shè)配送中心 A = {A1，A2，…，Ah} 為運輸出發(fā)點，目標地點為需求點 B = {B1，B2，…，Bn} ，根據(jù)需求點 B、配送中心 A、運輸車輛的運輸路網(wǎng)結(jié)構(gòu)可以列出所有運輸線路，如表1所示。其中，序號欄 lj 表示路徑分類，設(shè)置 A 為出發(fā)點，運輸路徑可以用 lj×md 維的 0-1 矩陣 A 來表示路徑情況。當 A 中元素 ali= 1 時，表示 lj條線路經(jīng)過需求 Bi；當 ali= 0 時，則 lj 條線路不經(jīng)過需求點 Bi。

表1 運輸路線示意表

（2）待運輸?shù)奈镔Y。假設(shè)有 t 種物資要運輸?shù)叫枨簏c，分別記為 m = 1，2，…，t。設(shè)配送中心 Al關(guān)于物資 t 的儲備總量為 clt，其中 l = 1，2，…，mc，mc 為 t 種物資的儲備總量。

（3）運輸工具。假設(shè)有 r 輛運輸車輛可以進行物資運輸，分別記為 k = 1，2，…，r，trk為 k 的裝載能力。假設(shè)在線路不發(fā)生堵塞的情況下，所有運輸工具的運輸效率相同，并且行駛速度也相同，則可以用lj×md 維實數(shù)矩陣 TS 來表示全部路徑上的運輸時間。TS 中的元素表示第 lj 條線路到達需求點 Bi的時間，tsli∈ [0，mt]，當 ali= 0 時，tsli= mt，mt 為運輸時間的極大值。

（4）決策變量。χ，y，z 分別為雙目標運輸規(guī)劃的決策變量，χki為運輸工具 k 運輸?shù)叫枨簏c Bi的物資數(shù)量；yk∈ [1，2，…，lj] 為整數(shù)，表示 k 選表1 中第 lj 條線路；zk∈ [1，2，…，t] 為整數(shù)，表示 k承擔第 t 種物資的運輸。

1.2 模型構(gòu)建

模型的目標函數(shù)為需求點的價值函數(shù)之和最大，然后根據(jù)路徑是否擁堵、運輸資源、運力、單一物資單一路徑等限制設(shè)置約束條件。以運輸時間和運輸費用價值最大為目標建立雙目標規(guī)劃模型[5]，將不同的應對資源同時進行運輸規(guī)劃，該模型計算公式為

式中：vdi為需求點的子任務(wù)價值函數(shù)之和；vDi,m() 為運輸品類 m 運送到需求點 Bi的時間價值函數(shù)，⑵式為需求點 Bi的價值函數(shù)之和，其中vDi,m() 的具體內(nèi)容根據(jù)需求點價值函數(shù)的約束條件確立；⑶ 式中 χsmi,d表示不同運輸工具 k 運輸 m 類物資到需求點的時間價值；⑷ 式用于計算同一時間段內(nèi)到達需求點 Bi運輸品類 m 的數(shù)量；trk表示 k 的運力；cml為需求點 Bi可用物資 m 的總量；⑹ 式中 ayki為決策變量，表示只有當路徑 l 經(jīng)過需求點 Bi時，才會在 Bi處卸下物資；yk∈ [1，2，…，lj] 表示 k 選擇的路線；zk∈ [1，2，…，t] 表示 k 裝載的運輸品類類型。

2 模型近似解的遺傳算法

采用遺傳算法對上述模型的最優(yōu)近似解進行求解，算法步驟如下[5-10]。

步驟 1：生成初始染色體，將滿足上述模型的約束條件的染色體轉(zhuǎn)換為變量 (χ，y，z)。

步驟 3：選擇運算，選出滿足條件的染色體。

步驟 4：交配運算，按照上述模型的約束條件進行交配，選出符合條件的染色體。

步驟 5：變異運算，按照上述模型的約束條件進行變異，選出符合條件的染色體。

步驟 6：使用步驟 2 中的適應性指標計算新一代染色體的適應性。

步驟 7：按照給定的循環(huán)次數(shù)循環(huán)步驟 3—步驟6，按照給定的循環(huán)次數(shù)進行迭代。

步驟 8：輸出結(jié)果，選出適應性指標最好的染色體轉(zhuǎn)變?yōu)樽顑?yōu)解，輸出 χ，y，z，(vd1，vd2，…，vdmd)。

根據(jù)以上算法，運用 Matlab 軟件計算得到上述模型的近似最優(yōu)解，根據(jù)輸出的 (χ，y，z) 可以得到運輸工具的路徑選取及各個需求點的運送物資量。

3 實例分析

假設(shè)有 7 個需求點，分別記為 B1，B2，…，B7，各個需求點需求量為不確定變量，其數(shù)值按無量綱化進行處理，需求情況如表2 所示，一個配送中心記為 A，運輸物流網(wǎng)絡(luò)如圖1 所示。

根據(jù)相關(guān)部門的統(tǒng)計數(shù)據(jù)，計算各個需求點之間的行駛時間 TS 如表3 所示。根據(jù)圖1的運輸物流網(wǎng)絡(luò)整理得到 6 條運輸路線，分別為①A→B6→B7；②A→B6→B5→B4→B3→B1；③A→B6→B5→B4→ B2；④A→B3→B4→B5→B6→B7；⑤A→B3→B4→B2；⑥A→B3→B1。根據(jù)得到的運輸路線結(jié)合表3 的行駛時間，可以得出每條線路經(jīng)過各需求點的時間，如表4 所示。

表2 各需求點運輸品類需求情況

圖1 運輸物流網(wǎng)絡(luò)圖

表3 各個需求點之間的行駛時間

表4 各條路線到達需求點的時間

假設(shè)配送中心的物資量為 10，品種為單一物資，而且只有 4 輛運輸車可供使用，每輛車的最大載貨量為 2。采用決策變量 χli表示第 l 條路線送至需求點 Bi的物資量，則需求點 Bi的價值函數(shù)計

算公式[11]為，其中 v (χ) =則運輸任務(wù)的價值函數(shù)為 v =采用 Matlab 軟件計算上述模型的近似最優(yōu)解，根據(jù)輸出的 χ 可以得到最優(yōu)近似解，最佳運輸路線選取②、③、④、⑤，根據(jù)輸出的 y 和 z 可以得到各需求點接收運輸品類數(shù)量如表5 所示，最優(yōu)價值函數(shù)為 3.96。

表5 各需求點接收運輸品類數(shù)量

4 結(jié)束語

以整體價值最大化為目標來構(gòu)建運輸規(guī)劃模型，不僅可以滿足不同客戶需求，而且在提高運輸效率的同時能夠降低企業(yè)成本[12]。該模型在一般物流配送網(wǎng)絡(luò)中應用良好，為解決該類運輸問題提供了可借鑒的思路，同時也為處理多配送點的復雜網(wǎng)絡(luò)設(shè)計提供了相應的理論支持。另外，該模型還適用于銷售高峰期物流中心向各分銷點配貨的緊急情況[13]，通過進一步優(yōu)化模型，盡可能全面地考慮影響因素，從而提出更加合理的運輸優(yōu)化方案。

[1] 于 銳，曹介南，朱 培. 車輛運輸路徑規(guī)劃問題研究[J]. 計算機技術(shù)與發(fā)展，2011，21(1)：5-8. YU Rui，CAO Jie-nan，ZHU Pei. Study on Vehicle Path Planning Problem[J]. Computer Technology and Development，2011，21(1)：5-8.

[2] Amos T，Daniel K. Advance in Prospect Theory：Cumulative Representation of Uncertainty[J]. Journal of Risk and Uncertainty，1992(5)：297-323.

[3] Saber H M，Ravindran A. Nonlinear Goal Programming Theory and Practice：A Survey[J]. Computers and Operations Research，1993(20)：275-291.

[4] 田 青，繆立新，鄭 力. 基于運輸規(guī)劃和組合GA 的基本物流網(wǎng)絡(luò)設(shè)計[J]. 清華大學學報(自然科學版)，2004，44 (11)：22-23. TIAN Qin，LIAO Li-xin，ZHENG Li. Logistics Network Design based on Transport Planning and Combined GA[J]. Journal of Tsinghua University (Natural Science Edition)， 2004，44(11)：22-23.

[5] 王連鋒，宋建社，曹繼平，等. 帶硬時間窗模糊車輛路徑問題的多目標優(yōu)化[J]. 計算機工程，2013，39(4)：9-17. WANG Lian-feng，SONG Jian-she，CAO Ji-ping，et al. The Multi-objective Optimization Fuzzy Vehicle Routing Problem with Hard Time Windows[J]. Computer Engineering，2013，39(4)：9-17.

[6] 劉寶碇，趙瑞清，王 綱. 不確定規(guī)劃及應用[M]. 北京：清華大學出版社，2003. LIU Bao-ding，ZHAO Rui-qing，WANG Gang. Uncertain Programming and Application[M]. Beijing：Tsinghua University press，2003.

[7] 張 潛，高立群，胡祥培. 集成化物流中的定位運輸路線安排問題(LRP)優(yōu)化算法評述[J]. 東北大學學報(自然科學版)，2003，24(1)：31-34. ZHANG Qian，GAO Li-qun， HU Xiang-pei. Integrated Logistics Location Routing Arrangement Problem (LRP) Optimization Algorithm Review[J]. Journal of Northeastern University (Natural Science Edition)， 2003，24 (1)：31-34.

[8] 王紹仁，馬祖軍. 震害緊急響應階段應急物流系統(tǒng)中的LRP[J]. 系統(tǒng)工程理論與實踐，2011，31(8)： 1497-1507. WANG Shao-ren，MA Zu-jun. Earthquake Disaster Emergency Response in the Stage of Emergency Logistics System LRP[J]. Theory of System Engineering and Practice，2011，31 (8)：1497-1507.

[9] 汪傳旭，鄧先明. 模糊環(huán)境下多出救點應急救援車輛路徑與物資運輸優(yōu)化研究[J]. 系統(tǒng)管理學報．2011，20(3)：269-275.

(??)(??)WANG Chuan-xu，DENG Xian-ming. Multi-depot Emergency Vehicle Routing and Transportation Optimization with Fuzzy Variables[J]. Journal of Systems & Management，2011，20(3)：269-275.

[10] 鄒 彤，李 寧，孫德寶. 不確定車輛數(shù)量的有時間窗車輛路徑問題的遺傳算法[J]. 系統(tǒng)工程理論與實踐，2004，24(6)：134-138. ZOU Tong，LI Ning，SUN De-bao. Uncertain Number of Vehicles，Vehicle Routing Problem with Time Windows，Genetic Algorithm[J]. System Engineering Theory and Practice，2004，24 (6)：134-138.

[11] Amos T，Daniel K. Advance in Prospect Theory：Cumulative Representation of Uncertainty[J]. Journal of Risk and Uncertainty，1992(5)：297-323.

[12] Liu B D. Uncertainty Theory：A Branch of Mathematics for Modeling Human Uncertainty[J]. Springer-Verlag，2010(12)：147-152.

[13] 梁強升. 城市軌道交通線路高峰期的不均衡運輸組織研究與應用[J]. 都市快軌交通，2014，27(4)：30-34. LIANG Qiang-sheng. The Unbalanced Transportation Organization Research and Application of the Peak of the City Rail Transit Line[J]. Urban Rapid Rail Transit，2014，27(4)：30-34.

責任編輯：吳文娟

Design of Transportation Planning Model based on Cost Function

Based on expounding the modeling idea and algorithm of transportation planning model, targeting with the problems of transport delivery in logistic network, the transportation planning model is designed, and then, a bi-level objective model combined with category number of transport products and cost function of arrival time is established and the optimized approximate solution of the model is solved by using genetic algorithm. Through example analysis, according to demand status of transport product category in each demand point, the running time among each demand point and the time of each line arriving the demand point are calculated, then relative optimum transport route is achieved, so the study result shows this calculation method is feasible.

Transportation Planning; Cost Function; Genetic Algorithm

1003-1421(2016)07-0053-04

：U294.1；U116.2

B

10.16668/j.cnki.issn.1003-1421.2016.07.10

2015-10-20

2016-03-16

甘肅省自然基金項目 (1506RJZA079)