The design of single allocation incomplete hub networks

The hub location problem deals with finding the location of hub facilities and allocating the demand nodes to these hub facilities so as to effectively route the demand between any origin–destination pair. In the extensive literature on this challenging network design problem, it has widely been assumed that the subgraph induced by the hub nodes is complete. Relaxation of this basic assumption constitutes the starting point of the present work. In this study, we provide a uniform modeling treatment to all the single allocation variants of the existing hub location problems, under the incomplete hub network design. No network structure other than connectivity is imposed on the induced hub network. Within this context, the single allocation incomplete p-hub median, the incomplete hub location with fixed costs, the incomplete hub covering, and the incomplete p-hub center network design problems are defined, and efficient mathematical formulations for these problems with O(n³) variables are introduced. Computational analyses with these formulations are presented on the various instances of the CAB data set and on the Turkish network.     

Single-assignment hub location problems with multiple capacity levels

In this paper, an extension of the classical capacitated single-allocation hub location problem is studied in which the size of the hubs is part of the decision making process. For each potential hub a set of capacities is assumed to be available among which one can be chosen. Several formulations are proposed for the problem, which are compared in terms of the bound provided by the linear programming relaxation. Different sets of inequalities are proposed to enhance the models. Several preprocessing tests are also presented with the goal of reducing the size of the models for each particular instance. The results of the computational experiments performed using the proposed models are reported.     

站城融合理念下高铁客运枢纽区域步行交通布置研究

本文对高铁客运枢纽区域内步行交通的影响范围和功能定位进行分析,提出在站城融合理念下,步行交通是高铁客运枢纽最重要的交通方式。利用开源数据,对比我国京沪高铁沿线与日本东海道新干线,以及北京南站、上海虹桥站、东京站、名古屋站,分析枢纽步行交通的影响因素,并提出站城融合背景下枢纽步行交通系统的规划建设重点和指标体系,为高铁客运枢纽实现站城融合、建立完善的步行交通系统提供参考。     

Assessment of hub status among Asian ports from a network perspective

This paper proposes a novel network-based hub port assessment (NHPA) model through explicit formulations of connectivity and cooperation indices. Such a model is useful for port operators and policy makers to evaluate the relative influences of various quality characteristics from which carriers base their port choices on and identify port partners. Key insights can be obtained for port authorities to improve their port infrastructures and operations to achieve a competitive and sustainable hub port status. Three comprehensive case studies are conducted to assess the current standings and potentials of major Asian ports within networks of major carriers.     

The design of capacitated intermodal hub networks with different vehicle types

In this study, we allow using alternative transportation modes and different types of vehicles in the hub networks to be designed. The aim of the problem is to determine the locations and capacities of hubs, which transportation modes to serve at hubs, allocation of non-hub nodes to hubs, and the number of vehicles of each type to operate on the hub network to route the demand between origin-destination pairs with minimum total cost. Total cost includes fixed costs of establishing hubs with different capacities, purchasing and operational costs of vehicles, transportation costs, and material handling costs. A mixed-integer programming model is developed and a variable neighborhood search algorithm is proposed for the solution of this problem. The heuristic algorithm is tested on instances from the Turkish network and CAB data set. Extensive computational analyzes are conducted in order to observe the effects of changes in various problem parameters on the resulting hub networks.     

Service network design with asset management: Formulations and comparative analyses

In this paper, we address the service network design with asset management problem, which integrates asset management considerations into service network design models for consolidation-based freight carriers. We propose model formulations based on arc variables for both flow and design, as well as formulations with path flow variables and new cycle design variables. Problem instances reflecting actual planning problems are used in the computational study to analyze the strengths and weaknesses of the various model formulations and the impact of asset management considerations on the transportation plan and the computational effort. Experimental results indicate that formulations based on cycle variables outperform traditional arc-based formulations, and that considering asset management issues may significantly impact the outcome of service planning models.     

Hub location in the South-Atlantic airline market: A spatial competition game

The paper analyzes the airlines’ hub location problem through a spatial competition game played in two stages. First, airlines sequentially choose the location of their hub and second, they compete offering direct or connecting services between each city-pair. Different outcomes in the first stage will affect competition in the second, and as a consequence, the market share that airlines can obtain.Given actual demand patterns, results of the model are applied to the South-Atlantic airline market. We study the subgame perfect equilibriums obtained as a result of competition in each city-pair to anticipate where airlines will probably locate their hubs once an “open skies” policy is adopted in this market.     

A disjunctive convex programming approach to the pollution-routing problem

The pollution-routing problem (PRP) aims to determine a set of routes and speed over each leg of the routes simultaneously to minimize the total operational and environmental costs. A common approach to solve the PRP exactly is through speed discretization, i.e., assuming that speed over each arc is chosen from a prescribed set of values. In this paper, we keep speed as a continuous decision variable within an interval and propose new formulations for the PRP. In particular, we build two mixed-integer convex optimization models for the PRP, by employing tools from disjunctive convex programming. These are the first arc-based formulations for the PRP with continuous speed. We also derive several families of valid inequalities to further strengthen both models. We test the proposed formulations on benchmark instances. Some instances are solved to optimality for the first time.     

On the existence of pricing strategies in the discrete time heterogeneous single bottleneck model

In this paper, we study the pricing strategies in the discrete time single bottleneck model with general heterogeneous commuters. We first prove that in the system optimal assignment, the queue time must be zero for all the departures. Based on this result, the system optimal problem is formulated as a linear program. The solution existence and uniqueness are discussed. Applying linear programming duality, we then prove that the optimal dual variable values provide an optimal toll with which the system optimal solution is also an equilibrium solution. Extensive computational results are reported to demonstrate the insights gained from the formulations in this paper. These results confirm that a system optimal equilibrium can be found using the proposed approach.     

Bus maintenance systems and maintenance scheduling: model formulations and solutions

This paper deals with the problem of scheduling bus maintenance activities. The scheduling of maintenance activities is an important component in bus transit operations planning process. The other components include network route design, setting timetables, scheduling vehicles, and assignment of drivers. This paper presents a mathematical programming approach to the problem. This approach takes as input a given daily operating schedule for all buses assigned to a depot along with available maintenance resources. It, then, attempts to design daily inspection and maintenance schedules for the buses that are due for inspection so as to minimize the interruptions in the daily bus operating schedule, and maximize the utilization of the maintenance facilities. Three integer programming formulations are presented and different properties of the problem are discussed. Several heuristic methods are presented and tested. Some of these procedures produce very close to optimal solutions very efficiently. In some cases, the computational times required to obtain these solutions are less than 1% of the computational time required for the conventional branch and bound algorithm. Several small examples are offered and the computational results of solving the problem for an actual, 181-bus transit property are reported.     

The reliable hub-and-spoke design problem: Models and algorithms

Hub-and-spoke structure is widely adopted in industry, especially in transportation and telecommunications applications. Although hub-and-spoke paradigm demonstrates significant advantages in improving network connectivity with less number of routes and saving operating cost, the failure of hubs and reactive disruption management could lead to substantial recovery cost to the operators. Thus, we propose a set of reliable hub-and-spoke network design models, where the selection of backup hubs and alternative routes are taken into consideration to proactively handle hub disruptions. To solve these nonlinear mixed integer formulations for reliable network design problems, Lagrangian relaxation and Branch-and-Bound methods are developed to efficiently obtain optimal solutions. Numerical experiments are conducted with respect to real data to demonstrate algorithm performance and to show that the resulting hub-and-spoke networks are more resilient to hub unavailability.     

枢纽机场航线网络优化研究

枢纽机场航线网络优化主要解决由于航线网络结构与功能定位不匹配而导致的机场连通性低、航线网络同质化竞争严重、运行效率低下的问题。通过改进引力模型对城市对间的客流量进行预测,以此为预测的客流量为依据之一,以提高机场连通性为目的,构建航线网络优化模型,并进行求解。实现提高枢纽机场连通性、构建符合功能定位的层级网络的目标。并以位于我国中部,具有"连接南北,贯穿东西"地理优势的西安咸阳国际机场为例进行分析。由于国际航线受客观因素较多,本文主要研究国内客运航线,国际及货运不在本文研究之列。     

Hub location with flow economies of scale

A characteristic feature of hub and spoke networks is the bundling of flows on the interhub links. This agglomeration of flows leads to reduced travel costs across the interhub links. Current models of hub location do not adequately model the scale economies of flow that accrue due to the agglomeration of flows. This paper shows that current hub location models, by assuming flow-independent costs, not only miscalculate total network cost, but may also erroneously select optimal hub locations and allocations. The model presented in this paper more explicitly models the scale economies that are generated on the interhub links and in doing so provides a more reliable model representation of the reality of hub and spoke networks.     

An aggregate demand model for air passenger traffic in the hub-and-spoke network

In this paper, we build an aggregate demand model for air passenger traffic in a hub-and-spoke network. This model considers the roles of airline service variables such as service frequency, aircraft size, ticket price, flight distance, and number of spokes in the network. It also takes into account the influence of local passengers and social-economic and demographic conditions in the spoke and hub metropolitan areas. The hub airport capacity, which has a significant impact on service quality in the hub airport and in the whole hub-and-spoke network, is also taken into consideration.Our demand model reveals that airlines can attract more connecting passengers in a hub-and-spoke network by increasing service frequency than by increasing aircraft size in the same percentage. Our research confirms the importance of local service to connecting passengers, and finds that, interestingly, airlines’ services in the first flight leg are more important to attract passengers than those in the second flight segment. Based on data in this study, we also find that a 1% reduction of ticket price will bring about 0.9% more connecting passengers, and a 1% increase of airport acceptance rate can bring about 0.35% more connecting passengers in the network, with all else equal. These findings are helpful for airlines to understand the effects of changing their services, and also useful for us to quantify the benefits of hub airport expansion projects.At the end of this paper, we give an example as an application to demonstrate how the developed demand model could be used to valuate passengers’ direct benefit from airport capacity expansion.     

Airport privatization in congested hub–spoke networks

This paper investigates the airport privatization issue. One congested hub and two linked local airports serve symmetric hub carriers. Passengers valuate the congestion delay cost and benefit from greater frequencies. The government considers privatizing either the hub or local airports. We find that in each privatizing scenario, welfare-maximizing public airport(s) set a charge below their operating costs in order to fully coordinate the high charge of privatized airport(s). If this fiscal deficit is not allowed, each scenario causes distortion. Interestingly, the distortion—and hence welfare losses—in privatizing a hub are smaller (larger) than those in privatizing both local airports when both passengers’ valuations are small (large); this is exactly the case when privatized local airports are strategic substitutes (complements). We also surprisingly find that retaining the hub airport as public and privatizing one or both local airports achieves the same market outcomes. We further find that if all airports are privatized, welfare becomes worse than the other scenarios; the hub airport charges lower (higher) prices than local airports when both local airports are strategic substitutes (complements).     

A two‐leveled multi‐objective symbiotic evolutionary algorithm for the hub and spoke location problem

We consider a hub and spoke location problem (HSLP) with multiple scenarios. The HSLP consists of four subproblems: hub location, spoke location, spoke allocation, and customer allocation Under multiple scenarios, we aim to provide a set of well‐distributed solutions, close to the true Pareto optimal solutions, for decision makers. We present a novel multi‐objective symbiotic evolutionary algorithm to solve the HSLP under multiple scenarios. The algorithm is modeled as a two‐leveled structure, which we call the two‐leveled multi‐objective symbiotic evolutionary algorithm (TMSEA). In TMSEA, two main processes imitating symbiotic evolution and endosymbiotic evolution are introduced to promote the diversity and convergence of solutions. The evolutionary components suitable for each sub‐problem are defined. TMSEA is tested on a variety of test‐bed problems and compared with existing multi‐objective evolutionary algorithms. The experimental results show that TMSEA is promising in solution convergence and diversity.     

Path-differentiated pricing in congestion mitigation

Instead of charging tolls on individual links, this paper considers doing the same on paths. Path and link tolls are “valid” if they encourage motorists to use routes that collectively lead to a target distribution, e.g., one that minimizes travel delay. Because the numbers of valid link and path tolls are typically infinite, an objective in pricing tolls is to find a set of valid tolls that yields the least revenue to lessen the financial burden on motorists.Path tolls are generally more flexible than link tolls and this paper shows that this flexibility can substantially reduce the financial burden on motorists. Additionally, valid path tolls yielding the least revenue possess characteristics with interesting policy implications. To determine these path tolls, it is natural to formulate the problem as a mathematical program with complementarity constraints. However, this paper also investigates alternative formulations that highlight the problem’s complexity and suggest ways to solve the problem efficiently.     

Complementarity formulations for the cell transmission model based dynamic user equilibrium with departure time choice, elastic demand and user heterogeneity

In this paper we formulate the dynamic user equilibrium problem with an embedded cell transmission model on a network with a single OD pair, multiple parallel paths, multiple user classes with elastic demand. The formulation is based on ideas from complementarity theory. The travel time is estimated based on two methods which have different transportation applications: (1) maximum travel time and (2) average travel time. These travel time functions result in linear and non-linear complementarity formulations respectively. Solution existence and the properties of the formulations are rigorously analyzed. Extensive computational experiments are conducted to demonstrate the benefits of the proposed formulations on various test networks.     

Fuel burn and environmental implications of airline hub networks

Hubs act as switching points for interactions and so are places through which flows are concentrated. This research uses the interactions between a system of cities as an experimental context for understanding selected environmental costs and benefits of concentrated flow. Whether hub based networks create additional environmental costs has been debated in the literature. In this paper, fuel burn is used as an indicator of environmental cost. The essential ideas are: (1) to examine fuel costs associated with larger aircraft; (2) to determine implications of higher loads on dense routes; and (3) to model the resulting implications for hub and gateway location. Variants of these questions apply to passenger and freight flows, and the paper will initially concentrate on passenger models.The paper shows that by modeling fuel burn and introducing a fixed charge (like a set up cost), a multiple allocation hub and spoke model can be adjusted to direct more or less flow onto the inter-facility connector. In other words, usage of multiple connections and direct links can be controlled and modeled as a function of the fixed charge. The resulting networks are characterized by quite different levels of passenger miles, aggregate fuel burn and fixed charges. The preferred network in terms of minimal fuel burn is found by subtracting the fixed set up charge, thereby focusing attention on the modeled fuel burn. The lowest cost set up is a network with a high degree of connectivity, and a pure single assignment hub network has the highest fuel cost (as a result of larger passenger miles needed by connecting paths). The data also allow a tabulation of total passenger miles, which, not surprisingly, track very closely with the fuel burn. In an interesting application of the ideas, it is shown that a fuel efficient network may require a large number of smaller regional jets, and in the interests of avoiding noise and congestion from so many extra airport operations, the carriers may choose to substitute a smaller number of larger planes, thereby slightly increasing fuel needs. This paper also provides a key ingredient for models of an international network where it is impossible to serve many long distance market pairs without consolidation.     

国家级综合运输枢纽型城市发展策略研究

以南京市为例,从枢纽型城市整体构建、综合运输通道系统、综合运输枢纽集疏运体系、保障策略四个方面综合提出构建国家级综合运输型城市的发展策略。