2024年1月23日发(作者：一模数学试卷江西中考)
“华为杯”第十四届中国研究生数学建模竞赛题目构建分层优化的城市地下物流系统网络摘要：当前我国正处于城市化进程的加速阶段，城市规模急剧扩张，人口密度和产业密度迅猛提高，城市物流的规模也随之日益增大，由此带来了城市交通拥堵、生态恶化、资源浪费等一系列问题。为改善和缓解城市问题，实现城市可持续发展，因此，建立城市地下物流系统网络十分必要。针对问题一，首先，对附件1中115个点的坐标数据进行预处理，计算它们之间距离小于3公里的所有点，并按照小于的点的数量对其排序，筛选出需要作为节点的点。接着，建立APH-PCA多目标系统分析模型，将区域划分为5个小区域，对交通拥堵率（T）、总货物量（H）、货物面积比（F）进行等级划分，依据相对重要性构建判断矩阵，采用方根法计算判断矩阵权重，然后进行一致性检验，计算检查判断矩阵是否具有完全一致性，得到5个区域的节点排序情况。依据节点的覆盖范围、拥堵率及货运量，我们选择出5个一级节点((149951.9,1577738.28)、(146987.68,15418.21)、(149951.9,157738.28)、(138793.52,155638.13)、(14367.06,153444.63))，27个二级节点。依据拥堵率与货运量成正比的关系，可以计算出每个节点地下物流运输的最少货运量，且给地下的实际货运量有预留量，得到每个区域的一级节点以及其覆盖的点、二级节点以及其覆盖的点的实际货运量。最后，根据一级节点的转运率计算公式，得到每个一级节点的转运率，即左1节点φ1=0.65260、左2节点φ2=0.58731、左3节点φ3=0.61495、左4节点φ4=0.62944、右节点φ5=0。针对问题二，首先，对城市地下物流系统网络的各类布局情况进行分析，在问题一-1-
的基础上（且转运率变化不大的情况下），建立基于遗传算法的模型。在满足物流货运量的基础上，我们对每个区域分别进行物流网络优化，得到优化后的地下物流网路图。基于问题一的各节点实际货运量，在优化后的网络图上得到最新的各节点实际货运量和各级通道的实际流量。接着，我们适当调整一、二级节点位置，将物流网络图调整为星型或栅格型，且调整后的网络图也满足成本及货运量的要求。通过对双向双轨运输和双向四轨运输总费用进行对比，最终选择双向双轨+双向四轨综合的运输方式（总费用为182亿元），更大程度上缓解交通拥堵，且降低物流成本，达到地下物流系统最优化。针对问题三，以问题二中设计的网络为基础，根据节点和路径负载能力以及节点的复杂度（即节点之间空间距离和节点与其他节点的关系），计算出每个节点在该区域距离其他节点的重要度。根据对地下物流系统运行情况的分析，以及各个节点的重要度信息，我们对问题二的网络图增加节点个数，调整节点的位置或级别，缩短货物运输总里程，降低运输成本，共计增加7个二级节点，并把23号二级节点变为一级节点。此外，当网络中某个节点失效时，通过增加、减少、改变路径的方法，利用Dijkstra算法获取最短路径模型，比较不同路径的费用，得到最优化的网络节点图。针对问题四，首先，通过Matlab计算得到30年内货运量从76240.97346吨增长到313818.1846吨。根据第一问得到的权重，可知货运量对地下物流网络的影响较大，所以在每年货运量以5%的速度增长的情况下，扩展和改进网络是必不可少的。然后，建立基于贪婪算法的动态规划模型，将每年的成本最低设为目标，在原有网络的基础上，不断地增加节点和改进增加节点的路径。最后，利用蚁群算法进行迭代求解，得出一级节点增加了1个，二级节点增加了6个，以及可满足30年物流需求的地下物流网络。在本论文中，充分运用了点线面地下物流网络系统，问题一是解决如何选择节点，问题二是对节点之间的路径进行合理规划，问题三是优化物流网络图，问题四是为满足更高要求，对节点以及路径进行最优化处理。并且，我们将各个因素进行归一化处理，计算权重和重要度，在规划路径和改进路径的过程中，定量比较各网络图的优势。关键字：城市地下物流；APH-PCA多目标系统；节点重要度；最短路径；网络优化-2-
一、问题重述地下物流系统是城市内部及城市间通过地下管道或隧道运输货物的运输和供应系统，我们需要通过选择节点和规划路线完成两个最直接的目标是缓解交通拥堵和降低物力成本。地下物流系统的节点建设面临的最大挑战就是在满足完全覆盖的条件下，需要巨额的投资，所以一味地考虑覆盖率和拥堵率是不合理的。而且，其主要工作场所处于地下，所以在进行线路设计时，必须考虑隧道建设成本，确定合适的网络布局和轨道方案。长远考虑，地下物流系统造价高，改建困难，所以本文需要根据时间序列做好扩容处理，提高此系统的长期使用价值。图1.1地下物流系统结构图我们需要建立数学模型来解决以下问题：（1）根据所给中心点的位置及当前拥堵率、OD矩阵表，以缓解拥堵率为最终目标（使每个位置的交通至少为基本畅通），充分考虑完全覆盖条件，建立一个模型，找出最少的节点数目，并确定出一级节点和二级节点，给出一级节点的转运率和各节点货运量。（2）根据题目所给隧道和节点建设成本和上题中所算出的节点信息，以地下物流网络建设成本最低为目标，设计或采用一个方法，规划出合理的地下物流网络系统，给出新的节点（若有节点变动）和通道位置、在此系统中各节点实际货运量和通道实际流量，并将规划的地下物流网络系统进行仿真。（3）综合上述两步结果，根据上题仿真结果考虑地下系统的全局性，整体考虑此系统覆盖率、拥堵率、建设费用和抗风险能力，以整个系统最优为目标，建立模型，修改节点位置和路径修改。（4）由于地下物流系统主体在地下，造价高、风险大、改建困难，所以上题所设计的地下物流系统网络满足应该市30年内的交通需求。我们将考虑随着地下物流系统的建设，接下来每年的交通拥堵率变化，建立模型，确定地下物流系统更路线建设时序和演进过程仿真，比较出与上题确定的系统网络的优劣。-3-
二、模型假设与说明1、物流网络由两级节点组成，即一级节点（转运节点）和而节点（配送节点）；2、假设两节点之间的直线距离即为所建隧道的长度；3、假设所有种类的货物均可通过隧道运输；4、忽略节点间的经济成本及时间成本。三、符号说明本文中，用到的主要符号与说明如下表。符号说明THF交通拥堵指数总货物量货物面积比最大特征值转运率线路长度记作货物运输量为每个一级节点的建造成本maxφLijXijWi-4-
四、模型的建立与求解4.1基于点线面网络的地下物流系统网络随着城市经济的快速发展，城市人口的不断增长和人们对物质生活质量要求的提高，使得城市货运量逐年增加，引起了严重的城市交通问题。城市交通拥堵、交通安全、城市空间拥挤、噪音污染、能源消耗加剧、尾气污染等严重影响着城市居民的出行环境、生活质量和身心健康。近年来，地下物流系统（UndergroundLogisticsSystem—ULS）是适应城市货运发展的新思路和新途径是解决城市交通问题最优远见的方案之一。整ULS的功能(管理操控、运输配送、存储保管等)都是通过系统网络来实现和支撑的，本文将物流网络结构抽象成图论中的网络，根据图论中网络符号的表达方式进行描述，ULS的网络定义如下：U={N,V,W}式中：U—地下物流系统的网络；N—地下物流网络节点；V—地下物流网络路线；W—网络路线的权重。根据以上定义，地下物流网络被抽象为物流节点和网络路线，在整个网络中，物流节点是最关键的，物流节点有着不同的分类与分级，本文将地下物流系统将网络节点进行了分类，分为一级节点和二级节点。物流中心是地下物流网络的出发点和聚集点，是地下物流系统管理控制的枢纽，分为地上和地下两个部分。它的主要功能是负责运输货物、操作和管理物流、控制与维护系统运载工具、保障整个系统的安全等。配送中心是物流网络的节点，它与物流中心的功能相似，但组成和运作都比物流中心简单很多。网络路线是指将网络节点相连接，也可与传统的地面运输路线连通而组成的线路，最终将货物输送到目的地，部分ULS的网络路线也可以根据实际需要在地面上进行规划。4.2问题一4.2.1问题一分析城市地下物流网络为了缓解交通和降低物流成本，所以我们在选择节点时，应该在保证地区全部覆盖的前提下选取最少的节点。从所给地图地图可以看出每个区域中心点密集度不同，每个中心点的区域面积差别较大，题目中给出货运量与面积之比过小，若节点覆盖了某区域中心点即可视为对该区域进行了覆盖，根据所给数据，计算出运货量和区域面积之比，我们需要将地图进行区域划分，各个区域分开计算选取节点。每个节点的服务半径在3公里范围内自由选择，附件所给数据包含了110个中心点和四个物流园区的位置，我们需要据此计算出中心点的距离，保证选取的节点群可以覆盖服务所有区域。此网络主要为了缓解交通，至少保证交通基本畅通，根据所给的各小区域的当前拥堵率和拥堵指数与货运量成正比，所以选取节点后我们需要计算出各小区域的拥堵系数并保证其小于等于4。由于有很多中心点距离小于3公里，所以一个节点可以覆盖服务很多个小区域，我们需要经过计算分配每个节点的服务范围和一级节点的转运率。4.2.2OD流量矩阵OD流量矩阵是记录物流网络中所有起点（Origin，O点）到所有终点（Destination，-5-
D点）货运流量的二维数据矩阵。反映所有物流货物对物流网络的基本需求，描述全天物流网络的所有起点到所有终点的货运量。物流网络中货物发送的起点也叫始发地，货物发送的终点也叫目的地。物流网络中的一个节点，既可以是货物始发地，也可以是货物目的地。一个有n个货物始发/目的地（OD点）的物流网络的OD矩阵如表4.1所示。表4.1OD矩阵OD12in1t11t21ti1t1nD12t12t22ti2t2nD2jt1jt2jtijtnjDjnt1nt2ntin始发地O1O2OitnnDnOnT目的地表中tij表示物流网络中的第i个起点到第j个终点的货运量，对角线元素tii表示的是OD点内部的物流量，均为0；Oi表示第i个起点的物流始发地；Dj表示第j个终点的物流目的地；T表示物流总量。4.2.3OD数据预处理根据附件1中的坐标数据，可以计算出115个点中，每个点与每个点之间的距离。题目中的“所有节点的服务半径在3公里范围内自由选择，节点间距离不受限制”的条件，我们对所有点之间的距离进行筛选，当中心点之间的距离小于3公里时，我们对此点进行记录，可得到小于3公里所有点的位置及次数，如表4.2所示。表4.2距离小于3公里所有点的位置及次数编号数量编号数量编号数量编号8762815861-6-82827283884728578232648814794
数量编号数量编号数量编号数量编号数量39959886689868968936838869466782531628741.2.4基于APH-PCA的多目标系统分析模型层次分析法是一种定量和定性相结合的系统分析方法，能将定性问题定量化，它对于解决多层次、多目标的大系统优化问题行之有效，具有高度逻辑性、灵活性及简洁性等特点。AHP法首先将所要分析的问题层次化，然后在此基础上，根据问题的性质和所要达到的总目标，将问题分解为不同的组成因素，并按照因素间的相互关联影响以及隶属关系将因素按不同层次聚集组合，形成一个多层次分析结构模型，最终获得各要素相对重要程度的权值，判断以决定诸因素相对重要性的顺序。层次分析方法的基本过程，大体可以分为如下六个基本步骤：明确问题；建立层次结构；构造判断矩阵；计算权重；一致性检验；层次总排序。对于地下物流节点的选择而言，可以把选择的目标分为两层，第一层为地下网络节点群总体目标，第二层为“交通拥堵指数T”、“总货物量H”和“货物面积比F”（货物面积比=该区域总货物量/该区域面积）的三个二级目标，见图4.1。图4.1地下物流节点的层次分析（1）明确问题对于前期OD数据的预处理，可知区域编号885-900之间的区域，其距离小于3公里的点较少，所以，我们将整个物流区域分为两个部分，分别对两个区域进行节点选择判断，即对两个大区域建立层次模型。（2）建立层次结构根据对每个区域的交通拥堵指数、总货物量和货物面积比进行排序对比，我们可以看出在左区域内，因为存在非常密集的区域和较为宽广的区域，所以对较多的点的影响较大。因此，我们根据点的密集度，将左区域继续分为4个小区域建立层次结构，区域划分如图4.2。-7-
图4.2区域划分（3）构造判断矩阵判断矩阵是将层次模型中同一层次的要素相对于上层的某个因素，相互间做成对比较而形成的矩阵。根据交通拥堵指数、总货物量和货物面积比的排序，我们对三个指标进行重要性的判定。交通拥堵指数取值范围为0至10，每2个数为一等级，具体指标见表，数值越高，表明交通拥堵状况越严重。表4.3交通拥堵指数指标等级拥堵情况0-2畅通2-4基本畅通4-6轻度拥堵6-8中度拥堵8-10严重拥堵总货物量由于该地区非人口高度密集区，附件1中全天OD的数值，是每个区域的进货运量和出货运量，因为货物在地面运送才需要考虑到交通拥堵，而发展城市地下物流网络的其中一个直接目标是缓解交通拥堵直至交通畅通。所以，每个区域的地上货运量必须达到交通畅通的要求，即交通拥堵指数指标<4。又因为交通拥堵指数与OD数据反映出来的区域总货运量（进、出之和）成正比，我们可根据总货物量与交通拥堵指数的关系，推算出当该区域交通拥堵指数指标<4时，地上运输货物的最大数值，由此也可知地下需要运输货物的数量。按照地下运输货物的数量分为10个等级，具体等级划分见表4.4。表4.4总货物量等级划分数量等级H>4000103000 表4.5货物面积比等级划分数量等级F>3000102500 计算得出max=3。（5）一致性检验一般而言，判断矩阵的数值是根据数据资料、专家意见和分析者的认识，加以平衡后给出的。但是，因客观事物的复杂性和人们认识上的多样性，可能会产生片面性，因此要求每一个判断矩阵都有完全的一致性显然是不可能的，特别是因素多、规模大的问题更是如此。为了考察层次分析法得到的结果是否基本合理，需要对判断矩阵进行一致性检验。对于任意判断矩阵，当C.I.0时，则判断矩阵具有完全一致性；C.I.的值越大，偏离一致性的程度就越大。构造一致性检验指标C.I.，构造如下：nC.I.max（式4.4）n1求解得出C.I.0，则此判断矩阵具有完全一致性。故获得各个目标权重见表4.7。表4.7目标权重交通拥堵率T0.3总货物量H0.6货物面积比F0.1C.I.0（6）层次总排序层次总排序就是基于层次但排序得到的结果计算组合权重，然后通过比较各要素组合权重的大小，得到要素的相对重要顺序。对于地下物流节点的选择，我们根据分区后计算一致性检验指标，并对该指标排序，得到排序结果如下所示。左1区域：表4.8左1区域排序结果编号一致性编号一致性编号一致性84818.30384111.0048606.06384618.14285310.9418645.76684516.24286310.8648695.71685115.285210.168565.38386713.2998439.1668585.03684412.7988598.7568544.94986111.6848628.3488654.91985011.5498427.8368574.37784911.3488556.7558661.97984711.3228686.381左2区域：表4.9左2区域排序结果编号一致性编号一致性87715.9438814.71888013.5078724.65887613.0378734.64987512.4248834.33287411.9988793.5568789.9028829.2618706.3868846.3788716.364左3区域：表4.10左3区域排序结果编号一致性编号一致性79310.21780713.0267958.05980810.4877968.7258096.4179711.17281015.127988.5348119.629-10-8008.49781211.4398019.6098138.8738029.90881410.9038043.60481518.6598065.7728164.664 编号一致性编号一致性81710.6928348.87681811.45381916.31482018.98382115.40182314.70382711.9218283.60783011.6258339.25左4区域：表4.11左4区域排序结果编号一致性编号一致性79111.8048296.657927.79183112.7897948.77983210.2377997.74383511.2338036.0998366.4678056.06683710.84382211.1078388.3398246.17483919.2288259.7388408.01682612.116右区域：表4.12右区域排序结果编号一致性编号一致性88816.5628857.30488615.1199006.48288915.118915.72489212.3518972.7768939.3458962.2738909.3128951.4998989.2828878.6818998.3128947.682经过检验，根据地下的货运量、交通拥堵率和货物面积比的数值，我们运用层析分析法得到的排序第一的位置为一级节点。选取本区域二级节点时，需要满足两个条件，一是一级节点从地面收发货物总量上限为4000吨，二级节点从地面收发货物总量上限为3000吨；二是节点的服务半径在3公里范围内自由选择，选取的所有二级节点要全面覆盖该区域。所以，得到一级节点的个数为5个，二级节点数的个数为24个，具体位置如图4.3所示（大圆圈点为一级节点，小圆圈点为二级节点）。图4.3一、二级节点位置考虑到部分区域货运量与面积之比过小，若节点覆盖了某区域中心点即可视为对该区域进行了覆盖。又已知所有节点的服务半径在3公里范围内自由选择，节点间距离不受限制。所以，我们得到所有节点的服务范围如图4.4所示。-11- 图4.4所有节点的服务范围表4.13一级节点的具体位置一级节点坐标1(149951.9,1577738.28)2(146987.68,15418.21)3(149951.9,157738.28)4(138793.52,155638.13)5(14367.06,153444.63)根据各节点的拥堵率，在一级节点和二级节点的基础上，满足每个节点覆盖范围的要求，我们计算出每个节点地下物流最少货运量。因为计算得到的最少货运量为下限值，但在实际情况下，地下的实际货运量需要有预留，因此，我们在下限的基础上，给每个节点的货运量都进行了预留。每个区域的一级节点以及其覆盖的点、二级节点以及其覆盖的点的实际货运量如下表所示：左1区域：表4.14左1区域节点服务范围及实际货运量节点编号848（一级）843（二级）846（二级）860（二级）861（二级）862（二级）867（二级）一级节点编号848845覆盖范围85二级节点编号860实际货运量1200500实际货运量500二级节点编号861-12-服务范围845,850,851,853,849841,842,847844,852854,855856,864,865,857,858,868859,866,869二级节点编号843841覆盖范围842847实际货运量8覆盖范围二级节点实际货运量4600编号846实际货运量900实际货运量700二级节点编号862实际货运量500 覆盖范围二级节点覆盖范围854855863编号8675006001000实际货运量覆盖范围856864865400300500覆盖范围85785886846686914区域左2：表4.15左2区域节点服务范围及实际货运量节点编号880（一级）877（二级）878（二级）884（二级）一级节点覆盖范围二级节点覆盖范围编号880实际货运量2400服务范围871,873,883872,876,874,879875,881,870882二级节点覆盖范围编号877实际货运量1100二级节点覆盖范围编号878实际货运量3400实际货运量4编号884882300300400实际货运量77937588001000区域左3：表4.16左3区域节点服务范围及实际货运量节点编号820（一级）815（二级）821（二级）823（二级）793（二级）795（二级）834（二级）813（二级）服务范围819，818,811,806807,817809,816,804827,810801,802,795796,800833,828,830814,798实际货运量35002400-13- 一级节点覆盖范围二级节点覆盖范围二级节点覆盖范围编号826编号823827810编号实际货运量13300实际货运量实际货运量二级节点覆盖范围编号815807817实际货运量1500900400二级节点覆盖范围编号821809816804编号833834828830实际货运量13实际货运量8二级节点覆盖范围二级节点覆盖范围编号793801802795编号实际货运量8实际货运量二级节点覆盖范围868区域左4：表4.17左4区域节点服务范围及实际货运量节点编号839（一级）835（二级）826（二级）822（二级）808（二级）837（二级）794（二级）一级节点覆盖范围二级节点覆盖范围二级节点覆盖范围编号839840838实际货运量2300800700二级节点覆盖范围服务范围840,838831,836825,896824,803，805812,799832,829792,791编号835831836实际货运量1300700400二级节点覆盖范围编号826825896实际货运量3800实际货运量编号822824803805编号794792791实际货运量13实际货运量600600400二级节点覆盖范围编号812808799实际货运量二级节点覆盖范围编号837832829实际货运量900500600-14- 区域右：表4.18右区域节点服务范围及实际货运节点编号886（一级）888（二级）892（二级）893（二级）899（二级）898（二级）一级节点覆盖范围二级节点覆盖范围编号实际货运量编号实际货运量服务范围890807，889,887,891,885897,896894900895二级节点覆盖范围编号实际货运量二级节点覆盖范围编号实际货运量37实际货运量88689889887891885编号700实际货运量8928978960二级节点覆盖范围899900130800二级节点覆盖范围编号实际货运量8988951400100表4.19各物流园区到各一级节点的货运量O/D839（左四区）886（右区）820（左三区）848（左一区）880（左二区）总计园区12877.6493001.1787100.8364417.6391044.06318441.365园区26732.4913016.3964373.392256.0721790.17518441.365园区32094.9326481.6122793.0831825.6864717.56517912.878园区41176.6061716.2131330.0952936.8351294.0488453.797由图可知，物流园区1将所有货物直接运往左三区4号一级节点处后通过转运，物流园区2将所有货物运往左四区5号一级节点处后通过转运，物流园区3将右区的所有货物直接发给右区1号节点，将剩下所有货物发给左二区3号一级节点进行转运，物流园区4将所有货物运往左一区2号一级节点进行转运。由转运率公式：5mijmijj1j100% i1,2,3,4;j1,2,3,4,55mijj1其中，表示各园区，表示各一级节点，表示园区到节点的货运量，表示节点转运率，即从物流园区经由最近的一级节点转运至其他所有一级节点的货物量占该物流园区总-15- 出货量的百分比。故可得出转运路线和转运率如表4.20所示。表4.20转运路线及转运率节点编号12345运入货运量8453.79711431.26618441.36518168.5246481.612转出货运量5516.9626713.70111340.52911436.0330转运率0.652600.587310.614950.629440.000004.2.5问题一综述根据附件1中的坐标数据，我们针对115个点，计算它们之间距离小于3公里的所有点，并按照小于的点的数量对其排序，筛选出需要作为节点的点。接着，我们建立APH-PCA的多目标系统分析模型，将区域划分为5个小区域，对交通拥堵率、总货物量、货物面积比进行等级划分，依据相对重要性构建判断矩阵，采用方根法计算判断矩阵权重，接着进行一致性检验计算检查判断矩阵是否具有完全一致性，得到5个区域的节点排序情况。依据节点的覆盖范围、拥堵率及货运量，我们选择出5个一级节((149951.9,1577738.28)、(146987.68,15418.21)、(149951.9,157738.28)、(138793.52,155638.13)、(14367.06,153444.63))27个二级节点。根据拥堵率与货运量成正比的关系，我们可以计算出每个节点地下物流最少货运量，并且给地下的实际货运量有预留，得到每个区域的一级节点以及其覆盖的点、二级节点以及其覆盖的点的实际货运量。最后，根据一级节点的转运率计算公式，得到每个一级节点的转运率，即左1节点φ1=0.65260、左2节点φ2=0.58731、左3节点φ3=0.61495、左4节点φ4=0.62944、右节点φ5=0。4.3问题二4.3.1问题二分析在问题一地下物流网络节点群的基础上，选择合适的地下路线以建立该区域的“地下物流系统”网络。并在在转运率变化不大的情况下，若考虑优化网络，可适当调整一、二级节点位置，最终达到总成本最小的目标。除园区至一级节点的地下通道外其他地下通道均采用5吨的地下运输车辆，并且地下节点及通道内的货物每天要清仓。不考虑物流园区的建设及园区内的地下节点建设，但从园区出发的通道长度需要计入总成本。我们对问题一中选择的5个一级节点和24个二级节点建立遗传算法模型，对不同物流网络布局进行分析，如线状布局、环状布局、树状布局等，然后得到不同的物流网络线路。根据建立物流节点的成本、运输的成本、地下物流隧道的建设成本、运输的货物量的等要求，得到最满足服务的最佳物流网络图。4.3.2城市地下物流系统网络的布局根据网络路线与配送中心、物流中心之间连接形式的不同，ULS的网络布局形态有线状、环状、栅格状、树状和混合状布局等。(1)线状布局结构线形结构布局，是指城市地下物流网络路线，以一条单一的曲线连接各网络节点，此结构布局连接的网络节点不多，辐射范围不大，而且投资费用和开发难度不高，便于扩充，适合物流流量大而方向集中的城市地下物流系统.但对整个城市地下物流系统来-16- 说，各网络节点的连通度较低，运输容量也不大，若任一物流节点失效，将造成整个区域物流需求得不到满足，这种布局中连接的节点数量比较少，如图所示。图4.5线状布局图4.6环状布局(2)环状布局结构环形结构布局，是指城市地下物流网络路线，以一条首尾相接的曲线连接各网络节点，形成环形网络。该布局连接的节点位于环线上，由于环状连接中任意一条线路出问题，整个网络的连通都会受到影响，因此对环状布局来说，但是由于环形的网络连接，其中任何一个或多个网络节点或线路的增减，都可能会造成整个城市地下物流网络的运作瘫痪，每一条路线都特别关键。该网络布局结构连接了环线上的各网络节点，开发难度和成本低，网络节点数量也多，连通度较线性结构要好。如图3-8。（3）树形结构树状布局是指网络中的路线呈树状分布，，如图3.4所示。树形结构布局是指城市地下物流网络路线呈树枝状分布，该布局可以连接到较多数量的节点，但节点是由路线在一定程度上进行选择的，树状布局不构成回路。城市地下物流网络节点之间基本实现了点到点的连接，连通度较高，初步形成了简单的城市地下物流网络，但是网络路线对网络节点有一定的选择性，不利于各网络节点之间的高效互通，网络中一个或多个网络节点或网络路线的增减，都会影响到整个城市地下物流网络的运行，如3-9所示。图4.7树状布局图4.8栅格状布局图4.9混合状布局（4）栅格状布局结构栅格结构布局是指城市地下物流网络路线互相交叉，构成的方格网状比较规整的多边形几何结构，此布局结构连接的网络节点较多，网络节点之间的联通度和网络运输容量均较高，辐射面较广，开发难度和投资费用也较大，网络中一个或多个网络节点或网络路线的增减，基本不会影响到整个城市地下物流网络的正常运行，如图3-10所示。(5)混合布局结构混合布局是指将以上两种或两种以上的布局结构有机结合起来，构成的一个完整的网络结构。该结构网络节点和网络路线以比较随机的方式连接成网，可以连接更多的网络节点，网络的连通度和运输容量更高，开发难度也相对较高。如图3.5所示。4.3.3模型建立与求解—基于遗传算法和综合评分的地下物流网络优化模型在地下物流系统中，假设现需在N条备选线路中选出合理的地下物流轨道线路，使得这个地下物流系统可以完成配送任务，本文针对多少节点建立模型。设地下物流轨道线路k的长度为Ik；每公里的建设费用为CK，每公里的运输费用为DK，配送车在行驶过程中速度固定不变，设为v，货物从节点i出发到达节点j，线-17- 路长度记作Lij，货物运输量为Xij，C为建设投资成本，T为时间成本，Z为总成本，并引入k,ij，其中，1 线路k被选中（式4.6）k0 线路k未被选中1 节点i,j所在线路被选中（式4.7）ij0 节点i,j所在线未路被选中我们建立的数学模型如下：NCklk(ckdk)（式4.8）k1Lijh（式4.9）Tijxijtijpvj1i1p0mmjiminZmin(CT)mmNLij（式4.10）hminklkckdkijxijtijpvj1i1k1p0ji约束条件：i,jT，其中i,j是物流节点，T为所有节点的集合。LminklkLmax，Lmax和Lmin分别为地下物流运输线路总的长度最大值和最小k1N值，保证线路规模的合理性。1 线路k被选中（式4.11）k0 否则1 节点i,j所在路线选中（式4.12）ij0 否则遗传算法具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。用精确算法将会无法在可接受的时间内计算出全局最优解。遗传算法具有很好的收敛性，是一种相同计算精度下计算时间较少的全局优化算法。Step1:因为有N个节点可供选择，对其编号依次为：1，2，…，n，其含有0-1变量，编码为:{1,0,0,…，1,0}，其中，0表示该位置的节点未被选中，1则表示节点被-18- 选中。对单一供应点及其需求点进行编码，生成初始种群。Step2:当累计次数ｉ超过最大运输能力时，则将断点ｉ-1的节点记录下来，同时累计此时线路的长度。若未超过最大长度时，则在断点ｉ-１后插入０；若累计次数未达到i-１，就线路长度已达到最大长度，那么取此时线路有长度累计的次数为断点，并插入０，并将累积量清零。重复上述操作，直至在此序列末尾插入０为止。例如：节点1456352，生成断电后的序列为：140563052，则表示的含义为：线路一：供应点→节点1→节点4；线路二：供应点→节点5→节点6→节点3；线路三：供应点→节点5→节点2。Step3:将所有线路合并成一个完整的群体，在这个群体中进行交叉和变异运算，从而生成新的的完整物流网络群体。如此不断地进行“分割-并列-选择-合并”的操作，最终可求出多目标优化问题的最优解。Step4:根据题目中要求的各项指标因素地下物流隧道与节点的建设成本为：双向四轨（双洞）（10吨）造价5亿元/公里，双向双轨（双洞）（10吨）造价4亿元/公里，双向四轨（双洞）（5吨）造价3.5亿元/公里，双向双轨（双洞）（5吨）造价3亿元/公里，一级、二级节点的建设成本分别约为1.5亿元/个、1亿元/个；通道与节点的设计年限100年，年综合折旧率均为1%。并且，在满足物流货运量的基础上，我们对每个区域分别进行物流网络优化，得到以下的地下物流网路图：图4.10左1区域的网络构成图4.11左2区域的网络构成图4.12左3区域的网络构成图4.13左4区域的网络构成-19- 图4.14右区域的网络构成图4.15整个区域地下物流网络构成图根据物流系统网络的布局的原则，在转运率变化不大的情况下，考虑优化网络，我们适当调整一、二级节点位置，将物流网络图调整为星型或栅格型，调整后的网络图也满足成本及货运量的要求。-20- 图4.16右区域修改前图4.17右区域修改后图4.18左1区域修改前图4.19左1区域修改后图4.20左4区域修改前图4.21左4区域修改后已知每条线路所连节点（即即节点的链接情况）及节点间的运输货物量，经过问题一计算。网络中节点总数为m，ai为一级节点个数，aj为一级节点个数，wi为每个一级节点的建造成本，wj为每个二级节点的建造成本。在全天OD情况下（即18小时工作时间），双向双轨隧道的最大运输能力为Ymax。-21- mmWL1YijkYmax1，双向双轨建设成本i1j1Wl（式4.13）mmWL2YijkYmax1，双向四轨建设成本i1j1Yijk：线路k在节点（i,j）之间的运输能力。Xijk1,表示路线k经过路线(i,j)（式4.14）0,表示路线k不经过路线(i,j)mm建设成本：Z1PiWiPjWjWLlijkXijk；（式4.15）i1j1运输成本：Z2WLlijkXijk；（式4.16）i1j1k1mmlminZλ1Z1 λ2Z2；（式4.17）λλ21m1其中，（式4.18）YijkXijkYmaxi1根据题目中已知的数据，地下物流系统运行速度可以达到20-60公里/小时，一级节点与物流园区相连且采用10吨的大型车辆地下运输，从地面收发货物总量上限为4000吨，级节点从地面收发货物总量上限为3000吨。地下物流隧道与节点的建设成本为：双向四轨（双洞）（10吨）造价5亿元/公里，双向双轨（双洞）（10吨）造价4亿元/公里，双向四轨（双洞）（5吨）造价3.5亿元/公里，双向双轨（双洞）（5吨）造价3亿元/公里。并且，一级、二级节点的建设成本分别约为1.5亿元/个、1亿元/个；通道与节点的设计年限100年，年综合折旧率均为1%。表4.21表示的是各节点实际货运量，图4.22表示的是各级通道的位置和实际流量。-22- 图4.22各级通道的位置和实际流量表4.21各节点实际货运量节点编号实际货运量14822100节点编号实际货运量35①②③④⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮⑯⑰⑱⑲⑳㉑㉒㉓㉔㉕㉖㉗㉘㉙㉚㉛-23- 通过带入数据计算，得到：（1）采用双向双轨运输：总费用为208亿元；（2）采用双向四轨运输：总费用为197亿元；（3）采用双向双轨+双向四轨运输：总费用为182亿元。综上所述，我们采用双向双轨+双向四轨综合的运输方式，更大程度上缓解交通拥堵，并且降低物流成本，达到地下物流系统最优化。4.2.4问题二综述首先，我们分析了城市地下物流系统网络的各类布局情况，在问题一的基础上，且在转运率变化不大的情况下，建立基于遗传算法的模型，在满足物流货运量的基础上，我们对每个区域分别进行物流网络优化，得到优化后的地下物流网路图。基于问题一的各节点实际货运量，在优化后的网络图上得到最新的各节点实际货运量和各级通道的实际流量。接着，我们适当调整一、二级节点位置，将物流网络图调整为星型或栅格型，且调整后的网络图也满足成本及货运量的要求，通过比较对双向双轨运输和双向四轨运输总费用的比较，最终选择双向双轨+双向四轨综合的运输方式（总费用为182亿元），更大程度上缓解交通拥堵，并且降低物流成本，达到地下物流系统最优化。4.4问题三4.4.1问题三分析在前两问中的计算中，我们未对地下物流网络进行系统的考虑，由于地下物流系统在运作过程中的多样性和动态实时性，物流的风险会因蝴蝶效应而扩大，及时预知物流风险，选择合适的规避风险地下物流网络就尤为重要。在地下物流系统中会出现例如未考虑运输时间是否最短、某一方向的货运量剧增所带来的货物滞留以及某通道中断等问题。由于第二问中我们对每个节点的预留量都很大，所以可以忽略货运量剧增的问题。我们只需要分析出每个节点或通道出现问题时，所造成的影响的定量分析和比较，对影响较大的节点和通道在确保低成本的目标下，做出合适的预留量和预留通道，建立新的地下物流系统，并定性比较其与第二问中的地下物流网络的优劣。4.4.2模型建立与求解—基于重要度的失效负载分流模型和Dijkstra算法的最短路径模型根据问题一的分析，运输中断所在的路段在网络中的重要程度和负载能力大小对于地下物流系统中断后失联负载分配有重要影响，也影响ULS的抗风险能力。因此我们采用介数定义物流网络中每个节点路段的重要性。假设任意的一条路段eij，其介数为Bij，则：Bijpq(ij)（式4.19）pqpq其中，pq表示任意的节点vp和vq之间的最短路径的总数；pq(ij)表示任意节点vp和vq之间的所有最短路径中经过eij的路径个数，且piq。这结合物流OD需求运输的基本特点，将物流运输的任务经过该路径的次数作为路段重要度的表现，符合实际中物流特点。此外，我们给出路径的负载能力（即货运量）的定义，结合图论和介数的概念，得-24- 到：BijBiBj（式4.20）其中，节点介数的计算公式如下：pq(i)Bi（式4.21）pqpq其中，pq为任意节点vp和vq之间最短路径的总数；pq(ij)表示任意节点vp和vq之间的所有最短路径中途经节点vi的路径数量。接着，对节点两端的路径负载能力进行量化，假设任意边eij的负载能力Cij，CijBijkikj（式4.22）ki和kj分别代表运输路段两端节点vi和vj的度。假设任意边eij在节点F处突发失效，其任意邻接边e获得师兄负载的分配比例Pvi,vj，那么得到在运输方向性的新的分配比例，,vDF0pDijBDFDij（式4.23）Be其中，Dij为边eij的空间距离，DF为节点v与失效点处F的空间距离，为节点v端的失联邻接边的集合。那么，任意关联邻接边e获得的来自失效边eij上的负载分配量L为：LLijDFDijBeBLij（式4.24）我们根据节点和路径负载能力以及节点的复杂度（即节点之间空间距离和节点与其他节点的关系），计算出每个节点在该区域距离其他节点的重要度，如下表4.22所示：-25- 表4.22各节点的重要度节点编号实际货运量5节点编号实际货运量4⑥⑲66⑦⑳75㉑⑧107㉒⑨47㉓⑩610㉔⑪49㉕⑫410㉖⑬510㉗⑭1010㉘⑮69㉙⑯66㉚⑰57㉛⑱问题二中的网络是分步设计网络，并未从全局出发，根据对地下物流系统运行情况的分析，以及各个节点的重要度信息，我们对问题二的网络图增加节点个数，调整节点的位置或级别，通过增加、减少、改变路径的方法，縮短货物运输总里程（同时节省运输时间），降低运输成本，修改之后的地下物流运输网络图如图4.23所示。共计增加7个二级节点，并把23号二级节点变为一级节点。图4.23修改之后的地下物流运输网络图-26- Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。第一步（初始化）:令k0,P(0)Vs,T(0)V1,V2Vn,d(0)Vs0,d(0)Vi,ViVsrsentVs；第二步：令kk1，对所有的临时标号ViT(k1)计算；在起点为O终点为D的网络中，用f(0,i)(i1,2,,D)表示起点O到节点i的路线权值，那么最短的路径总是从起点O出发，沿着某条鲁到达节点i，再通过与i相连的路段i,j到达节点j，那么产生如下权值：f(O,j)min{f(O,i)f(i,j)}因此可采用以下的递推公式搜索从O到D的最短路线：令：f(1)(O,j)f(O,i)(iD)（式4.25）对t=2,3,...，f(t)(O,j)min{f(t1)(O,i)f(i,j)}(i1,2,..D)（式4.26）反复进行迭代计算，当迭代到第n步时，如果对所有的i=D，存在f(n)(O,j)f(n1)(O,i)（式4.27）(n){f(O,i)}就是从O到D的最短路径的权值。那么，将整个地下物流网络的二级节点均与一级节点相连，一级节点之间互相连接，得到如下的网络图4.24。图4.24各节点相连网络图以右区域为例，我们将右区域的一级节点和二级节点分别进行编号，如图所示。如果删除节点2（二级节点），通过Dijkstra算法的最短路径模型遍历该区域的所有点，-27- 得到最优的路径，即货物运输总里程最短（同时节省运输时间），且运输成本最低。通过多条不同路径对比，最终得到最优路径，如图所示4.25。图4.25删除节点后更新的网络图4.4.3问题三综述根据问题二中设计的网络，我们根据节点和路径负载能力以及节点的复杂度（即节点之间空间距离和节点与其他节点的关系），计算出每个节点在该区域距离其他节点的重要度。根据对地下物流系统运行情况的分析，以及各个节点的重要度信息，我们对问题二的网络图增加节点个数，调整节点的位置或级别，通过增加、减少、改变路径的方法，縮短货物运输总里程（同时节省运输时间），降低运输成本，共计增加7个二级节点，并把23号二级节点变为一级节点。当网络中某个节点失效时，通过Dijkstra算法获取最短路径算法，比较不同路径的费用，得到最优化的网络节点图。4.5问题四4.5.1问题四分析前三问只考虑了当前货运量下而建立的地下物流系统，由于此系统大部分工作在地下完成，所以改建困难。我们需要考虑可持续发展，做好扩容处理，使此系统满足30年的交通需求。正是由于其改建困难，所以在建设过程中，按每年的货运量所建设的节点和路线就不可再改变，我们必须在保证成本最低的情况下，选择当前网络以外的点和通道扩展此网络，所以我们只能选择迭代法每年进行最优路径迭代计算。最终确定此系统需要增加线网容量和节点数。4.5.2模型建立—基于贪婪算法的动态规划模型贪婪算法是一步步的进行求解，每一步都将最优化测度当做目标，对当前构造的不分解做一扩展，最终获得问题的完整解。所以它必须满足：①结果必须具有可行性，满足规划中所有的约束条件；②每一步结果必须是局部最优解；③结果的不可逆性，即上一步的最优解确定后，这一步的结果无法影响上一步规划结果，且不可改变。由于上一问中我们已经采用Dijkstra算法求解了当前日货运量的线路规划，即当前的最优物流网络。为了解决地下物流系统改建困难的问题，我们需要采用贪婪算法对已经规划的物流网络进行优化，使其满足近30年内的交通需求。根据题目所给，需求量每年呈5%增长，即根据当前货运量，我们可以预测出未来30年内每个区域每年的货运量，总货-28- 运量变化如下图4.26所示。图4.2630年内货运量变化曲线接下来我们需要在图中寻找合适的节点加入到此网络中。每年的货流量都在增加，所以此网络每年都在扩充，我们在进行迭代时，以贪婪的方式来对此网络进行扩充，也就是把不在网络中的并且成本最低的插入到网络中。图4.27当前货运量下的地下物流网络令地下物流网络为图GV,E，其网络的节点集合为Vt。mmWL1YijnYmax1，双向双轨建设成本i1j1WLn（式4.28）mmWL2YijnYmax1，双向四轨建设成本i1j1Yijk：第n年在节点(i,j)之间的线路运输能力，WLn1,表示第n年(i,j)间有路线（式4.29）Xijn0,表示第n年(i,j)间没有路线-29- 第n年建设成本：Z1nPinWinPjnWjnWLnlijnXijn；（式4.30）i1j1mm第n年运输成本：Z2nWLnlijnXijnWLnlijnXijn；（式4.31）i1j1mm我们的规划目标为：minZnλ1Z1n λ2Z2n其中，λ1λ21mYXY。（式4.32）ijnijnmaxi1若Xijn1，则Xijn11必须存在。接下来，我们运用蚁群算法进行迭代求解。算法实现流程如图4.28所示：图4.28基于蚁群算法求解流程图迭代求解后的地下物流网络如图4.29所示：-30- 图4.29迭代求解后的地下物流网络4.5.3问题四综述首先，我们计算出30年内货运量从76240.97346吨增长到313818.1846吨，根据第一问算出权重可以知道货运量对地下物流网络的影响比较大，所以在每年货运量5%增长的情况下，扩展和改进网络是必不可少的。然后我们建立了基于贪婪算法的动态规划模型，以每年的成本最低为目标，不断的在原有网络的基础上，增加节点和改进增加节点的路线。最后，利用蚁群算法不断迭代求解，得出一级节点增加了1个，二级节点增加了6个，以及可满足30年物流需求的地下物流网络如图4.29所示。五、模型的优缺点优点：1、充分运用了点—线—面—地下物流网络系统之间的关联性；2、在规划路径和改进路径的过程中，定量比较了不同类型网络布局的优缺点；3、在问题四中，本文充分考虑了地下物流网络改建困难问题，保证下一年的规划仅在上一年的基础上扩建，并不改变上一年的网络结构；4、考虑到长期成本和收益。缺点：1、只考虑了地下物流网络中部分影响因素的权重，并未将其他相关参数进行详尽的定量分析；2、在问题四中，利用蚁群算法进行迭代求解运算时间较长。参考文献[1]刘向东,何建敏,张岳峰.基于APH-PCA的应急调度系统多目标优化方法研究[J].西安电子科技大学学报.2010.3(20):46-50.[2]徐国峰.城市地下物流系统构架研究[D].华中科技大学.2012.[3]曾令慧.周爱莲,基于遗传算法的城市地下物流网络优化模型[J].交通科学与工程.2016.3(22):84-93.[4]周婷.周爱莲,基于时间成本的地下物流配送路线优化模型[J].物流工程与管理.2016.38(8):60-62.[5]张妍.随机环境下的地铁换乘问题两阶段优化模型[D].北京交通大学:2016.[6]MILLER-HOOKSED,mparisonsforapriori-31- andtime-adaptivedecisionsinstochastic,time-varyingnetworks[J].EuropeanJournalofOperationalResearch,2003,146(1):67-82.[7]tedhypergraphmodelforrandomtimedependentshortestpaths[J].EuropeanJournalofOperationalResearch.2000,123(2):315-324.附件：//问题1x=xlsread(\'C:UsersYoucansuccessDesktop11\',1,\'D6:D115\');y=xlsread(\'C:UsersYoucansuccessDesktop11\',1,\'E6:E115\');%数据提取%节点间的距离运算fori=1:110forj=1:110D(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);endend%3公里覆盖范围判别k=1;fori=1:110forj=i+1:110ifD(i,j)<=3000Dp(k,1)=i+790;Dp(k,2)=j+790;Dp(k,3)=D(i,j);k=k+1;endendend%货物量遍历fora=791:900shu(a-790,1)=a;shu(a-790,2)=0;fori=1:680if(Dp(i,1)==a)shu(a-790,2)=shu(a-790,2)+1;elseif(Dp(i,2)==a)shu(a-790,2)=shu(a-790,2)+1;endendendend%P=[1,1,9;1,1,7;1/9,1/7,1]判别矩阵的选取P=[1,2,6;1/2,1,3;1/6,1/3,1];-32- m=[];fori=1:3m(i,1)=(P(i,1)*P(i,2)*P(i,3))^(1/3);endsum=0;fori=1:3sum=sum+m(i,1);endk=1/sum;fori=1:3w(i,1)=k.*m(i,1);%获取权重因子end%一致性检验模型的实现Pw=P*w;sum2=0;fori=1:3sum2=sum2+(Pw(i,1)/w(i,1));endmax=1/3*sum2;CI=(max-3)/2;CR=CI/0.58;//问题2clc;clear;x=xlsread(\'C:UsersYoucansuccessDesktop11\',1,\'D6:D115\');y=xlsread(\'C:UsersYoucansuccessDesktop11\',1,\'E6:E115\');%数据获取%右区节点网络与分析x5=x(95:110);y5=y(95:110);xj5=x5([2,7,8,9,14,15]);yj5=y5([2,7,8,9,14,15]);plot(x5,y5,\'.\');holdonplot(xj5,yj5,\'ro\');plot([xj5(1)xj5(2)],[yj5(1)yj5(2)]);plot([xj5(3),xj5(4)],[yj5(3),yj5(4)]);plot([xj5(2),xj5(4)],[yj5(2),yj5(4)]);plot([xj5(2),xj5(5)],[yj5(2),yj5(5)]);plot([xj5(3),xj5(6)],[yj5(3),yj5(6)]);%左四区节点网络与分析x4=x([1,2,4,9,13,15,18,22,32,34:36,39,41,42,45:50]);y4=y([1,2,4,9,13,15,18,22,32,34:36,39,41,42,45:50]);plot(x4,y4,\'.\');xj4=x4([3,7,9,12,16,18,20]);-33- yj4=y4([3,7,9,12,16,18,20]);holdonplot(xj4,yj4,\'ro\');%左三区节点网络与分析x3=x([3,5,6:8,10:12,14,16,17,19:21,23:31,33,37,38,40,43,44]);y3=y([3,5,6:8,10:12,14,16,17,19:21,23:31,33,37,38,40,43,44]);plot(x3,y3,\'.\');xj3=x3([1,2,15,17,22,23,24,28]);yj3=y3([1,2,15,17,22,23,24,28]);holdonplot(xj3,yj3,\'ro\');%左二区节点网络与分析x2=x(80:94);y2=y(80:94);plot(x2,y2,\'.\');xj2=x2([8,9,11,15]);yj2=y2([8,9,11,15]);holdonplot(xj2,yj2,\'ro\');%左一区节点网络与分析x1=x(51:79);y1=y(51:79);plot(x1,y1,\'.\');xj1=x1([3,6,8,20:22,27]);yj1=y1([3,6,8,20:22,27]);holdonplot(xj1,yj1,\'ro\');%时间最优化fork=0:18%时间上限为18ift<(30+60*k)&&t>=(60*k)y=k*5.86-7.46*(t-60*k)/30;elseift>=(30+60*k)&&t<(60*k+60)y=k*5.86-7.46+13.32*(t-30-60*k)/30;%12分钟的车辆通行能力为不多于8辆%2.11-8.9-0.67=-7.46，22.89-8.9-0.67=13.32elsey=y;endendm=y;endy=0;%经济最优化-34- fork=0:20ift<(30+60*k)&&t>=(60*k)y=14+k*1.53-7.15*(t-60*k)/30;%初始化车辆数elseift>=(30+60*k)&&t<(60*k+60)y=14+k*1.53-7.15+8.68*(t-30-60*k)/30;elseendendy=y;m=y;end-35-
更多推荐
节点,物流,网络,货运量,区域,编号,系统,实际
发布评论