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

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

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

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