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

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

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.     

Air intermodal freight transportation: The freight forwarder service problem

Despite being one of the most relevant figures in international multimodal transportation, freight forwarding companies optimization problems did not receive much attention from the research community. In this work we try to fill this gap by presenting the general features of air transportation from the freight forwarder’s perspective and we introduce the air transportation freight forwarder service problem (ATFFSP). A MILP formulation of the problem is proposed and tested on real-life data coming from an Italian freight forwarding company. We study the performance of the model in terms of optimality gap and time needed to reach the optimal solution. Furthermore we compare the solutions found with the ones provided by the company in order to evaluate the effectiveness of the model and its ability to find good and practical solutions. Finally, we study the possibility of opening a new warehouse facility to better manage services and we analyze the corresponding potential benefits.     

The supplier selection problem with quantity discounts and truckload shipping

To minimize procurement expenditures both purchasing and transportation costs need to be considered. We study a procurement setting in which a company needs to purchase a number of products from a set of suppliers to satisfy customer demand. The suppliers offer total quantity discounts and transportation costs are based on truckload shipping rates. The goal is to select a set of suppliers so as to satisfy product demand at minimal total costs. The resulting optimization problem is strongly NP-hard. We develop integer programming based heuristics to solve the problem. Extensive computational experiments demonstrate the efficacy of the proposed heuristics and provide insight into the impact of instance characteristics on effective procurement strategies.     

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

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

电动汽车物流配送系统的换电站选址与路径优化问题研究

在能源、环境形势日益严重的今天,电动汽车因其清洁、节能的显著优势,已经逐步成为物流配送公司重要的新能源交通工具,优化物流配送网络成为电动汽车作为物流工具普及的一个重要问题。本文提出了电动汽车物流配送系统的换电站选址与配送路径优化问题,建立了整数规划模型,并设计禁忌搜索-改进Clarke-Wright 节省的两阶段启发式算法来求解该模型,提出了两种不同的禁忌准则,并且通过算例对这两种准则进行了比较。为了证明算法的有效性,还将该算法的结果同CPLEX的计算结果进行了比较,结果表明该算法更加有效和可靠。最后,对车辆的装载容量、电池续航里程和单位建站成本做敏感性分析,发现总成本随着装载容量的增加而显著降低,电池续航里程的提升有助于降低建站成本并降低目标函数值,而单位建站成本的增加可能减少建站个数,增加运输成本,但由于续航里程的限制,建站个数也可能保持不变。     

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

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

装卸一体化的车辆路径问题及基于插入法的新禁忌算法

在日益激烈的市场竞争中,如何在降低成本的同时,让各个顾客尽快收到货物成了现代交通运输物流中一个越来越重要的考虑因素。基于某快递公司的运输实例,本文提出了装卸一体化的车辆路径问题模型,最终优化目标是最小化车辆运输时间和货物到各个顾客的时间的加权和,并给出了一种基于插入法的新禁忌算法,实验结果表明新禁忌算法在显著提高传统禁忌算法计算时间的同时,还能得到理想的成本,并且对节约快递公司的运输成本方面有显著成效。     

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.     

随机需求下基于“自营+外包”模式的配送中心选址-配送问题研究

针对顾客需求量不确定情况下末端配送中心选址及提前备货问题，提出了基于“自营+外包”配送模式的配送中心选址-配送问题。以自营配送中心的固定运行成本、提前备货成本和各种场景下的自营配送成本、外包配送成本以及缺货损失成本的期望值之和最小化为目标，建立了两阶段连续型随机规划模型。第一阶段确定自营配送中心的选址位置和各个配送中心的提前备货量；第二阶段确定各种场景下的自营配送货运量、外包配送货运量和客户点的缺货量等，使总成本期望值达到最小。基于Monte Carlo抽样理论设计了求解模型的样本均值近似方法；以及求解大规模问题L-shaped分解算法。通过模拟算例验证了两阶段随机规划模型的优越性和样本均值近似方法的有效性；并对自营配送中心固定运行成本、单位商品的自营配送成本和外包配送成本等进行灵敏度分析，得到了不同参数对应的最优配送策略，结果表明，正常情况下“自营+外包”配送模式是企业的最佳选择。本文同时将配送中心选址和提前备货量作为随机规划模型的第一阶段决策变量，可以帮助企业降低物流成本、提高顾客的满意度。     

Optimal Purchase and Transportation Cost Lot Sizing for a Single Item

A review of the literature indicates that the traditional approach for evaluating quantity discount offerings for purchased items has not adequately considered the effect that transportation costs may have on the optimal order quantity; despite the general fact that purchased materials must bear transportation charges. The transportation cost structure for less-than-truckload (LTL) shipments reflects sizable reductions in freight rates when the shipment size exceeds one of the nominal rate breakpoints. However, the shipper must also be aware of the opportunity to reduce total freight costs by artificially inflating the actual shipping weight to the next rate breakpoint, in order that a lower marginal tariff is achieved for the entire shipment. Such over-declared shipments result in an effective freight rate schedule that is characterized by constant fixed charge segments in addition to the nominal marginal rates. Over-declared shipments are economical when the shipment volume is less than the rate breakpoint, but greater than a cost indifference point between the two adjacent marginal rates. This paper presents a simple analytical procedure for finding the order quantity that minimizes total purchase costs which reflect both transportation economies and quantity discounts. After first solving for the series of indifference points that apply to a particular freight rate schedule, a total purchase cost expression is presented that properly accounts for the actual transportation cost structure. The optimal purchase order quantity will be one of the four following possibilities: (1) the valid economic order quantity (EOQ), QC; (2) a purchase price breakpoint in excess of QC; (3) a transportation rate breakpoint in excess of QC; and (4) a modified EOQ which provides an over-declared shipment in excess of QC. Finally, an algorithm which systematically explores these four possibilities is presented and illustrated with a numerical example.     

Risk control in maritime shipping investments

In this paper we extend the state-of-the-art stochastic programming models for the Maritime Fleet Renewal Problem (MFRP) to explicitly limit the risk of insolvency due to negative cash flows when making maritime shipping investments. This is achieved by modeling the payment of ships in a number of periodical installments rather than in a lump sum paid upfront, representing more closely the actual cash flows for a shipping company. Based on this, we propose two alternative risk control measures, where the first imposes that the cash flow in each time period is always higher than a desired threshold, while the second limits the Conditional Value-at-Risk. We test the two models on realistic test instances based on data from a shipping company. The computational study demonstrates how the two models can be used to assess the trade-offs between risk of insolvency and expected profits in the MFRP.     

A Two-Phase Exact Algorithm for MAX-SAT and Weighted MAX-SAT Problems

We describe a two-phase algorithm for MAX-SAT and weighted MAX-SAT problems. In the first phase, we use the GSAT heuristic to find a good solution to the problem. In the second phase, we use an enumeration procedure based on the Davis-Putnam-Loveland algorithm, to find a provably optimal solution. The first heuristic stage improves the performance of the algorithm by obtaining an upper bound on the minimum number of unsatisfied clauses that can be used in pruning branches of the search tree.We compare our algorithm with an integer programming branch-and-cut algorithm. Our implementation of the two-phase algorithm is faster than the integer programming approach on many problems. However, the integer programming approach is more effective than the two-phase algorithm on some classes of problems, including MAX-2-SAT problems.     

A MODEL-BASED DECISION SUPPORT SYSTEM FOR SCHEDULING LUMBER DRYING OPERATIONS

Raw lumber must be dried to a specified level of moisture content before it can be used to make furniture. This paper deals with a model-based decision support system (DSS) for a local furniture manufacturing company to assist its management in scheduling lumber drying operations. In addition to buying ready-to-use dried lumber from vendors at a premium, the company processes raw lumber in house using two production process that require various lengths of processing time in predryers and dry-kilns. Given the demand for various types of dried lumber over a specified planning horizon, the processing times and costs for each production process, technological restrictions, and management policies, the problem of interest is to satisfy the demand at a minimum cost. The DSS incorporates the mathematical formulation of this problem, is user friendly, maintains model and data independence, and generates the necessary reports, including loading and unloading schedules for the equipment.     

Maximum latency scheduling problem on two-person cooperative games

This paper studies a two-person cooperative game in which a set of jobs has to be processed jointly by two people. Each of them has a single machine and his processing cost is defined as the minimum value of the maximum latency of his negotiably assigned jobs. The objective is to maximize the multiplication of their rational positive cooperative profits. In the case where all jobs have the same processing time, if they have a common due date, the problem is polynomial-time solvable; if due dates can be different, there exits an optimal schedule in which the jobs assigned to each person are scheduled in Earlier Due Date first (EDD) order and a polynomial-time dynamic programming is further proposed. In the case where processing times can be different, the NP-completeness of this problem is proved, and a pseudo-polynomial-time dynamic programming algorithm is developed.     

模糊环境下考虑缺货和延期支付的Stackelberg均衡策略

在具有价格弹性需求的两层供应链系统中,考虑到价格弹性指数的模糊性和供应链延期支付策略,建立了含缺货的制造商-零售商协调模型.运用符号距离反模糊化方法将其转化为确定模型.基于遗传算法,设计了其求解方法,获得了制造商最优信用期和零售商最优零售价.数值结果表明:模糊环境下的延期支付策略降低了产品的市场零售价,同时增加了供应链中各成员的利润,因此实现了供应链协调.进一步分析显示当模糊价格弹性指数的上(下)界变化反映出的不确定性减弱时,制造商提供更长的信用期,且制造商和零售商的利润均增加(减少).     

Integer programming approach to static monopolies in graphs

A subset M of vertices of a graph is called a static monopoly, if any vertex v outside M has at least \(\lceil \tfrac{1 }{2}\deg (v)\rceil \) neighbors in M. The minimum static monopoly problem has been extensively studied in graph theoretical context. We study this problem from an integer programming point of view for the first time and give a linear formulation for it. We study the facial structure of the corresponding polytope, classify facet defining inequalities of the integer programming formulation and introduce some families of valid inequalities. We show that in the presence of a vertex cut or an edge cut in the graph, the problem can be solved more efficiently by adding some strong valid inequalities. An algorithm is given that solves the minimum monopoly problem in trees and cactus graphs in linear time. We test our methods by performing several experiments on randomly generated graphs. A software package is introduced that solves the minimum monopoly problem using open source integer linear programming solvers.     

A mixed integer programming and heuristic algorithm for a warehouses location problem

A warehouses location problem is treated using a mixed integer programming and a heuristic algorithm. A simplification of freight rates schedules, based upon shipments consolidation and a linear regression of rates vs distances was made. Warehousing costs were divided according to fixed and variable and related to the throughput of the warehouses. Consideration was given in the analysis to the choice between owning and leasing each warehouse. In the case studied, the analysis demonstrated that a possible saving of approximately 22 per cent in annual distribution costs could be realized under the optimized warehouse location network.     

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

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

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

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