The combination of continuous network design and route guidance

In this study, a traffic management measure is presented by combining the route guidance of Advanced Traveler Information System (ATIS) and the continuous network design (CNDP) to alleviate increasing traffic congestion. The route guidance recommends the travelers to choose the shortest path based on marginal travel cost and user constraints. The problem is formulated into a bi-level programming problem. The most distinct property of this problem formulation is that the feasible path set of its lower-level problem is determined by the decision variable of upper-level problem, while in conventional transportation network design problems the feasible path set for lower-level traffic assignment problem is fixed to be all the viable paths between each specific origin-destination pair. The simulated annealing algorithm is improved to solve this bi-level problem. A path-based traffic algorithm is developed to calculate the lower-level traffic assignment problem under the route guidance. Compared to the results of conventional CNDP, the measure presented in this study can better improve the transportation network performance.     

A bi-level programming for logistics network design with system-optimized flows

This paper proposes a bi-level programming for a logistics network design problem with system-optimized flows. We applied the Wardrop’s second principle to the logistics network design problem. A system-optimized logistics network design problem can be formulated as a bi-level program. For the system-optimized flows, a user equilibrium traffic assignment problem with marginal costs can be solved at the lower level problem. Due to the non-differentiability of the perturbed solutions in system-optimized flows, we present a novel solution algorithm to efficiently solve the logistics network design problem. By using the subgradients of the objective function, a new projection method is proposed with global convergence. Numerical calculations are implemented using a grid-size hypothetical network and comparisons are made with other alternatives in solving the logistics network design problem. Numerical results disclose that the proposed method has successful solved the logistics network design problem and achieved significant performance both in computational efficacy and cost reduction when compared to other alternatives.     

A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem

We present a heuristic to solve the NP-hard bi-level network design problem (NDP). The heuristic is developed based on the Dantzig-Wolfe decomposition principle such that it iteratively solves a master problem and a pricing problem. The master problem is the budget allocation linear program solved by CPLEX to determine the budget allocation and construct a modified cell transmission network for the pricing problem. The pricing problem is the user-optimal dynamic traffic assignment (UODTA) solved by an existing combinatorial algorithm. To facilitate the decomposition principle, we propose a backward connectivity algorithm and complementary slackness procedures to efficiently approximate the required dual variables from the UODTA solution. The dual variables are then employed to augment a new column in the master program in each iteration. The iterative process repeats until a stopping criterion is met. Numerical experiments are conducted on two test networks. Encouraging results demonstrate the applicability of the heuristic scheme on solving large-scale NDP. Though a single destination problem is considered in this paper, the proposed scheme can be extended to solve multi-destination problems as well.     

动态平衡运量配流问题及其稳态伴随解算法

动态平衡运量配流问题的建模和求解是发展智能车辆导驶系统的理论基础.本文对多起 点单讫点交通网络建立了连续时间最优控制模型,该模型的最优解对应于动态用户平衡解.文 中提出的稳态伴随解算法避免了解复杂的两点边界值问题,可以获得原问题的近似解.该算 法利用了交通网络和计算机网络的结构特性,计算速度较高,可用于城市交通流的实时控制.     

Dynamic Traffic Assignment with More Flexible Modelling within Links

Traffic network models tend to become very large even for medium-size static assignment problems. Adding a time dimension, together with time-varying flows and travel times within links and queues, greatly increases the scale and complexity of the problem. In view of this, to retain tractability in dynamic traffic assignment (DTA) formulations, especially in mathematical programming formulations, additional assumptions are normally introduced. In particular, the time varying flows and travel times within links are formulated as so-called whole-link models. We consider the most commonly used of these whole-link models and some of their limitations.In current whole-link travel-time models, a vehicle's travel time on a link is treated as a function only of the number of vehicles on the link at the moment the vehicle enters. We first relax this by letting a vehicle's travel time depend on the inflow rate when it enters and the outflow rate when it exits. We further relax the dynamic assignment formulation by stating it as a bi-level program, consisting of a network model and a set of link travel time sub-models, one for each link. The former (the network model) takes the link travel times as bounded and assigns flows to links and routes. The latter (the set of link models) does the reverse, that is, takes link inflows as given and finds bounds on link travel times. We solve this combined model by iterating between the network model and link sub-models until a consistent solution is found. This decomposition allows a much wider range of link flow or travel time models to be used. In particular, the link travel time models need not be whole-link models and can be detailed models of flow, speed and density varying along the link. In our numerical examples, algorithms designed to solve this bi-level program converged quickly, but much remains to be done in exploring this approach further. The algorithms for solving the bi-level formulation may be interpreted as traveller learning behaviour, hence as a day-to-day traffic dynamics. Thus, even though in our experiments the algorithms always converged, their behaviour is still of interest even if they cycled rather than converged. Directions for further research are noted. The bi-level model can be extended to handle issues and features similar to those addressed by other DTA models.     

多用户动态交通分配和信号优化的组合研究

提出了一种饱和路网中考虑多用户行为下的动态交通分配和交通信号优化的组合模型。模型采用广义双层规划来表示。模型的上层是信号控制优化,下层是考虑多用户路径选择条件下的动态交通分配,进行交通网络流的配置。同时,模型中采用具有物理排队的动态网络模型,从而考虑了饱和路网中物理排队对基于路段的网络条件的影响。通过仿真说明了饱和路网中考虑多用户行为下的动态交通分配和交通信号优化的组合模型可以实现交通信号的优化配置和交通网络流的优化,并反映了排队的物理效应。     

Research on Combined Dynamic Traffic Assignment and Signal Control

This paper presents a generalized bi-level programming model of combined dynamic traffic assignment and traffic signal control,and especially analyzes a procedure for determining the equilibrium queuing delays on saturated links for dynamic network signal control satisfying the FIFO (first-in-first-out)rule.The chaotic optimal algorithm proposed in this paper can not only present the optimal signal settings,but also calculate,at each interval,the link inflow rates and outflow rates for the dynamic user optimal problem,and provide real-time information for the travelers.Finally,a numerical example is given to illustrate the application of the proposed model and solution algorithm, and comparison shows that this model has better system performance.     

Traffic Equilibrium and Charging Facility Locations for Electric Vehicles

This study investigates the electric vehicle (EV) traffic equilibrium and optimal deployment of charging locations subject to range limitation. The problem is similar to a network design problem with traffic equilibrium, which is characterized by a bi-level model structure. The upper level objective is to optimally locate charging stations such that the total generalized cost of all users is minimized, where the user’s generalized cost includes two parts, travel time and energy consumption. The total generalized cost is a measure of the total societal cost. The lower level model seeks traffic equilibrium, in which travelers minimize their individual generalized cost. All the utilized paths have identical generalized cost while satisfying the range limitation constraint. In particular, we use origin-based flows to maintain the range limitation constraint at the path level without path enumeration. To obtain the global solution, the optimality condition of the lower level model is added to the upper level problem resulting in a single level model. The nonlinear travel time function is approximated by piecewise linear functions, enabling the problem to be formulated as a mixed integer linear program. We use a modest-sized network to analyze the model and illustrate that it can determine the optimal charging station locations in a planning context while factoring the EV users’ individual path choice behaviours.     

动态交通分配与信号控制的组合模型及算法研究

This paper presents a generalized bi-level programming model of combined dynamic traffic assignment and traffic signal control, and especially analyzes a procedure for determining the equilibrium queuing delays on saturated links for dynamic network signal control satisfying the FIFO (first-in-first-out) rule. The chaotic optimal algorithm proposed in this paper can not only present the optimal signal settings, but also calculate, at each interval, the link inflow rates and outflow rates for the dynamic user optimal problem, and provide real-time information for the travelers. Finally, a numerical example is given to illustrate the application of the proposed model and solution algorithm, and comparison shows that this model has better system performance.     

Integrated Network Capacity Expansion and Traffic Signal Optimization Problem: Robust Bi-level Dynamic Formulation

This paper presents a robust optimization formulation, with an exact solution method, that simultaneously solves continuous network capacity expansion, traffic signal optimization and dynamic traffic assignment when explicitly accounting for an appropriate robustness measure, the inherent bi-level nature of the problem and long-term O-D demand uncertainty. The adopted robustness measure is the weighted sum of expected total system travel time (TSTT) and squared up-side deviation from a fixed target. The model propagates traffic according to Daganzo’s cell transmission model. Furthermore, we formulate five additional, related models. We find that when evaluated in terms of robustness, the integrated robust model performs the best, and interestingly the sequential robust approach yields a worse solution compared to certain sequential and integrated approaches. Although the adopted objective of the integrated robust model does not directly optimize the variance of TSTT, our experimental results show that the robust solutions also yield the least-variance solutions.     

Hierarchical spanning tree network design with Nash genetic algorithm

In this paper, we will propose a Nash genetic algorithm (Nash GA) for solving a hierarchical spanning tree network design problem, formulated as a bi-level programming problem. The proposed algorithm can be employed in designing the backbone topology in a hierarchical link-state (LS) routing domain. Because the well-designed backbone topology structure has a great impact on the overall routing performance in a hierarchical LS domain, the importance of this research is evident. The proposed algorithm is to find an optimal configuration of backbone network for backbone provider (BP) and distribution network for internet service provider (ISP), properly meeting two-aspect engineering goals: i.e., average message delay and connection costs. Also, it is assumed that there are the decision makers for BP and the decision makers for ISP join in the decision making process in order to non-cooperatively optimize the own objective function. From the experiment results, we can see clearly that our proposed algorithm can be employed in effectively designing the spanning tree network of hierarchical LS routing domain considering not only engineering aspects but also specific benefits from systematical layout of backbone network.     

蚁群算法求解连续空间优化问题的一种方法

针对蚁群算法不太适合求解连续性优化问题的缺陷,提出用蚁群算法求解连续空间优化问题的一种方法.该方法将解空间划分成若干子域,在蚁群算法的每一次迭代中,首先根据信息量求出解所在的子域,然后在该子域内已有的解中确定解的具体值.以非线性规划问题为例所进行的计算结果表明,该方法比使用模拟退火算法、遗传算法具有更好的收敛速度.     

Solving the Dynamic User Optimal Assignment Problem Considering Queue Spillback

This paper studies the dynamic user optimal (DUO) traffic assignment problem considering simultaneous route and departure time choice. The DUO problem is formulated as a discrete variational inequality (DVI), with an embeded LWR-consistent mesoscopic dynamic network loading (DNL) model to encapsulate traffic dynamics. The presented DNL model is capable of capturing realistic traffic phenomena such as queue spillback. Various VI solution algorithms, particularly those based on feasible directions and a line search, are applied to solve the formulated DUO problem. Two examples are constructed to check equilibrium solutions obtained from numerical algorithms, to compare the performance of the algorithms, and to study the impacts of traffic interacts across multiple links on equilibrium solutions.     

A NEW EXPERIMENTAL STUDY OF GENETIC ALGORITHM AND SIMULATED ANNEALING WITH BOUNDED VARIABLES

Genetic algorithms (GA) can work in very large and complex spaces, which gives them the ability to solve many complex real-world problems. The bounded variables linear programming is formulated as genetic algorithms and simulated annealing (SA). This article demonstrates that genetic algorithms and simulated annealing are much easier to implement for solving network problems compared with constructing mathematical programming formulations, because it is a very simple matter to implement a new cost function and solution constraints when using a GA and SA. Finally, the presented results show that the genetic algorithm and simulated annealing provide a good scheduling methodology to bounded variables programming.     

Goal programming approach to solving network design problem with multiple objectives and demand uncertainty

The transportation network design problem (NDP) with multiple objectives and demand uncertainty was originally formulated as a spectrum of stochastic multi-objective programming models in a bi-level programming framework. Solving these stochastic multi-objective NDP (SMONDP) models directly requires generating a family of optimal solutions known as the Pareto-optimal set. For practical implementation, only a good solution that meets the goals of different stakeholders is required. In view of this, we adopt a goal programming (GP) approach to solve the SMONDP models. The GP approach explicitly considers the user-defined goals and priority structure among the multiple objectives in the NDP decision process. Considering different modeling purposes, we provide three stochastic GP models with different philosophies to model planners’ NDP decision under demand uncertainty, i.e., the expected value GP model, chance-constrained GP model, and dependent-chance GP model. Meanwhile, a unified simulation-based genetic algorithm (SGA) solution procedure is developed to solve all three stochastic GP models. Numerical examples are also presented to illustrate the practicability of the GP approach in solving the SMONDP models as well as the robustness of the SGA solution procedure.     

交叉口有交通信号控制时用户最优动态配流模型

针对智能交通系统（ＴＴＳ）基础上中主要基础理论之一的动态交通分配问题,在现有研究成果的基础上,提出了更接近真实路网的多起点多旋点交叉口设置有交通信号控制（Ｔｒａｆｆｉｃ Ｓｉｇｎａｌ Ｃｏｎｔｒｏｌ）时的动态配流模型,给出了对现有的通过Ｆｒａｎｋ Ｗｏｉｆｅ算法所得的ＤＵＯ配流解进行修正的原则,最后的算例表明由修正后的模型和算法所得到的ＤＵＯ配流解满足ＴＳＣ约束。     

Optimized planning of frequency hopping in cellular networks

We consider a generalization of the classical frequency assignment problem. The generalization arises when frequency hopping is used in a cellular network. The planning problem concerns assigning lists of frequencies to blocks of transceivers, such that the total interference is minimized. This problem is considerably more difficult than the classical frequency assignment problem, because of the large number of possible frequency lists. We provide the technical background that motivates our study, and present a mathematical model which includes the classical frequency assignment problem as a special case. We describe a simulated annealing algorithm. The algorithm explores the solution space by solving an integer program in each iteration. We report computational results for real-life and synthesized networks.     

基于粒子群算法的移动边缘计算任务分配方法

为提高移动终端任务分配效率,降低计算能量损耗,提出基于粒子群算法的移动边缘计算任务分配方法。通过构建异构网络获取完整的需要分配的任务,明确任务分配时所需的特定条件,即分配消耗和时延等。将分配任务转化成寻找分配结果的最优解,构建最优解模型,利用粒子群算法对模型实施求解,经过不断迭代和更新,生成最优边缘计算任务的分配结果。实验结果表明,粒子群方法在分配任务数量为20~100之间时计算时间在1 s~3.3 s;当任务数量为100时,本文方法能耗仅为4107 J;粒子群方法在任务达到率达到100%时,其时延仅为12.5 ms;其任务分配计算时间短、能量消耗小和数据传输的时延短,能较好地满足实际应用需要。     

最优动态配流问题的离散模型及其解

对一般路网建立了具有良好结构形式的离散动态配流模型，该模型在多起点单讫点路网中的最优解满足交通流守恒约束和动态平衡原则。在提出了完全不同路段概念的基础上，对最优解的奇异性进行了分析，得到稳态最优解为非奇异解的结论。给出的算例验证了结论的正确性。     

A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem

Discrete network design problem (DNDP) is generally formulated as a bi-level programming. Because of non-convexity of bi-level formulation of DNDP which stems from the equilibrium conditions, finding global optimal solutions are very demanding. In this paper, a new branch and bound algorithm being able to find exact solution of the problem is presented. A lower bound for the upper-level objective and its computation method are developed. Numerical experiments show that our algorithm is superior to previous algorithms in terms of both computation time and solution quality. The conducted experiments indicate that in most cases the first incumbent solution which is obtained within a few seconds is superior to the final solution of some of previous algorithms.