從定性分析的角度來看，可以將專家判斷以數(shù)值形式表示，再經(jīng)過綜合分析后對選址進(jìn)行決策。首先，根據(jù)影響物流設(shè)施選址的因素，建立備選方案的評價指標(biāo)體系；然后，采用一定的評價方法（例如：偏好理論、權(quán)重因素分析方法、專家評分法、層次分析法、模糊層次分析法、模糊綜合評判法等）得到所需的評價指標(biāo)的權(quán)重；最后，通過求出各備選方案的優(yōu)劣排序，得到最優(yōu)方案[1~4]。車輛路徑問題是物流配送中的另一個重要問題。一般定義為：對一系列發(fā)貨點(diǎn)和/或收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件（例如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用極小、時間盡量少、使用車輛數(shù)盡量少等）。在實(shí)際應(yīng)用中，車輛路徑問題可以按照不同的分類原則細(xì)分為許多子問題。多數(shù)的研究都是只針對1~2個屬性的問題展開[5~7]。由于這些組合問題多是NP難的，使用動態(tài)規(guī)劃、分支限界、回溯方法進(jìn)行求解的確定性算法難以避免計算中的組合爆炸。因此，當(dāng)問題規(guī)模稍大時，這類算法在應(yīng)用中就難以發(fā)揮作用，目前的應(yīng)用中多采用啟發(fā)式算法和近似算法求解。

電子商務(wù)物流組合優(yōu)化問題的參數(shù)算法研究

參數(shù)理論研究

從一個更開放的角度來看，電子商務(wù)物流系統(tǒng)中的諸多問題可以歸約到更多的算法問題上去。例如，物流配送中心選址實(shí)際上可以歸約到一些覆蓋和支配問題以及斯坦納（Steiner）問題上去，車輛路徑問題可以歸約到哈密爾頓回路問題和旅行商問題上去，而庫存控制和車輛裝載可以歸約到背包和裝箱問題上去。這些問題中很多已經(jīng)被證明為NP難問題。同時，這類問題很多都與物流網(wǎng)絡(luò)的拓?fù)涮匦杂嘘P(guān)，多數(shù)都來自于圖論中的一些經(jīng)典問題，但不同的是，由物流應(yīng)用導(dǎo)出的問題往往會在原始圖問題的基礎(chǔ)上附加一些新的約束條件，例如費(fèi)用、路線、時間等方面的約束，這些約束有時還會給原問題帶來復(fù)雜度的增加。盡管多數(shù)這類問題都是NP難的，但是問題本身的重要性和挑戰(zhàn)性還是引起了研究人員的廣泛關(guān)注。如前面提到的一些選址和路徑問題就是近年來研究得比較多的問題。由于難以求得精確解，研究人員通常設(shè)計啟發(fā)式算法和近似算法求解，在某些場合也取得了較好的效果。盡管如此，但很多時候啟發(fā)式算法和近似算法得到的結(jié)果無助于我們深刻地理解問題的本質(zhì)，也難以準(zhǔn)確評價算法在應(yīng)用中的實(shí)際性能。對此，我們的想法是將參數(shù)算法設(shè)計和分析理論引入到電子商務(wù)物流優(yōu)化問題的求解中，將電子商務(wù)物流中的一些組合優(yōu)化問題進(jìn)行參數(shù)化建模，進(jìn)而采用參數(shù)算法設(shè)計的一些技術(shù)設(shè)計可行的參數(shù)算法來求解這些優(yōu)化問題。

參數(shù)理論的研究最初來源于觀察到很多計算問題都與一個取值范圍較小的重要參數(shù)相聯(lián)系，利用參數(shù)的性質(zhì)可以在一定程度上加速計算。當(dāng)一個參數(shù)問題可在時間f（k）nc內(nèi)解決，其中c是一個常數(shù)，而函數(shù)f獨(dú)立于輸入規(guī)模n，則稱該問題是固定參數(shù)可解的（FixedParameterTractable，F(xiàn)PT），用FPT表示該類問題的集合。根據(jù)這一定義，對于小的參數(shù)值，F(xiàn)PT問題是實(shí)際可解的。根據(jù)現(xiàn)有的研究結(jié)果，利用參數(shù)方法來解決組合優(yōu)化問題已被證明有著廣泛的應(yīng)用。因此，即使這些計算問題在其一般形式下是NP難的，其實(shí)際應(yīng)用中的實(shí)例卻有其特殊性。很多計算優(yōu)化問題都可參數(shù)化，且其參數(shù)值僅在一個很小的范圍內(nèi)變化。對于這些NP難問題的參數(shù)化求解也取得了令人矚目的成績。例如，與電子商務(wù)物流選址問題相關(guān)的一個經(jīng)典的NP完全問題—點(diǎn)覆蓋問題的參數(shù)化定義就是：給定一個圖G（V，E）和一個整數(shù)k，|V|=n，判斷圖G是否存在一個有k個點(diǎn)的集合C哿V，使得圖G中的所有邊至少有一個端點(diǎn)在C中。在參數(shù)計算與復(fù)雜性理論中k（k<<n）被看作是一個參數(shù)。利用參數(shù)k，人們提出了實(shí)際有效的算法，在實(shí)際應(yīng)用中取得了很好的效果。1993年Buss和Goldsmith首次提出針對點(diǎn)覆蓋的復(fù)雜度為O（kn+2kk2k+2）的算法[8]，而目前最好的算法是有Chen給出的時間復(fù)雜度為O（kn+13.285k）的算法[9]。上述算法的求解策略往往都是將參數(shù)化問題核化到一個更小的核上，然后再在核上采用分支限界等技術(shù)求解。同樣，對于在電子商務(wù)物流中有著廣泛應(yīng)用的支配集問題的參數(shù)化求解也取得了重要的進(jìn)展。研究表明，參數(shù)化支配集問題不是FPT可解的。但是將參數(shù)化支配集問題限定在平面圖這樣一個背景下，則平面圖支配集問題可以在O（c姨k?n）時間求解[10]，其中c≤4346姨，隨后，常數(shù)c的上界又被優(yōu)化到215.13[11]。最近的研究表明，在平面圖上求解支配集，通過兩個圖規(guī)約和預(yù)處理技術(shù)，可以得到一個不超過335k大小的核[12]，這個線性核完全獨(dú)立于原始圖的規(guī)模。由于k相對n通常是很小的數(shù)，問題的規(guī)模就從降低到的線性函數(shù)，這也就大大降低了問題的規(guī)模。因此參數(shù)算法技術(shù)在一些組合優(yōu)化問題的求解上是極其有益的。

電子商務(wù)物流組合優(yōu)化問題的參數(shù)算法研究

針對電子商務(wù)物流中的一些組合優(yōu)化問題，可以首先從參數(shù)算法的角度對這些問題建模，然后設(shè)計有效的參數(shù)算法求解，最后將這些參數(shù)算法轉(zhuǎn)化為適合于實(shí)際應(yīng)用環(huán)境的近似算法。具體來說可以采用如下方法。（1）電子商務(wù)物流問題的參數(shù)化。對電子商務(wù)物流中的優(yōu)化問題的不同參數(shù)化會導(dǎo)致差異巨大的參數(shù)復(fù)雜性，特別是，如果不適當(dāng)?shù)倪M(jìn)行參數(shù)化，則問題可能變成參數(shù)不可解的。因此，需要注意的是如何將物流中的優(yōu)化問題正確的參數(shù)化，使得參數(shù)化后的計算問題滿足如下兩點(diǎn)條件：①參數(shù)化的計算問題仍能夠反映原問題的本質(zhì)。②參數(shù)化計算問題使得小參數(shù)算法的方法可以有效地應(yīng)用并解決原問題。值得注意的是，由于物流網(wǎng)絡(luò)的復(fù)雜性和本身固有的其他約束，電子商務(wù)物流網(wǎng)絡(luò)優(yōu)化問題中必然會存在某些無法用參數(shù)算法解決或不能夠用參數(shù)算法很好解決的問題。對于這一類問題，我們還需研究一套行之有效的方法，使得能夠解決或部分解決參數(shù)化問題。（2）電子商務(wù)物流優(yōu)化問題的參數(shù)算法設(shè)計及性能分析。利用參數(shù)問題的特殊性來研究與傳統(tǒng)算法技術(shù)不同的參數(shù)算法設(shè)計與分析的新技術(shù)將對有效使用參數(shù)算法在電子商務(wù)物流優(yōu)化問題中的應(yīng)用有著非常重要的影響。一旦優(yōu)化問題參數(shù)化以后，利用參數(shù)值的特殊性，以及其對整個計算問題復(fù)雜性的影響，特殊的參數(shù)算法技術(shù)可能大大改善解決問題的效率，而達(dá)到傳統(tǒng)算法無法達(dá)到的效果。這一方面的研究所遇到的挑戰(zhàn)是如何從傳統(tǒng)算法設(shè)計的框架中跳出來，設(shè)計嶄新的行之有效的參數(shù)算法及其分析技術(shù)。通過利用參數(shù)理論中發(fā)展起來的一些算法設(shè)計技術(shù)，例如核化、有限搜索樹、分解規(guī)約等，設(shè)計一些可行的參數(shù)算法來求解這些算法優(yōu)化問題。參數(shù)算法得到的精確解可以更深刻的理解優(yōu)化問題本質(zhì)，對其他啟發(fā)式算法和近似算法的評估也有著重要的意義。（3）電子商務(wù)物流優(yōu)化問題的近似算法設(shè)計與分析。在前述參數(shù)算法的基礎(chǔ)上，通過一些改進(jìn)和簡化，設(shè)計一些更適合于實(shí)際應(yīng)用場合的近似算法。在以往的研究中我們注意到，參數(shù)理論中發(fā)展起來的很多規(guī)約和預(yù)處理技術(shù)不僅僅可用于參數(shù)算法設(shè)計，在近似算法中同樣有著重要的作用。在一些場合，這些技術(shù)能迅速化簡問題，降低問題的復(fù)雜度，無論是在理論上還是在實(shí)際應(yīng)用場合。同時對這些近似算法和分布式算法的分析可以采用平攤分析技術(shù)。在以往的物流優(yōu)化問題研究中，對算法的分析和評價主要以最壞情況分析和仿真實(shí)驗比較居多。最壞情況分析在某些問題上無法客觀地評價算法性能，而仿真實(shí)驗的說服力有限。例如經(jīng)典的快速排序算法，它的最壞情況是相對較差的，但是它的平均性能卻是所有排序算法中最好的。因此在某些應(yīng)用場合一些近似算法往往比一些確定性算法（或者有理論下界保證的算法）具有好得多的平均性能。這是對這些算法進(jìn)行平攤分析的一個重要原因。