Toward developing a national transportation planning model: A bilevel programming approach for Korea

The paper addresses specific issues associated with solving a bilevel transportation planning model in which public-private interaction is explicitly represented. Provisions for interaction between the public and private sectors in planning models would shed light on many important issues of planning strategy because the private sector pursues its own interests, while the public sector attempts to broaden public interests in a mixed economic system.Bilevel programming models have been applied to analyzing problems of managing natural resources, project selection, agricultural sector strategic planning, regional development and transportation network design. Most of the problems formulated thus far in bilevel programming frameworks, however, are small examples which are illustrative in nature due to the lack of efficient algorithmic procedures to solve the programming problems. In fact, none of available solution algorithms were actually tested for solving a large scale-real world problem.By reviewing and evaluating available literature, the paper strives to shed light on the issue of the extent to which bilevel programming approaches can explain public-private interaction in a mixed economic system. The paper also discusses issues on solving a large scale bilevel programming problem and attempts to contribute toward building a normative theory of ways in which resources are allocated in a mixed economic system.On this special occasion of paying tribute to Mischaikow's contributions to Regional Science, particularly to his dedication to the enhancement of Regional Science in the Pacific Region, the paper also addresses issues toward developing a national transportation planning model for Korea in a bilevel programming framework.     

A Hybrid Branch‐and‐Bound and Benders Decomposition Algorithm for the Network Design Problem

Given a set of candidate road projects associated with costs, finding the best subset with respect to a limited budget is known as the network design problem (NDP). The NDP is often cast in a bilevel programming problem which is known to be NP‐hard. In this study, we tackle a special case of the NDP where the decision variables are integers. A variety of exact solutions has been proposed for the discrete NDP, but due to the combinatorial complexity, the literature has yet to address the problem for large‐size networks, and accounting for the multimodal and multiclass traffic flows. To this end, the bilevel problem is solved by branch‐and‐bound. At each node of the search tree, a valid lower bound based on system optimal (SO) traffic flow is calculated. The SO traffic flow is formulated as a mixed integer, non‐linear programming (MINLP) problem for which the Benders decomposition method is used. The algorithm is coded on a hybrid and synchronized platform consisting of MATLAB (optimization engine), EMME 3 (transport planning module), MS Access (database), and MS Excel (user interface). The proposed methodology is applied to three examples including Gao's network, the Sioux‐Falls network, and a real size network representing the city of Winnipeg, Canada. Numerical tests on the network of Winnipeg at various budget levels have shown promising results.     

Sensitivity analysis for a continuum traffic equilibrium problem

This paper develops a sensitivity analysis for the continuum traffic equilibrium problem of a city with several competing facilities. In the city, the customers’ origins are continuously dispersed. We assume that the customer demand is dependent on the total cost of patronizing these facilities. Specific travel cost–flow relationships are considered. The choice of facility in the continuum transportation system follows a user equilibrium principle in which from each origin, no customer can reduce their individual cost to patronize any of the facilities by unilaterally changing route or facility. The problem can be formulated as a minimization problem that is subject to a set of constraints and solved with a finite element method. The sensitivity analysis is based on the implicit function theorem at the equilibrium solution. A numerical example is presented to illustrate the applications of these sensitivity analysis results.     

混合交通网络设计的双层模型及遗传算法求解

根据混合交通网络设计问题的特点,利用双层规划模型和遗传算法对该问题进行求解。对交通网络中的路段进行分类,通过限定决策变量的取值范围,将混合交通网络离散化。建立混合交通网络设计的双层模型。其中,上层模型以方案总投资额最小为目标函数,以路段负荷度和可行域为约束条件;下层模型为交通流分配的用户均衡模型。根据所建模型的离散特性,研究其遗传算法解法,并给出算法的具体实现步骤。以一个抽象的交通网络为例,给定网络中的路段属性、OD交通量等参数,利用MATLAB软件对模型编程求解,能够获得满意的交通网络设计方案,表明双层模型和遗传算法是一种研究混合交通网络设计问题的有效方法。最后,对该模型存在的不足及改进方向进行了探讨。     

城市交通网络设计问题中的双层规划模型

城市交通网络设计问题的主要内容就是通过规划的思想建立数学模型,通过优化计算方法寻找最优的用于道路网络新建或改善的交通建设投资决策方案,即研究如何能用最少的资金投入达到使整个交通网络中某种指标最优的目的。这些具体的系统性能指标可以是使整个网络中的系统总阻抗最小、交通拥挤程度最低、能源消耗最少等,从而为交通规划部门和决策人员提供科学、系统、合理、有效的决策方案和决策数据,使政府有限的资金投入能取得最佳的投资效益。本文首先简单介绍了城市交通网络设计问题研究的主要内容,然后给出了城市交通网络设计中一般形式的双层规划模型及其推广形式。     

A combined distribution and assignment model for continuous facility location problem

Consider a general, heterogeneous geographical space with a set of competitive facilities, where the customers' demand locations from each of the facilities are continuously dispersed over the area. The total demand generated from a particular location in the space is fixed, but the demands from this location to the set of competitive facilities are subject to a distribution function with respect to the relative transportation costs to these facilities. Furthermore, we take into account congested transportation cost in characterizing customer choices. Congestion effect is explicitly built into our model by using a flow-dependent and location-dependent transportation cost function. The routing behavior of customers over the space and the user equilibrium choices of facilities are modeled by constructing a spatial user equilibrium flow pattern. The problem is formulated as a combined distribution and assignment model. An iterative algorithm between the distribution function for the choice of facilities and a mixed finite element method for route choices is proposed to solve the resulting continuous facility location problem. A numerical example is given to demonstrate the effectiveness of the proposed methodology. Received: May 1999/Accepted: May 2000     

Optimization of tower crane and material supply locations in a high-rise building site by mixed-integer linear programming

Facility layout design and planning within construction sites are a common construction management problem and regarded as a complex combinatorial problem. To transport heavy materials, tower cranes are needed and should be well located to reduce operating costs and improve overall efficiency. Quadratic assignment problem (QAP), non-linear in nature, has been developed to simulate the material transportation procedure. Applying linear constraint sets, the quadratic problem can be linearized and the problem could be formulated into a mixed-integer-linear programming (MILP) problem solvable by a standard branch-and-bound technique for true optimal results. Numerical findings show that MILP results outperform those optimized by Genetic Algorithms with almost 7% on improving the objective function values in which facilities and locations can be modeled using integer variables. To demonstrate the design flexibility of using MILP formulation, the problem is also extended to non-homogeneous storages where different materials can be stored at a single supply point.     

Joint power distribution and charging network design for electrified mobility with user equilibrium decisions

Rapid adoption of electric vehicles (EVs) requires the development of a highly flexible charging network. The design and management of the charging infrastructure for EV-dominated transportation systems are intertwined with power grid operations both economically and technically. High penetration of EVs in the future can increase the charging loads and cause a wide range of operational issues in power distribution networks (PDNs). This paper aims to design an EV charging network with an embedded PDN layout to account for energy dispatch and underlying traffic flows in urban transportation networks supporting electric mobility in the near future. A mixed-integer bilevel model is proposed with the EV charging facility location and PDN energy decisions in the upper level and user equilibrium traffic assignment in the lower level considering an uncertain charging demand. The objective is to minimize the cost of PDN operations, charging facility deployments, and transportation. The proposed problem is solved using a column and constraint generation (C&CG ) algorithm, while a macroscopic fundamental diagram concept is implemented to estimate the arc travel times. The methodology is applied to a hypothetical and two real-world case study networks, and the solutions are compared to a Benders decomposition benchmark. The east-coast analysis results indicate a 77.3% reduction in the computational time. Additionally, the benchmark technique obtains an optimality gap of 1.15%, while the C&CG algorithm yields a 0.61% gap. The numerical experiments show the robustness of the proposed methodology. Besides, a series of sensitivity analyses has been conducted to study the impact of input parameters on the proposed methodology and draw managerial insights.     

Integrated Planning of Supply Chain Networks and Multimodal Transportation Infrastructure Expansion: Model Development and Application to the Biofuel Industry

Abstract: As the biofuel industry continues to expand, the construction of new biorefinery facilities induces a huge amount of biomass feedstock shipment from supply points to the refineries and biofuel shipment to the consumption locations, which increases traffic demand in the transportation network and contributes to additional congestion (especially in the neighborhood of the refineries). Hence, it is beneficial to form public‐private partnerships to simultaneously consider transportation network expansion and biofuel supply chain design to mitigate congestion. This article presents an integrated mathematical model for biofuel supply chain design where the near‐optimum number and location of biorefinery facilities, the near‐optimal routing of biomass and biofuel shipments, and possible highway/railroad capacity expansion are determined. The objective is to minimize the total cost for biorefinery construction, transportation infrastructure expansion, and transportation delay (for both biomass/biofuel shipment and public travel) under congestion. A genetic algorithm framework (with embedded Lagrangian relaxation and traffic assignment algorithms) is developed to solve the optimization model, and an empirical case study for the state of Illinois is conducted with realistic biofuel production data. The computational results show that the proposed solution approach is able to solve the problem efficiently. Various managerial insights are also drawn. It shall be noted that although this article focuses on the booming biofuel industry, the model and solution techniques are suitable for a number of application contexts that simultaneously involve network traffic equilibrium, infrastructure expansion, and facility location choices (which determine the origin/destination of multi‐commodity flow).     

An equilibrium network design model with a social cost function for multimodal networks

In this paper, we present a comprehensive investment planning model and its solution approach. The model takes a bilevel programming form and allows a variety of effects of the investments incorporated. The model is characterized by its ability to address the total social costs occurring in transportation networks and to estimate the equilibrium link volumes in multimodal networks. Two solution algorithms were proposed. Both algorithms handle the discrete optimization problem by exploiting the strings of binary digits of integer variables. In an illustrative example, we performed network design analyses for three scenarios in which 25, 50, and 75% of the total required capital is available. By applying the two solution algorithms to the example problem, the optimal network alternative for each scenario was found. If a cost/benefit analysis is coupled with the proposed model, the optimal investments and the optimal network configuration will be determined simultaneously.

---

基于空间价格均衡的物流中心选址双层规划模型研究

空间价格均衡原理是商品出行普遍遵循的运输价格规律,在进行物流中心规划时,可以基于上述原理考虑商品需求量在各区域的分配情况。因此,本文建立了双层规划选址模型,上层规划从系统规划者的角度出发使选址总费用最小,下层规划为在考虑各物流中心相互影响的情况下的空间价格均衡的变分不等式模式。同时设计了启发式方法对上述模型进行求解。     

Modeling,equilibrium, and demand management for mobility and delivery services in Mobility-as-a-Service ecosystems

Mobility-as-a-Service (MaaS) is an emerging business model integrating various travel modes into a single mobility service accessible on demand. Besides the on-demand mobility services, instant delivery services have increased rapidly and particularly boomed during the coronavirus (COVID-19) pandemic, requiring online orders to be delivered timely. In this study, to deal with the redundant mobility resources and high costs of instant delivery services, we model an MaaS ecosystem that provides mobility and instant delivery services by sharing the same multimodal transport system. We derive a two-class bundle choice user equilibrium (BUE) for mobility and delivery users in the MaaS ecosystems. We propose a bilateral surcharge–reward scheme (BSRS) to manage the integrated mobility and delivery demand in different incentive scenarios. We further formulate a bilevel programming problem to optimize the proposed BSRS, where the upper level problem aims to minimize the total system equilibrium costs of mobility and delivery users, and the lower level problem is the derived two-class BUE with BSRS. We analyze the optimal operational strategies of the BSRS and develop a solution algorithm for the proposed bilevel programming problem based on the system performance under BSRS. Numerical studies conducted with real-world data validate the theoretical analysis, highlight the computational efficiency of the proposed algorithm, and indicate the benefits of the BSRS in managing the integrated mobility and delivery demand and reducing total system equilibrium costs of the MaaS ecosystems.     

青岛轨道交通与快速路系统立体联网的构想

为减少青岛道路交通拥堵,提出将轨道交通与快速路系统立体联网的构想.由于地下快速路和地铁建设上的相似性,考虑土地的利用和成本,在规划修建时可将两者合建.本研究为城市交通政策和空间增长策略的制定提供了决策依据.     

Optimal excavation profile for a pipeline freely resting on the sea floor

A submarine pipeline resting on a rigid, frictionless sea bed assumes an equilibrium configuration which can be determined by solving a unilateral contact problem, i.e. a quadratic program or a variational inequality.Since the sea bed profile is usually irregularly hilly, its regularization is often carried out, in present offshore technology, by costly trench excavations, both in order to avoid excessive bending moments in the pipe and to bury it for protection. Thus, the problem arises of determining profile changes of minimum cost under the condition that an assigned curvature be nowhere exceeded.This optimal design problem is tackled in the paper with reference to a discrete model of the mechanical system, as the minimization of a linear cost function under linear constraints and a single, nonlinear and non-convex, complementarity constraint.A theory is developed which reduces this nonlinear programming problem to a sequence of linear programs, the optimal solutions of which are shown to converge to the original NLP solution. Upper and lower bounds on the absolute minimum cost and optimality conditions are established, on the basis of duality theory in linear programming. An algorithm suitable for solving the problem in a finite number of steps is proposed. Generalizations obtained by relaxing some of the simplifying hypotheses are considered.     

Uncertainty and the design of building subsystems—A dynamic programming approach

This paper discusses the general problem of designing building subsystems which include probabilistic demands thus producing a stochastic problem. This class of problem, if linear, can be readily solved using classical stochastic linear programming. It is shown that the problem may be formulated as a stochastic dynamic program. A problem of designing the HVAC subsystem is formulated and solved as a dynamic program. Comparisons are made between the two methods. It is shown that dynamic programming is the more powerful method both in terms of obtaining the solution and in its post-optimality analysis. It is suggested that dynamic programming is a suitable technique for a wide range of building and architectural design problems.     

Optimization of material hoisting operations and storage locations in multi-storey building construction by mixed-integer programming

Material storage locations incurring minimum transportation costs in construction are a common construction management problem. Storage locations influence the delivery path and overall project efficiency. Lower floors of buildings after completion and developing sufficient structural strength will be utilized as storages and layout plans should be designed to achieve maximum construction efficiency in terms of total transportation and distribution costs. A mixed-integer programming is formulated to optimize the vertical hoisting and storage layout solvable by a branch-and-bound technique. Total transportation cost is derived as an objective for optimization. Material storage locations are defined as binary variables. Linear constraints are developed to satisfy design requirements. A numerical example storing 10 material types and delivering materials in a 30-storey building is given for illustration. Numerical results optimized by the MIP approach will be compared with those optimized by the genetic algorithms. The MIP solution shows better solution quality taking less computing time.     

DESIGN OF SERVICE SYSTEMS WITH FUNCTIONALLY FOCUSED FACILITIES

ABSTRACT In this paper we present a mathematical model in study certain design dimensions of facility systems that provide a wide variety of services to a geographical area. Facilities of different types are defined on the basis of the services they provide. We maintain that providing all these services by use of such specialised for functionally differentiated) facilities will help achieve a greater degree of system efficiency, especially it different facility types are coordinated in the delivery of these services and in the use of resources. The problem of determining the numbers, sizes, and locations of these "focused" facility types is formulated as a mixed-integer quadratic programming problem. An approximate algorithm is given for the analysis of this model whose computational feasibility is discussed for actual applications. A hypothetical example is provided to illustrate the model and the solution method.     

Tabu Search Strategies for the Public Transportation Network Optimizations with Variable Transit Demand

Abstract:   Systematic tabu search (TS)-based heuristic methods are put forward in this article and applied for the design of public transportation networks with variable demand. A multi-objective nonlinear mixed integer model is formulated. Solution methodologies are proposed, which consist of three main components: an initial candidate route set generation procedure (ICRSGP) that generates all feasible routes incorporating practical bus transit industry guidelines; a network analysis procedure (NAP) that decides transit demand matrix, assigns transit trips, determines service frequencies, and computes performance measures; and a Tabu search method (TSM) that combines these two parts, guides the candidate solution generation process, and selects an optimal set of routes from the huge solution space. Comprehensive tests are conducted and sensitivity analyses are performed. Characteristics analyses are undertaken and solution qualities from different algorithms are compared. Numerical results clearly indicate that the preferred TSM outperforms the genetic algorithm used as a benchmark for the optimal bus transit route network design problem without zone demand aggregation .     

Strategic network expansion of urban rapid transit systems: A bi‐objective programming model

With the development of urbanization and the extension of city boundaries, the expansion of rapid transit systems based on the existing lines becomes an essential issue in urban transportation systems. In this study, the network expansion problem is formulated as a bi‐objective programming model to minimize the construction cost and maximize the total travel demand covered by the newly introduced transit lines. To solve the bi‐objective mixed‐integer linear program, an approach called minimum distance to the utopia point is applied. Thus, the specific trade‐off is suggested to the decision makers instead of a series of optimal solutions. A real‐world case study based on the metro network in Wuxi, China, is conducted, and the results demonstrate the effectiveness and efficiency of the proposed model and solution method. It is found that the utopia method can not only provide a reasonable connecting pattern of the network expansion problem but also identify the corridors with high priority under the limited budget condition.     

A Linear Model for the Continuous Network Design Problem

Abstract:   This article is concerned with the continuous network design problem on traffic networks, assuming system optimum traffic flow conditions and time-dependent demand. A linear programming formulation is introduced based on a dynamic traffic assignment (DTA) model that propagates traffic according to the cell transmission model. The introduced approach is limited to continuous link improvements and does not provide for new link additions. The main contribution of the article is to provide an analytical formulation for network design that accounts for DTA conditions that can be used for further analysis and extensions. The model is tested on a single destination example network, resembling a freeway corridor, for various congestion levels, loading patterns and budget sizes, to demonstrate the simplicity and effectiveness of the approach.