Tighter MIP models for Barge Container Ship Routing

This paper addresses the problem of optimal planning of a liner service for a barge container shipping company. Given estimated weekly demands between pairs of ports, our goal is to determine the subset of ports to be called and the amount of containers to be shipped between each pair of ports, so as to maximize the profit of the shipping company. In order to save possible leasing or storage costs of empty containers at the respective ports, our approach takes into account the repositioning of empty containers. The line has to follow the outbound–inbound principle, starting from the port at the river mouth. We propose a novel integrated approach in which the shipping company can simultaneously optimize the route (along with repositioning of empty containers), the choice of the final port, length of the turnaround time and the size of its fleet. To solve this problem, a new mixed integer programming model is proposed. On the publicly available set of benchmark instances for barge container routing, we demonstrate that this model provides very tight dual bounds and significantly outperforms the existing approaches from the literature for splittable demands.We also show how to further improve this model by projecting out arc variables for modeling the shipping of empty containers. Our numerical study indicates that the latter model improves the computing times for the challenging case of unsplittable demands. We also study the impact of the turnaround time optimization on the total profit of the company.     

竞争环境下的轴-辐式集装箱海运网络设计问题

针对航运企业的重组与全球扩张引起的竞争问题,提出了竞争环境下的轴-辐式集装箱海运网络设计模型。模型采用基于路径的变量作为决策变量,利用离散函数来表示航运企业与航运联盟的竞争可吸引的流量(或客户),目的在于通过设计混合轴-辐式集装箱海运网络,实现以更低的服务成本和更短的服务时间最大化可吸引的流量,建立了枢纽港口数量约束、航线连接约束、航线中转约束、流量竞争约束等,运用多点交叉遗传算法进行求解,最后结合亚欧航线的集装箱海运市场进行实例分析,对考虑客户需求多样性与航运联盟对策下的轴-辐式集装箱海运网络进行设计,并验证了算法的计算效果。     

Preventing the Importation of Illicit Nuclear Materials in Shipping Containers

We develop a mathematical model to find the optimal inspection strategy for detecting a nuclear weapon (or nuclear material to make a weapon) from being smuggled into the United States in a shipping container, subject to constraints of port congestion and an overall budget. We consider an 11-layer security system consisting of shipper certification, container seals, and a targeting software system, followed by passive (neutron and gamma), active (gamma radiography), and manual testing at overseas and domestic ports. Currently implemented policies achieve a low detection probability, and improved security requires passive and active testing of trusted containers and manually opening containers that cannot be penetrated by radiography. The annual cost of achieving a high detection probability of a plutonium weapon using existing equipment in traditional ways is roughly several billion dollars if testing is done domestically, and is approximately five times higher if testing is performed overseas. Our results suggest that employing high-energy x-ray radiography and elongating the passive neutron tests at overseas ports may provide significant cost savings, and several developing technologies, radiation sensors inside containers and tamper-resistant electronic seals, should be pursued aggressively. Further effort is critically needed to develop a practical neutron interrogation scheme that reliably detects moderately shielded, highly enriched uranium.     

Scheduling material handling vehicles in a container terminal

Increasing global trade has created the need for efficient container ports. The goal of the port is to move containers as quickly as possible and at the least possible cost. Goods that are delayed at the port are inevitably tardy when delivered to the customer, and thus sanctioned by late charges. Two key activities in the port are (i) unloading of containers from truck and then storage in the export area, and (ii) removal of containers from import storage and then loading onto the trucks. Since containers are large and heavy, specialized material handling vehicles are required for transporting them within the terminal. The focus of this paper is on port terminals where straddle carriers are primarily used to move containers. Container terminals typically have well developed computer and communication networks. Through these networks a terminal scheduler will control and schedule the movement of the straddle carrier fleet in real time. The objective of the terminal scheduler is to minimize the empty travel of straddle carriers, while at the same time minimizing any delays in servicing customers. This paper presents a straddle scheduling procedure that can be used by a terminal scheduler to control the movement of straddle carriers. At its core, the procedure is driven by an assignment algorithm that dynamically matches straddle carriers and trucks, as each becomes available. The procedures were developed and tested in collaboration with the largest container terminal operator in the Port of New York and New Jersey. Using a simulation model of the real system, the superiority of the proposed procedure over two alternative scheduling strategies is illustrated.     

An Industrial Ocean-Cargo Shipping Problem

This paper reports the modeling and solution of an industrial ocean-cargo shipping problem. The problem involves the delivery of bulk products from an overseas port to transshipment ports on the Atlantic Coast, and then over land to customers. The decisions made include the number and the size of ships to charter in each time period during the planning horizon, the number and location of transshipment ports to use, and transportation from ports to customers. The complexity of this problem is compounded by the cost structure, which includes fixed charges in both ship charters and port operations. Such a large scale, dynamic, and stochastic problem is reduced to a solvable stationary, deterministic, and cyclical model. The process of modeling the problem and the solution of the resultant mixed integer program are described in detail. Recommendations from this study have been implemented.     

A solution framework for the multi-mode resource-constrained cross-dock scheduling problem

In this paper we propose a framework for shift-level container scheduling and resource allocation decisions at a cross-dock facility. The Multi-Mode Resource-Constrained Cross-Dock Scheduling Problem (MRCDSP) approach minimizes material flow and schedules inbound and outbound containers to dock-doors such that the total processing time is minimized subject to the resource constraints at the cross-dock. While container scheduling and resource allocation problems at cross-dock facilities have been studied previously in isolation, our work is the first to consider a complete view of cross-dock operations providing optimal container to dock-door allocation, and a makespan minimizing schedule of containers to the cross-dock. We present a comprehensive framework that includes identification of container clusters to reduce the problem size, a container-to-dock-door assignment algorithm, and a container clusters scheduling model that is solvable for practically sized problems. In a comparative numeric study based on data simulating a cross-dock facility, our approach is shown to outperform current practice, reducing the average time required for processing a set of containers by 37% and reducing the weighted-distance material traveled within the cross-dock by 45%.     

A continuous-time supply-driven inventory-constrained routing problem

We address an inventory routing problem (IRP) in which routing and inventory decisions are dictated by supply rather than demand. Moreover, inventory is held in containers that act as both a storage container and a movable transport unit. This problem emanates from logistics related to biogas transportation in which biogas is transported in containers from many suppliers to a single facility. We present a novel and compact formulation for the supply-driven IRP which addresses the routing decisions in continuous-time in which inventory levels within the containers are continuous. Valid inequalities are included and realistic instances are solved to optimality. For all experiments, we found that the total transportation time is minimized when the storage capacity at each supplier is larger than or equal to the vehicle capacity. These routes are characterized by tours in which mostly single suppliers are visited. In 95% of the instances, the average content level of the exchanged containers exceeded 99.6%.     

港口管理与运营: 新兴研究热点及其进展

中国已经成为世界最大的集装箱集疏地.随着建设"新丝绸之路经济带"和"21世纪海上丝绸之路"(简称"一带一路")国家战略的提出,中国港口迎来了新的发展机遇.港口管理和运营涉及单一港口维度一个或者多个资源的运作优化问题,港口群维度港口之间的协作行为和机制问题,海运供应链维度港口与主要利益相关者之间的协作行为和机制问题等.文章介绍了中国港口在国际海运物流中的重要地位以及全面梳理了近年来港口管理与运营相关问题的研究进展;基于国内外学者已取得的最新研究成果,结合中国本土实践情境,文章指出当今的研究空白,从新的研究视角出发详细介绍了潜在的研究热点问题,分析了相关领域研究的必要性和迫切性.     

Time-Varying Risk Measurement for Ship Collision Prevention

We propose an innovative time-varying collision risk (TCR) measurement for ship collision prevention in this article. The proposed measurement considers the level of danger of the approaching ships and the capability of a ship to prevent collisions. We define the TCR as the probability of the overlap of ships’ positions in the future, given the uncertainty of maneuvers. Two sets are identified: (1) the velocity obstacle set as the maneuvers of the own ship that lead to collisions with target ships, and (2) the reachable velocity set as the maneuvers that the own ship can reach regarding its maneuverability. We then measure the TCR as the time-dependent percentage of overlap between these two sets. Several scenarios are presented to illustrate how the proposed measurement identifies the time-varying risk levels, and how the approach can be used as an intuitively understandable tool for collision avoidance.     

From theory to practice: maximizing revenues for on-line dial-a-ride

We consider the on-line dial-a-ride problem, where a server fulfills requests that arrive over time. Each request has a source, destination, and release time. We study a variation of this problem where each request also has a revenue that the server earns for fulfilling the request. The goal is to serve requests within a time limit while maximizing the total revenue. We first prove that no deterministic online algorithm can be competitive unless the input graph is complete and edge weights are unit. We therefore focus on these graphs and present a 2-competitive algorithm for this problem. We also consider two variations of this problem: (1) the input graph is complete bipartite and (2) there is a single node that is the source for every request, and present a 1-competitive algorithm for the former and an optimal algorithm for the latter. We also provide experimental results for the complete and complete bipartite graphs. Our simulations support our theoretical findings and demonstrate that our algorithms perform well under settings that reflect realistic dial-a-ride systems.     

Improving robustness of next-hop routing

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following tree augmentation problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that tree augmentation is NP-hard in general and present a simple \(\frac{1}{2}\)-approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, tree augmentation has not been previously studied.     

A New Approach to Hazardous Materials Transportation Risk Analysis: Decision Modeling to Identify Critical Variables

We take a novel approach to analyzing hazardous materials transportation risk in this research. Previous studies analyzed this risk from an operations research (OR) or quantitative risk assessment (QRA) perspective by minimizing or calculating risk along a transport route. Further, even though the majority of incidents occur when containers are unloaded, the research has not focused on transportation-related activities, including container loading and unloading. In this work, we developed a decision model of a hazardous materials release during unloading using actual data and an exploratory data modeling approach. Previous studies have had a theoretical perspective in terms of identifying and advancing the key variables related to this risk, and there has not been a focus on probability and statistics-based approaches for doing this. Our decision model empirically identifies the critical variables using an exploratory methodology for a large, highly categorical database involving latent class analysis (LCA), loglinear modeling, and Bayesian networking. Our model identified the most influential variables and countermeasures for two consequences of a hazmat incident, dollar loss and release quantity , and is one of the first models to do this. The most influential variables were found to be related to the failure of the container. In addition to analyzing hazmat risk, our methodology can be used to develop data-driven models for strategic decision making in other domains involving risk.     

基于“前港后厂”模式的进口铁矿石采购物流成本优化

作为钢铁产量大国，国内铁矿石资源品位低、开采难度大、选矿成本高，需要大量进口国外优质铁矿石，导致钢铁企业采购物流成本居高不下；长期大批量远距离的铁矿石海运历史，促使了我国"港-钢"企业的发展紧密相连。因此，本文基于"前港后厂"模式，构建了以船型、供应商和接卸港的选择为变量，以最小化铁矿石采购物流成本为目标的组合优化模型。运用免疫遗传算法和MATLAB进行求解与仿真验证，结果表明"前港后厂"模式较传统模式在优化采购物流系统上更优，为推行"前港后厂"模式提供了理论依据。     

Risk Reduction of an Invasive Insect by Targeting Surveillance Efforts with the Assistance of a Phenology Model and International Maritime Shipping Routes and Schedules

Reducing the risk of introduction to North America of the invasive Asian gypsy moth (Lymantria dispar asiatica Vnukovskij and L. d. japonica [Motschulsky]) on international maritime vessels involves two tactics: (1) vessels that wish to arrive in Canada or the United States and have visited any Asian port that is subject to regulation during designated times must obtain a predeparture inspection certificate from an approved entity; and (2) vessels with a certificate may be subjected to an additional inspection upon arrival. A decision support tool is described here with which the allocation of inspection resources at North American ports can be partitioned among multiple vessels according to estimates of the potential onboard Asian gypsy moth population and estimates of the onboard larval emergence pattern. The decision support tool assumes that port inspection is uniformly imperfect at the Asian ports and that each visit to a regulated port has potential for the vessel to be contaminated with gypsy moth egg masses. The decision support tool uses a multigenerational phenology model to estimate the potential onboard population of egg masses by calculating the temporal intersection between the dates of port visits to regulated ports and the simulated oviposition pattern in each port. The phenological development of the onboard population is simulated each day of the vessel log until the vessel arrives at the port being protected from introduction. Multiple independent simulations are used to create a probability distribution of the size and timing of larval emergence.     

Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties

In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.

     

The two-dimensional vector packing problem with piecewise linear cost function

The two-dimensional vector packing problem with piecewise linear cost function (2DVPP-PLC) is a practical problem faced by a manufacturer of children׳s apparel that ships products using courier service. The manufacturer must ship a number of items using standard-sized cartons, where the cost of a carton quoted by the courier is determined by a piecewise linear function of its weight. The cost function is not necessarily convex or concave. The objective is to pack all given items into a set of cartons such that the total delivery cost is minimized while observing both the weight limit and volume capacity constraints. This problem is commonly faced by many manufacturers that ship products using courier service. We formulate the problem as an integer programming model. Since the 2DVPP-PLC generalizes the classical bin packing problem, it is more complex and challenging. Solving it directly using CPLEX is successful only for small instances. We propose a simple heuristic that is extremely fast and produces high-quality solutions for instances of practical size. We develop an iterative local search algorithm to improve the solution quality further. We generate two categories of test data that can serve as benchmark for future research.     

Detecting nuclear materials smuggling: performance evaluation of container inspection policies

In recent years, the United States, along with many other countries, has significantly increased its detection and defense mechanisms against terrorist attacks. A potential attack with a nuclear weapon, using nuclear materials smuggled into the country, has been identified as a particularly grave threat. The system for detecting illicit nuclear materials that is currently in place at U.S. ports of entry relies heavily on passive radiation detectors and a risk-scoring approach using the automated targeting system (ATS). In this article we analyze this existing inspection system and demonstrate its performance for several smuggling scenarios. We provide evidence that the current inspection system is inherently incapable of reliably detecting sophisticated smuggling attempts that use small quantities of well-shielded nuclear material. To counter the weaknesses of the current ATS-based inspection system, we propose two new inspection systems: the hardness control system (HCS) and the hybrid inspection system (HYB). The HCS uses radiography information to classify incoming containers based on their cargo content into "hard" or "soft" containers, which then go through different inspection treatment. The HYB combines the radiography information with the intelligence information from the ATS. We compare and contrast the relative performance of these two new inspection systems with the existing ATS-based system. Our studies indicate that the HCS and HYB policies outperform the ATS-based policy for a wide range of realistic smuggling scenarios. We also examine the impact of changes in adversary behavior on the new inspection systems and find that they effectively preclude strategic gaming behavior of the adversary.     

Assurance of security in maritime supply chains: Conceptual issues of vulnerability and crisis management

Security assurance across maritime trading systems is a critical factor for international business managers and in the evolution of international trade generally. A number of initiatives are underway focusing on security issues in ports and ships (International Ship & Port Security Code), customs inspections in international ports (Container Security Initiative) and whole-of-supply chain outcomes (Customs & Trade Partnership against Terrorism). The main purpose of the above initiatives is to reduce the likelihood of maritime-vectored terrorism; however inappropriate implementation of these programs could affect competitiveness.This paper suggests that the complexity of interaction between ports, maritime operations and supply chains create vulnerabilities that require analysis that extends beyond the structured requirements of these initiatives and creates significant management challenges. Also the paper highlights the need for enhanced crisis management capabilities within ports as part of a standard management repertoire and suggests a new classification scheme for mapping vulnerability within ports and across supply networks. The paper concludes that there is a need to examine the goodness-of-fit of these security initiatives against business efficiency and competitiveness, and to consider the training needs for crisis management capabilities that will allow private and public sector groups involved in global trade to effectively mitigate the threat of maritime terrorism and loss of competitiveness.     

一种能力外包且费用时变批量问题的启发式算法

当企业自身能力不能满足需求时考虑外包,可以有效提高企业的竞争力。一种带能力外包的多产品动态经济批量问题得以提出,并设定外包能力使用价格较高且费用时变。建立混合整数规划模型,通过约束松弛与模型分解,设计出一个基于拉格朗日松弛理论的启发式算法进行模型求解。大量随机实验表明,无论解的质量还是求解时间都表现较好。     

考虑空箱调运的集装箱海运收益管理能力分配优化模型

文章基于收益管理的思想对面临不确定需求的海运集装箱能力分配问题进行了定量研究。首先描述了集装箱海运收益管理问题与航空客运收益管理的差异,接着建立了考虑和不考虑空箱调运的海运集装箱能力分配随机规划模型,并应用稳健优化方法对模型进行求解,最后通过数值仿真,说明了模型和求解方法对于海运集装箱运输企业的收益管理问题具有重要的应用价值。