A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem

In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+. The GOSST problem has some important applications. In network design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements.     

An exact algorithm for solving the bilevel facility interdiction and fortification problem

We present an exact approach for solving the $r$-interdiction median problem with fortification. Our approach consists of solving a greedy heuristic and a set cover problem iteratively that guarantees to find an optimal solution upon termination. The greedy heuristic obtains a feasible solution to the problem, and the set cover problem is solved to verify optimality of the solution and to provide a direction for improvement if not optimal. We demonstrate the performance of the algorithm in a computational study.     

基于辛格式的深度哈密尔顿神经网络

HNN是一类基于物理先验学习哈密尔顿系统的神经网络.本文通过误差分析解释使用不同积分器作为超参数对HNN的影响.如果我们把网络目标定义为在任意训练集上损失为零的映射,那么传统的积分器无法保证HNN存在网络目标.我们引进反修正方程,并严格证明基于辛格式的HNN具有网络目标,且它与原哈密尔顿量之差依赖于数值格式的精度.数值实验表明,由辛HNN得到的哈密尔顿系统的相流不能精确保持原哈密尔顿量,但保持网络目标;网络目标在训练集、测试集上的损失远小于原哈密尔顿量的损失;在预测问题上辛HNN较非辛HNN具备更强大的泛化能力和更高的精度.因此,辛格式对于HNN是至关重要的.     

开源教学平台的可用性研究——以Sakai为例

越来越多的国内外高校开始考虑使用基于开源软件的网络教学平台,在投入使用之前,开源教学平台一般需要进行二次开发过程,其中需要重点解决平台的可用性问题,因为网络教学平台的可用性是影响学习效果的重要因素.发现并解决网络教学环境中的可用性问题,是促进人机交互、提高学习效率的重要途径.开源教学平台的可用性指的是系统的有效性、效率和满意度,分析了网络教学平台的可用性诉求,并以浙江大学Sakai开放学习平台为例,进行个案研究.使用了ThinkAloud、观察法和访谈法等可用性测试方法,研究结果发现,浙江大学Sakai开放学习平台主要功能人机交互设计合理,但是由于文化差异和用户使用习惯问题,部分功能存在一定的可用性问题,值得学习平台设计者借鉴.     

Optimal infrastructure design and expansion of broadband wireless access networks

This paper investigates the important infrastructure design and expansion problem for broadband wireless access networks subject to user demand constraints and system capacity constraints. For the problem, an integer program is derived and a heuristic solution procedure is proposed based on Lagrangean relaxation. In the computational experiments, our Lagrangean relaxation based algorithm can solve this complex design and expansion problem quickly and near optimally. Based on the test results, it is suggested that the proposed algorithm may be practically used for the infrastructure design and expansion problem for broadband wireless access networks.     

Network DEA approach to airports performance assessment considering undesirable outputs

In this paper, a directional distance approach is proposed to deal with network DEA problems in which the processes may generate not only desirable final outputs but also undesirable outputs. The proposed approach is applied to the problem of modelling and benchmarking airport operations. The corresponding network DEA model considers two process (Aircraft Movement and Aircraft Loading) with two final outputs (Annual Passenger Movement and Annual Cargo handled), one intermediate product (Aircraft Traffic Movements) and two undesirable outputs (Number of Delayed Flights and Accumulated Flight Delays). The proposed approach has been applied to Spanish airports data for year 2008 comparing the computed directional distance efficiency scores with those obtained using a conventional, single-process directional distance function approach. From this comparison, it can be concluded that the proposed network DEA approach has more discriminatory power than its single-process counterpart, uncovering more inefficiencies and providing more valid results.     

Optimal location with equitable loads

The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn ³) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.     

A capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

Robust improvement schemes for road networks under demand uncertainty

This paper is concerned with development of improvement schemes for road networks under future travel demand uncertainty. Three optimization models, sensitivity-based, scenario-based and min–max, are proposed for determining robust optimal improvement schemes that make system performance insensitive to realizations of uncertain demands or allow the system to perform better against the worst-case demand scenario. Numerical examples and simulation tests are presented to demonstrate and validate the proposed models.