交通小區(qū)劃分問題的整數規(guī)劃建模與優(yōu)化算法研究.pdf

1、城市交通是城市發(fā)展和進步的決定性因素，與社會經濟的發(fā)展相輔相成。交通超前于社會經濟的發(fā)展，是發(fā)達國家保持經濟長期快速發(fā)展的一個重要因素，反之交通問題則會成為制約經濟發(fā)展的豐要瓶頸。為此，如何做好交通規(guī)劃是我國當前急需解決的迫切問題，也是保障未來發(fā)展不可忽視的重要問題。交通調查作為交通規(guī)劃的主要內容之一，是獲取交通數據的基本方法和必要手段。通過交通調查獲得的數據是未來需求預測、規(guī)劃方案制定的主要依據，其真實性和可靠性直接決定著規(guī)劃結果。由

2、于交通源的數量巨大，交通調查一般以交通小區(qū)作為空間統(tǒng)計單元，要求確定合理的統(tǒng)計單元，不能過細而造成資源浪費，又不能過粗而影響后續(xù)的規(guī)劃結果，這就要求使用科學的方法制定這些統(tǒng)計單元。
　　有鑒于此，本文以城市交通規(guī)劃為研究背景，運用整數規(guī)劃建模求解理論與方法，分別針對交通小區(qū)劃分問題的數據抽象和最優(yōu)化建模、空間鄰接約束的建模、分區(qū)個數已知的交通小區(qū)劃分問題（基本交通小區(qū)劃分問題）以及考慮分區(qū)個數決策的交通小區(qū)劃分問題（擴展的交通小區(qū)

3、劃分問題）的建模與求解開展了系統(tǒng)的研究，主要研究工作如下文所述。
　　(1)圍繞交通規(guī)劃中交通小區(qū)的實際劃分方法、理論研究中最優(yōu)交通小區(qū)劃分問題的數據抽象過程、優(yōu)化目標的選擇與建立以及優(yōu)化框架與求解方法等幾個方面，開展了較全面的綜述研究工作，并在此基礎上針對空間單元的鄰接矩陣構造方法、空間單元的可達性計算方法以及基于可達性的交通小區(qū)劃分的優(yōu)化目標建立等問題開展了算法設計與建模工作。該項研究工作的具體內容包括:針對交通活動實踐中的交

4、通小區(qū)，以文獻資料為依據闡述了優(yōu)化劃分交通小區(qū)的意義，并概述了交通規(guī)劃管理實踐中交通小區(qū)劃分的原則及方法;從微觀角度，針對交通小區(qū)劃分問題的理論研究，重點圍繞使用優(yōu)化技術解決交通小區(qū)劃分問題時設立何種優(yōu)化目標以及如何抽象構建優(yōu)化目標的問題，分別針對建立優(yōu)化目標前對連續(xù)的空間研究區(qū)域進行離散化的方法、離散化后面狀空間單元的可達性度量方法、現實與文獻中劃分交通小區(qū)最優(yōu)目標的內容與形式以及基于可達性構建的交通小區(qū)劃分最優(yōu)目標的內容與表達形式四

5、個方面，開展了文獻綜述工作;在此基礎上分別提出了基于Z型順序編碼的基本地理單元鄰接矩陣的構造算法、使用路段局部深度值度量基本地理單元可達性的方法以及兩個交通小區(qū)劃分優(yōu)化目標的數學表達形式—最小化總區(qū)內加權出行費用目標和最小化總區(qū)內可達性差異目標;從宏觀角度，針對交通小區(qū)劃分問題研究中的理論優(yōu)化框架與方法，綜述了最優(yōu)交通小區(qū)劃分問題的相關研究成果，將其優(yōu)化問題的框架概括為分區(qū)依據數據、最優(yōu)目標、基本分區(qū)約束、問題約束、算法以及評價分區(qū)解的

6、指標這五個要素;并分別從不同類型的分區(qū)依據數據和求解方法兩個方面對交通小區(qū)劃分問題的理論研究進行了進一步的綜述。
　　(2)圍繞使用整數規(guī)劃技術對最優(yōu)交通小區(qū)空間鄰接約束建模的方法，針對文獻中保障最優(yōu)交通小區(qū)分區(qū)解滿足空間鄰接約束的方法進行了簡要的綜述，在此基礎上，針對空間鄰接約束整數規(guī)劃建模方法以及不同建模方法對問題求解效率的影響這兩個方面的問題開展了建模求解與算例分析等研究工作。該項研究工作的具體內容包括:在綜述最優(yōu)交通小區(qū)空

7、間鄰接約束建模的方法的基礎上，修正文獻中鄰接約束整數規(guī)劃建模的方法以適用于交通小區(qū)劃分問題，給出了最小生成樹表示、順序路徑表示以及網絡流表示三種對空間鄰接約束建模的方法;提出了基于鄰接矩陣表示的保障分區(qū)一階鄰接約束的一種新建模方法;分別從模型的決策變量規(guī)模與模型的約束規(guī)模兩個角度，給出了四種模型的變量、約束數量的推算過程以及理論計算表達式;基于對四種模型決策變量與約束規(guī)模的理論值估算，討論并比較與分析了四種模型的求解復雜度;基于兩個小規(guī)

8、模仿真算例對四種模型的求解過程及原理、求解效率進行了比較與分析，并簡要探討了本文所提出的基于鄰接矩陣的建模方法的適用范圍。
　　(3)圍繞基本交通小區(qū)劃分問題，研究了在分區(qū)個數已知的情景下，基于P中位問題模型的交通小區(qū)劃分問題的0-1整數規(guī)劃建模及求解方法。該項研究工作的具體內容包括:根據P中位問題模型，在假設分區(qū)決策參數已知的條件下，建立了以最小異質性為優(yōu)化目標，滿足空間鄰接約束的整數規(guī)劃模型的基本形式—最優(yōu)交通小區(qū)劃分問題的P

9、中位問題模型（TAZ-PMP模型），并分析與探討了模型的性質;將空間鄰接約束與TAZ-PMP模型分離，由此將最優(yōu)交通小區(qū)劃分問題分解為構造列池以及求解最優(yōu)下料問題兩個過程，基于此，將鄰接約束作為隱枚舉規(guī)則，給出了通過構造TAZ-PMP模型主問題的初始化列池進而將TAZ-PMP模型轉化為求解最優(yōu)下料問題的精確求解算法（TAZ-IE算法）;使用拉格朗日替代松弛技術對TAZ-PMP模型進行分解，結合近似求解拉格朗日對偶問題的搜索算法、優(yōu)化求解

10、拉格朗日對偶問題的下降梯度算法以及TAZH算法給出了基于拉格朗日替代松弛的局部搜索啟發(fā)式算法（TAZ-LSLSH算法）;通過識別、推導拉格朗日替代松弛和下降花費問題中的共同優(yōu)化的子問題，將拉格朗日替代松弛與列生成過程相結合，給出了基于拉格朗日替代松弛方法的主問題與價格子問題的分解過程，并基于此設計了基于拉格朗日替代松弛技術的列生成算法(TAZ-LSCG算法);使用基于OR-Library和Pcb3038修改的仿真數值算例對三種算法的求解

11、過程及求解效率進行了比較與分析。
　　(4)對基本交通小區(qū)劃分問題進行擴展，圍繞考慮分區(qū)個數未知的情景下，交通小區(qū)劃分問題的非線性混合整數規(guī)劃建模、模型的解析求解特征以及模型的求解算法等內容，開展了建模、算法設計與算例分析等研究工作。該項研究工作的具體內容包括:考慮分區(qū)組成、分區(qū)中心設置以及分區(qū)個數三個決策變量，建立了以最小地理誤差為目標，以各分區(qū)空間可達性同質、各分區(qū)面積同質為主要約束條件的最優(yōu)交通小區(qū)劃分問題的混合整數規(guī)劃模型

12、（K-TAZ模型）;在分析了基本地理單元設置與最優(yōu)分區(qū)問題之間關系的基礎上給出了影響區(qū)的定義，給出了構造影響區(qū)的三個核心要素為鄰接關系謂詞、同質性度量的劃分謂詞以及影響區(qū)構成規(guī)則，設計了構造影響區(qū)的啟發(fā)式搜索算法;將最優(yōu)交通小區(qū)劃分問題的求解空間離散單元由基本地理單元改為影響區(qū)，對提出的K-TAZ模型進行了改進，使最優(yōu)分區(qū)問題更容易求解;對K-TAZ模型進行了解析推導，給出了關于模型最優(yōu)分區(qū)個數解下界的引理與定理，以縮小分區(qū)個數取值范圍

13、為目標，提出了確定最大分區(qū)個數下界的方法;基于K-TAZ模型中與分區(qū)個數決策變量相關的同質性約束，作為搜索可行分區(qū)個數的限制條件，結合引理給出了可行分區(qū)個數的隱枚舉算法;分析了K-TAZ模型無解情景以及導致K-TAZ模型無解的理論原因;設計了包含兩個階段的聚合式聚類啟發(fā)式算法以重構求解空間使K-TAZ模型可解;通過對比僅包含一階段的聚合式聚類啟發(fā)過程與所提出算法的啟發(fā)式過程中求解空間結構的變化，說明了所提出算法的有效性;將最大Kmin域

14、縮減方法與約束規(guī)劃模型求解過程結合，給出了求解K-TAZ模型的約束規(guī)劃方法;將可行分區(qū)個數隱枚舉域縮減方法與P中位問題模型求解過程結合，給出了求解K-TAZ模型的P中位模型方法;使用基于Pcb3038修改的仿真數值算例對兩種算法的求解過程及求解效率進行了比較與分析。
　　(5)結合蘇州工業(yè)園區(qū)公交規(guī)劃中最優(yōu)交通小區(qū)劃分的實際案例，開展了抽象建模與算例分析等應用研究。該項研究工作的具體內容包括:基于本文提出的抽象建模與計算方法，給出

15、了案例的數據模型及其建立過程;考慮分區(qū)個數固定的情景，將案例的最優(yōu)交通小區(qū)劃分問題抽象為最小化分區(qū)異質性的TAZ-PMP模型;分別使用IE算法、LSLSH算法以及LSCG算法給出了案例最小化分區(qū)異質性TAZ-PMP模型的最優(yōu)交通小區(qū)劃分方案，并對算法求解實例的效率進行了討論與分析;考慮分區(qū)個數未知的情景，將案例的最優(yōu)交通小區(qū)劃分問題抽象為最小化地理誤差的K-TAZ模型;分別使用CP方法以及PMP方法給出了最小化地理誤差K-TAZ模型的最