The generalized bin packing problem

In the Generalized Bin Packing Problem (GBPP), given two sets of compulsory and non-compulsory items characterized by volume and profit and a set of bins with given volume and cost, we want to select the subset of profitable non-compulsory items to be loaded together with the compulsory ones into the appropriate bins in order to minimize the total net cost. Lower and upper bounds to the GBPP are given. The results of extensive computational experiments show that the proposed procedures are efficient and the bounds are tight.     

The generalized lock scheduling problem: An exact approach

The present paper introduces an integrated approach to solving the generalized lock scheduling problem. Three interrelated sub problems can be discerned: ship placement, chamber assignment and lockage operation scheduling. In their turn, these are closely related to the 2D bin packing problem, the assignment problem and the (parallel) machine scheduling problem respectively. In previous research, the three sub problems mentioned were considered separately, often using (heuristic) interaction between them to obtain better solutions. A mixed integer linear programming model is presented and applied to instances from both inland locks and locks in a tide independent port. The experiments show that small instances incorporating a wide range of real-life constraints can be solved to optimality.     

The strategic berth template problem

A marine container terminal operator may have a situation with excessive calling requests to be served especially when some new service contracts are under consideration. For this situation, we propose a strategic berth template problem (BTPS) that selects the ships among the requesting ones to be served and arrange their berth-windows within a limited planning horizon. The BTPS employs the subgradient optimization procedure, which is an improved version of the procedure that the authors developed for the operational berth allocation problem. A wide variety of numerical experiments indicate the improved subgradient procedure works well for the BTPS.     

The congested multicommodity network design problem

This paper studies a version of the fixed-charge multicommodity network design problem where in addition to the traditional costs of flow and design, congestion at nodes is explicitly considered. The problem is initially modeled as a nonlinear integer programming formulation and two solution approaches are proposed: (i) a reformulation of the problem as a mixed integer second order cone program to optimally solve the problem for small to medium scale problem instances, and (ii) an evolutionary algorithm using elements of iterated local search and scatter search to provide upper bounds. Extensive computational results on new benchmark problem instances and on real case data are presented.     

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.     

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 competitive facility location problem under disruption risks

Two players sequentially locate a fixed number of facilities, competing to capture market share. Facilities face disruption risks, and each customer patronizes the nearest operational facility, regardless of who operates it. The problem therefore combines competitive location and location with disruptions. This combination has been absent from the literature. We model the problem as a Stackelberg game in which the leader locates facilities first, followed by the follower, and formulate the leader’s decision problem as a bilevel optimization problem. A variable neighborhood decomposition search heuristic which includes variable fixing and cut generation is developed. Computational results suggest that high quality solutions can be found quickly. Interesting managerial insights are drawn.     

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 fixed charge facility location problem with coverage restrictions

This paper develops a fixed charge facility location model with coverage restrictions, minimizing cost while maintaining an appropriate level of service, in identifying facility locations. Further, it discusses the insights that can be gained using the model. Two Lagrangian relaxation based heuristics are presented and tested. Both heuristics use a greedy adding algorithm to calculate upper bounds and subgradient optimization to calculate lower bounds. While both procedures are capable of generating good solutions, one is computationally superior.     

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 container shipping network design problem with empty container repositioning

This paper addresses the design of container liner shipping service networks by explicitly taking into account empty container repositioning. Two key and interrelated issues, those of deploying ships and containers are usually treated separately by most existing studies on shipping network design. In this paper, both issues are considered simultaneously. The problem is formulated as a two-stage problem. A genetic algorithm-based heuristic is developed for the problem. Through a number of numerical experiments that were conducted it was shown that the problem with the consideration of empty container repositioning provides a more insightful solution than the one without.     

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 heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion

The green vehicle routing and scheduling problem (GVRSP) aims to minimize green-house gas emissions in logistics systems through better planning of deliveries/pickups made by a fleet of vehicles. We define a new mixed integer liner programming (MIP) model which considers heterogeneous vehicles, time-varying traffic congestion, customer/vehicle time window constraints, the impact of vehicle loads on emissions, and vehicle capacity/range constraints in the GVRSP. The proposed model allows vehicles to stop on arcs, which is shown to reduce emissions up to additional 8% on simulated data. A hybrid algorithm of MIP and iterated neighborhood search is proposed to solve the problem.     

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.     

The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem

This paper introduces the vehicle routing problem with soft time windows (VRPSTW) in which problem definition differs from ones previously defined in literature. Branch-and-price approach is employed, resulting in a set partitioning master problem and its new subproblem. Novel techniques are consequently developed to solve this new subproblem. Experimental results report the comparisons of these solution techniques under the branch-and-price framework. The VRPSTW solutions have further been compared to the state-of-the-art literature, signifying the superiority of the VRPSTW on this issue.     

The airfare pricing and seat allocation problem in full-service carriers and subsidiary low-cost carriers

This study investigates the competitive market situation in the air transport industry considering full-service carriers (FSC), subsidiary low-cost carriers (LCC) and rival LCCs on the flight-leg level while subsidiary LCCs are established by FSCs against rival LCCs to keep the market share and to make more profit. It is assumed that the demand of economy class for each airline follows a known distribution, and the mean value of that distribution is a function of its airfare and the airfare differences with other airlines. In addition, no-shows and cancellations are introduced to reflect a real situation. Based on this situation, a mathematical model is developed to derive efficient airfare pricing and seat allocation for each airline for maximizing the profit sum of both FSCs and subsidiary LCCs using a repeated game. A repeated game model integrated with a Tabu search algorithm and an EMSR based heuristic is suggested to deal with the proposed repeated game. A numerical example is provided to validate the model and solution procedure with hypothetical system parameter values under two kinds of market situations that show before and after the emergence of subsidiary LCCs.     

Robust hub network design problem

This paper presents a robust formulation for the uncapacitated single and multiple allocation hub location problem where demand is uncertain and its distribution is not fully specified. The proposed robust model is formulated as a mixed integer nonlinear program and then transformed into a mixed integer conic quadratic program. An efficient linear relaxation strategy is proposed which is found to deliver the optimal solutions for all the cases considered in this paper. Numerical experiments suggest location of more number of hubs when accounting for demand uncertainty using robust optimization compared to the deterministic setting.     

Refueling-station location problem under uncertainty

In this paper, we introduce a two-stage stochastic refueling station location model, where the first stage locates permanent stations and the second locates portable stations. The portable alternative fuel stations are an innovative feature in transportation network. The models are applied to an intercity network for Arizona. Computational results show that the permanent stations locate in and around heavily populated nodes. In addition, the results obtained for the portable stations can be utilized to set up permanent stations when the investor intends to increase the number of such stations. The computational results of the exact and greedy approach are reported.