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.     

The liner shipping berth scheduling problem with transit times

In this paper speed optimization of an existing liner shipping network is solved by adjusting the port berth times. The objective is to minimize fuel consumption while retaining the customer transit times including the transhipment times. To avoid too many changes to the time table, changes of port berth times are only accepted if they lead to savings above a threshold value. Since the fuel consumption of a vessel is a non-linear convex function of the speed, it is approximated by a piecewise linear function. The developed model is solved using exact methods in less than two minutes for large instances. Computational experiments on real-size liner shipping networks are presented showing that fuels savings in the magnitude 2–10% can be obtained. The work has been carried out in collaboration with Maersk Line and the tests instances are confirmed to be representative of real-life networks.     

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.     

The split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem, a fleet of vehicles must service the demands of customers in a least-cost way. By allowing multiple vehicles to service the same customer (i.e., splitting deliveries), substantial savings in travel costs are possible. However, split deliveries are often an inconvenience to the customer who would prefer to have demand serviced in a single visit. We consider the vehicle routing problem in which split deliveries are allowed only if a minimum fraction of a customer’s demand is serviced by a vehicle. We develop a heuristic method for solving this problem and report computational results on a wide range of problem sets.     

The toll plaza optimization problem: Design,operations, and strategies

This paper presents comprehensive decision-making procedures for designing a new toll plaza with the right initial capacity, then finding the optimal dynamic lane configuration for operations, evaluating the effects of increasing future traffic volume on waiting time by sensitivity analysis, and establishing a long-term quantitative strategy by transferring low-throughput lane users to high-throughput lanes. We develop a non-linear integer programming model integrated with the M/G/1 queueing process. A case study based on actual data demonstrates how effective the model and the strategy are in reducing operating and user-waiting costs and, thus, improving overall system performance at toll plazas.     

Managing severe airspace flow programs: The Airlines’ side of the problem

This paper presents a heuristic-based approach for minimizing airlines’ schedule disruptions and operation costs associated with severe airspace flow programs. It considers primary decisions made by flight dispatchers such as flight slot substitution and rerouting outside the boundaries of the flow-constrained area. A two-stage heuristic is developed. In the first, a linear approximation of the problem is used to screen inefficient routing and slot substitution alternatives. The second stage examines possible solution improvements through trading flight assignments for every pair of conflicting routes. A genetic algorithm is developed and used to benchmark the performance of the two-stage heuristic. In the algorithm, flight route and slot allocation schemes are modeled as chromosomes. The fitness of these chromosomes measures the magnitude of schedule disruption and overall operating cost. A set of experiments that compare the performance of the two heuristics considering airspace flow programs with different levels of severity is presented.     

A study of the airline boarding problem

The airline industry is currently under intense pressure to simultaneously increase efficiency, customer satisfaction, and profitability. The boarding process is one way to achieve this objective as it lends itself to adaptive changes. The purpose of this paper is to determine the most cost-effective way to board passengers and still maintain quality and customer satisfaction. We conclude that the best strategy is to use a non-traditional methodology of outside-in or some modification thereof. The findings suggest that airline managers should consider issues related to evenly distributing boarding activity throughout the aircraft, developing more effective policies for managing carry-on luggage, and using simultaneous loading through two doors.     

Hierarchical multimodal hub location problem with time-definite deliveries

Hierarchical multimodal hub location problem is a cost-minimizing hub covering problem where two types of hubs and hub links, accounting for ground and air transportation, are to be established, while ensuring time-definite deliveries. We propose a mixed-integer programming formulation and perform a comprehensive sensitivity analysis on the Turkish network. We show that the locations of airport hubs are less sensitive to the cost parameters compared to the locations of ground hubs and it is possible to improve the service quality at not much additional cost in the resulting multimodal networks. Our methodology provides the means for a detailed trade-off analysis.     

Charging station location problem of plug-in electric vehicles

A novel model for the charging station location problem of plug-in electric vehicles is proposed in this paper. With the objective of minimizing the total cost, the proposed model simultaneously handles the problem of where to locate the charging stations and how many chargers should be established in each charging station. Furthermore, the model is expanded to consider a more general case. A genetic algorithm-based method is proposed for solving the expanded model. The results show that a better location scheme can be obtained using the expanded model.     

A generalized algebraic model for optimizing inventory decisions in a multi-stage complex supply chain

In this paper, we deal with more generalized inventory coordination mechanism in an n-stage, multi-customer, non-serial supply chain, where we extend and generalize pervious works that use algebraic methods to optimize this coordinated supply chain. We establish the recursive expressions for this multi-variable optimization problem. These expressions are used for the derivation of the optimal replenishment policy and the development of the solution algorithm. Further, we describe a simple procedure that can help in sharing the coordination cost benefits to induce all stages to adopt the inventory coordination mechanism. We provide a numerical example for illustrative purposes.     

A supply chain generalized network oligopoly model for pharmaceuticals under brand differentiation and perishability

In this paper, we construct a generalized network oligopoly model with arc multipliers for supply chains of pharmaceutical products using variational inequality theory. The model captures the Cournot competition among the manufacturers who seek to determine their profit-maximizing product flows, which can be perishable, with the consumers differentiating among the products of the firms, whether branded or generic, and the firms taking into consideration the discarding costs. The numerical examples demonstrate that a brand pharmaceutical product may lose its dominant market share as a consequence of patent rights expiration and because of generic competition.     

Branch-and-price algorithm for the location-routing problem with time windows

This study proposes a branch-and-price algorithm to solve the Location-Routing Problem with Time Windows (LRPTW) which has never been attempted with the exact solutions before. The problem is solved by the simplex algorithm in the master problem and elementary shortest path problems with resource constraint corresponding to column generation in the subproblem until only the non-negative reduced cost columns remain. The proposed algorithm can solve many testing instances effectively. The computational results and the effect of time windows are also compared and discussed.     

Stochastic optimization models for the airport gate assignment problem

Uncertainties inherent in the airport traffic may lead to the unavailability of gates for accommodating scheduled flights. Incorporating random disruptions is crucial in constructing effective flight-gate assignments. We consider the gate assignment problem under uncertainty in flight arrival and departure times and develop stochastic programming models incorporating robustness measures based on the number of conflicting flights, idle and buffer times. The proposed models are formulated as large-scale mixed-integer programming problems and tabu search algorithms are implemented to obtain assignments of reasonable quality. We conduct a computational study to analyze the proposed alternate models and show the effectiveness of the solution methods.     

A Lagrangian heuristic for the real-time vehicle rescheduling problem

When a public transit vehicle breaks down on a scheduled trip, one or more vehicles need to be rescheduled to serve that trip and other service trips originally scheduled for the disabled vehicle. In this paper, the vehicle rescheduling problem (VRSP) is investiaged to consider operating costs, schedule disruption costs, and trip cancellation costs. The VRSP is proven to be NP-hard, and a Lagrangian relaxation based insertion heuristic is developed. Extensive computational experiments on randomly generated problems are reported. The results show that the Lagrangian heuristic performs very well for solving the VRSP.     

A less-than-truckload carrier collaboration planning problem under dynamic capacities

This paper addresses the deterministic dynamic single carrier collaboration problem for the small- to medium-sized less-than-truckload (LTL) industry. It is formulated as a binary (0–1) multi-commodity minimum cost flow problem and solved using a branch-and-cut algorithm. Its inherent network structure is exploited to generate the lower bounds to the branch-and-cut algorithm using the network simplex method and by relaxing the integrality constraints. Results from numerical experiments indicate inherent trade-offs at the higher degrees of collaboration between waiting for more affordable collaborative capacity and incurring higher holding costs. They also suggest that collaborating LTL carriers experience increased capacity utilization.     

Analysis of an integrated maximum covering and patrol routing problem

In this paper, we address the problem of determining the patrol routes of state troopers for maximum coverage of highway spots with high frequencies of crashes (hot spots). We develop a specific mixed integer linear programming model for this problem under time feasibility and budget limitation. We solve this model using local and tabu-search based heuristics. Via extensive computational experiments using randomly generated data, we test the validity of our solution approaches. Furthermore, using real data from the state of Alabama, we provide recommendations for (i) critical levels of coverage; (ii) factors influencing the service measures; and (iii) dynamic changes in routes.     

On the formulation and solution of the convoy routing problem

In this work, we will identify important variables that contribute to vehicular movement in an emergency environment. In particular, we formulate and pose the convoy routing problem. We suggest a method for modeling the problem and formulate a precise problem statement that significantly reduces the number of variables under consideration relative to similar previous work; even so, we prove that the decision version of this problem is NP-complete. After devising an algorithm using artificial intelligence techniques, we then empirically analyze this model (via software simulation) to get computational results on a single instance of the problem.     

Comparing heuristic algorithms of the planar storage location assignment problem

This paper discusses the newly defined planar storage location assignment problem (PSLAP). We develop a mathematical programming model and GA-based and dynamic PSLAP heuristic algorithms for the solving procedure. Using the testing set, we compare the performance of GA-based and dynamic PSLAP heuristic algorithms. The mathematical programming model is utilized as a comparison criterion. The comparison results demonstrate that the dynamic PSLAP heuristic algorithm performs better than the other solving procedures. In addition, we describe simulation experiments conducted to investigate the effects of stock yard layout and production schedule instability on the operation of the block stock yard.     

Solutions to the request reassignment problem in collaborative carrier networks

The paper considers an arrangement for exchanging transportation requests to facilitate collaboration among independent carriers. The goal is to maximize the total profit without decreasing the individual profit of the carriers. Two solution approaches are developed for this problem involving decentralized control and auction based exchange mechanisms. The results are compared with those obtained without collaboration and by a centralized control. They indicate that horizontal collaboration pays off even in highly competitive environments.