Scheduling technicians for planned maintenance of geographically distributed equipment

A real-world planned maintenance scheduling problem that exists at several business units within United Technologies Corporation (UTC) is addressed in this paper. The scheduling problem is formulated as a multiple tour maximum collection problem with time-dependent rewards and an adaptive memory tabu search heuristic is developed to solve it. The effectiveness of the proposed solution approach is examined using real-world problem instances supplied by UTC. Relevant upper bounds are derived for the application. Results of numerical experiments indicate that the proposed tabu search heuristic is able to obtain near optimal solutions for large-size (i.e., actual) problem instances in reasonable computation time.     

The ship routing and freight assignment problem for daily frequency operation of maritime liner shipping

To cope with excess capacity and improve service quality, maritime international liner carriers have recently adopted a new operational model known as daily frequency. In this new model, carriers provide daily pickup and delivery service to customers at major ports along the Pacific Rim. We investigate the ship routing and freight assignment problem for daily frequency operation of liner shipping. A solution procedure that incorporates a Lagrangian relaxation technique and local search was proposed. The numerical results show that Shanghai, Hong Kong and Singapore are ports that are ideal for carriers in establishing daily frequency operations along the Pacific Rim.     

A novel heuristic approach for solving aircraft landing problem with single runway

Nowadays, airlines administrations are more willing to utilize optimization tools to control air traffic due to considerable increases in volume of air transports. A challenging problem in the field of air traffic is how to optimally schedule landing time of aircrafts and assign them to different runways such that early and late landing costs are minimized. This problem is called aircraft landing problem (ALP). This paper proposes a novel decomposition based heuristic by solving two sub-problems for the ALP with single runway. In the first sub-problem, we apply the adaptive large neighborhood search (ALNS) algorithm to find a sequence of aircrafts. The solution found in the first sub-problem will be sent to the second sub-problem, to check for the feasibility of the solution using CPLEX solver. A set of benchmark problem are taken from the OR library for the purpose of comparison with other existing approaches. The computational results exhibit that the proposed algorithm is capable of finding the best known optimal solution for all the instances.     

Path finding with stowage planning consideration in a mixed pickup–delivery and specified-node network

This paper considers the mixed pickup–delivery shortest path problem with specified nodes and stowage planning (mixed-PDSPSNSP), which combines path finding and three-dimensional stowage planning. The mixed-PDSPSNSP appears in many operational problems in various industries. However, to the best of our knowledge, there is no study in the literature for such a problem. The mixed-PDSPSNSP is NP-hard. Our proposed solution algorithm is shown to be effective and efficient when applied to a real-life mixed-PDSPSNSP.     

Heuristics for quay crane scheduling at indented berth

This paper discusses the quay crane scheduling problem at indented berth, an extension to the current quay crane scheduling problem in the field of container terminal operation. A mixed integer programming model by considering the unique features of the quay crane scheduling problem at indented berth is formulated. For solution, decomposition heuristic framework is developed and enhanced by Tabu search. To evaluate the performance of the proposed heuristic framework, a comprehensive numerical test is carried out and its results show the good quality of the proposed heuristic framework.     

The capacitated plant location problem with customers and suppliers matching

This paper introduces a new problem called the capacitated plant location problem with customer and supplier matching (CLCSM). The product distribution from plants to customers and the material supply from suppliers to plants are considered together. We merge a distribution trip and a supply trip into one triangular trip for saving allocation cost. Vehicles from plants visit a customer and a supplier for each trip. We provide a heuristic solution procedure based on Lagrangian relaxation. Computational results indicate that the proposed heuristic solution procedure is shown to be efficient yielding optimal or near-optimal solutions for randomly generated instances.     

A metaheuristic approach to the reliable location routing problem under disruptions

This paper examines a reliable capacitated location–routing problem in which depots are randomly disrupted. Customers whose depots fail must be reinserted into the routes of surviving depots. We present a scenario-based mixed-integer programming model to optimize depot location, outbound delivery routing, and backup plans. We design a metaheuristic algorithm that is based on a maximum-likelihood sampling method, route-reallocation improvement, two-stage neighborhood search and simulated annealing. Numerical tests show that the heuristic is able to generate results that would keep operating costs and failure costs well balanced. Managerial insights on scenario identification, facility deployment and model simplification are drawn.     

Integrated recovery of aircraft and passengers after airline operation disruption based on a GRASP algorithm

This paper considers the integrated recovery of both aircraft routing and passengers. A mathematical model is proposed based on both the flight connection network and the passenger reassignment relationship. A heuristic based on a GRASP algorithm is adopted to solve the problem. A passenger reassignment solution is demonstrated to be optimal in each iteration for a special case. The effectiveness of the heuristic is illustrated through experiments based on synthetic and real-world datasets. It is shown that the integrated recovery of flights and passengers can decrease both the recovery cost and the number of disrupted passengers.     

Joint location-inventory problem with differentiated service levels using critical level policy

This paper analyzes the design of a distribution network for fast-moving items able to provide differentiated service levels in terms of product availability for two demand classes (high and low priority) using a critical level policy. The model is formulated as a MINLP with chance constraints for which we propose a heuristic to solve it. Although the heuristic does not guarantee an optimal solution, our computational experiments have shown that it provides good-quality solutions that are on average 0.8% and at worst 2.7% from the optimal solution.     

Incorporating location,routing and inventory decisions in supply chain network design

This paper for the first time presents a novel model to simultaneously optimize location, allocation, capacity, inventory, and routing decisions in a stochastic supply chain system. Each customer’s demand is uncertain and follows a normal distribution, and each distribution center maintains a certain amount of safety stock. To solve the model, first we present an exact solution method by casting the problem as a mixed integer convex program, and then we establish a heuristic method based on a hybridization of Tabu Search and Simulated Annealing. The results show that the proposed heuristic is considerably efficient and effective for a broad range of problem sizes.     

The multistage stochastic integer load planning problem

Time-definite freight delivery common carriers, who pickup, consolidate and deliver small shipments are a key third-party logistics service provider in the supply chains. Under uncertain demands, carrier’s multistage stochastic integer load planning in the pure hub-and-spoke line-haul operations network is to determine multistage freight paths and distribute trailers over time while meeting operational restrictions, service requirements, and balancing trailer inventory at the termination of planning horizon. We developed a heuristic approach, scenario aggregation with embedded branching on the binary variables. The numerical experiments showed a proactive operations strategy with a lower operating cost than the conventionally deterministic approach.     

Carrying capacity procurement of rail and shipping services for automobile delivery with uncertain demand

The determination of the optimal carrying capacity procurement of rail and shipping services in the automobile intermodal network with unique characteristics is essential to save automobile delivery cost. In this research we develop a two-stage stochastic programming model for the tactical-level decision problem arising in the special automobile intermodal network. Furthermore, we improve the sample average approximation algorithmic procedure to solve the model. We apply the model and solution method to a case study associated with the Shanghai Automobile Industry Corporation. We believe that this study deals with an emerging new research topic with practical significance for the automobile industry.     

The simultaneous berth and quay crane allocation problem

This paper addresses efficient berth and crane allocation scheduling at a multi-user container terminal. First, we introduce a formulation for the simultaneous berth and crane allocation problem. Next, by employing genetic algorithm we develop a heuristic to find an approximate solution for the problem. The fitness value of a chromosome is obtained by crane transfer scheduling across berths, which is determined by a maximum flow problem-based algorithm based on a berth allocation problem solution defined by the chromosome. The results of numerical experiments show that the proposed heuristic is applicable to solve this difficult but essential terminal operation problem.     

Modeling and optimizing transportation decisions in a manufacturing supply chain

We describe a transportation problem we studied at the trucking division of a textile manufacturer that owns and operates a large number of manufacturing facilities in all stages of the manufacturing supply chain. The problem involves scheduling of pickup and delivery of daily inventory movement between plants. We develop integer programming models that are based on the current workflow of the schedulers and that capture and optimize crucial aspects of the problem. We validate the models and demonstrate their use with actual data. The results suggest that an effective computerized decision-support system can be built around these models.     

A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies

This paper discusses a dynamic evacuation network optimization problem that incorporates lane reversal and crossing elimination strategies. These two lane-based planning strategies complement one another by increasing capacity in specific directions through the evacuation network. A bi-level network optimization model is formulated, in which the upper level aims at optimizing the network evacuation performance subject to the lane-reversal and crossing-elimination constraints and the lower level conveys a cell transmission-based dynamic traffic assignment problem. An integrated Lagrangian relaxation and tabu search method is devised for approximating optimal problem solutions through an iterative optimization-evaluation process. The numerical results of implementing the developed modeling and solution approach to a synthetic network and a real-world example application justify its theoretical and practical value.     

Solving a static repositioning problem in bike-sharing systems using iterated tabu search

In this paper, we study the static bike repositioning problem where the problem consists of selecting a subset of stations to visit, sequencing them, and determining the pick-up/drop-off quantities (associated with each of the visited stations) under the various operational constraints. The objective is to minimize the total penalties incurred at all the stations. We present an iterated tabu search heuristic to solve the described problem. Experimental results show that this simple heuristic can generate high quality solutions using small computing times.     

A robust optimization approach to the integrated berth allocation and quay crane assignment problem

This paper investigates the integrated berth allocation and quay crane assignment problem in container terminals. A deterministic model is formulated by considering the setup time of quay cranes. However, data uncertainties widely exist, and it may cause the deterministic solution to be infeasible. To handle the uncertainties, a robust optimization model is established. Furthermore, to control the level of conservativeness, another robust optimization model with the price constraints is proposed. A genetic algorithm and an insertion heuristic algorithm are suggested to obtain near optimal solutions. Computational experiments indicate that the presented models and algorithms are effective to solve the problems.     

Runway capacity management – An empirical study with application to Doha International Airport

This paper examines a three-faceted approach for runway capacity management, based on the runway configuration, a chosen scheduling approach, and an aircraft separation standard. These factors prompt alternative runway settings that are encapsulated using a classical mixed-integer formulation. The optimal solution for each runway setting is compared against our proposed optimization-based heuristic. This integrated approach is applied to investigating the transition from the (Old) Doha International Airport to the New Doha International Airport. Our empirical study based on historical data reveals that the proposed heuristic consistently yields optimal or near-optimal schedules, with considerable savings in fuel cost and reductions in delays, while preserving the spirit of an FCFS sequencing policy.     

Mixed truck delivery systems with both hub-and-spoke and direct shipment

This paper studies a mixed truck delivery system that allows both hub-and-spoke and direct shipment delivery modes. A heuristic algorithm is developed to determine the mode of delivery for each demand and to perform vehicle routing in both modes of deliveries. Computational experiments are carried out on a large set of randomly generated problem instances to compare the mixed system with the pure hub-and-spoke system and the pure direct shipment system. The experiment results show that the mixed system can save around 10% total traveling distance on average as compared with either of the two pure systems.     

Aircraft line maintenance scheduling and optimisation

With the advent of new technologies and more modern aircraft, many of the maintenance jobs traditionally scheduled for periodic block checks can now be performed in the ‘‘line maintenance” environment, i.e., during layovers between scheduled flights of an aircraft. This flexibility can be exploited to reduce maintenance costs and improve fleet utilisation of an airline. In this paper we introduce and study the Line Maintenance Scheduling Problem (LMSP). The LMSP assigns jobs to available maintenance opportunities, defined by aircraft routes, and sets the starting time for each job. Its objective is to minimise the deviation from this schedule with respect to given due dates for each task, without exceeding resource capacity at the airports at any moment. We formulate the LMSP as a mixed integer programming problem, and describe and compare two solution approaches for this problem: an integrated exact solution algorithm, which solves job assignment and timetabling simultaneously, and a sequential, heuristic approach. We tested our algorithms on a set of instances inspired on data provided by an industry partner. Our experiments show the applicability of both approaches on realistic settings: the exact approach was able to find the optimal solution for all instances, in less than 10 min on average. Our analysis also shows with an example that line maintenance can be more efficient when capacity is spatially spread, even if the total capacity is reduced.