Short-term planning of liquefied natural gas deliveries

The ability of a supplier of liquefied natural gas (LNG) to deliver cargoes at desired times, while effectively managing a fleet of cryogenic vessels can significantly impact its profits. We investigate in this paper an LNG short-term delivery planning problem by considering mandatory cargoes as well as optional cargoes to select, along with the scheduling of a heterogeneous vessel fleet with controllable cruising speeds. Several technical constraints are accommodated including time windows, berth availability, bunkering restrictions, inventory, liquefaction terminal storage capacity, maximum waiting time, and planned maintenance restrictions. The objective is to maximize the net profit.We propose a mixed-integer programming formulation that includes a polynomial number of variables and constraints and accommodates all of the problem features. Also, we describe an optimization-based variable neighborhood search procedure that embeds the proposed compact formulation. To assess the quality of the generated solutions, we propose a second valid formulation with an exponential number of decision variables and we solve its linear programming relaxation using column generation. We provide the results of extensive computational results that were carried out on a set of large-scale set of realistic instances, with up to 62 vessels and 160 cargoes, provided by a major LNG producer. These results provide evidence that the proposed improvement procedure yields high-quality solutions.     

Hybrid simulated annealing and genetic algorithm for optimizing arterial signal timings under oversaturated traffic conditions

The implementation of system‐wide signal optimization models requires efficient solution algorithms that can quickly generate optimal or near‐optimal signal timings. This paper presents a hybrid algorithm based on simulated annealing (SA) and a genetic algorithm (GA) for arterial signal timing optimization. A decoding scheme is proposed that exploits our prior expectations about efficient solutions, namely, that the optimal green time distribution should reflect the proportion of the critical lane volumes of each phase. An SA algorithm, a GA algorithm and a hybrid SA‐GA algorithm are developed here using the proposed decoding scheme. These algorithms can be adapted to a wide range of signal optimization models and are especially suitable for those optimizing phase sequences with oversaturated intersections. To comparatively evaluate the performance of the proposed algorithms, we apply them to a signal optimization model for oversaturated arterial intersections based on an enhanced cell transmission model. The numerical results indicate that the SA‐GA algorithm outperforms both SA and GA in terms of solution quality and convergence rate. Copyright © 2014 John Wiley & Sons, Ltd.     

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%.     

Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm

This paper addresses a Time Dependent Capacitated Vehicle Routing Problem with stochastic vehicle speeds and environmental concerns. The problem has been formulated as a Markovian Decision Process. As distinct from the traditional attempts on the problem, while estimating the amount of fuel consumption and emissions, the model takes time-dependency and stochasticity of the vehicle speeds into account. The Time Dependent Capacitated Vehicle Routing Problem is known to be NP-Hard for even deterministic settings. Incorporating uncertainty to the problem increases complexity, which renders classical optimization methods infeasible. Therefore, we propose an Approximate Dynamic Programming based heuristic as a decision aid tool for the problem. The proposed Markovian Decision Model and Approximate Dynamic Programming based heuristic are flexible in terms that more environmentally friendly solutions can be obtained by changing the objective function from cost minimization to emissions minimization. The added values of the proposed decision support tools have been shown through computational analyses on several instances. The computational analyses show that incorporating vehicle speed stochasticity into decision support models has potential to improve the performance of resulting routes in terms of travel duration, emissions and travel cost. In addition, the proposed heuristic provides promising results within relatively short computation times.     

A lamda-optimal based heuristic for the berth scheduling problem

Berth scheduling aims to optimally schedule vessels to berthing areas along a quay and is a complex optimization problem. In this paper we propose a lamda-optimal based heuristic as a resolution approach for the discrete space berth scheduling problem. The proposed heuristic can also be applied to validate optimality, in the case where other (meta)heuristics are applied as resolution approaches. A second internal Genetic Algorithms based heuristic is also proposed to reduce the computational time required for medium to large scale instances. Numerical experiments performed show that the proposed heuristic is adequate to produce near-optimal results within acceptable computational times.     

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.     

An AI-based approach for transit route system planning and design

We present an AI-based solution approach to the transit network design problem (TNDP). Past approaches fall into three categories: optimization formulations of idealized situations, heuristic approaches, or practical guidelines and ad hoc procedures reflecting the professional judgement and practical experience of transit planners. We discuss the sources of complexity of the TNDP as well as the shortcomings of the previous approaches. This discussion motivates the need for AI search techniques that implement the existing designer's knowledge and expertise to achieve better solutions efficiently. Then we propose a hybrid solution approach that incorporates the knowledge and expertise of transit network planners and implements efficient search techniques using AI tools, algorithmic procedures developed by others, and modules for tools implemented in conventional languages. The three major components of the solution approach are presented, namely, the lisp-implemented route generation design algorithm (RGA), the analysis procedure TRUST (Transit Route Analyst), and the route improvement algorithm (RIA). An example illustration is included.     

A simulation model of reliable schedule design for a fixed transit route

This paper describes a simulation model of schedule design for a fixed transit route adopting the holding control strategy. The model is capable of determining the locations of time points and the amount of slack time allocated to each time point by minimizing the total cost associated with the schedule. The optimization is carried out through a process, which combines a heuristic search, enumeration, and population ranking and selection techniques. Examples showing applications and potential savings of the proposed model are given. It is shown that the model can serve as a practical tool for designing reliable, economical as well as operational transit schedules.     

Real option analysis for environmental compliance: LNG and emission control areas

A wide array of technical and operational solutions is available to shipowners in order to comply with existing and upcoming environmental regulation within Emission Control Areas (ECAs). Liquefied Natural Gas (LNG) is a promising alternative since it offers potential cost savings in addition to ensuring compliance with ECA regulation. But investment to retrofit existing vessels to be able to use LNG carries significant upfront costs, and a high degree of uncertainty remains on the differential between the prices of LNG and conventional maritime fuels, as well as on the availability of LNG and the reliability of its supply chain. New technologies such as LNG inherently carry substantial risk and an ill-chosen investment strategy may have irreversible consequences that could jeopardise the future of the shipping company. One important question is whether interested owners should invest in LNG now to comply with ECA rules in 2015 and reap the benefits of lower LNG prices, or whether it would be advisable to wait until some of the uncertainty is resolved.While traditional discounted cash flow techniques are unable to account for the value of managerial flexibility linked, for example, to the possibility of deferring an investment, real option analysis can be used to analyse such cases. The paper discusses the optimal time for investment in LNG retrofit and takes specific account of the value of an investment deferral strategy versus the advantages obtainable from the immediate exploitation of fuel price differentials. Through the use of a real option model the paper shows that there is a trade-off between low fuel prices and capital expenses for investment in LNG retrofit. The development in LNG is critically dependent on its future price as well as the reduction in capital costs and ship retrofitting costs. In this respect, policy makers can play a critical role in providing support to advance technical knowledge, maintain LNG prices at favourable levels and in avoiding ambiguity on regulation.     

Probabilistic analysis of the release of liquefied natural gas (LNG) tenders due to freight-train derailments

Liquefied natural gas (LNG) has emerged as a possible alternative fuel for freight railroads in the United States, due to the availability of cheap domestic natural gas and continued pursuit of environmental and energy sustainability. A safety concern regarding the deployment of LNG-powered trains is the risk of breaching the LNG tender car (a special type of hazardous materials car that stores fuel for adjacent locomotives) in a train accident. When a train is derailed, an LNG tender car might be derailed or damaged, causing a release and possible fire. This paper describes the first study that focuses on modeling the probability of an LNG tender car release incident due to a freight train derailment on a mainline. The model accounts for a number of factors such as FRA track class, method of operation, annual traffic density level, train length, the point of derailment, accident speed, the position(s) of the LNG tender(s) in a train, and LNG tender car design. The model can be applied to any specified route or network with LNG-fueled trains. The implementation of the model can be undertaken by the railroad industry to develop proactive risk management solutions when using LNG as an alternative railroad fuel.     

Train design and routing optimization for evaluating criticality of freight railroad infrastructures

Freight transportation by railroads is an integral part of the U.S. economy. Identifying critical rail infrastructures can help stakeholders prioritize protection initiatives or add necessary redundancy to maximize rail network resiliency. The criticality of an infrastructure element, link or yard, is based on the increased cost (delay) incurred when that element is disrupted. An event of disruption can cause heavy congestion so that the capacity at links and yards should be considered when freight is re-routed. This paper proposes an optimization model for making-up and routing of trains in a disruptive situation to minimize the system-wide total cost, including classification time at yards and travel time along links. Train design optimization seeks to determine the optimal number of trains, their routes, and associated blocks, subject to various capacity and operational constraints at rail links and yards. An iterative heuristic algorithm is proposed to attack the computational burden for real-world networks. The solution algorithm considers the impact of volume on travel time in a congested or near-congested network. The proposed heuristics provide quality solutions with high speed, demonstrated by numerical experiments for small instances. A case study is conducted for the network of a major U.S. Class-I railroad based on publicly available data. The paper provides maps showing the criticality of infrastructure in the study area from the viewpoint of strategic planning.     

Strategic evacuation planning with pedestrian guidance and bus routing: a mixed integer programming model and heuristic solution

This paper presents a mathematical model to plan emergencies in a densely populated urban zone where a certain numbers of pedestrians depend on transit for evacuation. The proposed model features an integrated operational framework, which simultaneously guides evacuees through urban streets and crosswalks (referred to as “the pedestrian network”) to designated pickup points (e.g., bus stops), and routes a fleet of buses at different depots to those pick‐up points and transports evacuees to their destinations or safe places. In this level, the buses are routed through the so‐called “vehicular network.” An integrated mixed integer linear program that can effectively take into account the interactions between the aforementioned two networks is formulated to find the maximal evacuation efficiency in two networks. Because the large instances of the proposed model are mathematically difficult to solve to optimality, a two‐stage heuristic is developed to solve larger instances of the model. Results from hundreds of numerical examples analysis indicate that proposed heuristic works well in providing (near) optimal or feasibly good solutions for medium‐scale to large‐scale instances that may arise in real transit‐based evacuation situations in a much shorter amount of computational time compared with cplex (can find optimal/feasible solutions for only five instances within 3 hours of running). Copyright © 2016 John Wiley & Sons, Ltd.     

Parametric search for the bi-attribute concave shortest path problem

A bi-attribute concave shortest path (BC-SP) problem seeks to find an optimal path in a bi-attribute network that minimizes a linear combination of two path costs, one of which is evaluated by a nondecreasing concave function. Due to the nonadditivity of its objective function, Bellman’s principle of optimality does not hold. This paper proposes a parametric search method to solve the BC-SP problem, which only needs to solve a series of shortest path problems, i.e., the parameterized subproblems (PSPs). Several techniques are developed to reduce both the number of PSPs and the computation time for these PSPs. Specifically, we first identify two properties of the BC-SP problem to guide the parametric search using the gradient and concavity of its objective function. Based on the properties, a monotonic descent search (MDS) and an intersection point search (IPS) are proposed. Second, we design a speedup label correcting (LC) algorithm, which uses optimal solutions of previously solved PSPs to reduce the number of labeling operations for subsequent PSPs. The MDS, IPS and speedup LC techniques are embedded into a branch-and-bound based interval search to guarantee optimality. The performance of the proposed method is tested on the mean-standard deviation shortest path problem and the route choice problem with a quadratic disutility function. Experiments on both real transportation networks and grid networks show that the proposed method reduces the computation time of existing algorithms by one to two orders of magnitude.     

Combinatorial programming,statistical optimization and the optimal transportation network problem

This paper presents and evaluates a branch and bound algorithm and two heuristic hill-climbing techniques to solve a discrete formulation of the optimal transportation network design problem. For practical applications it is proposed to combine a hill-climbing algorithm with a uniform random generation of the initial solutions, thereby inducing a statistical distribution of local optima. In order to determine when to stop sampling local optima and in order to provide an estimate of the exact optimum based on the whole distribution of local optima, we follow previous work and fit a Weibull distribution to the empirical distribution of local optima. Several extensions are made over previous work: in particular, a new confidence interval and a new stopping rule are proposed. The numerical application of the statistical optimization methodology to the network design algorithms consolidates the empirical validity of fitting a Weibull distribution to the empirical distribution of local optima. Numerical experiments with hill-climbing techniques of varying power suggest that the method is best applied with heuristics of intermediate quality: such heuristics provide many distinct sample points for statistical estimation while keeping the confidence intervals sufficiently narrow.     

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.     

Constraint handling methods in pavement maintenance programming

The problem of pavement maintenance management at the network level is one of maintaining as high a level of serviceability as possible for a pavement network system through reactive and proactive repair actions, whilst optimising the use of available resources. This problem has traditionally been solved using techniques like mathematical programming and heuristic methods. Lately, the use of genetic algorithms (GAs) to solve resource allocation problems like the network pavement maintenance problem has received increased attention from researchers. GAs have been demonstrated to be better than traditional techniques in terms of solution quality and diversity. However, the performance of the GAs is affected by the method used to handle the many constraints present in the formulation of such resource allocation methods. Penalty as well as generate and repair methods are the usual techniques used to handle constraints, but these have their drawbacks in terms of computational efficiency and tendency to get trapped in sub-optimal solution spaces. The paper proposes a third method that is computationally more efficient than the previous methods. The method is based on prioritised allocation of resources to maintenance activities and the maximum utilisation of resources. Constraints on maximum resource availability are no longer used passively to check on solution feasibility (as in the previous methods) but are used to help generate feasible solutions during the resource allocation phase of the algorithm itself. It is demonstrated that the GA with the prioritised resource allocation method (PRAM) outperforms the traditional GA with repair or penalty methods. PRAM was able to consistently outperform the other two GA based methods, both in terms of solution quality as well as computational time. It is concluded that PRAM can be used as the basis of more efficient resource allocation procedures in the area of pavement maintenance management.     

The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace

The integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two air traffic management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms.     

LNG燃料动力船在广西内河推广应用的思考

文章分析了液化天然气(LNG)在航运业推广应用的必要性和以LNG作为船舶动力燃料的主要危险特性,介绍了国内外LNG燃料动力船改造应用的基本情况及难点,提出了广西内河现有船舶进行LNG动力改造面临的主要问题与对策,为LNG燃料动力船在广西内河的推广应用提供参考。     

Real-time partway deadheading strategy based on transit service reliability assessment

This paper presents a partway deadheading strategy for transit operations to improve transit service of the peak directions of transit routes. This strategy consists of two phases: reliability assessment of further transit service and optimization of partway deadheading operation. The reliability assessment of further transit service, which is based on the current and recent service reliability, is used to justify whether or not to implement a partway deadheading operation. The objective of the second phase is to determine the beginning stop for a new service for the deadheaded vehicle by maximizing the benefit of transit system. A heuristic algorithm is also defined and implemented to estimate reliability of further transit service and to optimize partway deadheading operation. Then, the partway deadheading strategy proposed in this paper is tested with the data from a transit route in Dalian city of China. The results show the partway deadheading strategy with the reasonable parameters can improve transit service.     

Chemical reaction optimization for solving a static bike repositioning problem

In this paper, the single-vehicle static repositioning problem is studied. The objective of repositioning is to minimize the weighted sum of unmet customer demand and operational time on the vehicle route. To solve this problem, chemical reaction optimization (CRO) is proposed to handle the vehicle routes, and a subroutine is proposed to determine the loading and unloading quantities at each visited station. An enhanced version of CRO is proposed to improve the solution quality of the original CRO by adding new operators, rules, and intensive neighbor solution search methods. The concept of a neighbor-node set is proposed to narrow the solution search space. To illustrate the efficiency and accuracy of the enhanced CRO, different test scenarios are set and the results obtained from IBM ILOG CPLEX, the original CRO, and the enhanced CRO are compared. The computational results indicate that the enhanced CRO provides high-quality solutions with shorter computing times than those of IBM ILOG CPLEX and provides better solutions than the original CRO. The results also demonstrate that incorporation of the two neighbor-node sets into the enhanced CRO improves the solution quality, and the probability of running the intensive search should increase with iteration in the final part of the main stage of the algorithm to obtain better solutions.