Multi-objective highway alignment optimization incorporating preference information

This paper presents a GIS-based multi-objective optimization model, particularly designed to aid highway engineers and planners in proposing competitive highway alignment alternatives when building a new highway or expanding an existing highway. The proposed model can effectively examine tradeoffs among various objectives that represent possibly conflicting interests of different stakeholders. A Hybrid Multi-Objective Genetic Algorithm, which utilizes designers’ knowledge about the preference of decision makers, is developed to search for a set of Pareto-optimal solutions with an acceptable level of diversity. Two case studies demonstrate the capability of the proposed approach in providing multiple trade-off solutions. The results indicate that the incorporation of preference information, even if preliminary in nature, has great potential to save computation time and improve the quality of the obtained Pareto-optimal set.     

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.     

Integrated optimization on train scheduling and preventive maintenance time slots planning

We address the problem of simultaneously scheduling trains and planning preventive maintenance time slots (PMTSs) on a general railway network. Based on network cumulative flow variables, a novel integrated mixed-integer linear programming (MILP) model is proposed to simultaneously optimize train routes, orders and passing times at each station, as well as work-time of preventive maintenance tasks (PMTSs). In order to provide an easy decomposition mechanism, the limited capacity of complex tracks is modelled as side constraints and a PMTS is modelled as a virtual train. A Lagrangian relaxation solution framework is proposed, in which the difficult track capacity constraints are relaxed, to decompose the original complex integrated train scheduling and PMTSs planning problem into a sequence of single train-based sub-problems. For each sub-problem, a standard label correcting algorithm is employed for finding the time-dependent least cost path on a time-space network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted on a small artificial network and a real-world network adapted from a Chinese railway network, to evaluate the effectiveness and computational efficiency of the integrated optimization model and the proposed Lagrangian relaxation solution framework. The benefits of simultaneously scheduling trains and planning PMTSs are demonstrated, compared with a commonly-used sequential scheduling method.     

A hybrid heuristic strategy for liquefied natural gas inventory routing

As liquefied natural gas (LNG) steadily grows to be a common mode for commercializing natural gas, LNG supply chain optimization is becoming a key technology for gas companies to maintain competitiveness. This paper develops methods for improving the solutions for a previously stated form of an LNG inventory routing problem (LNG-IRP). Motivated by the poor performance of a Dantzig-Wolfe-based decomposition approach for exact solutions, we develop a suite of advanced heuristic techniques and propose a hybrid heuristic strategy aiming to achieve improved solutions in shorter computational time. The heuristics include two phases: the advanced construction phase is based on a rolling time algorithm and a greedy randomized adaptive search procedure (GRASP); and the solution improvement phase is a series of novel MIP-based neighborhood search techniques. The proposed algorithms are evaluated based on a set of realistic large-scale instances seen in recent literature. Extensive computational results indicate that the hybrid heuristic strategy is able to obtain optimal or near optimal feasible solutions substantially faster than commercial optimization software and also the previously proposed heuristic methods.     

Distributed optimization and coordination algorithms for dynamic speed optimization of connected and autonomous vehicles in urban street networks

Dynamic speed harmonization has shown great potential to smoothen the flow of traffic and reduce travel time in urban street networks. The existing methods, while providing great insights, are neither scalable nor real-time. This paper develops Distributed Optimization and Coordination Algorithms (DOCA) for dynamic speed optimization of connected and autonomous vehicles in urban street networks to address this gap. DOCA decomposes the nonlinear network-level speed optimization problem into several sub-network-level nonlinear problems thus, it significantly reduces the problem complexity and ensures scalability and real-time runtime constraints. DOCA creates effective coordination in decision making between each two sub-network-level nonlinear problems to push solutions towards optimality and guarantee attaining near-optimal solutions. DOCA is incorporated into a model predictive control approach to allow for additional consensus between sub-network-level problems and reduce the computational complexity further. We applied the proposed solution technique to a real-world network in downtown Springfield, Illinois and observed that it was scalable and real-time while finding solutions that were at most 2.7% different from the optimal solution of the problem. We found significant improvements in network operations and considerable reductions in speed variance as a result of dynamic speed harmonization.     

Generating synthetic baseline populations from register data

The paper presents a population synthesiser based on the method of Iterative Proportional Fitting (IPF) algorithm developed for the new Danish national transport model system. The synthesiser is designed for large population matrices and allows target variables to be represented in several target constraints. As a result, constraints for the IPF are cross-linked, which makes it difficult to ensure consistency of targets in a forecast perspective. The paper proposes a new solution strategy to ensure internal consistency of the population targets in order to guarantee proper convergence of the IPF algorithm. The solution strategy consists in establishing a harmonisation process for the population targets, which combined with a linear programming approach, is applied to generate a consistent target representation. The model approach is implemented and tested on Danish administrative register data. A test on historical census data shows that a 2006 population could be predicted by a 1994 population with an overall percentage deviation of 5-6% given that targets were known. It is also indicated that the deviation is approximately a linear function of the length of the forecast period.     

Evaluating the impacts of urban corridor traffic signal optimization on vehicle emissions and fuel consumption

This study investigates the impacts of traffic signal timing optimization on vehicular fuel consumption and emissions at an urban corridor. The traffic signal optimization approach proposed integrates a TRANSIMS microscopic traffic simulator, the VT-Micro model (a microscopic emission and fuel consumption estimation model), and a genetic algorithm (GA)-based optimizer. An urban corridor consisting of four signalized intersections in Charlottesville, VA, USA, is used for a case study. The result of the case study is then compared with the best traffic signal timing plan generated by Synchro using the TRANSIMS microscopic traffic simulator. The proposed approach achieves much better performance than that of the best Synchro solution in terms of air quality, energy and mobility measures: 20% less network-wide fuel consumption, 8–20% less vehicle emissions, and nearly 27% less vehicle-hours-traveled (VHT).     

An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints

This study introduces a new practical variant of the combined routing and loading problem called the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints (3L-FCVRP). It presents a meta-heuristic algorithm for solving the problem. The aim is to design routes for a fleet of homogeneous vehicles that will serve all customers, whose demands are formed by a set of three-dimensional, rectangular, weighted items. Unlike the well-studied capacitated vehicle routing problem with 3D loading constraints (3L-CVRP), the objective of the 3L-FCVRP is to minimize total fuel consumption rather than travel distance. The fuel consumption rate is assumed to be proportionate to the total weight of the vehicle. A route is feasible only if a feasible loading plan to load the demanded items into the vehicle exists and the loading plan must satisfy a set of practical constraints.To solve this problem, the evolutionary local search (ELS) framework incorporating the recombination method is used to explore the solution space, and a new heuristic based on open space is used to examine the feasibility of the solutions. In addition, two special data structures, Trie and Fibonacci heap, are adopted to speed up the procedure. To verify the effectiveness of our approach, we first test the ELS on the 3L-CVRP, which can be seen as a special case of the 3L-FCVRP. The results demonstrate that on average ELS outperforms all of the existing approaches and improves the best-known solutions for most instances. Then, we generate data for 3L-FCVRP and report the detailed results of the ELS for future comparisons.     

Classification modeling approach for vehicle dynamics model‐integrated traffic simulation assessing surrogate safety

To assess safety impacts of untried traffic control strategies, an earlier study developed a vehicle dynamics model‐integrated (i.e., VISSIM‐CarSim‐SSAM) simulation approach and evaluated its performance using surrogate safety measures. Although the study found that the integrated simulation approach was a superior alternative to existing approaches in assessing surrogate safety, the computation time required for the implementation of the integrated simulation approach prevents it from using it in practice. Thus, this study developed and evaluated two types of models that could replace the integrated simulation approach with much faster computation time, feasible for real‐time implementation. The two models are as follows: (i) a statistical model (i.e., logit model) and (ii) a nonparametric approach (i.e., artificial neural network). The logit model and the neural network model were developed and trained on the basis of three simulation data sets obtained from the VISSIM‐CarSim‐SSAM integrated simulation approach, and their performances were compared in terms of the prediction accuracy. These two models were evaluated using six new simulation data sets. The results indicated that the neural network approach showing 97.7% prediction accuracy was superior to the logit model with 85.9% prediction accuracy. In addition, the correlation analysis results between the traffic conflicts obtained from the neural network approach and the actual traffic crash data collected in the field indicated a statistically significant relationship (i.e., 0.68 correlation coefficient) between them. This correlation strength is higher than that of the VISSIM only (i.e., the state of practice) simulation approach. The study results indicated that the neural network approach is not only a time‐efficient way to implementing the VISSIM‐CarSim‐SSAM integrated simulation but also a superior alternative in assessing surrogate safety. Copyright © 2014 John Wiley & Sons, Ltd.     

Globally energy-optimal speed planning for road vehicles on a given route

This paper provides a globally optimal solution to an important problem: given a real-world route, what is the most energy-efficient way to drive a vehicle from the origin to the destination within a certain period of time. Along the route, there may be multiple stop signs, traffic lights, turns and curved segments, roads with different grades and speed limits, and even leading vehicles with pre-known speed profiles. Most of such route information and features are actually constraints to the optimal vehicle speed control problem, but these constraints are described in two different domains. The most important concept in solving this problem is to convert the distance-domain route constraints to some time-domain state and input constraints that can be handled by optimization methods such as dynamic programming (DP). Multiple techniques including cost-to-go function interpolation and parallel computing are used to reduce the computation of DP and make the problem solvable within a reasonable amount of time on a personal computer.     

A discrete optimization approach for locating Automatic Vehicle Identification readers for the provision of roadway travel times

This paper develops an algorithm for optimally locating Automatic Vehicle Identification tag readers by maximizing the benefit that would accrue from measuring travel times on a transportation network. The problem is formulated as a quadratic 0–1 optimization problem where the objective function parameters represent benefit factors that capture the relevance of measuring travel times as reflected by the demand and travel time variability along specified trips. An optimization approach based on the Reformulation–Linearization Technique coupled with semidefinite programming concepts is designed to solve the formulated reader location problem. To illustrate the proposed methodology, we consider a transportation network that is comprised of freeway segments that might include merge, diverge, weaving, and bottleneck sections. In order to derive benefit factors for the various origin–destination pairs on this network, we employ a simulation package (INTEGRATION) in combination with a composite function, which estimates the travel time variability along a trip that is comprised of links that include any of the four identified sections. The simulation results are actually recorded as generic look-up tables that can be used for any such section for the purpose of computing the associated benefit factor coefficients. Computational results are presented using data pertaining to a freeway section in San Antonio, Texas, as well as synthetic test cases, to demonstrate the effectiveness of the proposed approach, and to study the sensitivity of the quality of the solution to variations in the number of available readers.     

Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations

This study addresses the problem of scheduling a fleet of taxis that are appointed to solely service customers with advance reservations. In contrast to previous studies that have dealt with the planning and operations of a taxi fleet with only electric vehicles (EVs), we consider that most taxi companies may have to operate with fleets comprised of both gasoline vehicles (GVs) and plug-in EVs during the transition from GV to (complete) EV taxi fleets. This paper presents an innovative multi-layer taxi-flow time-space network which effectively describes the movements of the taxis in the dimensions of space and time. An optimization model is then developed based on the time-space network to determine an optimal schedule for the taxi fleet. The objective is to minimize the total operating cost of the fleet, with a set of operating constraints for the EVs and GVs included in the model. Given that the model is formulated as an integer multi-commodity network flow problem, which is characterized as NP-hard, we propose two simple but effective decomposition-based heuristics to efficiently solve the problem with practical sizes. Test instances generated based on the data provided by a Taiwan taxi company are solved to evaluate the solution algorithms. The results show that the gaps between the objective values of the heuristic solutions and those of the optimal solutions are less than 3%, and the heuristics require much less time to obtain the good quality solutions. As a result, it is shown that the model, coupled with the algorithms, can be an effective planning tool to assist the company in routing and scheduling its fleet to service reservation customers.     

A joint bottom-up solution methodology for system-level pavement rehabilitation and reconstruction

We present a methodology for the joint optimization of rehabilitation and reconstruction activities for heterogeneous pavement systems under multiple budget constraints. The proposed bottom-up approach adopts an augmented condition state to account for the history-dependent properties of pavement deterioration, and solves for steady-state policies for an infinite horizon. Genetic algorithms (GAs) are implemented in the system-level optimization based on segment-specific optimization results. The complexity of the proposed algorithm is polynomial in the size of the system and the policy-related parameters. We provide graphical presentations of the optimal solutions for various budget situations. As a case study, a subset of California’s highway system is analyzed. The case study results demonstrate the economic benefit of a combined rehabilitation and reconstruction budget compared to separate budgets.     

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.     

Testing and evaluation of a multi-commodity multi-modal network flow model for disaster relief management

The results of the testing of an optimization model in disaster relief management are presented. The problem is a large-scale multi-commodity, multi-modal network flow problem with time windows. Due to the nature of this problem, the size of the optimization model grows extremely rapidly as the number of modes and/or commodities increase. The formulation is based on the concept of a time-space network. Two heuristic algorithms are developed. One exploits an inherent network structure of the problem with a set of side constraints and the other is an interactive fix-and-run heuristic. The findings of the model-testing and a wide range of sensitivity analyses using an artificially generated data set are presented. Both solution procedures prove to be efficient and effective in providing close to optimal solutions.     

A rolling-horizon quadratic-programming approach to the signal control problem in large-scale congested urban road networks

The paper investigates the efficiency of a recently developed signal control methodology, which offers a computationally feasible technique for real-time network-wide signal control in large-scale urban traffic networks and is applicable also under congested traffic conditions. In this methodology, the traffic flow process is modeled by use of the store-and-forward modeling paradigm, and the problem of network-wide signal control (including all constraints) is formulated as a quadratic-programming problem that aims at minimizing and balancing the link queues so as to minimize the risk of queue spillback. For the application of the proposed methodology in real time, the corresponding optimization algorithm is embedded in a rolling-horizon (model-predictive) control scheme. The control strategy’s efficiency and real-time feasibility is demonstrated and compared with the Linear-Quadratic approach taken by the signal control strategy TUC (Traffic-responsive Urban Control) as well as with optimized fixed-control settings via their simulation-based application to the road network of the city centre of Chania, Greece, under a number of different demand scenarios. The comparative evaluation is based on various criteria and tools including the recently proposed fundamental diagram for urban network traffic.     

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 carbon footprint-based closed-loop supply chain model under uncertainty with risk analysis: A case study

The management of products’ end-of-life and the recovery of used products has gained significant importance in recent years. In this paper, we address the carbon footprint-based problem that arises in a closed-loop supply chain where returned products are collected from customers. These returned products can either be disposed of or be remanufactured to be resold as new ones. Given this environment, an optimization model for a closed-loop supply chain (CLSC) in which carbon emission is expressed in terms of environmental constraints, i.e., carbon emission constraints, is developed. These constraints aim to limit the carbon emission per unit of product supplied with different transportation modes. Here, we design a closed-loop network where capacity limits, single-item management and uncertainty on product demands and returns are considered. First, fuzzy mathematical programming is introduced for uncertain modeling. Then, the statistical approach to the possibility to synthesize fuzzy information is utilized. Therefore, using a defined possibilistic mean and variance, we transform the proposed fuzzy mathematical model into a crisp form to facilitate efficient computation and analysis. Finally, the risk caused by violating the estimated resource constraints is analyzed so that decision makers (DMs) can trade off between the expected cost savings and the expected risk. We utilize data from a company located in Iran.     

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.     

Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem

Using a sample-based representation scheme to capture spatial and temporal travel time correlations, this article constructs an integer programming model for finding the a priori least expected time paths. We explicitly consider the non-anticipativity constraint associated with the a priori path in a time-dependent and stochastic network, and propose a number of reformulations to establish linear inequalities that can be easily dualized by a Lagrangian relaxation solution approach. The relaxed model is further decomposed into two sub-problems, which can be solved directly by using a modified label-correcting algorithm and a simple single-value linear programming method. Several solution algorithms, including a sub-gradient method, a branch and bound method, and heuristics with additional constraints on Lagrangian multipliers, are proposed to improve solution quality and find approximate optimal solutions. The numerical experiments investigate the quality and computational efficiency of the proposed solution approach.