A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil

A heuristic based on genetic algorithms is proposed to the problem of configuring hub-and-spoke networks for trucking companies that operate less-than-truckload (LTL) services in Brazil. The problem consists of determining the number of consolidation terminals (also known as hubs), their locations and the assignment of the spokes to the hubs, aiming to minimize the total cost, which is composed of fixed and variable costs. The proposed formulation differs from similar formulations found in the literature in the sense that it allows variable scale-reduction factors for the transportation costs according to the total amount of freight between hub terminals, as occurs to less-than-truckload (LTL) freight carriers in Brazil. Our genetic algorithm approach incorporates an efficient local improvement procedure that is applied to each generated individual of the population. Computational results for benchmark problems are presented. A practical application to a real world problem involving one of the top-ten trucking companies in Brazil is also described.     

Integrated scheduling of crane handling and truck transportation in a maritime container terminal

This paper studies the interactions between crane handling and truck transportation in a maritime container terminal by addressing them simultaneously. Yard trucks are shared among different ships, which helps to reduce empty truck trips in the terminal area. The problem is formulated as a constraint programming model and a three-stage algorithm is developed. At the first stage, crane schedules are generated by a heuristic method. At the second stage, the multiple-truck routing problem is solved based on the precedence relations of the transportation tasks derived from the first stage. At the last stage a complete solution is constructed by using a disjunctive graph. The three procedures are linked by an iterative structure, which facilitates the search for a good solution. The computational results indicate that the three-stage algorithm is effective for finding high-quality solutions and can efficiently solve large problems.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

Routing and location on a network with hazardous threats

The aim of this paper is to minimise the impact of hazards located on or near a network. Two situations are considered: (1) where a hazard is located on a network and affects off network sites and (2) an off-network hazard which can affect traffic on the network. Eight models aimed at optimising different objectives are developed and solved, including finding a route between two nodes on a network which minimises the hazard along it and finding a location on a network where the hazard is minimised.     

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.     

Models and computational algorithms for maritime risk analysis: a review

Due to the undesirable implications of maritime mishaps such as ship collisions and the consequent damages to maritime property; the safety and security of waterways, ports and other maritime assets are of the utmost importance to authorities and researches. Terrorist attacks, piracy, accidents and environmental damages are some of the concerns. This paper provides a detailed literature review of over 180 papers about different threats, their consequences pertinent to the maritime industry, and a discussion on various risk assessment models and computational algorithms. The methods are then categorized into three main groups: statistical, simulation and optimization models. Corresponding statistics of papers based on year of publication, region of case studies and methodology are also presented.     

Routing,districting and location for arc traversal problems

We summarize the main results of the authors PhD thesis, defended in February 2003 at the Katholieke Universiteit Leuven (Belgium) and supervised by Dirk Cattrysse. The thesis is written in English and presents a number of solution and modeling approaches for distribution problems in the context of arc routing. In particular, the focus is on (1) local search procedures for arc routing problems, (2) district design for arc routing applications and (3) the study of location aspects in relation with districting and arc routing.AMS classification: 90B06, 05C38, 90C35, 90C59     

Routing a mix of conventional,plug-in hybrid,and electric vehicles

We introduce an electric vehicle routing problem combining conventional, plug-in hybrid, and electric vehicles. Electric vehicles are constrained in their service range by their battery capacity, and may require time-consuming recharging operations at some specific locations. Plug-in hybrid vehicles have two engines, an internal combustion engine and an electric engine using a built-in rechargeable battery. These vehicles can avoid visits to recharging stations by switching to fossil fuel. However, this flexibility comes at the price of a generally higher consumption rate and utility cost.To solve this complex problem variant, we design a sophisticated metaheuristic which combines a genetic algorithm with local and large neighborhood search. All route evaluations, within the approach, are based on a layered optimization algorithm which combines labeling techniques and greedy evaluation policies to insert recharging stations visits in a fixed trip and select the fuel types. The metaheuristic is finally hybridized with an integer programming solver, over a set partitioning formulation, so as to recombine high-quality routes from the search history into better solutions. Extensive experimental analyses are conducted, highlighting the good performance of the algorithm and the contribution of each of its main components. Finally, we investigate the impact of fuel and energy cost on fleet composition decisions. Our experiments show that a careful use of a mixed fleet can significantly reduce operational costs in a large variety of price scenarios, in comparison with the use of a fleet composed of a single vehicle class.     

A heuristic for sea-freight container selection,cargo allocation and cargo orientation

A model is proposed to generate solutions for container selection, for the allocation of cargo to containers, and for cargo orientation within a container. The model is in the form of a mixed integer program with the objective of minimizing the total shipping cost. The practical requirements of loading priority and weight distribution along the main dimension of the container are incorporated into the model. A heuristic solution strategy is proposed and used to control the computation time by pre-setting the search increments. Three case examples are presented. The first and third examples show that the proposed model can produce a better solution than the manual schedulers. The second example is taken from the literature and is compared with the solution generated by the proposed model, demonstrating that the practical considerations incorporated into the model do not necessarily lead to increased shipping costs.     

Assessing a set of additive utility functions for multicriteria decision-making,the UTA method

The purpose of the method presented in this paper is to assess additive utility functions which aggregate multiple criteria in a composite criterion, using the information given by a subjective ranking on a set of stimuli or actions (weak-order comparison judgments) and the multicriteria evaluations of these actions. It is an ordinal regression method using linear programming to estimate the parameters of the utility function.Stability and sensitivity analysis leads to the assessment of a set of utility functions by means of post-optimality analysis techniques in linear programming.Finally, a simple illustrative example is presented and some extensions of the method are proposed.     

Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk,Part I: Applications and model

This paper formulates a model for finding a minimum cost routing in a network for a heterogeneous fleet of ships engaged in pickup and delivery of several liquid bulk products. The problem is frequently encountered by maritime chemical transport companies, including oil companies serving an archipelago of islands. The products are assumed to require dedicated compartments in the ship. The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the production rates, the consumption rates, and the storage capacities of the various products in each port. This important and challenging inventory constrained multi-ship pickup–delivery problem is formulated as a mixed-integer nonlinear program. We show that the model can be reformulated as an equivalent mixed-integer linear program with special structure. Over 100 test problems are randomly generated and solved using CPLEX 7.5. The results of our numerical experiments illuminate where problem structure can be exploited in order to solve larger instances of the model. Part II of the sequel will deal with new algorithms that take advantage of model properties.     

Reducing mosquito-borne disease outbreak size: The relative importance of contact and transmissibility in a network model

The complex biological and environmental factors involved in the transmission of mosquito-borne diseases in humans have made their control elusive in many instances. Conceptual models contribute to gain insight and help to reduce the risk of taking poor managerial decisions. The focus of this paper is to compare, using a contact network model, the impact that perturbation of the number infectious contacts and of transmissibility have on the size of an outbreak. We illustrate the analysis on a contact network parametrized with data that associates humans and the mosquito Culex quinquefasciatus, a vector for lymphatic filariasis. The model suggests that, if the values corresponding to transmissibility and number of infectious contacts is relatively large, variations in the size of an outbreak are significantly in favor of control measures to reduce infectious contacts.     

A Lagrangian heuristic for determining the speed and bunkering port of a ship

This study addresses the problem of determining the ship speed and bunkering ports in a ship route. All of the previous research has investigated the ship speed optimization issues by assuming that the ship navigates at constant speed or by ignoring the bunkering port decision. In this study, the problem of determining the variable speed and bunkering port is formulated mathematically with a nonlinear program in order to minimize the bunker fuel, ship time costs, and carbon tax imposed on greenhouse gas emissions. This study then provides a Lagrangian heuristic by deriving a property for a relaxed problem. The performance of the heuristic is evaluated and analysed using the data obtained from the literature, real practice and random generation.     

A Routing and Scheduling Problem for a Rail System: A Case Study

Railways are extensively used in the Australian sugar industry to transport cane from farms to the factories. Development of efficient schedules manually is difficult, given a weak set of constraints and the need to consider operating and capital costs and the deterioration of cane in the period between harvesting and processing. The Cane Railway Scheduling Problem deals with the design of a regular schedule. The algorithm devised is based on a serial decomposition (with routing and scheduling considered separately) to generate a trial solution, modification of the trial solution to provide a first feasible solution and iterative refinement to provide the final solution. Comparison of solutions produced by the algorithm and those generated manually suggests potential savings ranging from 20% to 30% in annual operating costs with accompanying reductions in rolling stock requirements. Use of the model in the industry is noted.     

Optimal locations for a class of nonlinear, single-facility location problems on a network

This paper investigates a class of single-facility location problems on an arbitrary network. Necessary and sufficient conditions are obtained for characterizing locally optimal locations with respect to a certain nonlinear objective function. This approach produces a number of new results for locating a facility on an arbitrary network, and in addition it unifies several known results for the special case of tree networks. It also suggests algorithmic procedures for obtaining such optimal locations.     

Power, sample size and sampling costs for clustered data

The data collected in epidemiological or clinical studies are frequently clustered. In such settings, appropriate variance adjustments must be made in order to estimate the sufficient sample size correctly. This paper works through the sample size calculations for clustered data. Importantly, our explicit variance expressions also enable us to optimize the design with respect to the number of clusters and number of subjects; the objective could be either to maximize the power or to minimize the costs with given costs on the clusters and on the individuals. In our approach, units on different levels and treatment groups can have different costs, but the members of the same cluster are assumed to belong to the same treatment group. Design considerations in the health coaching project TERVA are used as motivating examples. R-functions for carrying out the computations presented are provided.     

A general solution for the newsboy model with random order size and possibly a cutoff transaction size

In a recent paper, Dekker et al developed a solution procedure for the newsboy problem with a cutoff transaction size (CTS), such that customers with orders larger than the cutoff value are satisfied in an alternative way, against additional cost. A compound Poisson demand with discrete order sizes is assumed, and a computational procedure developed to identify the optimal solution. In this paper, we discard all distributional assumptions, and, given that order size is random, only the first three moments of the arrival rate and the order size are specified. A general optimal solution is developed, using Shore's piece-wise linear approximations. For cases where a CTS exists, the derived optimal solution is extended to also identify the optimal CTS. The new solution approach requires minimal distributional information, and its merits relative to current approaches are discussed and numerically demonstrated. The new methodology, based on a ‘Calculus of moments’ combined with a distributional approximation, may be easily extended to other computationally intractable problems.     

Automatic differentiation for the optimization of a ship propulsion and steering system: a proof of concept

We describe the optimization of the Voith-Schneider-Propeller (VSP) which is an industrial propulsion and steering system of a ship combined in one module. The goal is to optimize efficiency of the VSP with respect to different design variables. In order to determine the efficiency, we have to use numerical simulations for the complex flow around the VSP. Such computations are performed with standard (partly commercial) flow solvers. For the numerical optimization, one would like to use gradient-based methods which requires derivatives of the flow variables with respect to the design parameters. In this paper, we investigate if Automatic Differentiation (AD) offers a method to compute the required derivatives in the described framework. As a proof of concept, we realize AD for the 2D-code Caffa and the 3D-code Comet, for the simplified model of optimizing efficiency with respect to the angle of attack of one single blade (like an airfoil). We show that AD gives smooth derivatives, whereas finite differences show oscillations. This regularization effect is even more pronounced in the 3D-case. Numerical optimization by AD and Newton’s method shows almost optimal convergence rates.     

A container yard storage strategy for improving land utilization and operation efficiency in a transshipment hub port

This paper studies the storage yard management problem in a busy transshipment hub, where intense loading and unloading activities have to be considered at the same time. The need to handle huge volumes of container traffic and the scarcity of land in the container port area pose serious challenges for the port operator to provide efficient services. A consignment strategy with a static yard template has been used to reduce the level of reshuffles in the yard, but it sacrifices on land utilization because of exclusive storage space reservation. Two space-sharing approaches are proposed to improve on the land utilization through dynamic reservation of storage space for different vessels during different shifts. Meanwhile, workload assignment among reserved spaces will also satisfy the high-low workload balancing protocol to reduce traffic congestion in the yard. A framework which integrates space reservation and workload assignment is proposed. Experimental results show that the framework is able to provide solutions for containers handling within much less storage space, while guarantee the least yard crane deployment.