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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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