曹 茜，宋筱影 （上海電力學(xué)院，上海 201399）

·現(xiàn)代物流·

基于Lingo的關(guān)鍵路徑法在冷鏈物流中的應(yīng)用

曹 茜，宋筱影 （上海電力學(xué)院，上海 201399）

冷鏈物流是近期發(fā)展起來的新型物流形式，物流企業(yè)在進(jìn)行冷鏈配送時(shí)往往會進(jìn)行多方面的考慮。文章主要研究了關(guān)鍵路徑法在冷鏈物流中的應(yīng)用，通過分析具體的實(shí)例，并運(yùn)用Lingo軟件進(jìn)行求解來解決關(guān)于冷鏈物流中配送的時(shí)效性問題。

關(guān)鍵路徑法；冷鏈物流；Lingo

0 引言

關(guān)鍵路徑法（Critical Path Method，CPM）[1]作為目前現(xiàn)代項(xiàng)目管理的重要管理工具，是通過分析某項(xiàng)活動過程中各子項(xiàng)進(jìn)度安排的最少時(shí)差之和，以此來對該活動的時(shí)間和成本進(jìn)行預(yù)測和優(yōu)化的方法。

關(guān)鍵路徑法作為一種網(wǎng)絡(luò)技術(shù)中的重要方法，在物流行業(yè)有著許多的應(yīng)用。而在整個(gè)物流過程中，物流的配送是其中非常重要的一個(gè)環(huán)節(jié)。它是公司根據(jù)不同企業(yè)不同的要求，對其需要的產(chǎn)品進(jìn)行分揀、包裝以及配貨的過程。物流配送的時(shí)效性對于客戶滿意度和企業(yè)的日常經(jīng)營具有較大的影響，而在冷鏈物流的配送中，這種影響則會更為重要。

1 關(guān)鍵路徑法

關(guān)鍵路徑法簡單來說就是對一個(gè)大型的項(xiàng)目進(jìn)行分解，然后根據(jù)估算的各個(gè)任務(wù)的時(shí)間及其活動之間的相互聯(lián)系建立起關(guān)聯(lián)關(guān)系，形成一個(gè)網(wǎng)絡(luò)，通過對建立起的網(wǎng)絡(luò)模型求解，就可以找到網(wǎng)絡(luò)圖中的關(guān)鍵路徑，可通過它追蹤整個(gè)計(jì)劃實(shí)施的進(jìn)度，對關(guān)鍵路徑上的活動進(jìn)行有效的控制與調(diào)整，最后制定出一個(gè)最優(yōu)的方案。

關(guān)鍵路徑法的操作步驟大致如下：

（1）列出組成項(xiàng)目的活動清單。每個(gè)項(xiàng)目都可分解為一個(gè)個(gè)小的活動和步驟，正是這些活動按照一定的順序連接起來才形成了整個(gè)項(xiàng)目。

（2）確定每項(xiàng)活動的緊前活動。緊前活動即是緊挨著該項(xiàng)活動前面的事件。也可理解為，只有當(dāng)緊前活動結(jié)束時(shí)，該項(xiàng)活動才能開展。

（3）估計(jì)每項(xiàng)活動的完成時(shí)間。

（4）繪制網(wǎng)絡(luò)圖。根據(jù)活動清單和每項(xiàng)活動的緊前活動來繪制圖形。流程方向用箭頭來表明，箭頭上方標(biāo)注每項(xiàng)活動的完成時(shí)間，節(jié)點(diǎn)以圓圈表明，代表事件。

（5）建模求解。關(guān)鍵路徑模型是一個(gè)相對成熟的模型，運(yùn)用許多軟件都可以用它進(jìn)行求解，例如WINQSB、Microsoft Office Project、Matlab、Lingo軟件等。本文主要討論用Lingo軟件進(jìn)行建模求解的方法。

（6）找出整個(gè)項(xiàng)目的關(guān)鍵路徑。

2 冷鏈物流

冷鏈物流是國民經(jīng)濟(jì)中的一項(xiàng)重要經(jīng)濟(jì)活動[2]，指生鮮冷凍食品等需要在低溫環(huán)境下進(jìn)行儲存、運(yùn)輸和配送的一項(xiàng)工程。因?yàn)槠鋵Ψ€(wěn)定的溫度要求較高，所以與其他常溫的物流配送相比，難度和成本也要更高。是否能進(jìn)行準(zhǔn)時(shí)的冷鏈物流配送，滿足物流時(shí)效的要求，直接關(guān)系到物流企業(yè)的經(jīng)濟(jì)效益。

在配送問題中應(yīng)用關(guān)鍵路徑法，主要應(yīng)用到了關(guān)鍵路徑是整個(gè)項(xiàng)目中持續(xù)時(shí)間最長的路徑這一特點(diǎn)。可以將物流配送過程中的連接弧抽象為活動，即將一地到另一地的運(yùn)輸過程看成是一個(gè)活動，連接弧上的數(shù)字，即兩個(gè)地點(diǎn)之間貨物的運(yùn)送時(shí)間看做為該活動執(zhí)行所需要的時(shí)間。所以，就可以根據(jù)這個(gè)配送模型建立一個(gè)計(jì)劃網(wǎng)絡(luò)圖，在這個(gè)計(jì)劃網(wǎng)絡(luò)圖中，路徑最長也就是配送時(shí)間最長的路徑就是關(guān)鍵路徑。若是關(guān)鍵路徑的長度滿足了配送時(shí)效的要求，那么該企業(yè)就可以進(jìn)行及時(shí)的物流配送。

3 建立模型

近年來，由于人們對生鮮冷凍食品等的需求，冷鏈物流成為了現(xiàn)代物流發(fā)展的重點(diǎn)。V1企業(yè)是一家冷鏈物流配送企業(yè)，位于圖1中①所示位置， V10企業(yè)是一家快餐店，位于圖1中⑩所示位置。V1企業(yè)到V10企業(yè)的連通路徑如圖1所示，連接弧上的數(shù)字表示兩個(gè)節(jié)點(diǎn)之間貨物的運(yùn)送時(shí)間。現(xiàn)在V1企業(yè)承擔(dān)了為V10企業(yè)運(yùn)輸冷凍食品的任務(wù)，由于貨物的特殊性，V10企業(yè)提出V1企業(yè)必須在12個(gè)小時(shí)內(nèi)將貨物送達(dá)，否則車廂里的冷凍食品就會變質(zhì)。在最壞的情況下，V1企業(yè)能否為V10企業(yè)進(jìn)行及時(shí)的物流派送是本文要解決的問題。

圖1 連通路徑及時(shí)間

4 利用關(guān)鍵路徑法求解

本文將求出這個(gè)網(wǎng)絡(luò)的關(guān)鍵路徑，并計(jì)算其長度。若是關(guān)鍵路徑的長度小于規(guī)定配送的時(shí)間，則說明就算是在最壞的情況下，V1企業(yè)也能為V10企業(yè)進(jìn)行及時(shí)的物流派送；否則，V1企業(yè)就不能為V10企業(yè)進(jìn)行及時(shí)的物流派送。

（1）建立計(jì)劃網(wǎng)絡(luò)圖

首先，根據(jù)圖1建立貨物物流配送作業(yè)的數(shù)據(jù)表（表1）及計(jì)劃網(wǎng)絡(luò)圖（圖2）。

表1 貨物物流配送作業(yè)數(shù)據(jù)

圖2 相應(yīng)的計(jì)劃網(wǎng)絡(luò)圖

（2）寫出相應(yīng)的規(guī)劃問題

設(shè)xi是事件i的開始時(shí)間，1為最初事件，n為最終事件。希望總的配送時(shí)間最短，即目標(biāo)函數(shù)就是求xn的最小值，設(shè)tij是作業(yè) i,（ ）j的計(jì)劃時(shí)間，則對于事件i與事件j有不等式 xj≥xi+tij，由此得到相應(yīng)的數(shù)學(xué)規(guī)劃問題：

分別用xi，zi表示第i（ i=1,…,10 ）個(gè)事件的最早開始時(shí)間和最遲開始時(shí)間，esij，lsij，efij，lfij分別表示作業(yè) （i,j ）的最早開工時(shí)間、最遲開工時(shí)間、最早完工時(shí)間、最晚完工時(shí)間。找出最早開工時(shí)間與最遲開工時(shí)間相同的作業(yè)，就能得到項(xiàng)目的關(guān)鍵路徑。

根據(jù)問題，有下面的遞推公式：

（3）運(yùn)用Lingo軟件對上述規(guī)劃問題求解

Lingo程序如下：

model:

sets:

events/1..10/:x,z;!x為事件的最早時(shí)間，z為事件的最遲時(shí)間;

operate（ events,events ）/1 2,1 3,2 4,3 7,4 7,4 5,4 6,6 5,7 8,5 9,8 9,9 10/:t,s,ls,es,ef,lf;!s為松弛變量，ls為作業(yè)的最遲開工時(shí)間，es為最早開工時(shí)間，ef為最早完工時(shí)間，lf為最遲完工時(shí)間;

endsets

data:

t=1 3 2 2 2 3 3 2 3 2 1 2;

@text（ txt 1.txt）=es,ls;!把計(jì)算結(jié)果輸出到外部純文本文件;

enddata

min=@sum（ events:x）;

@for（ operate（ i,j ）:x（j）>x（i）+t（ i,j ））;

n=@size（ ev ents）;

z（n）=x（n）;

@for（ events（i）|i#lt#n:z（i）=@min（ operate（ i,j）:z（j）-t（ i,j ）））;

@for（ operate（ i,j ）:es（ i,j ）=x（i ））;

@for（ operate（ i,j ）:lf（ i,j ）=z（j ））;

@for（ operate（ i,j ）:ls（ i,j ）=lf（ i,j ）-t（ i,j ））;

@for（ operate（ i,j ）:ef（ i,j ）=x（i）+t（ i,j ））;

end

運(yùn)行程序，得出的結(jié)果如表2所示，方括號中第1個(gè)數(shù)字是最早開工時(shí)間，第2個(gè)數(shù)字是最遲開工時(shí)間。

表2 作業(yè)數(shù)據(jù)

當(dāng)最早開工時(shí)間與最遲開工時(shí)間相同時(shí)，對應(yīng)的作業(yè)就在關(guān)鍵路線上，因此可以根據(jù)表2看出關(guān)鍵路線為A→C→G→I→K→M。

關(guān)鍵路線是整個(gè)計(jì)劃網(wǎng)絡(luò)的最長路線，現(xiàn)在關(guān)鍵路線長度為1+2+3+2+2+2=12，也就是說，在最壞的情況下，V1企業(yè)為V10企業(yè)進(jìn)行物流派送所花費(fèi)的最長時(shí)間為12個(gè)小時(shí)，等于V10企業(yè)所要求的12個(gè)小時(shí)。因此V1企業(yè)可以為V10企業(yè)進(jìn)行及時(shí)的物流派送。

5 結(jié)束語

本文研究了關(guān)鍵路徑法在冷鏈物流中的應(yīng)用，對相關(guān)的問題建立了模型，并通過Lingo軟件對該模型進(jìn)行求解，得到關(guān)鍵路徑的長度滿足配送時(shí)效的要求，幫助該企業(yè)檢測了物流配送的可行性。

[1] 胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2012.

[2] 翁心剛，安久意，胡會琴.冷鏈物流[M].北京：中國財(cái)富出版社，2016.

Application of Critical Path Method Based on Lingo in Cold Chain Logistics

CAO Qian,SONG Xiaoying (Shanghai University of Electric Power,Shanghai 201399,China)

Cold chain logistics is a new form of logistics which developed recently,and the logistics enterprises consider in many aspects for the cold chain distribution.This paper mainly studies the application of critical path method in cold chain logistics. By analyzing the example,we solve the timeliness for the cold chain logistics distribution with the Lingo software.

critical path method;cold chain logistics;Lingo

U116.1

A

1002-3100(2017)08-0043-03

2017-06-05

國家自然科學(xué)基金項(xiàng)目，項(xiàng)目編號：61303010。

曹 茜（1982-），女，遼寧沈陽人，上海電力學(xué)院經(jīng)濟(jì)與管理學(xué)院， 副教授，博士，研究方向：物流與生產(chǎn)調(diào)度。