紧急疏散中最优抗出错路径选择模型与算法

疏散路径选择是紧急疏散中的重要问题，为了减小疏散人在紧急疏散过程中由于路径选择错误带来的损失，提出一对起讫点间最优抗出错路径选择模型。给出路径出错系数的定义，用以度量疏散人路径选择错误带来的疏散效率损失，并且设计了求解最优抗出错路径的DAE算法，证明该算法的时间复杂度为O（ mn2）。结果表明，选择最优抗出错路径作为疏散路径，能够有效地抵抗由于疏散人路径选择错误带来的损失，对提高突发事件下的疏散效率具有实际意义。     

道路修复条件下灾后应急资源配送LRP研究

灾后道路中断、道路通行可靠性减弱从根本上影响着救援工作的效率,文章通过在应急资源配送定位路径问题的基础上考虑对障碍道路进行修复。通过构建应急设施定位、障碍道路修复以及配送路径选择的综合优化模型,以应急救援的时间总成本最小为目标。集中考虑应急设施定位选址、修复障碍道路和选择配送路径的基础上,以时间总成本最小为目标函数,通过结合相关案例仿真与数据分析的基础上运用多吸引粒子群优化算法对模型进行求解,以期为灾后道路选择、提升道路通行可靠性和应急物资配送效率提供借鉴于理论指导。     

营救设备数量受限的应急疏散模型和算法

考虑在实际中可能面临着某些救援活动,必须借助于营救设备或者依赖营救人员的引导才能得以完成．针对这种情况,给出了设备数量受限的应急疏散模型．由于目标函数是疏散时间最小化,在考虑路径容量限制时,首先通过优先饱和最短路径来确定可行路径集合,把可行路径集合中的k短路作为初始解,再以每条路径上流量与旅行时间的比值流速作为更新路径的准则,每步迭代通过保留流速较大的路径来保存当前疏散时间最小的路径集合,从而确定疏散方案．最后通过算例验证了该算法的有效性和可行性．     

多波次导弹发射任务策略优化

针对第十四届中国研究生数学建模竞赛E题的多波次导弹发射中的规划问题展开研究.首先,简化各道路节点路径信息后通过Dijkstra算法和模拟退火算法,制定了整体最短暴露时间对应的具体发射点位及机动路线方案,得到最短暴露时间127.7h;再采用穷举法及模拟退火制定合理布设两个转载地域以及确定最优隐蔽节点的策略;最后,在考虑规避敌方打击以及单个发射装置最大暴露时间最短等其他因素下,将多目标优化问题转化为单目标优化问题.     

考虑道路修复的应急资源配送可靠路径选择问题研究

灾害发生后第一时间选择可靠路径完成应急资源的配送分发是应急救援快速展开的必要保障。本文考虑道路修复下的应急资源配送可靠路径规划问题,引入了道路中断和通行可靠性降低来描述灾难对应急资源配送交通路网的影响,以最大化配送效率为目标,构建了道路修复与应急资源配送可靠路径选择集成优化模型,给出了道路修复与可靠路径选择的全局优化方案;设计了多吸引子的粒子群优化模型算法,并结合仿真与分析,验证了模型和算法的有效性。模型与算法的研究对于突发事件下不确定交通路网应急资源配送决策具有很好的指导意义。     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

通行受限下需求可拆分的应急物资卡车-多无人机协同配送路径优化

研究通行受限情景下需求可拆分的应急物资卡车-多无人机协同配送路径优化问题,综合考虑灾区路网状况、卡车可途中发射/接受无人机、无人机单次起飞可配送多个需求点、需求可拆分等因素,以应急物资配送任务完成时间最短为目标,构建卡车-多无人机协同配送路径优化模型.根据问题与模型特征设计一种改进蚁群算法求解.实验结果表明:文章方法能合理分配卡车与无人机的配送任务,科学规划通行受限情景下需求可拆分的应急物资卡车-多无人机协同配送路径;卡车途中发射/接收无人机方式能有效缩短无人机飞行距离,减少卡车与无人机的协同时间,缩短通行受限情景下的应急物资配送时间,具有可行性、合理性与有效性.     

震后应急物流设施不确定失效情景下的LRP研究

针对震后应急物流设施不确定失效情景下的定位-路径问题,综合考虑灾区路网存在部分损毁、应急物资多方式配送与运达时间限制等因素,以应急物流设施最坏失效情景下的需求点覆盖期望最大、应急物资总配送时间最短为目标,采用情景建模方法构建多目标定位-路径问题的数学模型,并根据模型特点设计基于分层序列法的两阶段混合启发式求解算法,第一阶段设计改进贪婪算法进行应急物流设施定位分配,第二阶段采用蚁群算法优化应急物资配送路线。最后,通过算例验证了本文模型和算法的可行性与有效性。     

与运输路线有关的货物装载模型与算法

本文提出了一种同时考虑选择优化的运输路线的货物装载模型。该模型运用递归和试验式的方法以及选择最短运输路线的思想，得到在选定型号的运输工具上以装载量尽可能大以及运输路线为最短的运输装载方案。数值实验结果表明，该模型仍较大的应用价值。     

无预警紧急疏散中公交车辆路径的确定方法

针对无预警式紧急疏散中公交救援车辆的最佳路径确定问题,提出了一个非线性混合整数规划模型.模型不仅考虑了有接收能力限制的多避难所系统,还对如何处理具有不同载客上限的公交救援车进行了分析.利用添加了虚拟路段和节点的时空网络,在以加权的综合疏散时间最小为目标的同时实现了疏散伤亡最小化.通过分析实际疏散的实施过程,得到了一种产生模型可行解的有效方法.通过将时间滚动式的流量加载模式与经典遗传算法相结合,给出了新模型的实用解法.最后,通过算例验证了模型和算法的有效性.     

Path graphs

The concept of a line graph is generalized to that of a path graph. The path graph P_k(G) of a graph G is obtained by representing the paths P_k in G by vertices and joining two vertices whenever the corresponding paths P_k in G form a path P_k+1 or a cycle C_k. P₃-graphs are characterized and investigated on isomorphism and traversability. Trees and unicyclic graphs with hamiltonian P₃-graphs are characterized.     

Path Decomposition of Graphs with Given Path Length

A path decomposition of a graph G is a list of paths such that each edge appears in exactly onepath in the list.G is said to admit a {P_l}-decomposition if G can be decomposed into some copies of P_l,whereP_l is a path of length l-1.Similarly,G is said to admit a {P_l,P_k}=decomposition if G can be decomposed intosome copies of P_l or P_k.An k-cycle,denoted by C_k,is a cycle with k vertices.An odd tree is a tree of which allvertices have odd degree.In this paper,it is shown that a connected graph G admits a {P_3,P_4}-decompositionif and only if G is neither a 3-cycle nor an odd tree.This result includes the related result of Yan,Xu andMutu.Moreover,two polynomial algorithms are given to find {P_3}-decomposition and {P_3,P_4}-decompositionof graphs,respectively.Hence,{P_3}-decomposition problem and {P_3,P_4}-decomposition problem of graphs aresolved completely.     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

In the management and control of a vehicle fleet on a road network, the problem arises of finding the best route in relation to the mission of the fleet and to the typology of freight or users. Sometimes the route has to be adapted not only to current traffic conditions, but also to the physical, geometric and functional attributes of the roads, related to their urban location and environmental characteristics. This problem is approached here through an extension of the classic Shortest Path problem, named Resource Constrained Shortest Path problem (RCSP), where the resources are related to the road link attributes, assumed as relevant to the specific planning problem. A classification scheme of these attributes is first proposed and RCSP is described and reviewed. Next, a General Resource Constrained Shortest Path problem (GRCSP) is defined, which can be found in all cases where it is necessary to plan, statically or dynamically, the path of a vehicle and to respect a set of constraints expressed in terms of parameters and indices associated with the roads on the network. For this general problem a model has been formulated and a Branch and Cut solution approach is proposed. Computational results obtained on test and real networks during the experimentation of a fleet with low emission vehicles are also given. This revised version was published online in August 2006 with corrections to the Cover Date.     

On Models of Directed Path Graphs Non Rooted Directed Path Graphs

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a rooted tree. Clearly, rooted directed path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted directed path graphs. With the purpose of proving knowledge in this direction, we show in this paper properties of directed path models that can not be rooted for chordal graphs with any leafage and with leafage four. Therefore, we prove that for leafage four directed path graphs minimally non rooted directed path graphs have a unique asteroidal quadruple, and can be characterized by the presence of certain type of asteroidal quadruples.     

Path transferability of graphs

Path transferability of a graph is a notion that arises from the movement of a path along the graph, the behavior of the path seems as a train on a railroad. In this paper, we introduce two graph notions, transferability and reversibility, and study their properties.     

Path spectra for trees

The path spectrum of a graph is the set of lengths of all maximal paths in the graph. A set S of positive integers is spectral if it is the path spectrum of a tree. We characterize the spectral sets containing at most two odd integers (and arbitrarily many even ones) and obtain several necessary conditions for a set to be spectral. We show that for each even integer s≥2 at least 1/4 of all subsets of the set {2,3,…,s} are spectral and conjecture that all the subsets with at least 3s/4 integers are spectral.