A Decision Support System for Crew Planning in Passenger Transportation Using a Flexible Branch-and-Price Algorithm

This paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. Since it is far from trivial to build such a system from the information provided in the existing literature, technical issues about the system and its implementation are covered in more detail. We also discuss several applications. In particular, we focus on a specific aircrew rostering application. The computational results contain an interesting comparison of results obtained with the approach in which crew scheduling is carried out before crew rostering, and an approach in which these two planning problems are solved in an integrated manner.     

Designing Least-Cost Nonblocking Broadband Networks

Integrated network technologies, such as ATM, support multimedia applications with vastly different bandwidth needs, connection request rates, and holding patterns. Due to their high level of flexibility and communication rates approaching several gigabits per second, the classical network planning techniques, which rely heavily on statistical analysis, are less relevant to this new generation of networks. In this paper, we propose a new model for broadband networks and investigate the question of their optimal topology from a worst-case performance point of view. Our model is more flexible and realistic than others in the literature, and our worst-case bounds are among the first in this area. Our results include a proof of intractability for some simple versions of the network design problem and efficient approximation algorithms for designing nonblocking networks of provably small cost. More specifically, assuming some mild global traffic constraints, we show that a minimum-cost nonblockingstarnetwork achieves near-optimal cost; the cost ratio is at most 2 if switch source and sink capacities are symmetric and at most 3 when the total source and sink capacities are balanced. In the special case of unit link costs, we can show that a star network is indeed the cheapest nonblocking network.     

Designing Heteroclinic and Excitable Networks in Phase Space Using Two Populations of Coupled Cells

We give a constructive method for realising an arbitrary directed graph (with no one-cycles) as a heteroclinic or an excitable dynamic network in the phase space of a system of coupled cells of two types. In each case, the system is expressed as a system of first-order differential equations. One of the cell types (the p-cells) interacts by mutual inhibition and classifies which vertex (state) we are currently close to, while the other cell type (the y-cells) excites the p-cells selectively and becomes active only when there is a transition between vertices. We exhibit open sets of parameter values such that these dynamical networks exist and demonstrate via numerical simulation that they can be attractors for suitably chosen parameters.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

WDM网络中的一个改进的最优半光通道路由算法

本文在一个限定的条件下，提出了一个WDM网络中的寻找最优半光通道算法，使时间复杂度从O（k^2n km knlog(kn))提高到O（k^2n km nlogn)。     

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented.     

WDM网络中的排序与波长分配问题的一个多项式时间近似方案

本文考虑基于波分复用技术 (WDM)的光学网络中的排序与波长分配问题 .在波长数目固定的情况下 ,我们证明此问题是NP 困难问题 ,并且给出一个多项式时间近似方案 .若波长数目不固定 ,我们证明此问题不存在多项式时间近似方案     

光通信链路建模与网络规划

光纤是通信网络中优质的传输媒介,具有传输频带宽、容量大、抗干扰性能好等优点.首先考虑光通信链路中放大器自发辐射噪声和光纤非线性效应等效噪声对其信道进行建模,并分析了三种不同调制格式下的误码率(BER)性能.进一步,基于联盟形成算法,考虑存在中间节点和不存在中间节点两种情况,对光通信网络进行最优规划以获得最大化网络价值.此外,基于概率整形和几何整形原理对星座图进行设计,实现了误码率性能的改善.     

A Note on Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problems

One algorithm proposed in Branch-and-price algorithms for the one-dimensional cutting stock problems (COAP, vol. 9, pp. 211–228, 1998) may not find an optimal solution to the cutting stock problem, as it is stated.     

光传送网的建模与拓扑规划

光传送网是指在光域内实现业务信号的传送、复用、路由选择、监控的传送网络.由于其具有大容量、高可靠性和低能耗的优点,光传送网在全球通信中扮演着至关重要的作用.因此对光传送网的链路进行准确建模,从而制定网络规划至关重要.研究了光传送网的三个重要问题,并对问题进行了数学建模与模型求解.首先依据经典的调制编码格式建立了光传送网的链路传送模型,并对其传输性能进行了度量;然后以网络价值最大化原则,从不同方面为我国城市群制定网络价值最优化的规划方案;最后对经典调制编码格式进行了改进,提出容噪能力更强的新型调制编码方案.对上述模型进行了仿真求解,建模与规划算法取得了较好的实验效果.     

Branch-and-Price for a European variant of the Railroad Blocking Problem

In wagonload traffic, a production form in railway freight traffic, small groups of wagons have to be transported. In order to decrease transportation costs, wagons from different relations are consolidated. In railyards trains can be separated and rearranged to new trains. The costs arising from this process, which is called reclassification, must be balanced with the transportation costs. The minimization of total costs can be formulated as a network optimization model. We introduce a branch-and-price approach for the considered problem. Moreover, we present specialized cuts, which can be incorporated into the branching scheme. Solutions obtained from our implementation can keep up with results computed by CPLEX.     

A Branch-and-Price algorithm for the Single Source Capacitated Plant Location Problem

This paper considers the Single Source Capacitated Plant Location Problem (SSCPLP). We propose an exact algorithm in which a column generation procedure for finding upper and lower bounds is incorporated within a Branch-and-Price framework. The bounding procedure exploits the structure of the problem by means of an iterative approach. At each iteration, a two-level optimization problem is considered. The two levels correspond with the two decisions to be taken: first, the selection of a subset of plants to be opened and then, the allocation of clients within the subset of open plants. The second level subproblem is solved using column generation. The algorithm has been tested with different sets of test problems and the obtained results are satisfactory.     

Estimating Missing Values Using Neural Networks

The problem of missing values is common in statistical analysis. One approach to deal with missing values is to delete the incomplete cases from the data set. This approach may disregard valuable information, especially in small samples. An alternative approach is to reconstruct the missing values using the information in the data set. The major purpose of this paper is to investigate how a neural network approach performs compared to statistical techniques for reconstructing missing values. The backpropagation algorithm is used as the learning method to reconstruct missing values. The results of back-propagation are compared with results from two methods, viz., (1) using averages, and (2) using iterative regression analysis, to compute missing values. Experimental results show that backpropagation consistently outperforms other methods in both the training and the test data sets, and suggest that the neural network approach is a useful tool for reconstructing missing values in multivariate analysis.     

A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands

We address the Capacitated Arc Routing Problem with Stochastic Demands (CARPSD), which we formulate as a Set Partitioning Problem. The CARPSD is solved by a Branch-and-Price algorithm, which we apply without graph transformation. The demand’s stochastic nature is incorporated into the pricing problem. Computational results are reported.     

基于概率神经网络的欺诈性财务报告的识别研究

本文探索概率神经网络PNNs(Probabilistic Neural Networks)在构建欺诈性财务报告识别模型方面的有效性,重点探讨了PNN模型变量的选择及平滑参数的确定问题,同时将所提出模型的性能和人工神经网络(ANNs)、logit回归模型的性能进行了比较.结果证明,PNN模型具有很高的预测力,并发现该模型的性能优于ANN模型以及logit回归模型.     

利用贝叶斯网络分析基因表达数据

利用基因表达数据提出一种新的网络模型—贝叶斯网络,发现基因的互作.一个贝叶斯网络是多变量联合概率分布的有向图模型,表示变量间的条件独立属性.首先我们阐明贝叶斯网络如何表示基因间的互作,然后介绍从基因芯片数据学习贝叶斯网络的方法.     

用循环图构造可靠通讯网络

本文得到了５度、７～１５度连通循环图的连通度等于其度数的充要条件。从而可用循环图构造可靠通讯网络。     

Prediction of the Amount of Wood Using Neural Networks

Coniferous trees such as eucalyptus used to be preferred for papermaking because the cellulose fiber in the pulp of these species are longer, therefore making for stronger paper. In this study, the proposed neural network method solves in an efficient way, how to build prediction models in engineering. The system has been applied to predict amount of wood for production of paper, in which the coefficients can explain the variable with more influence over the variable to forecast. Obtaining a good prediction and as simple as possible, i.e. with the least number of forecast variables.     

人工神经网络在SARS疫情分析与预测中的应用

讨论人工神经网络在 SARS疫情分析与预测中的应用 .采用三层结构的反向传播网络 ( Backpropagation network,简称 BP网络 ) ,对 SARS在中国的传播与流行趋势及控制策略建立了网络模型 .并利用实际数据拟合参数 ,针对北京、山西的疫情进行了计算仿真 .结果表明 ,该网络模型算法收敛速度较快 ,预测精度很高     

Stochastic Networks: Admission and Routing Using Penalty Functions

We propose an admission and routing control policy for a network of service facilities in a stochastic setting in order to maximize a long run average reward. Queueing and reneging before entering the network is allowed; we introduce orbiting as an approximation to the queueing. Once a customer has entered the network, it incurs no more waiting. Our control policy is easy to implement and we prove that it performs well in steady state as long as the capacity request sizes are relatively small compared to the capacity of the service facilities. The policy is a target tracking policy: a linear program provides a target operating point and an exponential penalty function is used to translate the optimal deterministic point into a feasible admission and routing policy. This translation essentially transforms the admission and routing control problem into a problem of load balancing via the construction of fictitious systems. Simulation studies are included to illustrate that our policy also performs well when request sizes are moderate or large with respect to the capacity.