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

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

參數(shù)理論研究

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

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

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

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