基于價(jià)值函數(shù)的運(yùn)輸規(guī)劃模型設(shè)計(jì)

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

基于價(jià)值函數(shù)的運(yùn)輸規(guī)劃模型設(shè)計(jì)

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

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

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

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

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

1.1 建模思路

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

表1 運(yùn)輸路線示意表

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

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

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

1.2 模型構(gòu)建

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

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

2 模型近似解的遺傳算法

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

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

步驟 3：選擇運(yùn)算，選出滿足條件的染色體。

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

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

步驟 6：使用步驟 2 中的適應(yīng)性指標(biāo)計(jì)算新一代染色體的適應(yīng)性。

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

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

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

3 實(shí)例分析

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

根據(jù)相關(guān)部門的統(tǒng)計(jì)數(shù)據(jù)，計(jì)算各個(gè)需求點(diǎn)之間的行駛時(shí)間 TS 如表3 所示。根據(jù)圖1的運(yùn)輸物流網(wǎng)絡(luò)整理得到 6 條運(yùn)輸路線，分別為①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ù)得到的運(yùn)輸路線結(jié)合表3 的行駛時(shí)間，可以得出每條線路經(jīng)過(guò)各需求點(diǎn)的時(shí)間，如表4 所示。

表2 各需求點(diǎn)運(yùn)輸品類需求情況

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

表3 各個(gè)需求點(diǎn)之間的行駛時(shí)間

表4 各條路線到達(dá)需求點(diǎn)的時(shí)間

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

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

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

4 結(jié)束語(yǔ)

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

[1] 于 銳，曹介南，朱 培. 車輛運(yùn)輸路徑規(guī)劃問(wèn)題研究[J]. 計(jì)算機(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] 田 青，繆立新，鄭 力. 基于運(yùn)輸規(guī)劃和組合GA 的基本物流網(wǎng)絡(luò)設(shè)計(jì)[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，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] 王連鋒，宋建社，曹繼平，等. 帶硬時(shí)間窗模糊車輛路徑問(wèn)題的多目標(biāo)優(yōu)化[J]. 計(jì)算機(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ī)劃及應(yīng)用[M]. 北京：清華大學(xué)出版社，2003. LIU Bao-ding，ZHAO Rui-qing，WANG Gang. Uncertain Programming and Application[M]. Beijing：Tsinghua University press，2003.

[7] 張 潛，高立群，胡祥培. 集成化物流中的定位運(yùn)輸路線安排問(wèn)題(LRP)優(yōu)化算法評(píng)述[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，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] 王紹仁，馬祖軍. 震害緊急響應(yīng)階段應(yīng)急物流系統(tǒng)中的LRP[J]. 系統(tǒng)工程理論與實(shí)踐，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)境下多出救點(diǎn)應(yīng)急救援車輛路徑與物資運(yùn)輸優(yōu)化研究[J]. 系統(tǒng)管理學(xué)報(bào)．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ù)量的有時(shí)間窗車輛路徑問(wèn)題的遺傳算法[J]. 系統(tǒng)工程理論與實(shí)踐，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] 梁強(qiáng)升. 城市軌道交通線路高峰期的不均衡運(yùn)輸組織研究與應(yīng)用[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.

責(zé)任編輯：吳文娟

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

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