Optimality versus run time for isolated signalized intersections

Simulation-based optimization of traffic signal timing has become pervasive and popular, in the field of traffic engineering. When the underlying simulation model is well-trusted and/or well-calibrated, it is only natural that typical engineers would want their signal timing optimized using the judgment of that same model. As such, it becomes important that the heuristic search methods typically used by these optimizations are capable of locating global optimum solutions, for a wide range of signal systems. However off-line and real-time solutions alike offer just a subset of the available search methods. The result is that many optimizations are likely converging prematurely on mediocre solutions. In response, this paper compares several search methods from the literature, in terms of both optimality (i.e., solution quality) and computer run times. Simulated annealing and genetic algorithm methods were equally effective in achieving near-global optimum solutions. Two selection methods (roulette wheel and tournament), commonly used within genetic algorithms, exhibited similar effectiveness. Tabu searching did not provide significant benefits. Trajectories of optimality versus run time (OVERT) were similar for each method, except some methods aborted early along the same trajectory. Hill-climbing searches always aborted early, even with a large number of step-sizes. Other methods only aborted early when applied with ineffective parameter settings (e.g. mutation rate, annealing schedule). These findings imply (1) today’s products encourage a sub-optimal “one size fits all” approach, (2) heuristic search methods and parameters should be carefully selected based on the system being optimized, (3) weaker searches abort early along the OVERT curve, and (4) improper choice of methods and/or parameters can reduce optimization benefits by 22–33%.     

Metaheuristics for efficient aircraft scheduling and re-routing at busy terminal control areas

Intelligent decision support systems for the real-time management of landing and take-off operations can be very effective in helping air traffic controllers to limit airport congestion at busy terminal control areas. The key optimization problem to be solved regards the assignment of airport resources to take-off and landing aircraft and the aircraft sequencing on them. The problem can be formulated as a mixed integer linear program. However, since this problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY solver (a state-of-the-art optimization solver to deal with complex routing and scheduling problems) in order to improve the possibility of finding good quality solutions quickly. The proposed framework starts from a good initial solution for the aircraft scheduling problem with fixed routes (given the resources to be traversed by each aircraft), computed via a truncated branch-and-bound algorithm. A metaheuristic is then applied to improve the solution by re-routing some aircraft in the terminal control area. New metaheuristics, based on variable neighbourhood search, tabu search and hybrid schemes, are introduced. Computational experiments are performed on an Italian terminal control area under various types of disturbances, including multiple aircraft delays and a temporarily disrupted runway. The metaheuristics achieve solutions of remarkable quality, within a small computation time, compared with a commercial solver and with the previous versions of AGLIBRARY.     

海巡艇远程调度指挥系统建立与应用

介绍了基于北斗导航卫星系统的海巡艇远程调度指挥系统的组成及其功能,该系统的应用实现了对我国全海区海巡艇的无缝隙有效调度指挥,以及船舶之间、船岸之间的快速信息传输,提高了海事监管的快速反应能力和海上搜寻救助成功率。     

Heterogeneous fixed fleet vehicle routing considering carbon emission

The paper considers heterogeneous fixed fleet vehicle routing with carbon emission to minimizing the sum of variable operation costs. A cost-benefit assessment of the value of purchasing or selling of carbon emission rights, using a mixed integer-programming model to reflect heterogeneous vehicle routing, is incorporated. Essentially, the use of a carbon market as a means of introducing more flexibility into an environmentally constrained network is considered. Tabu search algorithms are used to obtain solutions within a reasonable amount of computation time. In particular, we show the possibility that the amount of carbon emission can be reduced significantly without sacrificing the cost due to the benefit obtained from carbon trading.     

搜救船舶优选和排序的评判方法研究

根据现代决策理论和模糊数学评判方法,用3种多目标选优方法对搜救船舶选优进行探讨:(1)利用多属性决策加权和法进行评判;(2)根据汉明距离结合各指标的满意度曲线和重要度综合评判;(3)用模糊相似优先比方法评判。对各评判方法提出了若干改进措施,使方法更客观、合理。     

A real-life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search based Matheuristic

In this paper, a new rich Vehicle Routing Problem that could arise in a real life context is introduced and formalized: the Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet. The goal of the problem is to minimize the total delivery cost. A heterogeneous fleet composed of vehicles with different capacity, characteristics (i.e. refrigerated vehicles) and hourly costs is considered. A limit on the maximum route duration is imposed. Unlike what happens in classical multi-depot VRP, not every customer may/will be served by all the vehicles or from all the depots. The planning horizon, as in most real life applications, consists of multiple periods, and the period in which each route is performed is a variable of the problem. The set of periods, within the time horizon, in which the delivery may be carried out is known for each customer. A Mixed Integer Programming (MIP) formulation for MDMPVRPHF is presented in this paper, and an Adaptive Large Neighborhood Search (ALNS) based Matheuristic approach is proposed, in which different destroy operators are defined. Computational results, pertaining to realistic instances, which show the effectiveness of the proposed method, are provided.     

基于可靠性最短路的实时定制公交线路优化研究

为实时优化定制公交线路，提出一种基于可靠性最短路的线路优化方法，在复杂的交通环境中，可以高效的将乘客送达目的地. 对可靠性最短路进行问题描述，建立可靠性时空网络；给出求解可靠性最短路的算法步骤，构建乘客和定制公交运营商总成本最小的目标函数，采用禁忌搜索算法对问题进行求解；最后，以某市定制公交路网进行实例分析. 结果表明：与最短路线路方案比较，所提方法更接近于实际运营；在高峰时段，交通拥堵的情况下，所提方法可以提高车辆的可靠性，提升定制公交线路的服务水平.     

效率与公平视角下的应急公交接驳调度优化

城市地铁突发故障后,需要采用高效的应急公交接驳方法疏散滞留乘客,减小社会和经济损失.建立两阶段优化模型,对每辆车从存车点出发后依次前往各站运输乘客的接驳过程进行决策.阶段 1,从管理部门角度最小化疏散时间;阶段 2,在此基础上,从乘客角度降低乘客延误,优化目标分别考虑了效率与公平原则.由于现有优化软件求解阶段 2效率过低,构造了针对性的禁忌搜索(TS)算法提高求解速度.最终通过算例验证了算法和模型的可行性,对比了效率与公平原则下的疏散效果,展示了两者的权衡关系：效率原则可能导致乘客服务水平不均;而公平原则提供了更均衡的疏散服务,但系统延误相对更高.     

基于改进A*GBNN算法的AUV路径规划研究

针对现有的离散生物启发神经网络(Glasius bioinspired neural networks, GBNN)算法在未知环境下,存在的路径规划时间长、易陷入局部最优等问题,提出一种结合A*与GBNN模型的改进算法。在GBNN活性值栅格网络中,算法将各栅格的活性值作为A*的代价函数进行运算并使用跳点搜索规则优化,实现未知环境下的实时路径规划。仿真实验结果表明,该算法有效改善了自主水下航行器在未知环境下的寻路效率,可以满足自主水下航行器实时路径规划需求。     

A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem

This paper proposes a new heuristic algorithm for the Capacitated Location-Routing Problem (CLRP), called Granular Variable Tabu Neighborhood Search (GVTNS). This heuristic includes a Granular Tabu Search within a Variable Neighborhood Search algorithm. The proposed algorithm is experimentally compared on the benchmark instances from the literature with several of the most effective heuristics proposed for the solution of the CLRP, by taking into account the CPU time and the quality of the solutions obtained. The computational results show that GVTNS is able to obtain good average solutions in short CPU times, and to improve five best known solutions from the literature. The main contribution of this paper is to show a successful new heuristic for the CLRP, combining two known heuristic approaches to improve the global performance of the proposed algorithm for what concerns both the quality of the solutions and the computing times required to find them.