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.     

MIP-based approaches for the container loading problem with multi-drop constraints

In this paper, we present approaches based on a mixed integer linear programming model (MIP) for the problem of packing rectangular boxes into a container or truck, considering multi-drop constraints. We assume that the delivery route of the container is already known in advance and that the volume of the cargo is less than or equal to the container volume. Considering the sequence that the boxes should be unloaded, the aim is to avoid additional handling when each drop-off point of the route is reached, as well as ensuring that the boxes do not overlap each other and the cargo loading is stable. Computational tests with the proposed model and the approaches were performed with randomly generated instances and instances from the literature using an optimization solver embedded into a modeling language. The results validate the model and the approaches, but indicate that they are able to handle only problems of a moderate size. However, the model and the approaches can be useful to motivate future research to solve larger problems, as well as to solve more general problems considering integrated vehicle routing and container loading problems.     

Three-dimensional packing of items with limited load bearing strength

A new heuristic approach is put forward for tackling container loading problems where the cargo involved has varying degrees of load bearing strength. In such cases the placement rules must ensure that the weight resting on an item remains below the maximum it can withstand without suffering crushing damage. The construction heuristic proposed is embedded in a search algorithm which seeks to optimise the parameter settings of the procedure. Limiting the time required to produce a good solution and the amount of technical expertise needed by the user are key considerations. The approach is evaluated in a series of tests against benchmarks from the literature. The results demonstrate that it outperforms other approaches which have been suggested for this type of problem and that it also performs well on problems where load bearing strength is not an issue. Potentially useful extensions of the work are discussed.     

Automating the planning of container loading for Atlas Copco: Coping with real-life stacking and stability constraints

The Atlas Copco^☆ distribution center in Allen, TX, supplies spare parts and consumables to mining and construction companies across the world. For some customers, packages are shipped in sea containers. Planning how to load the containers is difficult due to several factors: heterogeneity of the packages with respect to size, weight, stackability, positioning and orientation; the set of packages differs vastly between shipments; it is crucial to avoid cargo damage. Load plan quality is ultimately judged by shipping operators.This container loading problem is thus rich with respect to practical considerations. These are posed by the operators and include cargo and container stability as well as stacking and positioning constraints. To avoid cargo damage, the stacking restrictions are modeled in detail. For solving the problem, we developed a two-level metaheuristic approach and implemented it in a decision support system. The upper level is a genetic algorithm which tunes the objective function for a lower level greedy-type constructive placement heuristic, to optimize the quality of the load plan obtained.The decision support system shows load plans on the forklift laptops and has been used for over two years. Management has recognized benefits including reduction of labour usage, lead time, and cargo damage risk.     

三维多箱异构货物装载优化及其可视化

针对七种现实约束的集装箱三维多箱异构货物装载优化问题,提出了一种基于 “块”和“空间”的启发式搜索算法。算法采用树搜索策略,根据可用空间,对每一次搜索的货物块进行评估,得到最佳的货物块,直到无可用空间或无可装载的货物为止。基于开放式标准测试数据的计算结果表明,该算法在时间效率和体积利用率上均优于已有的同类研究。并基于Net平台开发了一款3D装箱布局优化可视化软件,已在相关物流企业中得到推广应用,验证了算法的实用性。     

MIP models for production lot sizing problems with distribution costs and cargo arrangement

This study presents mixed integer programming (MIP) models for production lot sizing problems with distribution costs using unit load devices such as pallets and containers. Problems that integrate production lot sizing decisions and loading of the products in vehicles (bins) are also modelled, in which constraints such as weight limits, volume restrictions or the value of the cargo loaded in the bins are considered. In general, these problems involve a trade-off between production, inventory and distribution costs. Lot sizing decisions should take into account production capacity and product demand constraints. Distribution decisions are related to the loading and transport of products in unit load devices. The MIP models are solved by the branch-and-cut method of an optimization package and the results show that these approaches have the potential to address different practical situations.     

Multilevel,threshold-based policies for cargo container security screening systems

To mitigate the threat of nuclear terrorism within the US using nuclear material that has been smuggled into the country, the US Bureau of Customs and Border Protection has expanded its cargo container detection capabilities at ports of entry into the US This paper formulates a risk-based screening framework for determining how to define a primary screening alarm for screening cargo containers given a set of dependent primary screening devices. To do so, this paper proposes two linear programming models for screening cargo containers for nuclear material at port security stations using knapsack problem models. All cargo containers undergo primary screening, where they are screened by a given number of security devices. The objective is to identifying the primary security outcomes that warrant a system alarm for each container risk group such that the system detection probability is maximized, subject to a screening budget. The base model is compared to a second model that explicitly requires a threshold-based policy. The structural properties of the two models are compared, which indicates that all risk groups except at most one have deterministic screening policies. A computational example suggests that the detection probability is not significantly altered by enforcing a threshold policy.     

Solving container loading problems by block arrangement

In order to solve heterogeneous single and multiple container loading problems, an algorithm is presented that builds homogeneous blocks of identically orientated items. First a greedy heuristic is presented that generates the desired block arrangements. Second the solutions provided by the greedy heuristic are improved by a tree search. Additional aspects such as load stability and weight distribution within the container are also taken into account. The test cases of Bischoff and Ratcliff are used for benchmarking purposes.     

带时间窗的三维装载物流配送优化方法研究

针对城市物流配送优化研究在客户服务时间窗和货物装载方式合理结合方面存在的不足,考虑物流配送车厢货物装载方式与客户访问序列相关的特征对车厢空间进行合理的区域划分。首先,构建了包含配送中心的固定成本、配送车辆的运输成本、维修成本、租赁成本和违反时间窗惩罚成本的物流运营成本最小化和配送车辆空间利用率最大化的双目标优化模型;然后,提出一种结合遗传算法(GA)全局搜索能力和禁忌搜索算法(TS)局部搜索能力的GA-TS混合算法求解模型;最后,结合重庆市某配送中心的三维装载物流配送实例数据进行了优化计算,实验结果给出了带时间窗的三维装载物流配送路径优化方案,并进行了不同车厢空间分区模式下平均装载率、物流运营成本和车辆使用数的比较分析。研究表明,当客户需求货物种类数与车辆的空间区域划分数相等且按货物类型进行区域划分时,物流运营成本最小,配送车辆使用数最少和车辆平均装载率最高。     

基于灰色预测模型的广州港货运发展研究

新冠肺炎疫情对广州港的货运发展产生了一定程度的影响,但目前仍然缺少相关的定量研究.基于灰色预测模型,利用港口货物吞吐量、外贸货物吞吐量、集装箱吞吐量三个货运指标,在新冠肺炎疫情没发生的这一假设下,推测2020年1-8月广州港的各货运发展指标值.基于预测值与实际值的比较,定量研究广州港的货运发展受新冠肺炎的影响值,反映新...     

时间敏感型货物两阶段集装箱舱位分配问题研究

本文旨在探索如何对时间敏感型货物的集装箱舱位分配和动态定价问题进行研究。考虑到时间敏感型货物对配送时间的要求,本文提出一种新的定价机制,即在该类货物的运费制定时,考虑时间敏感型货物的配送时效及港口拥挤对其存在的影响,建立运价和配送时间之间的关系。另外,以船舶公司总运费收益最大化为目标,构建两阶段随机整数规划模型,运用机会约束规划方法对模型进行求解。最后,通过算例研究,验证了模型及算法的有效性。结果表明,本文针对时间敏感型货物所提出的定价机制能够显著提高船公司收益。     

Port space allocation with a time dimension

In the Port of Singapore, as in many other ports, space has to be allocated in yards for inbound and transit cargo. Requests for container space occur at different times during the planning period, and are made for different quantities and sizes of containers. In this paper, we study space allocation under these conditions. We reduce the problem to a two-dimensional packing problem with a time dimension. Since the problem is NP-hard, we develop heuristic algorithms, using tabu search, simulated annealing, a genetic algorithm and ‘squeaky wheel’ optimization, as solution approaches. Extensive computational experiments compare the algorithms, which are shown to be effective for the problem.     

考虑运营稳定性的内支线班轮航线网络规划模型

货主选择承运航线的影响因素,既包括挂靠港口的计划到港时间与单箱运价,还包括反映班轮运营稳定性的甩箱率与准班率。对此,文章将挂靠港口的航行与在港时间不确定引入研究,并对挂靠港口间的不确定性建立联系,基于航次仿真来计算各挂靠港的到港时间分布、船舶的航次最大载箱量分布。以班轮航线的甩箱率与准班率限制、内支线最大船型与最长往返时间为约束,在优化内支线航线网络结构的同时,计算航线适配船型、班期密度及挂靠港计划到港时间。针对所构建的带不确定参数的NP难问题,文章设计了基于模拟仿真的智能优化算法,通过方案仿真技术来处理输入模型的众分布函数,借助智能优化原理从大范围解空间内寻找满意方案。文末对船舶航次仿真与网络规划模型的有效性进行了验证,算例分析表明:内支线班轮航线网络的货主选择比例达64%,且不论货主更偏好运输时间或价格,航线方案皆能贴近货主偏好。     

A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach

Increasing fuel costs, post-911 security concerns, and economic globalization provide a strong incentive for container carriers to use available container space more efficiently, thereby minimizing the number of container trips and reducing socio-economic vulnerability. A heuristic algorithm based on a tertiary tree model is proposed to handle the container loading problem (CLP) with weakly heterogeneous boxes. A dynamic space decomposition method based on the tertiary tree structure is developed to partition the remaining container space after a block of homogeneous rectangular boxes is loaded into a container. This decomposition approach, together with an optimal-fitting sequencing and an inner-right-corner-occupying placement rule, permits a holistic loading strategy to pack a container. Comparative studies with existing algorithms and an illustrative example demonstrate the efficiency of this algorithm.     

A revenue management model for products with two capacity dimensions

Many perishable products and services have multiple capacity attributes. Shipping capacity of container liners, for example, is measured by both volume and weight. Containers with different size consume various capacities in the two dimensions. Restaurant revenue management aims to maximize the revenue per available seat-hour that captures both the number of dining tables and service manpower. Similar issues arise in the air cargo, trucking and health care industries.     

港口货物总吞吐量概率分布数学模型的建立与分析

为了研究港口货物总吞吐量随时间变化的规律,提出了港口货物总吞吐量的概率分布模型.由于货物总吞吐量的变化与到达港口的货运船数目以及装卸设备的工作效率有密切关系,构造一个关于到达港口的货运船数目以及装卸设备的工作能力组合而成的复合变量,货物总吞吐量是这些复合变量所表示的货物装卸量的和.应用wald方程,得到货物总吞吐量的概率分布.货物总吞吐量服从何种概率分布依赖于到达港口的货运船数目所服从的概率分布.克服了传统预测模型难于对未来货物吞吐量大小变化的可能性作出量化判断的缺点.同时,根据建立的数学模型,分析了影响货物总吞吐量变化的因素,以山东地区某港口的货物吞吐量变化规律进行了案例分析.实际结果与理论分析相符.     

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.     

A Stackelberg game model for resource allocation in cargo container security

This paper presents a game theoretic model that analyzes resource allocation strategies against an adaptive adversary to secure cargo container transportation. The defender allocates security resources that could interdict an unauthorized weapon insertion inside a container. The attacker observes the defender’s security strategy and chooses a site to insert the weapon. The attacker’s goal is to maximize the probability that the weapon reaches its target. The basic model includes a single container route. The results in the basic model suggest that in equilibrium the defender should maintain an equal level of physical security at each site on the cargo container’s route. Furthermore, the equilibrium levels of resources to interdict the weapon overseas increase as a function of the attacker’s capability to detonate the weapon remotely at a domestic seaport. Investment in domestic seaport security is highly sensitive to the attacker’s remote detonation capability as well. The general model that includes multiple container routes suggests that there is a trade-off between the security of foreign seaports and the physical security of sites including container transfer facilities, container yards, warehouses and truck rest areas. The defender has the flexibility to shift resources between non-intrusive inspections at foreign seaports and physical security of other sites on the container route. The equilibrium is also sensitive to the cost effectiveness of security investments.     

How Useful are Queue Models in Port Investment Decisions for Container Berths?

The operational characteristics of U.K. container terminals and shipping services are reviewed in relation to their effect on the use of queue models in decisions on investment in berth construction and cargo handling equipment. Some simple queue models for a new container service are evaluated, showing the importance of interpreting the choice of parameters and results of these models in relation to the particular costs and requirements of container operations and how this ranks investment options differently to the traditional application of queue models to port investment. This ranking is compared with the actual decision made and the effects of some other factors not included in the models noted.     

Optimization of container inspection strategy via a genetic algorithm

It is estimated that 90% of the world’s freight is moved as containerized cargo, with over 125 million TEUs (Twenty foot Equivalent Units) of container being shipped by 2010. To inspect this volume of cargo for explosives, drugs or other contraband is a daunting challenge. This paper presents an optimization technique for developing an inspection strategy that will provide a specified detection rate for containers containing contraband at a minimum cost. Nested genetic algorithms are employed to optimize the topology of an inspection strategy decision tree, the placement of sensors on the tree and the sensor thresholds which partition suspicious containers (containers believed to contain contraband) from innocuous containers (containers which are believed to be free of contraband). The results of this optimization technique are compared to previously published techniques.