基于非概率可靠性的铁路应急设施选址-路径鲁棒优化

鉴于铁路应急设施选址研究中很难合理估计参数的概率分布或确定其隶属函数的问题,将选址-路径问题与区间非概率可靠性方法结合起来,以复杂网络理论为基础,提出网络节点区间权重的确定方法,同时考虑节点权重、边权及径权区间不确定性的共同作用,构建铁路应急设施选址节点加权网络。基于区间非概率可靠性理论及区间运算规则,提出路径的非概率可靠性度量及最优时间可靠度路径选择方法,建立节点权重、边权及径权均为区间数的非概率可靠性铁路应急设施选址-路径鲁棒优化模型,并给出了求解算法,确定了基于区间模型的铁路应急设施鲁棒选址的最优方案。算例表明,本文的优化方案能更好地保证救援的时间鲁棒性,能有效地规避不确定因素波动对设施选址的长期风险,具有很好的实际应用价值。     

基于系统最优的城市公交专用道网络设计模型及算法

设置公交专用道是实现"公交优先"的重要手段,然而,专用道设置将改变不同交通方式的道路通行能力,进而影响交通网络的整体性能。本文试图提出一种基于系统最优思想的公交专用道网络设计方法,既保证出行者的利益,又能满足交通系统总费用最优的目标。首先,本文分析了公交专用道设置对公交车辆和社会车辆这两种交通方式道路通行能力的影响,基于经典的BPR函数,构造了考虑专用道设置的不同方式的路段阻抗函数。其次,分析了出行者在多方式交通网络中的模式选择和路径选择问题,采用用户平衡理论分析了城市多方式交通平衡配流问题,给出了相应的变分不等式模型。更进一步,采用双层规划方法构造了基于系统最优的城市公交专用道网络设计模型,该模型以交通网络总费用最小为优化目标,并考虑了不同交通方式的平衡流量约束,采用分支定界算法对该双层规划模型进行求解。最后,通过一个简单算例对模型及算法的可行性和有效性进行了分析和验证。     

粒子群算法在VRP中的应用

物流配送车辆路径问题(VRP)属于NP—hard问题。谈文针对粒子群算法的局限性,引入了一种动态改变惯性权重的粒子群算法,在优化迭代过程中,惯性权重随粒子的位置和目标函数的性质而变化。实验结果表明,改进后的算法能使收敛速度显著加快,而且不容易陷入局部最优。     

震后伤员救援车辆两阶段规划模型及算法研究北大核心CSCDCSSCI

不确定情景下的应急物资配送和车辆路径优化问题是目前国内研究的一大热点,其中震后伤员运送车辆调度及路径优化问题随着近几年地震等自然灾害的频繁发生也逐渐引起人们的重视.本文采用聚合优化算法对灾区进行应急救援区域划分,建立了以总救援时间最短和相对综合救援权重值最大为目标的救援车辆两阶段数学规划模型,设计了带三角函数变异的离散型萤火虫优化算法进行求解,并与常规算法求解结果做了对比分析.通过算例进行模拟实验表明,所提出的模型和算法可以有效解决地震情景下的伤员救援车辆调度问题,且改进算法的全局搜索性能更优.     

基于PSO-PLS的组合预测方法在GDP预测中的应用

GDP预测是经济预测中一个非常重要的问题,随着经济的发展,对其预测精度的要求也越来越高.在考虑样本权重的基础上,提出一种微粒群算法与部分最小二乘回归方法相结合的组合预测方法,即采用微粒群方法对样本最优权重进行求解,在所得样本权重系数的基础上,用部分最小二乘回归方法确定组合预测的权重系数.将该方法用于中国GDP预测取得了较好的结果,与其他几种传统方法相比,预测精度有一定程度的提高,说明算法的有效性和可行性.     

时间依赖型多配送中心带时间窗的开放式车辆路径问题研究

本文研究了时间依赖型多配送中心带时间窗的开放式车辆路径问题,基于道路通行情况,建立车辆行驶速度时间函数;考虑车辆载重、里程限制与客户点服务时间窗的约束,建立混合整数规划模型,目标函数为最小化车辆总成本,具体包括车辆行驶时间成本和车辆固定发车成本;提出了一种二维编码方式的混合遗传算法,针对混合遗传算法设计了多分区段单点交叉策略、动态插入算子及局部搜索策略;最后,基于Solomon VRPTW基准数据集生成27个测试算例,使用混合遗传算法进行求解。数值实验结果表明,考虑道路通行情况,选择合理的出发时间,避免拥堵时段进行配送服务,能明显减少车辆的总行驶时间,且验证了混合遗传算法能够获得问题的满意解。     

基于最小偏差组合权重的突发事件应急能力评价模型

在突发事件应急能力评价问题中存在着不同评价方法的冲突性,即群决策评价结果的方法依赖性问题。本文以高速公路突发事件应急能力评价为研究对象,提出了基于最小偏差组合权重的评价模型。首先,系统地分析了高速公路突发事件应急能力的评价问题,建立了基于过程管理的高速公路突发事件应急能力评价的指标体系。根据语言评价指标分别运用二元语义层次分析法、G1主观赋权法和基于熵值法的二元语义赋权法等三种方法确定各评价指标的权重,然后综合各种评价方法构建了基于最小偏差的组合权重线性规划模型,确定准则层的最优复合权重,得出高速公路应急能力的评价值。最后,以上海"9·14"重大道路交通事故作为应急能力评价的分析案例,比较了不同评价模型的结果,并对评价指标进行敏感性分析。研究结果表明,基于最小偏差组合权重的评价模型能够在多个评价模型中达到最大的一致性,从而有效地减少了群决策中不同主客观评价方法的"极化"效应。     

平面信号交叉口通行能力及其分析应用

文章回顾了通行能力的研究方法,简要分析并评述了几个国内外常用的通行能力研究方法,最后根据我国实际情况运用停车断面法来研究实际道路交叉口的通行能力。论文通过对淮安市健康路-淮海路平面信号交叉口实地调查数据的分析计算得到了该交叉口的通行能力结果,最后根据交叉口实际情况分析了提高该平面信号交叉口通行能力的方法和措施。     

物理-社会耦合系统下震后多方协同救援的微分博弈模型

地震灾害救援系统是一个涉及道路通行能力和多方参与的物理-社会复杂耦合系统。其中,物理系统中道路受损是影响救灾物资运输的重要因素之一,社会系统中政府和社会力量的协同治理成效决定了救灾效果。为提高物资运输效率和灾区救灾量,本文考虑道路通行能力构建政府和社会组织协同运输非合作救援模式、协同合作救援模式以及政府补贴模式的微分博弈模型,计算了三种模式下多方努力水平、补贴比例、救灾量和系统均衡收益。研究发现,在一定条件下,政府补贴作为一种激励机制,可提高社会组织救灾努力水平、实现双方救灾效益的帕累托改进。社会系统中三种救灾模式具有不同的耦合效果。其中,协同合作救援最优策略及整体最优收益均严格优于非合作和政府补贴两种模式。     

考虑人车混采的道路信息采集的路径规划研究

本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题,精确求解算法无法在合理时间内得到问题的最优解,因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本;考虑到实际采集问题的大规模特性,在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。     

基于Dijkstra-PD-ACO算法的大城市公交线路优化与评价方法研究

城市公交线路的布设受到诸多影响因素的作用,单纯的追求线路单一指标的"最优"在实际公交线路优化时往往难以取得满意的效果。首先针对传统公交线路优化算法在求解线路优化问题中存在的不足,基于蚁群优化算法的寻优特性,结合Dijkstra算法在局部路径寻优中的优点,提出了Dijkstra蚁群混合优化算法。其次对于线路优化所得到的可行备选方案集,基于分层聚类主成分分析评价法进行优化效能评价。最后以合肥市一环内公交线路优化为实例进行验证。结果表明, 本文提出的方法在兼顾客流密度最大、出行路径最短的同时给出了有效公交线路备选方案,优化结果也符合合肥市的实际情况。同时,该方法对我国大中城市公交线网优化问题的研究具有一定的借鉴意义。     

A Genetic Algorithm for the Weight Setting Problem in OSPF Routing

With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most commonly used intra-domain Internet routing protocol (IRP). Traffic flow is routed along shortest paths, splitting flow at nodes with several outgoing links on a shortest path to the destination IP address. Link weights are assigned by the network operator. A path length is the sum of the weights of the links in the path. The OSPF weight setting (OSPFWS) problem seeks a set of weights that optimizes network performance. We study the problem of optimizing OSPF weights, given a set of projected demands, with the objective of minimizing network congestion. The weight assignment problem is NP-hard. We present a genetic algorithm (GA) to solve the OSPFWS problem. We compare our results with the best known and commonly used heuristics for OSPF weight setting, as well as with a lower bound of the optimal multi-commodity flow routing, which is a linear programming relaxation of the OSPFWS problem. Computational experiments are made on the AT&T Worldnet backbone with projected demands, and on twelve instances of synthetic networks.     

Network Reconfiguration for Increasing Transportation System Resilience Under Extreme Events

Evacuating residents out of affected areas is an important strategy for mitigating the impact of natural disasters. However, the resulting abrupt increase in the travel demand during evacuation causes severe congestions across the transportation system, which thereby interrupts other commuters' regular activities. In this article, a bilevel mathematical optimization model is formulated to address this issue, and our research objective is to maximize the transportation system resilience and restore its performance through two network reconfiguration schemes: contraflow (also referred to as lane reversal) and crossing elimination at intersections. Mathematical models are developed to represent the two reconfiguration schemes and characterize the interactions between traffic operators and passengers. Specifically, traffic operators act as leaders to determine the optimal system reconfiguration to minimize the total travel time for all the users (both evacuees and regular commuters), while passengers act as followers by freely choosing the path with the minimum travel time, which eventually converges to a user equilibrium state. For each given network reconfiguration, the lower‐level problem is formulated as a traffic assignment problem (TAP) where each user tries to minimize his/her own travel time. To tackle the lower‐level optimization problem, a gradient projection method is leveraged to shift the flow from other nonshortest paths to the shortest path between each origin–destination pair, eventually converging to the user equilibrium traffic assignment. The upper‐level problem is formulated as a constrained discrete optimization problem, and a probabilistic solution discovery algorithm is used to obtain the near‐optimal solution. Two numerical examples are used to demonstrate the effectiveness of the proposed method in restoring the traffic system performance.     

“货到人”拣选系统中AGV路径规划与调度研究

本文在电商行业快速发展及人工智能不断成熟的背景下,对智能仓库中采用“货到人”拣选系统的AGV(Automated Guided Vehicle)调度优化问题进行研究,此问题需同时考虑单AGV的路径规划及多AGV间的碰撞避免。基于此,本文提出了两阶段优化算法,首先分别采用数学模型求解和基于货架优先级的任务分配算法得到AGV的货架搬运任务序列,并根据AGV行驶规则生成初始路径。然后设计碰撞检测及避免算法对可能发生冲突的路径交叉点进行主动避撞调度。当发生突发情况时(如设备故障),采取实时重调度措施进行被动路径调整以获得全局AGV无碰路径。最后基于两阶段算法分析了两种AGV搬运任务分配策略的适用情况,并给出了最优的AGV数量配置建议。实验结果表明,本文算法能够调度100台AGV在配备有2015个货架、10个作业平台的仓库中完成100个订单的拣选作业。本研究可为企业采用“货到人”拣选系统实现多AGV的协同调度提供理论依据和实践指导。     

Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs

For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP₂) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time O(NlogN) for finding a minimum weight non-separating path between two given nodes in a grid graph of N nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP₂ problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP₂ problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows.     

Traffic engineering and congestion control for open shortest path first networks

Open shortest path first (OSPF) is the most widely used intra-domain Internet routing protocol. The OSPF protocol directs the Internet traffic along the shortest paths that are defined by the links weight. Traffic engineering is responsible for improving the network performance, for instance, the objective function that minimizes the maximal link utilization which is usually adopted to avoid the network congestion. This paper formulates the model of OSPF routing, and further evaluates the performance of different approaches. We also propose a heuristic algorithm to solve the routing problems by optimizing OSPF weights. Computational results indicated that the proposed algorithm could lead to good load balancing, and make efficient utilization of network resources.     

Path optimization for joint distribution of medical consumables under hospital SPD supply chain mode

The distribution of medical consumables inside the hospital is an important part of the daily operation of the hospital, which directly affects the operating efficiency of the entire hospital. Under the hospital SPD supply chain mode, the medical medicinal materials distribution nodes of various departments, pharmacies and warehouses of the hospital constitute the logistics distribution network of SPD central warehouse-secondary warehouse-consumption point. Considering the influence of time, distance and carrying vehicle on the distribution route of medical consumables in the hospital, the optimal distribution model of medical consumables under the hospital SPD supply chain mode was established with the minimum distribution cost of the hospital. The corresponding GA is designed and solved by MATLAB programming software. According to the established path optimization model, the distribution path optimization of medical consumables in a hospital in Shanghai is realized. The results show that the model is in line with the actual needs of the hospital; the algorithm is validated and the convergence speed is fast; compared with the traditional distribution path of medical consumables in the hospital, It is found that the optimized hospital medical consumables joint distribution path reduces logistics costs and improves the efficiency of distribution services. This article optimizes the joint distribution route of medical consumables in hospitals, promotes the organic combination of hospital SPD supply chain model and hospital operation structure, and promotes the modernization process of Chinese hospitals.

     

基于ART及多风险规避的交通网络均衡模型

随着对交通系统不确定性认识的深入,以绝对理性为基础的“期望效用理论”在风险环境下的路径选择分析中显示出局限性,而“预期后悔理论”则为之提供了新的分析思路.将预期后悔理论应用到风险环境下的路径选择分析中,将出行者一致风险规避的假设扩展到多风险规避,建立了基于后悔理论及多风险规避出行特征的交通网络随机用户均衡变分不等式模型,并给出了求解算法.通过算例分析发现,后悔心理对出行者的路径选择并不总是显著的.在非风险环境及极端风险环境中,后悔心理对出行者的路径选择影响是微弱的,但是当环境处于极端风险与非风险之间时,后悔心理对出行者路径选择有着较为显著的影响.     

Dealing with the White Death: Avalanche Risk Management for Traffic Routes

This article discusses mitigation strategies to protect traffic routes from snow avalanches. Up to now, mitigation of snow avalanches on many roads and railways in the Alps has relied on avalanche sheds, which require large initial investments resulting in high opportunity costs. Therefore, avalanche risk managers have increasingly adopted organizational mitigation measures such as warning systems and closure policies instead. The effectiveness of these measures is, however, greatly dependent on human decisions. In this article, we present a method for optimizing avalanche mitigation for traffic routes in terms of both their risk reduction impact and their net benefit to society. First, we introduce a generic framework for assessing avalanche risk and for quantifying the impact of mitigation. This allows for sound cost-benefit comparisons between alternative mitigation strategies. Second, we illustrate the framework with a case study from Switzerland. Our findings suggest that site-specific characteristics of avalanche paths, as well as the economic importance of a traffic route, are decisive for the choice of optimal mitigation strategies. On routes endangered by few avalanche paths with frequent avalanche occurrences, structural measures are most efficient, whereas reliance on organizational mitigation is often the most appropriate strategy on routes endangered by many paths with infrequent or fuzzy avalanche risk. Finally, keeping a traffic route open may be very important for tourism or the transport industry. Hence, local economic value may promote the use of a hybrid strategy that combines organizational and structural measures to optimize the resource allocation of avalanche risk mitigation.     

考虑交叉口影响的逆向路段选择优化

逆向车道作为提高路网整体通行能力的一种交通组织策略，已在疏散交通组织中得到了大量应用。以往关于逆向车道设置路段选择的研究，大多没有考虑交叉口影响。在拥挤的城市道路网中，这种忽略会导致过高的预期疏散通行能力估计。本文考虑交叉口影响，建立改进的最大流及其关键边模型，对疏散路网中逆向路段的选择进行优化。将交叉口分转向的通行能力表示为节点的方向性权重，将疏散路网抽象为方向性点权网络。定义该类网络中的最大流增流关键边，即一旦扩容会使网络最大流流值增加幅度最大的边。通过在方向性点权网络中寻找最大流增流关键边，得到考虑交叉口影响时疏散路网中对应的逆向车道设置路段。对经典最大流问题求解算法进行相应的改进，给出方向性点权网络中寻找最大流增流关键边的有效算法，并通过一个数值算例进行测试和仿真分析。结果表明，在考虑交叉口影响的情况下，得到的逆向车道设置路段更为合理，疏散时对其进行扩容能更有效地压缩总疏散时间。