大规模交通网络设计优化_1010.

周学松美国亚利桑那州立大学2014.7大规模交通网络设计优化：快速的拉格朗日分解解法讲座提纲可达性与时间地理学可达性的时空网络表示基于可达性的交通网络设计优化数学模型基于拉格朗日松弛技术的求解算法总结及下一步研究方向可达性Accessibility可达性的概念1959年，Hansen首次提出了可达性的概念，将其定义为交通网络中各节点相互作用的机会的大小1可达性是指利用一种特定的交通系统从某一给定区位到达活动地点的便利程度2可达性反映了人们利用交通系统到达目的地参与交往活动的难易程度1.Hansen,W.G.(1959).Howaccessibilityshapeslanduse.JournaloftheAmericanInstituteofPlanners,25(2),73-76.2.Morris,J.M.,Dumble,P.L.,&Wigan,M.R.(1979).Accessibilityindicatorsfortransportplanning.TransportationResearchPartA:General,13(2),91-109.可达性Accessibility可达性的概念Miller,H,J.(2014).GreenAccessibility低可达性高可达性移动性VS可达性移动性关注运输系统的效率（方法）可达性关注出行的个体（目标）高移动性——低可达性低移动性——高可达性可达性是出行的最终目标可达性AccessibilityGraphfrom:Levine,J.,Grengs,J.,Shen,Q.,&Shen,Q.(2012).DoesAccessibilityRequireDensityorSpeed?JournaloftheAmericanPlanningAssociation,78(2),157–172.doi:10.1080/01944363.2012.677119时间地理学TimeGeography时空路径Space-timepath时间地理空间t0t0+σt0+3σt0+4σot0+5σt0+2σt0+6σd2d1时间地理学TimeGeography时空棱镜——分析可达性的有效工具Space-timeprism最大速度时间地理空间潜在路径区域潜在路径空间时间预算时间地理学TimeGeography时空棱镜——应用于日常通勤t0时间地理空间t0+T家工作时间最大速度（傍晚）最大速度（早晨）可达工作地点不可达工作地点可达性的时空网络表示可达性的时空网络表示Space-timenetworko物理网络t0t0+4σ时间距离t0+2σt0+5σt0+σt0+3σ时间预算物理路段时空旅行弧起点可达地点不可达地点d2d1可达性的时空网络表示考虑活动参与的可达性时空网络表示o物理网络t0t0+4σ时间距离t0+2σt0+5σt0+σt0+3σ时间成本物理路段时空旅行弧起点可达地点不可达地点d2d1等待弧t0+6σt0+7σt0+8σ活动参与弧可达性的时空网络表示交通网络设计对于可达性的影响物理路段时空旅行弧起点可达地点不可达地点等待弧活动参与弧o物理网络时间距离d2d18:009:0010:0011:0012:0013:007:0014:0015:0016:0017:00o物理网络时间距离d2d18:009:0010:0011:0012:0013:007:0014:0015:0016:0017:00(a)不修建路段(o,d2)(b)修建路段(o,d2)虚拟旅行弧d1d2d1d2可达性的时空网络表示考虑活动参与的可达性时空网络构建步骤Step1:建立时空节点集合𝑸将时空网络中的节点𝑖,𝑡加入集合𝑄Step2:建立时空网络弧集合𝑨Step2.1:建立时空旅行弧Step2.2:建立时空等待弧Step2.3:建立时空活动参与弧Step2.4:建立时空虚拟旅行弧Step3:设定时空弧的费用及参数Step3.1:设定虚拟弧的费用𝑐𝑖,𝑗,𝑡,𝑠𝑜,𝑑=1Step3.2:设定虚拟弧和活动参与弧对应𝑔𝑖,𝑗,𝑡,𝑠𝑜,𝑑=1可达性的时空网络表示时空网络构弧建步骤示意3个节点：o,d1,d24条备选路径：(o,d1)，(d1,o)，(d1,d2)，(d2,d1)2个OD对：(o,d1)和(o,d2)时间预算7σ活动参与时间2σ路段旅行时间：o与d1之间2σ，d1与d2之间3σ可达性的时空网络表示Step2.1建立时空旅行弧o物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σo物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σ时空旅行弧可达性的时空网络表示Step2.2建立时空等待弧o物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σo物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σ时空等待弧可达性的时空网络表示Step2.3建立时空参与弧o物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σo物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σ时空参与弧可达性的时空网络表示Step2.4建立时空虚拟旅行弧o物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σo物理网络时间距离d2d1t0t0+4σt0+2σt0+5σt0+σt0+3σt0+6σt0+7σ(o,d1)(o,d2)时空虚拟旅行弧基于可达性的交通网络设计优化数学模型参数及变量定义定义符号𝑵物理路网中点的集合𝑷物理路网中活动地点的定义,𝑃∈𝑁𝑬物理路网中路段集合𝑬𝑩物理路网中已建路段的集合𝑬𝑬物理路网中备选待建路段集合𝑸时空网络中点的集合𝑨时空网络中弧的集合𝑨𝑻时空旅行弧集合,𝐴𝑇∈𝐴𝑨𝑾时空等待弧集合,𝐴𝑊∈𝐴𝑨𝑨时空活动参与弧集合,𝐴𝐴∈𝐴𝑨𝑽时空虚拟旅行弧集合,𝐴𝑉∈𝐴𝑻时间预算𝑻𝑨活动参与时间𝒕,𝒔时间序号𝒊,𝒋物理路网中点序号,𝑖,𝑗∈𝑁参数及变量定义定义符号𝒐起点序号,𝑜∈𝑃𝒅目的点序号,𝑑∈𝑃𝒊,𝒕,𝒋,𝒔时空网络中点的序号,𝑖,𝑡,𝑗,𝑠∈𝑄(𝒊,𝒋)物理网络中路段序号,(𝑖,𝑗)∈𝐸𝒊,𝒋,𝒕,𝒔时空网路中弧的序号,𝑖,𝑗,𝑡,𝑠∈𝐴𝒄𝒊,𝒋,𝒕,𝒔(𝒐,𝒅)不可达费用,=1虚拟旅行弧;=0非虚拟旅行弧𝒈𝒊,𝒋,𝒕,𝒔(𝒐,𝒅)活动参与系数=1𝑖,𝑗,𝑡,𝑠∈𝐴𝐴,𝐴𝑉;=0其他𝒇𝒊,𝒋路段𝑖,𝑗的建设费用𝑲总建设成本预算𝒙𝒊,𝒋,𝒕,𝒔(𝒐,𝒅)=1如果时空旅行弧𝒊,𝒋,𝒕,𝒔被从o到d的出行者采用;（变量）=0其他𝒚𝒊,𝒋=1如果建设物理路段(𝑖,𝑗);=0其他（变量）基于可达性的交通网络设计优化数学模型时空网络流平衡约束活动参与约束𝑥𝑖,𝑗,𝑡,𝑠(𝑜,𝑑)𝑗,𝑠∈𝑄−𝑥𝑗,𝑖,𝑠,𝑡(𝑜,𝑑)𝑗,𝑠∈𝑄=1,𝑖=𝑜,𝑡=𝑡0−1,𝑖=𝑑,𝑡=𝑡0+𝑇𝜎0,𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃(1)基于可达性的交通网络设计优化数学模型𝑔𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑(𝑖,𝑗,𝑡,𝑠)∈𝐴=1,𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃(2)物理路段对时空旅行弧的约束建设成本约束其他约束基于可达性的交通网络设计优化数学模型𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑≤𝑦𝑖,𝑗,𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃,𝑖,𝑗,𝑡,𝑠∈𝐴,𝑖,𝑗∈𝐸𝐵(3)𝑓𝑖,𝑗×𝑦𝑖,𝑗(𝑖,𝑗)∈𝐸𝐵≤𝐾(4)𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑∈0,1𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃,(𝑖,𝑗,𝑡,𝑠)∈𝐴𝑦𝑖,𝑗∈0,1𝑓𝑜𝑟𝑎𝑙𝑙(𝑖,𝑗)∈𝐸𝐵目标函数最大化可达性（最小化非可达性）基于可达性的交通网络设计优化数学模型Z=𝑐𝑖,𝑗,𝑡,𝑠𝑜,𝑑×𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑖,𝑗,𝑡,𝑠∈𝐴𝑜,𝑑∈𝑃(5)基于拉格朗日松弛技术的求解算法原问题拉格朗日乘子拉格朗日对偶问题求解子问题一：最小费用路径问题求解子问题二：背包问题次梯度法计算拉格朗日乘子更新拉格朗日乘子终止条件检验满足不满足输出原问题、对偶问题解及两者差距基于拉格朗日松弛技术的求解算法硬性约束Hardconstraints𝑔𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑(𝑖,𝑗,𝑡,𝑠)∈𝐴=1,𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃(2)𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑≤𝑦𝑖,𝑗,𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃,𝑖,𝑗,𝑡,𝑠∈𝐴,𝑖,𝑗∈𝐸𝐵(3)minZ=𝑐𝑖,𝑗,𝑡,𝑠𝑜,𝑑×𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑖,𝑗,𝑡,𝑠∈𝐴𝑜,𝑑∈𝑃(5)𝑥𝑖,𝑗,𝑡,𝑠(𝑜,𝑑)𝑗,𝑠∈𝑄−𝑥𝑗,𝑖,𝑠,𝑡(𝑜,𝑑)𝑗,𝑠∈𝑄=1,𝑖=𝑜,𝑡=𝑡0−1,𝑖=𝑑,𝑡=𝑡0+𝑇𝜎0,𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃(1)𝑓𝑖,𝑗×𝑦𝑖,𝑗(𝑖,𝑗)∈𝐸𝐵≤𝐾(4)𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑∈0,1𝑓𝑜𝑟𝑎𝑙𝑙𝑜,𝑑∈𝑃,(𝑖,𝑗,𝑡,𝑠)∈𝐴𝑦𝑖,𝑗∈0,1𝑓𝑜𝑟𝑎𝑙𝑙(𝑖,𝑗)∈𝐸𝐵obj.s.t.活动参与拉格朗日乘子𝜆(𝑜,𝑑)路段选择拉格朗日乘子𝜋𝑖,𝑗,𝑡,𝑠𝑜,𝑑基于拉格朗日松弛技术的求解算法拉格朗日松弛问题𝑐𝑖,𝑗,𝑡,𝑠𝑜,𝑑×𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑖,𝑗,𝑡,𝑠∈𝐴𝑜,𝑑∈𝑃+𝜆(𝑜,𝑑)1−𝑔𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑖,𝑗,𝑡,𝑠∈𝐴𝑜,𝑑∈𝑃−𝜋𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑦𝑖,𝑗−𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑖,𝑗,𝑡,𝑠∈𝐴𝑜,𝑑∈𝑃(6)𝐿=s.t.约束（1），（4）和0-1变量约束基于拉格朗日松弛技术的求解算法拉格朗日问题分解子问题一：基于每个OD对的最小费用时空路径问题子问题二：背包问题PX:min𝐿𝑋𝑜,𝑑=𝑐𝑖,𝑗,𝑡,𝑠𝑜,𝑑−𝜆𝑜,𝑑𝑔𝑖,𝑗,𝑡,𝑠𝑜,𝑑+𝜋𝑖,𝑗,𝑡,𝑠𝑜,𝑑×𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑖,𝑗,𝑡,𝑠∈𝐴(7)s.t.约束（1）和0-1变量约束Py:min𝐿𝑦=−𝜋𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑜,𝑑,𝑡,𝑠×𝑦𝑖,𝑗(8)s.t.约束（4）和0-1变量约束基于拉格朗日松弛技术的求解算法问题简化子问题一松弛活动参与约束后，得到路径选择费用子问题二假设每条路段建设的费用相等𝑐𝑜,𝑑=𝜋𝑖,𝑗,𝑡,𝑠(𝑜,𝑑)×𝑥𝑖,𝑗,𝑡,𝑠𝑜,𝑑𝑖,𝑗,𝑡,𝑠∈𝐴𝑇,𝑖,𝑗∈𝐸𝐵基于拉格朗日松弛技术的求解算法算法步骤Step1:初始化设迭代次数k=0;设置拉格朗日乘子𝜋𝑖,𝑗,𝑡,𝑠(𝑜,𝑑)