长江干线航道条件与船舶定线制问题分析与研究

通过分析长江干线已实施船舶定线制的特点,分析船舶定线制的一般形式与通航条件,提出了长江干线船舶定线制的航道尺度计算方法和水流条件指标,并结合航道条件,提出了长江干线其他未实施船舶定线制河段的定线制形式,为进一步完善内河船舶定线制提供了一种方法和思路。     

The design of bus route systems — An interactive location-allocation approach

An interactive modelling approach is developed to solve the practical problem of bus route network design. Possible bus routes are identified with facilities which can be located. Zones or pairs of zones in the urban area are identified with customers who will be allocated to the established facilities. It is shown that the classical Set Covering Problem is useful under the assumption of fixed demand; the Simple Plant Location Problem is effective under the assumption of demand which is sensitive to the level of bus service provided.     

基于无线Mesh网络技术的列车宽带接入原型系统设计

随着高速铁路、公路交通的发展,信息网络的移动接入技术需要得到相应的改善和提高。根据公共移动通信网和铁路专用移动通信网的发展现状,目前有多种列车移动接入技术。通过方案比较,本文原型系统采用了基于无线Mesh网络技术的无线宽带接入技术。当前,无线Mesh网络可遵循的标准有IEEE802.11s草案,该草案对无线Mesh网络的功能、接口及网络协议栈进行了全面的定义。本文根据IEEE802.11s草案,在Linux操作系统下定义了Mesh协议栈框架,并在此基础上设计实现了针对列车的车地宽带接入带状应用场景的无线Mesh网络原型系统,并就搭建的实际网络场景进行了性能测试。实验结果表明,所设计的原型系统基本达到了列车车地宽带接入应用的要求。     

考虑均衡性的城市轨道交通线路负荷水平评估研究

线路负荷水平的评价工作是优化运输组织方案的重要前提。首先,本文分析了采用单一均值性指标表征负荷水平不能体现线路内负荷分布偏差的问题。为此,从城市轨道交通线路客流与运输能力匹配的角度出发,以列车负荷为评价单元,建立包括负荷均值和标准差率二维指标的线路负荷水平评估模型。负荷均值指标考虑了各评价单元加权计算,以反映每个评价单元对线路负荷水平的贡献程度,标准差率指标表征负荷均衡性。模型分析得出,线路所有区间的运力同等规模变化不影响标准差率指标,相对提高大客流区间或大客流方向上的输送能力能够改善线路负荷的均衡性。算例分析表明：客流方向不均衡系数超过 1.4 时,应考虑运力优化措施以提高运输能力利用的均衡;组织列车大小交路方案和不成对行车模式,能够提高线路负荷的均衡程度。     

A hybrid optimization-simulation approach for robust weekly aircraft routing and retiming

We address the robust weekly aircraft routing and retiming problem, which requires determining weekly schedules for a heterogeneous fleet that maximizes the aircraft on-time performance, minimizes the total delay, and minimizes the number of delayed passengers. The fleet is required to serve a set of flights having known departure time windows while satisfying maintenance constraints. All flights are subject to random delays that may propagate through the network. We propose to solve this problem using a hybrid optimization-simulation approach based on a novel mixed-integer nonlinear programming model for the robust weekly aircraft maintenance routing problem. For this model, we provide an equivalent mixed-integer linear programming formulation that can be solved using a commercial solver. Furthermore, we describe a Monte-Carlo-based procedure for sequentially adjusting the flight departure times. We perform an extensive computational study using instances obtained from a major international airline, having up to 3387 flights and 164 aircraft, which demonstrates the efficacy of the proposed approach. Using the simulation software SimAir to assess the robustness of the solutions produced by our approach in comparison with that for the original solutions implemented by the airline, we found that on-time performance was improved by 9.8–16.0%, cumulative delay was reduced by 25.4–33.1%, and the number of delayed passengers was reduced by 8.2–51.6%.     

The load-dependent vehicle routing problem and its pick-up and delivery extension

The present paper examines a Vehicle Routing Problem (VRP) of major practical importance which is referred to as the Load-Dependent VRP (LDVRP). LDVRP is applicable for transportation activities where the weight of the transported cargo accounts for a significant part of the vehicle gross weight. Contrary to the basic VRP which calls for the minimization of the distance travelled, the LDVRP objective is aimed at minimizing the total product of the distance travelled and the gross weight carried along this distance. Thus, it is capable of producing sensible routing plans which take into account the variation of the cargo weight along the vehicle trips. The LDVRP objective is closely related to the total energy requirements of the vehicle fleet, making it a credible alternative when the environmental aspects of transportation activities are examined and optimized. A novel LDVRP extension which considers simultaneous pick-up and delivery service is introduced, formulated and solved for the first time. To deal with large-scale instances of the examined problems, we propose a local-search algorithm. Towards an efficient implementation, the local-search algorithm employs a computational scheme which calculates the complex weighted-distance objective changes in constant time. Solution results are presented for both problems on a variety of well-known test cases demonstrating the effectiveness of the proposed solution approach. The structure of the obtained LDVRP and VRP solutions is compared in pursuit of interesting conclusions on the relative suitability of the two routing models, when the decision maker must deal with the weighted distance objective. In addition, results of a branch-and-cut procedure for small-scale instances of the LDVRP with simultaneous pick-ups and deliveries are reported. Finally, extensive computational experiments have been performed to explore the managerial implications of three key problem characteristics, namely the deviation of customer demands, the cargo to tare weight ratio, as well as the size of the available vehicle fleet.     

Stability of transportation networks under adaptive routing policies

Growing concerns regarding urban congestion, and the recent explosion of mobile devices able to provide real-time information to traffic users have motivated increasing reliance on real-time route guidance for the online management of traffic networks. However, while the theory of traffic equilibria is very well-known, fewer results exist on the stability of such equilibria, especially in the context of adaptive routing policy. In this work, we consider the problem of characterizing the stability properties of traffic equilibria in the context of online adaptive route choice induced by GPS-based decision making. We first extend the recent framework of “Markovian Traffic Equilibria” (MTE), in which users update their route choice at each intersection of the road network based on traffic conditions, to the case of non-equilibrium conditions, while preserving consistency with known existence and uniqueness results on MTE. We then exhibit sufficient conditions on the network topology and the latency functions for those MTEs to be stable in the sense of Lyapunov for a single destination problem. For various more restricted classes of network topologies motivated by the observed properties of travel patterns in the Singapore network, under certain assumptions we prove local exponential stability of the MTE, and derive analytical results on the sensitivity of the characteristic time of convergence to network and traffic parameters. The results proposed in this work are illustrated and validated on synthetic toy problems as well as on the Singapore road network with real demand and traffic data.     

Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem

In this paper, we study two closely related airline planning problems: the robust weekly aircraft maintenance routing problem (RWAMRP) and the tail assignment problem (TAP). In real life operations, the RWAMRP solution is used in tactical planning whereas the TAP solution is implemented in operational planning. The main objective of these two problems is to minimize the total expected propagated delay (EPD) of the aircraft routes. To formulate the RWAMRP, we propose a novel weekly line-of-flights (LOF) network model that can handle complex and nonlinear cost functions of EPD. Because the number of LOFs grows exponentially with the number of flights to be scheduled, we propose a two-stage column generation approach to efficiently solve large-scale real-life RWAMRPs. Because the EPD of an LOF is highly nonlinear and can be very time-consuming to accurately compute, we propose three lower bounds on the EPD to solve the pricing subproblem of the column generation. Our approach is tested on eight real-life test instances. The computational results show that the proposed approach provides very tight LP relaxation (within 0.6% of optimal solutions) and solves the test case with more than 6000 flights per week in less than three hours. We also investigate the solutions obtained by our approach over 500 simulated realizations. The simulation results demonstrate that, in all eight test instances, our solutions result in less EPDs than those obtained from traditional methods. We then extend our model and solution approach to solve realistically simulated TAP instances.     

A rolling horizon algorithm for auto-carrier transportation

This paper introduces a rolling horizon algorithm to plan the delivery of vehicles to automotive dealers by a heterogeneous fleet of auto-carriers. The problem consists in scheduling the deliveries over a multiple-day planning horizon during which requests for transportation arrive dynamically. In addition, the routing of the auto-carriers must take into account constraints related to the loading of the vehicles on the carriers. The objective is to minimize the sum of traveled distances, fixed costs for auto-carrier operation, service costs, and penalties for late deliveries. The problem is solved by a heuristic that first selects the vehicles to be delivered in the next few days and then optimizes the deliveries by an iterated local search procedure. A branch-and-bound search is used to check the feasibility of the loading. To handle the dynamic nature of the problem, the complete algorithm is applied repeatedly in a rolling horizon framework. Computational results on data from a major European logistics service provider show that the heuristic is fast and yields significant improvements compared to the sequential solution of independent daily problems.     

Generalized Maximum Benefit Multiple Chinese Postman Problem

This research is focused on a generalization on the Max Benefit Chinese Postman Problem and the multiple vehicle variant of the Chinese Postman Problem. We call this generalization, the Generalized Maximum Benefit k-Chinese Postman Problem (GB k-CPP). We present a novel Mixed Integer Programming (MIP) formulation for the GB k-CPP. Four different cases of the model are discussed. The first case, performs arc-routing with profits and assumes that the origin and destination for each vehicle is the same for each cycle and is given by the user. The next case relaxes the assumption that the origin and destination for each vehicle should be the same and allows the users to select possible origins/destinations for vehicles. Case three gets the origin for each vehicle as input and produces a solution based on finding the best destination for each vehicle. The last case, that is very general, allows the optimization model to select possibly different locations for vehicle origin and destination, during each cycle. The different cases are applied to a security patrolling case conducted on the network of University of Maryland at College Park campus and the results are compared.