共查询到19条相似文献,搜索用时 343 毫秒
1.
2.
针对现有的最优路径选择模型结果很好但搜索速度相对较慢的问题,为了提升最优路径的搜索速度,并获取满意路径,采取空间索引技术,对最优路径问题进行了模型和算法的改进,以运输时间最短、算法搜索速度最快为目标进行了研究。通过与常见算法比较,空间索引技术在路径选择的应用上取得较满意的效果。 相似文献
3.
4.
5.
乘务排班计划是城市轨道交通运输计划的重要组成部分,高效的排班计划可以有效降低城市轨道交通运营成本。本文基于列生成算法,构建以班次数最小为目标的乘务排班模型。列生成算法的限制主问题采用集合覆盖模型,通过建立网络图模型,将定价子问题转化为带资源约束的最短路问题。提出了考虑复杂约束的改进的邻接矩阵构建方法,采用Floyed算法求得最短路径集合。在求解具有最小检验数的新班次时,提出了基于工作效率和工作时长综合惩罚的优化规则,以提高新班次集合的质量。最后求解0-1整数规划问题,即从可行班次集合中找到满足乘务片段全覆盖约束的最优子集,构成最终的排班方案。案例结果表明本文模型能够显著地减少乘务班次数,同时各项指标均有所改善。 相似文献
6.
7.
8.
9.
10.
11.
This paper proposes an alternative algorithm to solve the median shortest path problem (MSPP) in the planning and design of urban transportation networks. The proposed vector labeling algorithm is based on the labeling of each node in terms of a multiple and conflicting vector of objectives which deletes cyclic, infeasible and extreme-dominated paths in the criteria space imposing cyclic break (CB), path cost constraint (PCC) and access cost parameter (ACP) respectively. The output of the algorithm is a set of Pareto optimal paths (POP) with an objective vector from predetermined origin to destination nodes. Thus, this paper formulates an algorithm to identify a non-inferior solution set of POP based on a non-dominated set of objective vectors that leaves the ultimate decision to decision-makers. A numerical experiment is conducted using an artificial transportation network in order to validate and compare results. Sensitivity analysis has shown that the proposed algorithm is more efficient and advantageous over existing solutions in terms of computing execution time and memory space used. 相似文献
12.
Abstract Dial's algorithm is one of the most effective and popular procedures for a logit-type stochastic traffic assignment, as it does not require path enumeration over a network. However, a fundamental problem associated with the algorithm is its simple definition of ‘efficient paths’, which sometimes produces unrealistic flow patterns. In this paper, an improved algorithm based on the route extension coefficient is proposed in order to circumvent this problem, in which ‘efficient paths’ simultaneously consider link travel cost and minimum travel cost. Path enumeration is still not required and a similar computing efficiency with the original algorithm is guaranteed. A limitation of the algorithm is that it can only be applied to a directed acyclic network because a topological sorting algorithm is used to decide the order of the sequential calculation. A numerical example based on the Beijing subway network illustrates the effectiveness of the proposed algorithm. It is found that it is able to exclude most unrealistic paths, but include all reasonable paths when compared with path enumeration and the original Dial's algorithm. 相似文献
13.
Unfortunately, situations such as flood, hurricanes, chemical accidents, and other events occur frequently more and more. To improve the efficiency and practicality of evacuation management plan, an integrated optimization model of one‐way traffic network reconfiguration and lane‐based non‐diversion routing with crossing elimination at intersection for evacuation is constructed in this paper. It is an integrated model aiming at minimizing the network clearance time based on Cell Transmission Model. A hybrid algorithm with modified genetic algorithm and tabu search method is devised for approximating optimal problem solutions. To verify the effectiveness of the proposed model and solving method, two cases are illustrated in this paper. Through the first example, it can be seen that the proposed model and algorithm can effectively solve the integrated problems, and compared with the objective value of the original network, the network clearance time of the final solution reduces by 47.4%. The calculation results for the realistic topology and size network of Ningbo in China, which locates on the east coast of the Pacific Ocean, justify the practical value of the model and solution method, and solutions under different settings of reduction amount of merging cell capacity embody obvious differences. Copyright © 2015 John Wiley & Sons, Ltd. 相似文献
14.
Using a sample-based representation scheme to capture spatial and temporal travel time correlations, this article constructs an integer programming model for finding the a priori least expected time paths. We explicitly consider the non-anticipativity constraint associated with the a priori path in a time-dependent and stochastic network, and propose a number of reformulations to establish linear inequalities that can be easily dualized by a Lagrangian relaxation solution approach. The relaxed model is further decomposed into two sub-problems, which can be solved directly by using a modified label-correcting algorithm and a simple single-value linear programming method. Several solution algorithms, including a sub-gradient method, a branch and bound method, and heuristics with additional constraints on Lagrangian multipliers, are proposed to improve solution quality and find approximate optimal solutions. The numerical experiments investigate the quality and computational efficiency of the proposed solution approach. 相似文献
15.
The formulation of the static user equilibrium traffic assignment problem (UETAP) under some simplifying assumptions has a unique solution in terms of link flows but not in terms of path flows. Large variations are possible in the path flows obtained using different UETAP solution algorithms. Many transportation planning and management applications entail the need for path flows. This raises the issue of generating a meaningful path flow solution in practice. Past studies have sought to determine a single path flow solution using the maximum entropy concept. This study proposes an alternate approach to determine a single path flow solution that represents the entropy weighted average of the UETAP path flow solution space. It has the minimum expected Euclidean distance from all other path flow solution vectors of the UETAP. The mathematical model of the proposed entropy weighted average method is derived and its solution stability is proved. The model is easy to interpret and generalizes the proportionality condition of Bar-Gera and Boyce (1999). Results of numerical experiments using networks of different sizes suggest that the path flow solutions for the UETAP using the proposed method are about identical to those obtained using the maximum entropy approach. The entropy weighted average method requires low computational effort and is easier to implement, and can therefore serve as a potential alternative to the maximum entropy approach in practice. 相似文献
16.
Tao Xing Xuesong Zhou 《Transportation Research Part B: Methodological》2011,45(10):1660-1679
Path travel time reliability is an essential measure of the quality of service for transportation systems and an important attribute in travelers’ route and departure time scheduling. This paper investigates a fundamental problem of finding the most reliable path under different spatial correlation assumptions, where the path travel time variability is represented by its standard deviation. To handle the non-linear and non-additive cost functions introduced by the quadratic forms of the standard deviation term, a Lagrangian substitution approach is adopted to estimate the lower bound of the most reliable path solution through solving a sequence of standard shortest path problems. A subgradient algorithm is used to iteratively improve the solution quality by reducing the optimality gap. To characterize the link travel time correlation structure associated with the end-to-end trip time reliability measure, this research develops a sampling-based method to dynamically construct a proxy objective function in terms of travel time observations from multiple days. The proposed algorithms are evaluated under a large-scale Bay Area, California network with real-world measurements. 相似文献
17.
The improvement and expansion of public transport is an increasingly important solution to the high congestion costs and worsening environmental impacts of the car dominated transport systems seen in many cities today. The intelligent design of stop locations is one way to improve the quality of PT and thereby improve its ridership. Stop placement is a relatively complex task as it involves a trade-off between two competing goals; accessibility and operation; however this trade-off can be made explicit using an appropriate mathematical model. Many such models have been developed in the literature, however none consider the effects of uneven topography. Topography is an important but often neglected factor in the design of public transportation systems, with the potential to have a significant impact on the accessibility, operation and planning of a transit service. In this work a mathematical modelling approach to bus stop placement is developed which includes considerations of uneven topography in three ways; (1) Its effect on walking speed; (2) Its impact on the attractiveness of an access path to a transit service; and (3) Its effect on acceleration rates at stops. Because of the complexity of the model developed, a heuristic evolutionary algorithm’ is employed to approximate an optimal solution to the model. Finally, the model and solution method are applied to a case study in the Auckland CBD area in New Zealand. 相似文献
18.
We address the problem of simultaneously scheduling trains and planning preventive maintenance time slots (PMTSs) on a general railway network. Based on network cumulative flow variables, a novel integrated mixed-integer linear programming (MILP) model is proposed to simultaneously optimize train routes, orders and passing times at each station, as well as work-time of preventive maintenance tasks (PMTSs). In order to provide an easy decomposition mechanism, the limited capacity of complex tracks is modelled as side constraints and a PMTS is modelled as a virtual train. A Lagrangian relaxation solution framework is proposed, in which the difficult track capacity constraints are relaxed, to decompose the original complex integrated train scheduling and PMTSs planning problem into a sequence of single train-based sub-problems. For each sub-problem, a standard label correcting algorithm is employed for finding the time-dependent least cost path on a time-space network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted on a small artificial network and a real-world network adapted from a Chinese railway network, to evaluate the effectiveness and computational efficiency of the integrated optimization model and the proposed Lagrangian relaxation solution framework. The benefits of simultaneously scheduling trains and planning PMTSs are demonstrated, compared with a commonly-used sequential scheduling method. 相似文献