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

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

Container Scheduling: Complexity and Algorithms

We consider the transport of containers through a fleet of ships. Each ship has a capacity constraint limiting the total number of containers it can carry and each ship visits a given set of ports following a predetermined route. Each container has a release date at its origination port, and a due date at its destination port. A container has a size 1 or size 2; size 1 represents a 1 TEU (20‐foot equivalent unit) and size 2 represents 2 TEUs. The delivery time of a container is defined as the time when the ship that carries the container arrives at its destination port. We consider the problem of minimizing the maximum tardiness over all containers. We consider three scenarios with regard to the routes of the ships, namely, the ships having (i) identical, (ii) nested, and (iii) arbitrary routes. For each scenario, we consider different settings for origination ports, release dates, sizes of containers, and number of ports; we determine the computational complexity of various cases. We also provide a simple heuristic for some cases, with its worst case analysis. Finally, we discuss the relationship of our problems with other scheduling problems that are known to be open.     

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.     

集装箱枢纽港主辅码头间靠泊决策的协同优化

近年来集装箱枢纽港码头拥挤问题日益突出,船舶等泊时间的延长导致船公司经营成本增加,尤其对于经营支线运输的船公司而言更是如此.鉴于此,船公司在拥挤的集装箱枢纽港码头附近设置趸船或驳船作为辅助码头来停泊箱量较小的船舶,通过建立缓冲区以减少等泊时间及降低停泊费用.本文从集装箱支线运输公司经营人的角度,首次提出了集装箱枢纽港主辅码头间的靠泊决策的协同问题,基于泊位调度理论建立了靠泊决策的协同优化模型,并用改进的遗传算法求解.仿真实验定量分析并证实了设置浮动码头对集装箱支线运输公司减少等泊时间及降低成本的有效性.     

考虑长期运力合同的班轮收益管理运输路径优化模型

基于收益管理的方法,文章对随机需求环境下班轮运力分配和路径优化问题进行了定量研究。首先针对海运收益管理的特征,建立了考虑长期运力合同、空箱调运的轮运力分配和路径选择随机规划模型,然后应用稳健优化方法对此模型进行求解。最后,通过数值仿真得到了优化的舱位分配方案,比较发现稳健优化模型取得了较确定性规划模型更好的收益,显示了模型和方法对于集装箱海运企业的收益管理问题具有应用价值。     

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%.     

Vendor managed inventory in tramp shipping

This paper introduces a new problem to the OR community that combines traditional tramp shipping with a vendor managed inventory (VMI) service. Such a service may replace the more traditional contract of affreightment (COA) which for decades has been the standard agreement between a tramp shipping company and a charterer. We present a mathematical formulation describing the routing and scheduling problem faced by a tramp shipping company that offers a VMI service to its customers. The problem is formulated as an arc-flow model, and is then reformulated as a path-flow model which is solved using a hybrid approach that combines branch-and-price with a priori path-generation. To solve larger, and more realistic, instances we present a heuristic path-generation algorithm. Computational experiments show that the heuristic approach is much faster than the exact method, with insignificant reductions in solution quality. Further, we investigate the economic impact of introducing a VMI service, by comparing the results obtained with the new model with results obtained by solving the traditional routing and scheduling problem faced by tramp shipping companies using COA. The computational results show that it is possible to substantially increase supply chain profit and efficiency by replacing the traditional COAs with VMI services.     

基于收益管理的海运集装箱舱位分配与路径选择优化模型

文章应用收益管理的方法对不确定环境下海运集装箱的舱位分配问题进行了定量研究.首先针对海运收益管理的应用特征,建立了考虑空箱调运和路径选择的集装箱多航段能力分配模型,然后考虑需求的不确定性,应用稳健优化方法对此模型进行求解.最后,通过数值仿真得到了优化的舱位分配方案,比较发现稳健优化模型取得了较确定性规划模型更好的收益.显示了模型和方法对于集装箱海运企业的收益管理问题具有应用价值.     

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.     

竞争环境下基于服务约束的轴-辐式海运网络优化研究

针对同一海运市场中不同的海运企业——领导者与跟随者在设计多分配的轴-辐式海运网络时引起的竞争问题,突破已往枢纽港口集合是给定的假设,将航线连接设计扩展为可存在多条,引入基于服务约束（服务质量\价格\时间）的吸引力模型来定量表示托运人的选择行为,建立了竞争环境下基于服务约束的轴-辐式海运网络优化问题的数学模型,利用NCP函数、凝聚函数和增广Lagrange乘子罚函数法对这一问题进行求解。算例仿真结果显示：（1）跟随者在托运人考虑单位服务价格时,即使不存在规模经济效应,跟随者也可通过建立合适的枢纽港口来获取一定的市场机会;（2）跟随者在存在较大规模经济效应时其利润最可观,因采用比例模型,在不存在规模经济效应下跟随者在领导者决定设计不同数量的枢纽港口时其利润不会统一收敛于某一定值;（3）跟随者在领导者仅设计1个枢纽港口时可通过建立大量的枢纽港口来争夺丰厚的利润,但对于港口集合 N={1,2,…,12} 的海运市场,领导者只需设计2个以上枢纽港口时跟随者的利润空间便会受到较大挤压。     

考虑货主选择惯性的班轮运输系统优化模型

基于需求季节波动背景,在考虑货主选择惯性的条件下,以班轮公司收益最大为目标,构建远洋集装箱运输系统优化模型,优化航线网路结构、航线配船,基于需求波动与货主选择惯性特征优化航线网络的调整方案与舱位配置.基于遗传算法提出一种遗传线性规划混合算法.计算结果表明,优化模型能够在考虑运输服务稳定性的要求下,优化班轮运输系统,在提高班轮公司收益的同时,提升货主的服务体验.最后通过分析计算结果,证明了模型的实际意义与可靠性.     

Maximizing the rate of return on the capital employed in shipping capacity renewal

Decisions regarding investments in capacity expansion/renewal require taking into account both the operating fitness and the financial performance of the investment. While several operating requirements have been considered in the operations research literature, the corresponding financial aspects have not received as much attention. We introduce a model for the renewal of shipping capacity which maximizes the Average Internal Rate of Return (AIRR). Maximizing the AIRR sets stricter return requirements on money expenditures than classic profit maximization models and may describe more closely shipping investors׳ preferences. The resulting nonlinear model is linearized to ease computation. Based on data from a shipping company we compare a profit maximization model with an AIRR maximization model. Results show that while maximizing profits results in aggressive expansions of the fleet, maximizing the return provides more balanced renewal strategies which may be preferable to most shipping investors.     

Multi-item single-source ordering with detailed consideration of transportation capacities

We consider multi-item single-source ordering with detailed consideration of transportation capacities. Such problems are characteristic for companies which operate direct links as part of their supply chain to transport loads with heterogeneous physical dimensions and fluctuating demands. Given knowledge on transportation demands, companies can eliminate future transports by shifting the load to fill the inflexible capacity of prior transports. While reducing transportation costs, doing so will ceteris paribus imply inventory. The problem is to coordinate orders across multiple items such that transport costs are minimized at minimal increase in inventory. The approach is distinct from prior works in that it considers detailed loading restrictions. We therefore interpret the problem as a multi-period version of the container loading problem. A wall building approach is used and incorporated into a heuristic rolling horizon procedure. We test the proposed procedure on some random problems which resemble a real inbound case from the automotive industry. As compared to period-by-period planning and two benchmarks with aggregated capacity models from the literature and practice, cost savings are possible under a wide range of operating conditions and mostly independent of the shipping volume. The largest potential exists for mid- to long-distance transports. There is a relevant potential to improve short-distance transports as well, however, only if inventory cost rates are moderate.     

集装箱港口多期投资优化决策模型研究

以集装箱港口综合成本为主要优化目标,在分析运营效率、生态承载力、港口损益等约束下,借助动态规划建立集装箱港口多期投资优化决策理论模型,解决现有的集装箱港口投资优化决策理论忽视港口运营效率、生态承载力等可持续发展能力的弊端,从而防止港口资源的巨大浪费和对生态环境的破坏,具有现实指导意义.     

Eco-friendly container transshipment route scheduling problem with repacking operations

Currently, a huge amount of cargo is transported via containers by liner shipping companies. Under stochastic demand, repacking operations and carbon reduction, which may lead to an increase in effectiveness and environmental improvement, have been rarely considered in previous literature. In this paper, we investigate a container transshipment route scheduling problem with repacking operations under stochastic demand and environmental protection. The problem is a combinatorial optimization problem. Lacking historical data, a chance-constrained programming model is proposed to minimize the total operating and environment-related costs. We choose two distribution-free approaches, i.e., approximation based in Markov’s Inequality and Mixed Integer Second-Order Conic Program to approximate the chance constraints. As the loses induced by unfulfilled demand are not taken into account in the above model, a scenario-based model is developed considering the loses. Risk-neutral model may provide solutions that perform poorly while considering uncertainty. To incorporate decision makers’ perspectives, therefore, we also propose a risk-averse model adopting a risk aversion measure called Conditional Value-at-Risk to meet different preferences. Finally, we conduct computational experiments based on real data to compare the performances of the modeling methods and illustrate the impacts by testing different risk levels and confidence levels.

     

基于超效率CCR-DEA的中国港口上市公司成本效率评价研究

本文在选取固定资产净值、员工人数等为投入指标,每股收益等产出指标构建港口上市公司成本效率评价指标体系的基础上,建立了基于超效率CCR-DEA(SUP-CCR-DEA)的港口上市公司成本效率评价模型.本研究特点一是构建了一套包含固定资产净值等投入、每股收益等产出的中国港口上市公司成本效率评价指标体系,解决了现有文献缺乏对港口上市公司的成本效率评价指标体系不足,也为合理评价成本效率奠定基础.特点二是借助超效率CCR-DEA思想,对有效率(效率值1)的港口上市公司进一步评价,解决了以往在港口上市公司成本效率的评价研究中无法对有效率的单元进一步排序的弊端.特点三是采用国内13家港口上市公司2004年和2005年数据进行了实证研究,并计算得出我国港口上市企业的连续2年成本效率评价结果与相对排序,对比分析了港口上市公司的成本效率的随时间变化趋势,得出了如下结论:1)2004年和2005年的国内港口上市公司成本效率高的企业都约占整个样本数量的50%,而G上港在效率值1的港口中则位居首位.2)2004年和2005年的国内港口上市公司成本效率整体上比较稳定,但G盐田港大幅上升以及北海港和G天津港则下跌较深,其成本效率变化远高于其他港口上市公司.     

考虑双均衡的港航供应链可持续投资研究

针对港航联合可持续投资问题,构建了静态Stackelberg均衡与动态演化博弈双均衡联动模型,在政府碳排放规制和碳交易市场双重因素下,研究考虑可持续发展的港航供应链减排技术投资策略。研究表明：随着投资成本分担比例的增大,在静态Stackelberg均衡下,航运公司投资意愿逐渐降低,而港口却始终偏好自身投资,此时系统均衡策略由航运企业投资的囚徒困境转变为港口投资的帕累托最优;在动态演化博弈下,稳定结果是航运企业投资转变为港口投资。并从政府-市场-企业三方视角发现：(1)企业长期低碳投资策略与政府碳排放限额无关;(2)企业需要关注碳交易市场价格、托运人对可持续水平敏感度以及价格敏感度,这些参数值增高会降低碳排放量;(3)随着航运企业分担比例的增大,碳排放量呈现上升趋势。最后结合静态与动态投资策略,为政府、港口和航运企业可持续投资提供建议。     

航运供应链上的品牌价值、公平关切与契约协调

航运供应链上的船公司提高企业品牌价值需要付出大量的投资成本,因此将会更加关注供应链上利润分配的公平。本文以单个船公司和单个货代公司构成的两级航运供应链为研究对象,运用博弈论分析船公司的公平关切行为和品牌投入意愿对航运供应链上各方利润的影响,探讨决策者非理性条件下航运供应链的合作模式和协调机制。研究表明：1）船公司的公平关切提高了其在供应链上利润分配占比,但降低了整个航运供应链的利润和效率;2）随着品牌投入意愿的提高,船公司的公平关切对航运供应链上各方决策的负作用就越明显;3）"收益共享成本共担"式契约能够消除公平关切的负作用,达到航运供应链纵向联盟的最优收益和整体效率。