Search

Airport runway assignment and gate assignment are both crucial problems for large multirunway airports. A cooperative schedule for the runway and gate can have a significant effect on airport ground operation efficiency and safety. This paper focuses on the joint assignment problem of runways and gates considering parking time differences and airline preferences. A quadratic model is established to reduce taxiing fuel consumption loss and increase the robustness of gate assignment. An improved branch-and-price algorithm is proposed by utilizing an improved pulse algorithm and various acceleration strategies to improve the solution performance. The actual flight data at an international hub airport are utilized to validate the proposed model. The results indicate that the joint assignment model can effectively reduce ground taxiing loss, optimize gate assignment robustness, and increase the utilization rate of contact gates. The proposed algorithm also achieves better computational accuracy and efficiency. • Proposed joint runway–gate assignment model can reduce the taxiing loss and gate robustness loss. • The model optimizes the taxiing and gate robustness while ensuring airline's preference. • A better solution is obtained by an improved branch-and-price method. • Experiments are designed to verify the value of the joint model. [ABSTRACT FROM AUTHOR]

Highlights • We propose a novel, computational efficient, dynamic ridesharing algorithm. • The algorithm is based on a linear assignment problem and a federated optimization architecture. • The algorithm offers high computational efficiency and quality of service. • Real-time ridesharing is shown to offer clear benefits even with partial adoption. • In multi-company scenarios negative effects could arise in terms of higher number of vehicles. Abstract In this paper, we propose a novel, computational efficient, dynamic ridesharing algorithm. The beneficial computational properties of the algorithm arise from casting the ridesharing problem as a linear assignment problem between fleet vehicles and customer trip requests within a federated optimization architecture. The resulting algorithm is up to four times faster than the state-of-the-art, even if it is implemented on a less dedicated hardware, and achieves similar service quality. Current literature showcases the ability of state-of-the-art ridesharing algorithms to tackle very large fleets and customer requests in almost near real-time, but the benefits of ridesharing seem limited to centralized systems. Our algorithm suggests that this does not need to be the case. The algorithm that we propose is fully distributable among multiple ridesharing companies. By leveraging two datasets, the New York city taxi dataset and the Melbourne Metropolitan Area dataset, we show that with our algorithm, real-time ridesharing offers clear benefits with respect to more traditional taxi fleets in terms of level of service, even if one considers partial adoption of the system. In fact, e.g., the quality of the solutions obtained in the state-of-the-art works that tackle the whole customer set of the New York city taxi dataset is achieved, even if one considers only a proportion of the fleet size and customer requests. This could make real-time urban-scale ridesharing very attractive to small enterprises and city authorities alike. However, in some cases, e.g., in multi-company scenarios where companies have predefined market shares, we show that the number of vehicles needed to achieve a comparable performance to the monopolistic setting increases, and this raises concerns on the possible negative effects of multi-company ridesharing. [ABSTRACT FROM AUTHOR]

• Deal with the schedule-based HSR passenger flow assignment problem for large-scale HSR networks with explicit consideration of continuous time-varying passenger demand and tight capacity constraints. • Establish the assignment model by destination-based arc flow variables and propose the Dantzig-Wolfe decomposition-based reformulation and algorithmic framework to reduce the memory requirement regardless of demand discretization precision in the master problem. • Design an efficient method incorporating the "rooftops" method to solve the sub-problem. This method is an effective technique to tackle the continuous time-varying demand, and its computational complexity improvement for solving sub-problem speeds up the entire solution process. • Prove the convergence of the passenger flow assignment solution with discrete demand would converge to that with continuous demand when the increasing discretization number tends to infinity. • Investigate the computational efficiency and solution quality of the proposed algorithm by three practical cases with different scales. This paper proposes an algorithm for solving the schedule-based passenger assignment problem, with explicit consideration of continuous time-varying demand and tight capacity constraints for large-scale high-speed railway (HSR) networks. We construct the space–time travel network and formulate the assignment model by destination-based arc flow variables, then design a Dantzig-Wolfe (D-W) decomposition-based algorithm to solve the large-scale model of this problem with less memory requirement and computational complexity. The sub-problem in each iteration can be solved as a single-source (destination) minimum cost flow problem without capacity constraint by the "rooftops" method, which provides an effective technique to tackle both continuous and discrete time-varying demand in the assignment problem. It is further demonstrated that the assignment solutions for discrete time-varying demand can converge to that for continuous time-varying demand with the increase of demand discretization number. Three real case studies with different HSR network scales show that the proposed algorithm is efficient in memory and computational complexity, especially when highly accurate solutions for passenger assignment on large-scale HSR networks are needed. [ABSTRACT FROM AUTHOR]

• A tailored Parallel Block-Coordinate Descent algorithm for user equilibrium problem. • A novel rule to group indices (OD pairs) into blocks. • Parallelize the computationally expensive components in the iGP algorithm. • Test computation efficiency of the proposed algorithm on large transport networks. This paper presents a Parallel Block-Coordinate Descent (PBCD) algorithm for solving the user equilibrium traffic assignment problem. Most of the existing algorithms for the user equilibrium-based traffic assignment problem are developed and implemented sequentially. This paper aims to study and investigate the parallel computing approach to utilize the widely available parallel computing resources. The PBCD algorithm is developed based on the state-of-the-art path-based algorithm, i.e., the improved path-based gradient projection algorithm (iGP). The computationally expensive components in the iGP are identified and parallelized. A parallel block-coordinate method is proposed to replace the widely used Gauss-Seidel method for the procedure of path flow adjustment. A new rule is proposed to group OD pairs into different blocks. The numerical examples show that the implemented PBCD algorithm can significantly reduce the computing time. [ABSTRACT FROM AUTHOR]

• Trackable column generation method for large-sized flight-to-gate assignment problems. • Use of submodularity in column generation in solving pricing problems. • Combination of exact algorithms and approximation algorithms in solving pricing problems. In this paper, we provide a column generation-based approach for solving the airport flight-to-gate assignment problem, where the goal is to minimize the on-ground portion of arrival delays by optimally assigning each scheduled flight to a compatible gate. Specifically, we use a set covering formulation for the master problem and decompose the pricing problem such that each gate is the basis for an independent pricing problem to be solved for assignment patterns with negative reduced costs. We use a combination of an approximation algorithm based on the submodularity of the underlying set and dynamic programming algorithms to solve the independent pricing problems. To the best of our knowledge, this is the first use of submodularity property to efficiently solve pricing problems and improve the performance of column generation algorithm. We show that the dynamic programming algorithm is pseudo-polynomial when there are integer inputs. We also design and employ a rolling horizon method and block decomposition algorithm to solve large-sized instances. Finally, we perform extensive computational experiments to validate the performance of our approach. [ABSTRACT FROM AUTHOR]