A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem

Discrete network design problem (DNDP) is generally formulated as a bi-level programming. Because of non-convexity of bi-level formulation of DNDP which stems from the equilibrium conditions, finding global optimal solutions are very demanding. In this paper, a new branch and bound algorithm being able to find exact solution of the problem is presented. A lower bound for the upper-level objective and its computation method are developed. Numerical experiments show that our algorithm is superior to previous algorithms in terms of both computation time and solution quality. The conducted experiments indicate that in most cases the first incumbent solution which is obtained within a few seconds is superior to the final solution of some of previous algorithms.     

TV—Anytime服务器网络中一个映射问题的启发式算法

介绍了一个称为TV－Anytime的新型宽带媒体服务,提出了一个基于层次型服务器网络之上的大规模TV－Anytime系统模型。着重地研究了其中一个关键问题－－服务器网络的影像对象映射问题,并形式化地将其定义为一个组合优化问题。基于服务器网络的总存储容量、连接服务器结点之间的主干网通信带宽、用户的服务请求模式,来考虑尽大化服务器网络可提供的总服务质量。给出了基于模拟退火的启发式算法集,并基于一套映射问题的基准集实例对算法进行了模拟和性能分析。算法得到近似最优的方案。     

A Decomposition Scheme for System Optimal Dynamic Traffic Assignment Models

In this paper, a Dantzig-Wolfe decomposition based solution algorithm is developed for the linear programming formulation introduced by Ziliaskopoulos (2000) for System Optimal Dynamic Traffic Assignment problem. The algorithm takes advantage of the network structure in the constraint set of the formulation: the sub-problem is formulated as a minimum-cost-flow problem and the master as a simpler linear programming problem, which allows DTA to be solved more efficiently on meaningful networks. The algorithm is tested on an example network and its performance is analyzed.     

基于粗糙集优化神经网络结构的启发式算法

为了解决神经网络设计中确定网络结构尤其是隐层单元数的问题,提出了一种基于粗糙集理论确定神经网络结构的启发式算法.通过粗糙集理论属性约简算法对训练样本数据进行处理,根据处理结果确定网络的输入、输出以及隐层单元数.在对A320飞机自动驾驶仪不能衔接的故障诊断实例中,所设计的网络在训练中能够快速收敛,相对于传统的试探法能更快速准确地确定网络结构,从而提高飞机故障诊断效率,缩短维修时间,证明了该方法的实际可行性.     

Integrated Network Capacity Expansion and Traffic Signal Optimization Problem: Robust Bi-level Dynamic Formulation

This paper presents a robust optimization formulation, with an exact solution method, that simultaneously solves continuous network capacity expansion, traffic signal optimization and dynamic traffic assignment when explicitly accounting for an appropriate robustness measure, the inherent bi-level nature of the problem and long-term O-D demand uncertainty. The adopted robustness measure is the weighted sum of expected total system travel time (TSTT) and squared up-side deviation from a fixed target. The model propagates traffic according to Daganzo’s cell transmission model. Furthermore, we formulate five additional, related models. We find that when evaluated in terms of robustness, the integrated robust model performs the best, and interestingly the sequential robust approach yields a worse solution compared to certain sequential and integrated approaches. Although the adopted objective of the integrated robust model does not directly optimize the variance of TSTT, our experimental results show that the robust solutions also yield the least-variance solutions.     

基于空间分解的集装箱布局启发式算法及布局空间利用率规律

针对集装箱布局提出了一种利用三叉树结构表达三维矩形物体布局状态空间的方法。通过将布避空间依据分割,每次放入相对于当前布局空间来说是满足特定折最优布局块,将该布局块定位于当前布局空间后部的左下角,来完成不同大小的三维矩形全的布局方案的确定,并给出试验结果。     

基于多约束QoS问题的启发式算法

由于多媒体通信的需要,QoS路由技术已成为通信网络中研究的热点。通常情况下,在网络中寻找同时满足多个独立加性约束条件的路由是一个NP完全问题。本文探讨了多约束条件下的路径选择(MCP)问题,通过将MCP问题转化为离散化的动态网络,得到了一个性能更好的启发式QoS路由算法,复杂度从O(Tmn)降低为O(Tm),其中m、n分别是节点数和边数,T是算法定义的正整数,并在理论上证明了算法的正确性。最后给出实验举例,并通过与现有算法性能比较,表明改进的启发式算法能快速、有效地解决MCP问题,且适用于大规模的网络系统。     

基于动态约束网络的约束优化分解

约束网络通过对较大规模的任务和问题的分解,传递了并行工程产品开发过程中的各多功能小组之间必然存在的相互制约、相互依赖的关系。在任务和问题简单分解的过程中,由于所得到的子问题之间通常是不能完全独立的,因而只能在有限程度上降低难度、简化问题。在分析了约束求解的研究现状和不足的基础上,提出了一种基于动态约束的约束优化分解方法,使得各个子任务、子问题间的关系得到进一步的分解,从而在满足原要求的基础上,得到优化的结果。     

A Dual Variable Approximation Based Heuristic for Dynamic Congestion Pricing

This work presents a heuristic combining dual variable approximation techniques and the method of successive average to determine the time-varying tolls in a general transportation network. The dual approximation techniques exploit the linear programming structure of the underlying assignment problem which uses the cell transmission model to propagate the traffic dynamics. Both the first best and second best time-varying tolls can be determined in a computationally efficient manner with the proposed heuristic. Numerical experiments are conducted on two networks of different sizes to show the efficacy of the heuristic. From the experiments conducted, the proposed heuristic obtains the solutions with the maximum optimality gap of 2.03%.     

电子侦察卫星动态调度问题的快速启发式算法

卫星电子侦察中针对动态突发事件重新制定侦察计划是侦察任务规划所要解决的基本问题.分析导致动态调度的扰动因素,把不同扰动下的动态调度问题归结为一类复杂约束下的任务插入问题.建立混合整数规划模型,提出快速启发式任务插入算法(含三个基本算法--直接插入任务算法、移位插入任务算法和替换插入任务算法);基于初始调度方案的优良特性,极大降低动态调度复杂性.仿真实验表明:该算法能有效解决电子侦察卫星动态调度问题.     

一种实用化接入段全带宽动态分配方案

针对接入段多业务非均匀突发性特点,提出了一种实用的全带宽动态分配方案,该方案允许单业务最大可用带宽超出其公平共享范围。分析和实践结果表明,在保证带宽利用率、公平性和满足用户QoS指标的同时,该方案可使有需求链路在系统处于非饱和状态时占用全部剩余带宽(直至全带宽),大大提高系统的总带宽利用率。     

Stochastic and Dynamic Shipper Carrier Network Design Problem

The focus of this work is to determine the optimal storage capacity to be installed on transhipment nodes by shippers in a dynamic shipper carrier network under stochastic demand. A two stage linear program with recourse formulation is developed where in the first stage, the shipper decides the optimal capacity to be installed on transhipment nodes. In the second stage, the shipper chooses a routing strategy based on the realized demand. The performance of the following solution methods: Stochastic L Shaped Method, Regularized Decomposition and L Shaped Method with preliminary cuts were compared for various network sizes and numerous demand scenarios. A novel capacity shifting heuristic was introduced to generate a feasible implementable solution which significantly improves the performance of Regularized Decomposition and provides the best performance in the cases tested. Various ways of generating analytical bounds on the objective function value was discussed. The new capacity shifting heuristic was found to be efficient in generating tight upper bounds. Even though the formulation considered in this paper is for a single commodity, the model can be easily extended to account for multiple commodities.     

一种求解集合覆盖问题的启发式算法

集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小.集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域.对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法.本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法.算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列.用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的.     

基于禁忌搜索的启发式算法求解圆形packing问题

求解具有NP难度的圆形packing问题具有很高的理论与实用价值．现提出一个有效的启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题．此算法首先将圆按给定的优先级分组,然后逐组地用拟物拟人法放置圆,并且在整个过程中利用了禁忌搜索法的思想,通过禁止重复前面已做的工作,使搜索能有效地逃离局部极小值的陷阱,提高了搜索效率．实验结果表明,提出的算法是一个高效的实用求解算法．     

A Heuristic Algorithm for Hierarchical Hub-and-spoke Network of Time-definite Common Carrier Operation Planning Problem

Designing a heuristic approach to solve time-definite common carrier operation planning problem is the purpose of this research. The time-definite common carrier operation planning is implemented using the arcs and nodes of a hierarchical hub-and-spoke network. In light of the complexity involved in determining the types of the vehicles, as well as their associated routing and scheduling simultaneously, we design an algorithm, which employs the concept of tabu search to solve the network structure problem. The testing data are obtained from the second largest time-definite common carrier in Taiwan. When applied to the data of this test case company, the designed tabu search algorithm can obtain final solutions in a relatively short time regardless of the level of service required. Carriers can plan their operations according to the solutions on the operation networks. Although it is possible that the designed heuristic algorithm may converge to a local optimal solution, it can be a meaningful approach for the industrial application that emphasizes the value of time and can be satisfied with a near-optimal solution.     

一种用于作战任务分解的启发式算法研究

针对多CGF(Computer Generated Force,计算机生成兵力)协同仿真系统中面临的复杂作战任务描述和分解问题,首先对其进行了形式化描述,将任务分解问题转化为有约束条件下的最小开销问题,然后提出了一种启发式的任务分解算法,给出了算法的具体实现步骤.经过实际算例检验,该算法能较为有效地实现复杂任务的分解.     

一种平板车装载问题的启发式算法

提出平板车装载问题的一各上启发式方法,不仅能够从几种型号的平板车中选择出一种装载性能较好的平板车,而且能够将具有不同特性的不同尺寸的物品放在该型号平板车中,它能够在满足一些约束条件下求得一种可行的装载方案,实例充分证明了该算法的有效性和实用性,能够直接用于实际生活中。     

集合覆盖问题的启发函数算法

本文给出了求解NP困难问题的完备策略的概念,在此基础上提出了一个求解集合覆盖问题的启发函数算法SCHF(set-covering heuristic function),文中对该算法的合理性、时间复杂性以及解的精度进行了分析,本文的主要创新点是用已知的完备策略建立启发函数,并用该启发函数进行空间搜索求出优化解.该方法具有一定的普遍性,可以应用到其它的NP困难问题.它为求解NP困难问题的近似解提供了一种行之有效的方法.在规则学习中的应用结果表明,本文给出的SCHF算法是非常有效的.     

一种求解矩形块装填问题的拟人算法

在货物装载、木材下料、超大规模集成电路（VLSI）设计等工作中提出了矩形块装填与切割问题，对这一问题，国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验，提出了一种求解矩形块装填问题的拟人算法。谊算法使用了两个主要的思想策略，即矩形块选择策略和矩形块放置策略。用本文提出的算法，对21个测试算例进行了实算测试，测试结果表明：算法所得装填结果的优度高，计算时间短。对这21个测试算例。用本文算法计算，得到了其中16个算例的最优解，而计算时间都在2秒以内。进一步的测试表明，本文提出的算法对求解矩形块装填问题十分有效。