With the rapid improvement of the national economy in recent years, people's travel demand has increased, bringing increasingly severe pressure on the current urban traffic signal system relying on traditional non-intelligent traffic lights. The significant increase in the complexity of the traffic network has led to the development of traffic signal control from a single-point problem to a system engineering problem, and the development of artificial intelligence technology brings more methods to dealing with urban traffic signal control. Swarm intelligence methods, represented by multi-agent reinforcement learning, have been widely used in traffic signal control and optimization, including traffic light control, autonomous driving, and vehicle-road collaboration. Compared to traditional methods, multi-agent reinforcement learning can empower the intelligence of traffic signal systems while implementing large-scale traffic signal system collaboration to improve the efficiency of urban traffic operations. The various components involved in urban transportation must collaborate in the vision of intelligent urban traffic. Multi-agent reinforcement learning is of great research value in urban traffic signal control and optimization. This paper will systematically introduce the basic theory of multi-agent deep reinforcement learning and its use in urban traffic signal optimization, summarize the existing approaches and analyze the drawbacks of each method. In addition, this paper will outline the challenges of multi-agent reinforcement learning methods for urban traffic signal optimization. Then the paper points out possible future research directions to promote the development of multi-agent reinforcement learning methods in urban traffic signal optimization.
Bi-level programming is a typical NP-Hard problem. It is a nonconvex optimization problem with upper and lower hierarchical structure and contains optimization problems in constraint conditions. This paper systematically reviews the researches and applications of bi-level programming in the context of urban transport, focusing on transportation network design problem and OD estimation/adjustment problem. Firstly, the domestic and international research topics and evolution progress are summarized by bibliometrics. Secondly, it takes pioneering research as the clue to look back upon important researches, the first systematic review paper, the first doctoral dissertation, the first Transportation Research Part-B's issue, and the first review paper in Chinese are introduced. Thirdly, the recent development of network design problems including road, transit and multi-modal, and the static and dynamic OD estimation problems are expounded. Fourthly, some general solutions are concluded, and the trends of solutions are discussed, the relationship between bi-level programming and MPEC is expressed. Finally, it points out three opportunities and challenges in the future should be addressed, including exploring and revealing of smart transportation, the optimization of modeling architecture, and building a computing platform to share and interact.
With the development of the social economy and the progress of human production mode, the traffic management system provides a series of subjects for operations research. The operational research methods are widely applied in the field of traffic network modeling, and they also occupy some important positions in the intelligent traffic management system. To solve the problems existing in the traffic system, we can make full use of various branches of operations research, which can effectively ensure the efficiency and orderliness of transportation in real life. In this paper, we first introduce several solution models for solving traffic flow estimation problems and then review the existing research from seven aspects: linear programming, integer programming, dynamic programming, graph theory, statistical, heuristic approach, and machine learning method. Finally, to provide more references for transportation managers and researchers, we discuss the development directions and related problems for traffic flow estimation models and propose the potential problems that need to be further investigated and solved.
A charging and discharging scheduling strategy for electric bus charging station considering the configuration of energy storage system is proposed to address the management difficulties of high load pressure and high charging operation cost caused by disorderly charging at electric bus charging station. Firstly, a mixed integer programming model is established to minimize the overall daily cost of the charging station and to coordinate the charging of the electric bus and the charging and discharging of the energy storage system. The capacity of energy storage system is optimized and sensitivity analysis is performed. Secondly, the nonlinear charging characteristic of the onboard lithium battery is fully considered and the piecewise linear approximation method is used to describe the charging profile of battery SOC. Finally, model verification and case study are made based on the historical travel and charging records of an electric bus charging station in Chengdu. The findings demonstrate that the suggested charging scheduling strategy can successfully lower the overall cost of the charging station, ease load pressure of the grid, prolong the life of the lithium battery and enhance the economy of bus charging management and power grid stability.
Ride-sharing can effectively alleviate traffic congestion and parking pressure by improving the utilization of vehicle seat capacity and reducing the number of traffic travels. Considering setting parking and ride-sharing meeting points, a traffic management scheme for a linear monocentric city was proposed. Under the situation of parking and ride-sharing, the travel costs of solo driver, ride-sharing driver and ridesharing passenger were analyzed, and a route choice model based on stochastic user equilibrium was constructed. A bi-level programming model was proposed to minimize the total travel cost by optimizing the ride-sharing parking charge. Based on the method of sensitivity analysis, the Frank-Wolfe and BFGS algorithms were applied respectively to solve the proposed bi-level programming model. Finally, the results of numerical analysis show the effectiveness of the proposed model and algorithm.
This paper proposes a novel spatial equilibrium model integrating station locations of intercity high-speed rail (HSR), which allows for households.intracity commuting, intercity migration, and intercity commuting. The proposed model explicitly investigates the effects of station location on urban spatial structure, households. choices of residence and workplace, and housing market. We systematically analyze and summarize all spatial structures for two cities, as a result of a great diversity of station location. The analysis result reveals that station location will affect households.choices of residence and workplace, and administration will underestimate travel demand when ignoring intercity commuting due to population migration. Numerical results indicate that although the reconstruction of existing stations is not the best scheme for household utility, it may be the best one for social welfare from the perspective of saving demolition costs. It is also found that the improvement of intercity transport between specific cities may lead to population migration to lower-income cities and then flatten the urban population and housing rental prices of higher-income cities.
In this paper, we study the multi-model traffic equilibrium problem of private transportation and public transportation, which is modeled as a separable monotonous variational inequality problem with linear inequality constraints. We propose a modified alternating direction method of multipliers in a parallel way for the linear inequality constraint problem by modifying the subproblem appropriately and adding a simple correction step. Under general hypothetical conditions, the global convergence and sublinear convergence rate of this new algorithm are proved. Applying the algorithm to the traffic equilibrium shows its effectiveness.
Spectral graph theory is a captivating area of graph theory that employs the eigenvalues and eigenvectors of matrices associated with graphs to study them. In this paper, we present a collection of 20 topics in spectral graph theory, covering a range of open problems and conjectures. Our focus is primarily on the adjacency matrix of graphs, and for each topic, we provide a brief historical overview.
S-lemma is an important theorem in operations research and cybernetics. In this paper, starting from verifying the global asymptotic stability of a nonlinear control system, we draw S-procedure, S-lemma, and their relations and differences. Then the basic content of S-lemma and its latest advances are introduced. Moreover, several generalizations of S-lemma over the complex field and the quaternion set are discussed. Finally, some basic results corresponding to S-lemma are showed for any number of symmetric (or Hermitian) matrices.
The Multi-agent Path Finding (MAPF) problem is a core fundamental issue in multi-agent systems and has been widely applied in practical scenarios such as automated intelligent warehousing, autonomous driving, and swarm robotics. From the perspective of problem attributes, the key difficulty lies in enabling multiple intelligent agents to travel along paths simultaneously while ensuring no collisions occur, making it an NP-hard combinatorial optimization problem. However, the aforementioned realworld applications require algorithms to find high-quality, collision-free paths for a large number of intelligent agents within a short computation time. Shorter paths lead to higher system throughput and lower operating costs, presenting significant challenges for classical MAPF optimization algorithms. As a result, in recent years, numerous studies have begun focusing on using machine learning methods to empower MAPF research, aiming to accelerate solution speed and improve solution quality. This paper presents a comprehensive review in three parts, including the core concepts, optimization objectives, and benchmark tasks of the MAPF problem. It also covers the problem modeling, core ideas, and strengths and weaknesses of traditional MAPF algorithms. Additionally and most importantly, this paper introduces a series of machine learning-empowered MAPF algorithms with varying degrees of machine learning involvement, providing corresponding schematic diagrams and pseudocode. This paper further summarizes the major challenges currently faced by machine learning-driven MAPF algorithms and proposes potential future research directions. This is intended to assist researchers in the field and promote the development of machine learning methods in the classical MAPF domain.
As a very important feature in fingerprint images, fingerprint orientation field plays an important role in many aspects of Automatic Fingerprint Identification System (AFIS), such as fingerprint image enhancement, singular point detection, fingerprint classification, etc. Although existing orientation field estimation algorithms can achieve competitive extraction results, these algorithms are sensitive to image noise and often require prior knowledge for direction calculation, which consumes a lot of time. To address this issue, a fingerprint orientation field estimation algorithm based on fully convolutional network is proposed in this paper, which uses pixel-level classification tasks to estimate fingerprint orientation field. According to the characteristics of fingerprint image and attention mechanism, we design a fully convolutional network with attention mechanism (Attention FCN) for orientation field estimation. In addition, dilated convolution layers are added to the network to extract important discriminative features in different fingerprint images. At the same time, a new loss function is designed to train the network. According to the classification results of each pixel point, the orientation field is estimated. Experimental results show that the proposed algorithm achieves good performance and very fast estimation speed, and it is very robust to image noise.
Optimal control is an important branch of control theory, and its goal is to determine a control strategy that optimizes system performance indicators under the premise of satisfying dynamic systems and constraints. Optimal control has a wide range of applications in engineering, economics, finance, robotics, aerospace and other fields. The direct method is a common method to solve the optimal control problem. This method transforms the continuous optimal control problem into a finite-dimensional optimization problem by directly discretizing the control and state function. At present, the direct method mainly includes the direct collocation method and the control parameterization method. The direct collocation method uses a specific function form to approximate the state and control function at the same time; the control parameterization method uses a linear combination of basis functions to approximate the control function, thereby discretizing the control space. The purpose of the two methods is to transform the continuous optimal control problem into a finite-dimensional nonlinear programming problem, and then choose an appropriate optimization algorithm to solve it. Benefiting from its flexibility and ability to deal with constraints, the direct method has become the important method in recent years for practical applications requiring real-time control. Researchers and engineers continue to develop and improve direct methods to increase their efficiency and accuracy in solving complex optimal control problems. This article mainly introduces the relevant achievements and latest developments of the direct method for readers' reference, and discusses the research trends and potential research directions of the direct method.
In many application fields such as artificial intelligence and scientific computing, application-driven mathematical optimization models often show randomness due to their dependence on large data sets and/or noisy data, and the model scale is large and accompanied by complex non-convex operator constraints. Thus it is normally expensive to get access to the exact function information of those models and can bring great challenges to algorithm design as well as theoretical analysis. In recent years, stochastic approximation algorithms for nonconvex constrained optimization have attracted much attention. Currently those algorithms can be separated into three categories: penalty methods based on stochastic approximations, proximal point algorithms and stochastic sequential quadratic programming algorithms. In this paper, we will briefly introduce latest progress on these types of algorithms, and present their algorithmic frameworks and theoretical properties including asymptotic convergence and complexity theory.
The facility location and size are important factors that affect operation cost and service quality of supply chain, and also two decisive factors for enterprises to gain competitive advantage. In order to optimize facility location and size simultaneously, a mixed integer programming model is formulated to minimize the total costs, and to decide the location of plants and depots, select sizes for the plants, determine the product flows from the plants to the depots and assign the customers to the depots. According to characteristics of the problem model, a Lagrangian relaxation algorithm is designed to solve the problem, and a hybrid simulated annealing tabu search algorithm is developed to further improve the solution quality. To test the validity of the proposed algorithm, a large number of randomly generated instances of different sizes and parameters are provided. The numerical results indicate that the proposed algorithm is effective and efficient for the two-echelon facility location problem with choice of facility size.
The Nash equilibrium game has been applied to many fields, the algorithm for the problem has attracted much attention in recent years. But since the Nash equilibrium game is a complex system composed by a series of optimization problems, the standard optimization method cannot be directly used for the problem, this leads to the difficulty of solving it. For a class of Nash equilibrium games with strongly convex payoff functions, using the Nikaido-Isoda function to transform the Nash equilibrium game into a smooth constraint optimization problem is an effective method to solve the Nash equilibrium game. Based on the gradient strongly monotonity of the Nash equilibrium payoff function, we present a Nikaido-Isoda algorithm for the game and the global convergence of the algorithm is proved. Finally, by solving two kinds of standard Nash equilibrium problems, the feasibility and effectiveness of the Nikaido-Isoda algorithm are verified.
Optimization with nonnegative orthogonality constraints, which includes both nonnegative constraints and orthogonality constraints, has important applications in machine learning and data science. Some typical instances of optimization with nonnegative orthogonality constraints include the quadratic assignment problem, graph matching problem, orthogonal nonnegative matrix factorization problem, nonnegative principal component analysis, and K-indicator model, etc. Due to the coupling effects of nonnegative and orthogonal constraints, this type of problem has a certain combinatorial structure and is generally NP-hard. This paper mainly introduces the basic theoretical properties, algorithms, and related applications of optimization with nonnegative orthogonality constraints.
Polyhedral projectors play a fundamental role in modern optimization. Recently, significant progress has been made in the computation of generalized Jacobians of projectors over polyhedral convex sets. In this paper, we review some recent theoretical and computational developments related to polyhedral projectors and their generalized Jacobians. Similar analyses are also extended to solution mappings of strongly convex quadratic programming problems, and proximal mappings of continuous piecewise affine regularizers.
The alternating direction method of multipliers(ADMM) is an valid method for solving separable convex optimization problems, nevertheless, when the objective function has a nonconvex function, ADMM may not converge. This paper proposes an inertial symmetric regularization alternating direction method of multipliers for nonconvex two-block optimization problem with linear equality constraints. Under the appropriate hypothesis conditions, the global convergence of the algorithm is established. Secondly, When the benefit function satisfies the Kurdyka-Łojasiewicz(KL) property, the strong convergence of the algorithm is established. Finally, numerical experiments are performed on the algorithm, and the results show that the algorithm is an effective method.
With the requirement for the protection of energy saving and emission reduction and also the development of the artificial intelligence, the city logistics distribution that uses unmanned aerial vehicle as distribution device has gradually turned into reality. Considering the battery capacity constraints of device, the charging decision and the pickup and delivery simultaneous demands, a mathematical programming model is constructed with the objective of minimizing the distribution cost (E-VRPSDP). A new branch-cut-and-price algorithm is provided to solve the exact solution based on the column generation method and bi-directional dynamic programming. To solve the large size E-VRPSDP, an improved simulated annealing algorithm is designed. A new operator is introduced as the constructing feasible solution operator which evolves the original solution into a feasible solution, thereby improving the searching ability of the algorithm. Finally, the suitable data examples are generated based on the standard test set to verify the proposed algorithms. The theoretical guidance and algorithm support for city logistics enterprises is provided to develop the driver-less logistics distribution.
This paper investigates the optimal reinsurance-investment strategies of two competing insurers under VaR constraints. We assume that the insurers' dynamic surplus processes are described by the classic Cramer-Lundberg (C-L) risk model, in which the premiums are determined by the loss-dependent premium principle. Moreover, the insurers can purchase proportional reinsurance and invest in a financial market consisting of a risk-free asset and a risky asset, where the price process of the risky asset is described by the geometric Brownian motion. Firstly, we aim to maximize the expected utility of the insurers' relative terminal wealth and then establish optimization problems with the VaR constraints. In the next, we solve the corresponding constrained optimization problems by using the optimal control theory and the dynamic programming principle. Specially, we get three different Nash equilibrium strategies under exponential utility. Finally, we illustrate the effects of some parameters on the optimal reinsurance strategy and the optimal investment strategy through specific numerical analysis, and find some interesting results.
