Decision support based automatic container sequencing system using heuristic rules

Container terminals in seaports constitute interfaces between the seaborne transport and transport-over-land of goods in global transport chains. The loading and unloading of containers are performed using quay cranes (QCs), which is the most important equipment for handling servicing vessels at a container terminal. Following tremendous growth in global container transshipments, terminals are facing increasing demand. Terminals at Shanghai are equipped with Tandem Lift which can lift two 40’ containers simultaneously to improve the efficiency of the QCs. A reasonable container combinations of Tandem Lift and container operation sequence are required to improve the servicing of vessels, meanwhile the dual cycling container operation of quay cranes has to be investigated. This paper presents a two-stage mathematical model and two-level heuristic algorithm for planning the container operation sequence using Tandem Lift in a feasible computational time. Based on the proposed methodology, a decision support system, called the Tandem Lift Container Sequence System (TLCSS). A case study of Shanghai Shengdong International Port Company (SSICT) proves that consideration of the container sequence with Tandem Lift dramatically shortens servicing time of vessels with the TLCSS.     

A chassis exchange terminal to reduce truck congestion at container terminals

Truck congestion for container terminals seems to be a worldwide unwanted phenomenon. In this paper we present and analyze a chassis exchange terminal concept to reduce the congestion. The terminal works as a kind of extended gate of a group of traditional container terminals. During the night containers are collected from these container terminals using chassis (or trailers). In daytime these containers on chassis are then collected and exchanged with export containers also on chassis. By exchanging the chassis we avoid extra handling of containers. As connecting and disconnecting to a chassis can be done in a short time, the chassis exchange terminal increases handling capacity substantially during peak hours. In this paper we analyze the concept for the Maasvlakte container terminals in Rotterdam. We investigate both the effect on waiting time, as well as the environmental effects.     

Pricing storage of outbound containers in container terminals

In container yard of container terminals, a storage charge is imposed to encourage customers to limit the space required for their containers. This study addresses the storage price scheduling problem for the storage of outbound containers. The price schedule consists of the free-time limit, which is the maximum duration for a container to stay in the yard without any charge, and storage charge per day for storing a container past the free-time-limit. Empirical data suggests that the efficiency of loading operations significantly depends on the space utilized by a vessel’s outbound containers. Mathematical models are developed to determine the optimal storage price schedule in such a manner that the terminal’s total profit is maximized or the total system’s cost is minimized. Both single and multi-vessel cases are considered. Properties of the optimal solution are derived from the mathematical models and numerical experiments are conducted to validate solutions.     

Strategic allocation of cyclically calling vessels for multi-terminal container operators

We consider a terminal operator who provides container handling services at multiple terminals within the same port. In this setting, the well-known berth allocation problem can no longer be considered for each terminal in isolation since vessel calls should be spread over the various terminals to avoid peaks and troughs in quay crane utilization, and an allocation of two connecting vessels to different terminals will generate inter-terminal container transport. In this paper, we address the problem of spreading a set of cyclically calling vessels over the various terminals and allocating a berthing and departure time to each of them. The objectives are (1) to balance the quay crane workload over the terminals and over time and (2) to minimize the amount of inter-terminal container transport. We develop a solution approach based on mixed-integer programming that allows to solve real-life instances of the problem within satisfactory time. Additionally, a practical case study is presented based on data from the terminal operator PSA Antwerp who operates multiple terminals in the port of Antwerp, Belgium. The computational results show the cost of the currently agreed schedules, and that relatively small modifications can significantly reduce the required crane capacities and inter-terminal transport.     

Operating room scheduling and rescheduling: a rolling horizon approach

In this work we consider the problem of selecting a set of patients among a given waiting list of elective patients and assigning them to a set of available operating room blocks. We assume a block scheduling strategy in which the number and the length of available blocks are given. As each block is related to a specific day, by assigning a patient to a block his/her surgery date is fixed, as well. Each patient is characterized by a recommended maximum waiting time and an uncertain surgery duration. In practical applications, new patients enter the waiting list continuously. Patient selection and assignment is performed by surgery departments on a short-term, usually a week, regular base. We propose a so-called rolling horizon approach for the patient selection and assignment. At each iteration short-term patient assignment is decided. However, in a look-ahead perspective, a longer planning horizon is considered when looking for the patient selection. The mid-term assignment over the next \(n\) weeks is generated by solving an ILP problem, minimizing a penalty function based on total waiting time and tardiness of patients. The approach is iteratively applied by shifting ahead the mid-term planning horizon. When applying the first week solution, unpredictable extensions of surgeries may disrupt the schedule. Such disruptions are recovered in the next iteration: the mid-term solution is rescheduled limiting the number of variations from the previously computed plan. Besides, the approach allows to deal with new patient arrivals. To keep limited the number of disruptions due to uncertain surgery duration, we propose also a robust formulation of the ILP problem. The deterministic and the robust formulation based frameworks are compared over a set of instances, including different stochastic realization of surgery times.     

The storage capacity expansion and space leasing for container depots

Positioning empty containers is one of the most effective ways to solve the container imbalance problem and is affected by the capacity of depots. A shipping company will be more competitive if the depot capacity is large. This study provides a decision tool for planning the expansion of depot capacity. Mathematical models are utilized to minimize the total relevant costs that include the capacity expansion cost, storage space leasing cost, inventory holding cost, container leasing cost, and positioning cost. The problem is formulated as a mixed integer program. Then, we develop a heuristic algorithm that is based on Lagrangian relaxation. Computational experiments are conducted to evaluate the performance of the proposed algorithm.     

Simulated annealing with different vessel assignment strategies for the continuous berth allocation problem

The berth allocation problem is an optimization problem concerning seaside operations at container terminals. This study investigates the dynamic and continuous berth allocation problem (BAP), whose objective is to minimize the total weighted service time and the deviation cost from vessels’ preferred position. The problem is formulated as a mixed integer programming model. Due to that the BAP is NP-hard, two efficient and effective simulated annealing (SA) algorithms are proposed to locate vessels along the quay. The first SA assigns vessels to available positions along the quay from the left to the right, while the second assigns vessels from both sides. Both small and large-scale instances in the literature are tested to evaluate the effectiveness of the proposed SA algorithms using the optimization software Gurobi and heuristic algorithms from the literature. The results indicate that the proposed SAs can provide optimal solutions in small-scale instances and updates the best solutions in large-scale instances. The improvement over other comparing heuristics is statistically significant.     

A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem

The shortest common supersequence problem is a classical problem with many applications in different fields such as planning, Artificial Intelligence and especially in Bioinformatics. Due to its NP-hardness, we can not expect to efficiently solve this problem using conventional exact techniques. This paper presents a heuristic to tackle this problem based on the use at different levels of a probabilistic variant of a classical heuristic known as Beam Search. The proposed algorithm is empirically analysed and compared to current approaches in the literature. Experiments show that it provides better quality solutions in a reasonable time for medium and large instances of the problem. For very large instances, our heuristic also provides better solutions, but required execution times may increase considerably.     

A New Model for a Carpool Matching Service

Carpooling is an effective means of reducing traffic. A carpool team shares a vehicle for their commute, which reduces the number of vehicles on the road during rush hour periods. Carpooling is officially sanctioned by most governments, and is supported by the construction of high-occupancy vehicle lanes. A number of carpooling services have been designed in order to match commuters into carpool teams, but it known that the determination of optimal carpool teams is a combinatorially complex problem, and therefore technological solutions are difficult to achieve. In this paper, a model for carpool matching services is proposed, and both optimal and heuristic approaches are tested to find solutions for that model. The results show that different solution approaches are preferred over different ranges of problem instances. Most importantly, it is demonstrated that a new formulation and associated solution procedures can permit the determination of optimal carpool teams and routes. An instantiation of the model is presented (using the street network of Guangzhou city, China) to demonstrate how carpool teams can be determined.     

Added-value of mosquito vector breeding sites from street view images in the risk mapping of dengue incidence in Thailand

Dengue is an emerging vector-borne viral disease across the world. The primary dengue mosquito vectors breed in containers with sufficient water and nutrition. Outdoor containers can be detected from geotagged images using state-of-the-art deep learning methods. In this study, we utilize such container information from street view images in developing a risk mapping model and determine the added value of including container information in predicting dengue risk. We developed seasonal-spatial models in which the target variable dengue incidence was explained using weather and container variable predictors. Linear mixed models with fixed and random effects are employed in our models to account for different characteristics of containers and weather variables. Using data from three provinces of Thailand between 2015 and 2018, the models are developed at the sub-district level resolution to facilitate the development of effective targeted intervention strategies. The performance of the models is evaluated with two baseline models: a classic linear model and a linear mixed model without container information. The performance evaluated with the correlation coefficients, R-squared, and AIC shows the proposed model with the container information outperforms both baseline models in all three provinces. Through sensitivity analysis, we investigate the containers that have a high impact on dengue risk. Our findings indicate that outdoor containers identified from street view images can be a useful data source in building effective dengue risk models and that the resulting models have potential in helping to target container elimination interventions.     

A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids

The sensitivity analysis of a Cellular Genetic Algorithm (CGA) with local search is used to design a new and faster heuristic for the problem of mapping independent tasks to a distributed system (such as a computer cluster or grid) in order to minimize makespan (the time when the last task finishes). The proposed heuristic improves the previously known Min-Min heuristic. Moreover, the heuristic finds mappings of similar quality to the original CGA but in a significantly reduced runtime (1,000 faster). The proposed heuristic is evaluated across twelve different classes of scheduling instances. In addition, a proof of the energy-efficiency of the algorithm is provided. This convergence study suggests how additional energy reduction can be achieved by inserting low power computing nodes to the distributed computer system. Simulation results show that this approach reduces both energy consumption and makespan.     

An analytical model for designing yard layouts of a straddle carrier based container terminal

In designing a yard layout for a container terminal several decisions have to be made. In this paper we propose a model which provides decision support for the design of yard layouts of terminals at which straddle carrier are used. We assume that straddle carriers are used for the horizontal transport and the stacking of containers. For the proposed model we develop estimates for the expected cycle distances of straddle carriers. In this case, we distinguish between cycles to landside facilities and to the quay. Numerical results are presented for several parameter settings. For instance, we present results for a comparison of layouts where the rows in the block are orientated parallel with layouts where the rows are orientated perpendicularly to the quay.     

Optimal response to chemotherapy for a mathematical model of tumor–immune dynamics

An optimal control problem for cancer chemotherapy is considered that includes immunological activity. In the objective a weighted average of several quantities that describe the effectiveness of treatment is minimized. These terms include (i) the number of cancer cells at the terminal time, (ii) a measure for the immunocompetent cell densities at the terminal point (included as a negative term), (iii) the overall amount of cytotoxic agents given as a measure for the side effects of treatment and (iv) a small penalty on the terminal time that limits the overall therapy horizon which is assumed to be free. This last term is essential in obtaining a well-posed problem formulation. Employing a Gompertzian growth model for the cancer cells, for various scenarios optimal controls and corresponding responses of the system are calculated. Solutions initially follow a full dose treatment, but then at one point switch to a singular regimen that only applies partial dosages. This structure is consistent with protocols that apply an initial burst to reduce the tumor volume and then maintain a small volume through lower dosages. Optimal controls end with either a prolonged period of no dose treatment or, in a small number of scenarios, this no dose interval is still followed by one more short burst of full dose treatment.     

Dispatching,routing, and scheduling of two automated guided vehicles in a flexible manufacturing system

This article presents a new approach for planning the dispatching, conflict-free routing, and scheduling of automated guided vehicles in a flexible manufacturing system. The problem is solved optimally in an integrated manner, contrary to the traditional approach in which the problem is decomposed in three steps that are solved sequentially. The algorithm is based on dynamic programming and is solved on a rolling time horizon. Three dominance criteria are used to limit the size of the state space. The method finds the transportation plan minimizing the makespan (the completion time for all the tasks). Various results are discussed. A heuristic version of the algorithm is also proposed for an extension of the method to many vehicles.     

Mixed integer linear programming for maximum-parsimony phylogeny inference

Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be required if we are to be able to continue to make effective use of the rapidly growing stores of variation data now being gathered. In this paper, we present two integer linear programming (ILP) formulations to find the most parsimonious phylogenetic tree from a set of binary variation data. One method uses a flow-based formulation that can produce exponential numbers of variables and constraints in the worst case. The method has, however, proven extremely efficient in practice on datasets that are well beyond the reach of the available provably efficient methods, solving several large mtDNA and Y-chromosome instances within a few seconds and giving provably optimal results in times competitive with fast heuristics than cannot guarantee optimality. An alternative formulation establishes that the problem can be solved with a polynomial-sized ILP. We further present a web server developed based on the exponential-sized ILP that performs fast maximum parsimony inferences and serves as a front end to a database of precomputed phylogenies spanning the human genome.     

Integer programming approaches to haplotype inference by pure parsimony

In 2003, Gusfield introduced the haplotype inference by pure parsimony (HIPP) problem and presented an integer program (IP) that quickly solved many simulated instances of the problem. Although it solved well on small instances, Gusfield's IP can be of exponential size in the worst case. Several authors have presented polynomial-sized IPs for the problem. In this paper, we further the work on IP approaches to HIPP. We extend the existing polynomial-sized IPs by introducing several classes of valid cuts for the IP. We also present a new polynomial-sized IP formulation that is a hybrid between two existing IP formulations and inherits many of the strengths of both. Many problems that are too complex for the exponential-sized formulations can still be solved in our new formulation in a reasonable amount of time. We provide a detailed empirical comparison of these IP formulations on both simulated and real genotype sequences. Our formulation can also be extended in a variety of ways to allow errors in the input or model the structure of the population under consideration.     

An improved transiently chaotic neural network for the maximum independent set problem

By analyzing the dynamic behaviors of the transiently chaotic neural network and greedy heuristic for the maximum independent set (MIS) problem, we present an improved transiently chaotic neural network for the MIS problem in this paper. Extensive simulations are performed and the results show that this proposed transiently chaotic neural network can yield better solutions to p-random graphs than other existing algorithms. The efficiency of the new model is also confirmed by the results on the complement graphs of some DIMACS clique instances in the second DIMACS challenge. Moreover, the improved model uses fewer steps to converge to stable state in comparison with the original transiently chaotic neural network.     

Material Flows and Energy Analysis of Glass Containers Discarded in New Jersey,USA

The use of glass cullet (crushed recycled glass containers) as aggregate in construction projects and landfills has increased rapidly even though the use of cullet as feedstock in new glass container and fiberglass production is energetically more sound. The effect of increased use of cullet as aggregate has not yet been thoroughly assessed. The objectives of this study were to model and quantify glass container flows across New Jersey and the associated life cycle energy consumption, and then compare life cycle energy consumption for two different recycling scenarios and three different end‐use/disposal scenarios. The results of a material flow analysis showed that in 2008 only about 11% of the glass containers consumed in New Jersey were used as glass container or fiberglass feedstock, while five times more were used as construction aggregate. However, a lower system energy requirement can be achieved by increased use of cullet as container feedstock compared to construction aggregate, even when the cullet is transported 1,600 miles to a glass container manufacturer. Based on the uncertainty analysis, there is about an 80% probability for the scenario with increased use as container feedstock to have a lower system energy requirement when compared with all other scenarios. To achieve increased use of cullet as glass container feedstock in New Jersey, the quality of the cullet must be improved.     

Do container size and predator presence affect Culex (Diptera: Culicidae) oviposition preferences?

Organisms with complex life cycles typically do not exhibit parental care. Hence, the ability of adult females to choose quality oviposition sites is critical for offspring success. Gravid females of many insect taxa have the capability to detect environmental conditions in water-holding containers (e.g., resource level, presence of competitors or predators) and to choose the sites that are most suitable for offspring growth and development. Mosquitoes may also detect physical container characteristics related to water permanence such as surface area, volume, or container size, and some species such as those in the genus Culex have been shown to prefer larger containers. However, predators may also preferentially colonize larger containers; thus, ovipositing females may face decisions based on cues of site quality that balance the costs and benefits for offspring. We used a field experiment to evaluate the oviposition preferences of two Culex species in response to experimental container size and predator abundances within the containers. We found that both species avoided ovipositing in the largest containers, which have high abundances of Chaoborus sp. and dragonfly larvae (predators). However, the container size most commonly chosen for oviposition (15-L buckets) also had high mean abundance per liter of dragonfly larvae. These results suggest either prey naiveté or reduced vulnerability of these species to dragonflies compared to Chaoborus sp. Other potential mechanisms for the observed patterns are discussed.     

Resource allocation for epidemic control over short time horizons

We present a model for allocation of epidemic control resources among a set of interventions. We assume that the epidemic is modeled by a general compartmental epidemic model, and that interventions change one or more of the parameters that describe the epidemic. Associated with each intervention is a 'production function' that relates the amount invested in the intervention to values of parameters in the epidemic model. The goal is to maximize quality-adjusted life years gained or the number of new infections averted over a fixed time horizon, subject to a budget constraint. Unlike previous models, our model allows for interacting populations and non-linear interacting production functions and does not require a long time horizon. We show that an analytical solution to the model may be difficult or impossible to derive, even for simple cases. Therefore, we derive a method of approximating the objective functions. We use the approximations to gain insight into the optimal resource allocation for three problem instances. We also develop heuristics for solving the general resource allocation problem. We present results of numerical studies using our approximations and heuristics. Finally, we discuss implications and applications of this work.