Parking Capacity and Pricing in Park'n Ride Trips: A Continuous Equilibrium Network Design Problem

In this paper we consider the problem of designing parking facilities for park'n ride trips. We present a new continuous equilibrium network design problem to decide the capacity and fare of these parking lots at a tactical level. We assume that the parking facilities have already been located and other topological decisions have already been taken.The modeling approach proposed is mathematical programming with equilibrium constraints. In the outer optimization problem, a central Authority evaluates the performance of the transport network for each network design decision. In the inner problem a multimodal traffic assignment with combined modes, formulated as a variational inequality problem, generates the share demand for modes of transportation, and for parking facilities as a function of the design variables of the parking lots. The objective is to make optimal parking investment and pricing decisions in order to minimize the total travel cost in a subnetwork of the multimodal transportation system.We present a new development in model formulation based on the use of generalized parking link cost as a design variable.The bilevel model is solved by a simulated annealing algorithm applied to the continuous and non-negative design decision variables. Numerical tests are reported in order to illustrate the use of the model, and the ability of the approach to solve applications of moderate size.     

A bi-objective turning restriction design problem in urban road networks

This paper introduces a bi-objective turning restriction design problem (BOTRDP), which aims to simultaneously improve network traffic efficiency and reduce environmental pollution by implementing turning restrictions at selected intersections. A bi-level programming model is proposed to formulate the BOTRDP. The upper level problem aims to minimize both the total system travel time (TSTT) and the cost of total vehicle emissions (CTVE) from the viewpoint of traffic managers, and the lower level problem depicts travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. The modified artificial bee colony (ABC) heuristic is developed to find Pareto optimal turning restriction strategies. Different from the traditional ABC heuristic, crossover operators are captured to enhance the performance of the heuristic. The computational experiments show that incorporating crossover operators into the ABC heuristic can indeed improve its performance and that the proposed heuristic significantly outperforms the non-dominated sorting genetic algorithm (NSGA) even if different operators are randomly chosen and used in the NSGA as in our proposed heuristic. The results also illustrate that a Pareto optimal turning restriction strategy can obviously reduce the TSTT and the CTVE when compared with those without implementing the strategy, and that the number of Pareto optimal turning restriction designs is smaller when the network is more congested but greater network efficiency and air quality improvement can be achieved. The results also demonstrate that traffic information provision does have an impact on the number of Pareto optimal turning restriction designs. These results should have important implications on traffic management.     

Optimality conditions for mixed discrete bilevel optimization problems

In this article, we consider bilevel optimization problems with discrete lower level and continuous upper level problems. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. In the case where the lower level is a parametric linear problem, the bilevel problem is transformed into a continuous one. After that, we are able to discuss local optimality conditions using tools of variational analysis for each of the different approaches. Finally, we consider a simple application of our results namely the bilevel programming problem with the minimum spanning tree problem in the lower level.     

A turning restriction design problem in urban road networks

Turning restriction is one of the commonest traffic management techniques and an effective low cost traffic improvement strategy in urban road networks. However, the literature has not paid much attention to the turning restriction design problem (TRDP), which aims to determine a set of intersections where turning restrictions should be implemented. In this paper, a bi-level programming model is proposed to formulate the TRDP. The upper level problem is to minimize the total travel cost from the viewpoint of traffic managers, and the lower level problem is to depict travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. We propose a branch and bound method (BBM), based on the sensitivity analysis algorithm (SAA), to find the optimal turning restriction strategy. A branch strategy and a bound strategy are applied to accelerate the solution process of the TRDP. The computational experiments give promising results, showing that the optimal turning restriction strategy can obviously reduce system congestion and are robust to the variations of both the dispersion parameter of the SUE problem and the level of demand.     

基于Stackelberg博弈的时变双层交通分配模型

提出一个时变双层交通分配模型,其中上层网络管理者设立了一个路段的最大排队长度,其目标是使由网络流和排队长度定义的总出行时间最小.目标函数在离散时段内以路段流量和排队长度作为决策变量,同时考虑不同类型的信号交叉口延误的影响.下层网络用户的反应依赖于上层管理者的决策,其选择是使自身感知阻抗最小的路径,服从一个基于成对组合Logit的路径选择模型,构成一个成对组合Logit的均衡分配问题.结合了交通分配和流传播方法,将其表示为一个均衡约束下的双层数学规划问题,形成了一个Stackelberg非合作博弈.使用遗传算法求解该双层规划问题,并采用实证分析来表现模型的特征和算法的计算表现.结果表明路径重叠、路段流量、路段排队长度等因素对网络均衡流分布均有显著影响.     

A general MPCC model and its solution algorithm for continuous network design problem

This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.     

Designing robust coverage networks to hedge against worst-case facility losses

In order to design a coverage-type service network that is robust to the worst instances of long-term facility loss, we develop a facility location–interdiction model that maximizes a combination of initial coverage by p facilities and the minimum coverage level following the loss of the most critical r facilities. The problem is formulated both as a mixed-integer program and as a bilevel mixed-integer program. To solve the bilevel program optimally, a decomposition algorithm is presented, whereby the original bilevel program is decoupled into an upper level master problem and a lower level subproblem. After sequentially solving these problems, supervalid inequalities can be generated and appended to the upper level master in an attempt to force it away from clearly dominated solutions. Computational results show that when solved to optimality, the bilevel decomposition algorithm is up to several orders of magnitude faster than performing branch and bound on the mixed-integer program.     

A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

Computation of the optimal tolls on the traffic network

The present paper is devoted to the computation of optimal tolls on a traffic network that is described as fuzzy bilevel optimization problem. As a fuzzy bilevel optimization problem we consider bilinear optimization problem with crisp upper level and fuzzy lower level. An effective algorithm for computation optimal tolls for the upper level decision-maker is developed under assumption that the lower level decision-maker chooses the optimal solution as well. The algorithm is based on the membership function approach. This algorithm provides us with a global optimal solution of the fuzzy bilevel optimization problem.     

Time-dependent discrete road network design with both tactical and strategic decisions

This paper aims to model and investigate the discrete urban road network design problem, using a multi-objective time-dependent decision-making approach. Given a base network made up with two-way links, candidate link expansion projects, and candidate link construction projects, the problem determines the optimal combination of one-way and two-way links, the optimal selection of capacity expansion projects, and the optimal lane allocations on two-way links over a dual time scale. The problem considers both the total travel time and the total CO emissions as the two objective function measures. The problem is modelled using a time-dependent approach that considers a planning horizon of multiple years and both morning and evening peaks. Under this approach, the model allows determining the sequence of link construction, the expansion projects over a predetermined planning horizon, the configuration of street orientations, and the lane allocations for morning and evening peaks in each year of the planning horizon. This model is formulated as a mixed-integer programming problem with mathematical equilibrium constraints. In this regard, two multi-objective metaheuristics, including a modified non-dominated sorting genetic algorithm (NSGA-II) and a multi-objective B-cell algorithm, are proposed to solve the above-mentioned problem. Computational results for various test networks are also presented in this paper.     

带平衡约束的离散网络平衡设计问题的遗传算法

本文研究了带平衡约束的离散网络设计问题及其求解算法.模型中上层是一个离散网络设计的数学规划模型,采用遗传算法来求解.下层是采用变分不等式描述的用户平衡配流问题,利用对角化方法直接求解.通过实例对算法进行验证,结果表明该算法是有效的.     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).     

Locating replenishment stations for electric vehicles: application to Danish traffic data

Environment-friendly electric vehicles have gained popularity and increased attention in recent years. The deployment of a network of recharging stations is essential given their limited travel range. This paper considers the problem of locating electronic replenishment stations for electric vehicles on a traffic network with flow-based demand. The objective is to optimize the network performance, for example to maximize the flow covered by a prefixed number of stations or to minimize the number of stations needed to cover traffic flows. Two integer linear programming formulations are proposed to model the problem. These models are tested on real-life traffic data collected in Denmark.     

A discrete bilevel brain storm algorithm for solving a sales territory design problem: a case study

A sales territory design problem faced by a manufacturing company that supplies products to a group of customers located in a service region is addressed in this paper. The planning process of designing the territories has the objective to minimizing the total dispersion of the customers without exceeding a limited budget assigned to each territory. Once territories have been determined, a salesperson has to define the day-by-day routes to satisfy the demand of customers. Currently, the company has established a service level policy that aims to minimize total waiting times during the distribution process. Also, each territory is served by a single salesperson. A novel discrete bilevel optimization model for the sales territory design problem is proposed. This problem can be seen as a bilevel problem with a single leader and multiple independent followers, in which the leader’s problem corresponds to the design of territories (manager of the company), and the routing decision for each territory corresponds to each follower. The hierarchical nature of the current company’s decision-making process triggers some particular characteristics of the bilevel model. A brain storm algorithm that exploits these characteristics is proposed to solve the discrete bilevel problem. The main features of the proposed algorithm are that the workload is used to verify the feasibility and to cluster the leader’s solutions. In addition, four discrete mechanisms are used to generate new solutions, and an elite set of solutions is considered to reduce computational cost. This algorithm is used to solve a real case study, and the results are compared against the current solution given by the company. Results show a reduction of more than 20% in the current costs with the solution obtained by the proposed algorithm. Furthermore, a sensitivity analysis is performed, providing interesting managerial insights to improve the current operations of the company.     

Bilevel programming in traffic planning: Models,methods and challenge

Well-founded traffic models recognize the individual network user's right to the decision as to when, where and how to travel. On the other hand, the decisions concerning management, control, design and improvement investments are made by the public sector in the interest of the society as a whole. Hence, transportation planning is a characteristic example of a hierarchical process, in which the public sector at one level makes decisions seeking to improve the performance of the network, while at another level the network users make choices with regard to route, travel mode, origin and destination of their travel. Our objective is to provide a review on the current state of research and development in bilevel programming problems that arize in this context, and attract the attention of the global optimization community to this problem class of imense practical importance.     

交通网络建设序列的动态规划方法

交通网络建设序列优化是交通规划中一个重要问题。文章对交通网络设计及其建设序列问题的研究现状进行了分析。按照网络建设中规划者和用户间的关系,以交通网络建设序列下的各阶段系统总费用作为上层规划,以各阶段的交通流用户平衡模型作为下层规划,建立了双层规划模型。并依照问题的特点,采用动态规划的求解方法进行探讨,而下层模型则采用了基于路径搜索的GP算法进行求解。并针对网络规划算例进行了计算,针对固定和变动客流OD两种情况下的结果进行了分析。计算的结果表明,问题的双层规划模型和动态规划求解算法能够为路网规划决策提供支持。     

带有限反馈下层的二层规划问题的部分合作模型

对下层最优反馈为离散有限多个的二层规划问题的部分合作模型进行探讨. 当下层的合作程度依赖于上层的决策变量时, 给出一个确定合作系数函数的一般方法, 进而得到一个新的部分合作模型. 在适当地假设下, 可保证所给的部分合作模型一定可以找到比悲观解要好的解, 并结合新的部分合作模型对原不适定问题进行分析, 得到了一些有益的结论. 最后以实际算例说明了所给部分合作模型的可行性.     

关于二层规划的逼近问题

下层问题以上层决策变量作为参数,而上层是以下层问题的最优值作为响应 的一类最优化问题——二层规划问题。我们给出了由一系列此类二层规划去逼近原二层规划的逼近法,得到了这种逼近的一些有趣的结果.     

A penalty function method for solving inverse optimal value problem

In order to consider the inverse optimal value problem under more general conditions, we transform the inverse optimal value problem into a corresponding nonlinear bilevel programming problem equivalently. Using the Kuhn–Tucker optimality condition of the lower level problem, we transform the nonlinear bilevel programming into a normal nonlinear programming. The complementary and slackness condition of the lower level problem is appended to the upper level objective with a penalty. Then we give via an exact penalty method an existence theorem of solutions and propose an algorithm for the inverse optimal value problem, also analysis the convergence of the proposed algorithm. The numerical result shows that the algorithm can solve a wider class of inverse optimal value problem.     

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.