帶容量約束的開放式弧路徑問(wèn)題的算法研究.pdf

1、具有容量約束弧路徑問(wèn)題（Capacitated Arc Routing Problem, CARP）產(chǎn)生于交通運(yùn)輸服務(wù)系統(tǒng)，因其廣泛應(yīng)用于城市街道清掃、垃圾回收、輸電線路檢查、物流配送等現(xiàn)實(shí)生活中，而得到了廣泛的研究。本文主要研究CARP的一種新的擴(kuò)展類型―具有容量約束的開放式弧路徑問(wèn)題（Open CARP, OCARP），該類問(wèn)題與CARP的主要區(qū)別在于車輛在服務(wù)完所有客戶后無(wú)需返回車場(chǎng)。該類問(wèn)題主要產(chǎn)生于第三方物流配送服務(wù)業(yè)，而且隨

2、著電子商務(wù)的日漸繁榮，第三方物流配送企業(yè)間的競(jìng)爭(zhēng)也更加激烈，提升物流配送服務(wù)效率，較好地滿足大城市及超大城市的密集型配送需求，降低物流配送成本，對(duì)第三方物流企業(yè)的存亡至關(guān)重要。
　　本文詳細(xì)描述了OCARP的圖論模型及數(shù)學(xué)模型，分析了其現(xiàn)有的求解算法及求解效果，設(shè)計(jì)了兩種算法用于求解 OCARP，即禁忌搜索算法與改進(jìn)的變鄰域搜索算法。
　　禁忌搜索算法基于局部搜索算法，通過(guò)接受劣解來(lái)避免算法陷入局部最優(yōu)，同時(shí)使用禁忌表來(lái)避免

3、循環(huán)搜索，最后配合破特赦則來(lái)允許算法向更好的區(qū)域搜索，該策略使得算法同時(shí)具有廣度搜索與深度搜索的良好性能。變鄰域搜索其基本思想是在局部搜索的過(guò)程中系統(tǒng)地改變當(dāng)前解的鄰域結(jié)構(gòu)，以降低陷入局部最優(yōu)的風(fēng)險(xiǎn)，經(jīng)過(guò)多次迭代，最終達(dá)到收斂的目的。
　　兩種算法在81個(gè)基準(zhǔn)數(shù)據(jù)集上的測(cè)試結(jié)果表明了它的有效性，TS算法在23個(gè)算例上達(dá)到了最優(yōu)下界，并優(yōu)化了51個(gè)算例的最優(yōu)上界；IVNS算法在28個(gè)算例上達(dá)到了最優(yōu)下界，并優(yōu)化了55個(gè)算例的最優(yōu)上界