Scheduling Truck Arrivals at an Air Cargo Terminal

We consider the scheduling of truck arrivals at an air cargo terminal. By coordinating arrivals of cargo delivery trucks with outbound flight departure schedules, some of the shipments can be transferred directly to the departing flights, while others will be stored at the terminal's storage facility and incur extra handling and storage costs. The objective is to obtain a feasible schedule so as to minimize the total cost of operations. We formulate the problem as a time‐indexed integer program and show that, even with limited number of unloading docks at the terminal, the problem is non‐trivial (NP‐hard in the strong sense). Our solution method includes an exact solution procedure to determine an optimal unloading sequence for the shipments carried by each truck, together with a Lagrangian relaxation‐based heuristic for assigning trucks to truck docks and determining truck arrival times. We conducted computational experiments to test the performance of our solution method. Computational results show that our method can generate near‐optimal solutions efficiently. Our simulation results indicate that the scheduling approach proposed in this paper has the potential to generate significant cost savings over a first‐come, first‐served approach currently used at the air cargo terminal that we observed.     

Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil

This paper considers a truck scheduling problem in the context of solid waste collection in the City of Porto Alegre, Brazil. The problem consists of designing “good” daily truck schedules over a set of previously defined collection trips, on which the trucks collect solid waste in fixed routes and empty loads in one of several operational recycling facilities in the system. These facilities are managed by cooperatives whose members are poor and not part of the mainstream economy. The main objective is to minimize the total operating and fixed truck costs. We show that the problem can be modeled as a special case of the single-depot vehicle scheduling problem, which is polynomially solvable. However, due to the social benefits of the solid waste program, it is desirable to obtain balanced assignments of collection trips unloading their cargo at the recycling facilities. We prove that the truck scheduling problem considering balanced unloading is NP-hard. A heuristic approach, incorporating an auction algorithm and a dynamic penalty method, is designed to acquire a good solution. Finally, computational experiments are conducted on real data. The results show that the heuristic approach simultaneously reduces total costs and balances the number of trips assigned to each recycling facility.     

Storing Fresh Produce for Fast Retrieval in an Automated Compact Cross‐Dock System

We study temporary storage of fresh produce in a cross‐dock center. In order to minimize cooling cost, compact storage systems are used. A major disadvantage of these systems is that additional retrieval time is needed, caused by necessary reshuffles due to the improper storage sequence of unit loads. In practice therefore, a dedicated storage policy is used in which every storage lane in the system accommodates only one product. However, this policy does not use the planned arrival time information of the outbound trucks. To exploit this information, this study proposes a mathematical model for a shared storage policy that minimizes total retrieval time. The policy allows different products to share the same lane. In order to solve real‐sized problems, an effective and efficient heuristic is proposed, based on a greedy construction and an improvement part, which provides near optimal solutions. The gaps between the results of the heuristic and the lower bound are mostly less than 1%. The resulting shared storage policy is generally robust against disturbances in arrival or departure times. We compare our shared storage heuristic with dedicated storage to determine which policy performs best under which circumstances. For most practical cases, shared storage appears to outperform dedicated storage, with a shorter response time and better storage lane utilization.     

Strategic and operational decision-making in expanding supply chains for LNG as a fuel

The European Union aims for a 40% reduction in greenhouse gas emissions by 2030, compared to 1990 levels, and recognizes the opportunities of Liquefied Natural Gas (LNG) as an alternative fuel for transportation to reach this goal. The lack of a mature supply chain for LNG as a fuel results in a need to invest in new (satellite) terminals, bunker barges and tanker trucks. This network design problem can be defined as a Two-Echelon Capacitated Location Routing Problem with Split Deliveries (2E-CLRPSP). An important feature of this problem is that direct deliveries are allowed from terminals, which makes the problem much harder to solve than the existing location routing literature suggests. In this paper, we improve the performance of a hybrid exact algorithm and apply our algorithm to a real-world network design problem related to the expansion of the European supply chain for LNG as a fuel. We show that satellite terminals and bunker barges become an interesting option when demand for LNG grows and occurs further away from the import terminal. In those situations, the large investments associated with LNG satellites and bunker barges are offset by reductions in operational costs of the LNG tanker trucks.     

Shift scheduling for tank trucks

In this paper we deal with shift scheduling of tank trucks for a small oil company. Given are a set of tank trucks with different characteristics and a set of drivers with different skills. The objective is to assign a feasible driver to every shift of the tank trucks such that legal and safety restrictions are satisfied, the total working times of the drivers are within desired intervals, requested vacation of the drivers is respected and the trucks are assigned to more favored drivers. We propose a two-phase solution algorithm which is based on a mixed integer linear programming formulation and an improvement procedure. Computational results are reported showing that the algorithm is able to generate feasible schedules in a small amount of time.     

基于混合流水作业组织的集装箱码头装卸作业集成调度优化

集装箱码头集疏运资源调度的对象是由岸桥、集卡、场桥所构成的多阶段一体化的集装箱装、卸、运操作系统,将该系统的调度优化基于多阶段混合流水线调度问题建立混合整数规划模型,同时考虑集装箱码头现实作业中预定义顺序、避免岸桥交叉作业、以及取决于作业顺序的切换时间等现实约束,针对问题自身的特点设计了两阶段启发式算法,得出各阶段设备的指派结果及作业顺序。通过与基于现行调度规则的调度方案以及与目标函数理论下界值的对比实验,显示了所提出的集成调度模型及求解算法能够有效降低船舶在港时间并实现集卡资源的共享,为集装箱码头集疏运资源的集成调度提供了新的思路。     

A comparative study of formulations for a cross-dock door assignment problem

A cross docking facility is a type of warehouse in supply chain management that allows orders to be prepared with or without going through the phase of storing products in the warehouse and subsequently selecting them for delivery. The goods are unloaded from incoming trucks called origins on inbound doors of a cross-docking facility platform and, using a handling device inside the platform such as a forklift, immediately transferred to outbound doors to be loaded into outgoing trucks named destinations or delivery trucks for distribution to customers. Contrary to a traditional warehouse, goods are unloaded and loaded without placing them in temporary storage inside the cross-docking facility. The goal of the cross-docking assignment problem (CDAP) is to assign origins to inbound doors and destinations to outbound doors so that the total cost inside the cross-dock platform is minimized. To the best of our knowledge, there are only three mixed integer programming (MIP) formulations of the CDAP in the literature. We propose eight new MIP models and demonstrate the mathematical equivalence of all 11 models, together with rigorously proving some of their properties. In order to detect which of these 11 models is best, we conduct an extensive comparative analysis on benchmark instances from the literature, which discloses that the best model is one proposed in this paper for the first time.     

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.     

考虑实时预倒箱的出口箱堆场多场桥调度优化

在出口集装箱堆场的实际作业过程中，倒箱是制约场桥作业效率的瓶颈之一。为提高出口箱堆场的作业效能，减少船舶装船作业时间，采用实时预倒来降低倒箱的影响，研究出口箱堆场多场桥调度优化问题。考虑待提箱作业次序固定、场桥间保持安全距离及不可跨越的现实约束，兼顾内集卡的等待上限，侧重场桥作业过程中的实时预倒箱，构建了以带惩罚因子的内集卡总等待时间最少为目标的混合整数线性规划模型。基于问题自身的特点设计了混合和声模拟退火算法，得出了各场桥的行走路径与实时预倒箱方案。在算例实验中，通过与不考虑实时预倒箱的方案、FCFS方案以及下界进行对比，验证了考虑实时预倒箱的场桥调度模型及算法的有效性，为集装箱码头出口箱堆场的场桥调度提供参考。     

Distribution planning of bulk lubricants at BP Turkey

We address the distribution planning problem of bulk lubricants at BP Turkey. The problem involves the distribution of different lube products from a single production plant to industrial customers using a heterogeneous fleet. The fleet consists of tank trucks where each tank can only be assigned to a single lube. The objective is to minimize total transportation related costs. The problem basically consists of assigning customer orders to the tanks of the trucks and determining the routes of the tank trucks simultaneously. We model this problem as a 0–1 mixed integer linear program. Since the model is intractable for real-life industrial environment we propose two heuristic approaches and investigate their performances. The first approach is a linear programming relaxation-based algorithm while the second is a rolling-horizon threshold heuristic. We propose two variants of the latter heuristic: the first uses a distance priority whereas the second has a due date priority. Our numerical analysis using company data shows that both variants of the rolling horizon threshold heuristic are able to provide good results fast.     

供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题

取送货车辆路径问题在多点调拨系统普遍存在,属于NP-hard问题。该问题研究通常需考虑车场数、车型种类、货品种类、客户服务次数等诸多因素,已有文献多假设客户间供需已匹配、单车场、单车型、单货品和取送货需求一次性满足,优化目标多设置为总路径最短。而从企业运营实践来看,运输方案不仅要规划客户间访问路径,还需进行客户间供需匹配;运输成本不仅与运距有关,还涉及运输货品的重量和派车成本;运输网络中多车场、多车型和多货品更加常见,且客户需求量往往大于车辆装载能力。因此,本文首次尝试基于"运距×运量"的车辆路径成本和基于额定吨位的固定派车成本之和最小为优化目标,建立同时考虑多车场、多车型、多货品、客户间供需未匹配和需求可拆分的取送货车辆路径问题模型,并设计基于大规模邻域搜索的迭代局部搜索求解算法。该算法采用基于运输效率提升的贪婪思想来快速构建高质量初始可行解,并通过引入四种移除算子、两种修复算子和车场车型调整优化策略形成大规模可行搜索邻域以增强全局寻优能力。基于18个文献算例和6个企业实例的数值实验结果表明：1）本文提出的算法在求解质量和求解效率方面均优于相关文献中的算法;2）相对人工调拨方案,本文设计的方案能够帮助企业节约33%的运输成本和21%的车次。本研究不仅可拓展取送货车辆路径问题现有理论,而且可为企业实际运营提供决策支持。     

Shelf Loathing: Cross Docking at an Online Retailer

Online customers expect to wait, sometimes for a delay of many days. At the fulfillment center, there might be an opportunity to fill customer orders earlier than the due date through a cross‐docking transaction: rather than picking the item from inventory, the item moves directly from the receiving to the shipping dock, saving shelving and picking transactions. While cross docking reduces shelving and picking costs, it risks changing customer expectations for how soon a product will be delivered. Given customer order arrivals random in quantity and due dates, random replenishment arrivals, and costs (or benefits) for shipping a product early, we characterize the optimal decision as to whether to cross dock a replenishment item to fulfill demand that is not immediately due or to wait to (hopefully) cross dock in later periods. With multiple demands and due dates, the cross‐docking decision depends on the number of unfulfilled demands in each period across the horizon, the number of units that have just arrived (available for cross docking), picking and shelving costs, and the delay cost (or benefit). We formulate the problem as a Markov decision process, determine the structure of the optimal policy, and propose a well‐performing heuristic.     

Particle swarm optimization based-algorithms to solve the two-machine cross-docking flow shop problem: just in time scheduling

Cross-docking is an innovative logistical strategy which provides less inventory holding costs, less transportation costs and fast customer deliveries without storage in between or less than 24 hours. In this paper, we address the two-machine cross-docking scheduling problem within a Just-In-Time (JIT) context. This latter requires the punctuality and exactness of product deliveries. To satisfy this target, we aim to minimize the total earliness and tardiness, then early or tardy deliveries are discouraged. This study presents a great contribution in solving such NP-hard problem while applying different versions of the PSO (Particle Swarm Optimization) algorithm. One of them is hybridized with the Genetic Algorithm (GA). This latter is then shown to be the best one over computational experiments using different sized instances and by determining a percentage deviation from a developed lower bound.

     

Lot-sizing and scheduling in flat-panel display manufacturing process

In this paper, we consider a lot-sizing and scheduling problem arising in the real-world flat-panel display industry. This problem is formulated as a variant of the discrete lot-sizing and scheduling problem with a sequence-dependent setup. After describing the characteristics of the problem and analyzing its computational complexity, we propose an extended formulation based on a network structure. Even though the problem is NP-hard in general, we show that there exist special cases solvable in polynomial time. For the general cases, we demonstrate the tightness of the extended formulation by means of both polyhedral analysis and computational experiments with artificially generated data and real-world industry data. We also propose a relax-and-fix heuristic algorithm based on the extended formulation, which has been deployed in practice, with the corresponding computational results.     

Cost‐Effective Application of Thermal Protection on LPG Road Transport Tanks for Risk Reduction Due to Hot BLEVE Incidents

A simplified risk and cost‐benefit analysis is presented for the application of thermal protection (TP) on propane and LPG highway tanker trucks operating in North America. A risk analysis is performed to determine the benefits of risk reduction by TP, relative to the costs of applying and maintaining TP on a tanker truck. The results show that TP is cost effective if the tanker truck spends enough time (or travels enough distance) in areas of moderate or high population density. The analysis is very sensitive to a number of inputs, including: (i) value of life, (ii) hot boiling liquid expanding vapor explosion frequency, (iii) public exposure to severe hazards, and (iv) life cost of TP. With this simplified analysis, it is possible to generate tanker truck exposure times to the public that justify the application of TP based on cost and benefit considerations.     

Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends

The flow shop scheduling problem is finding a sequence given n jobs with same order at m machines according to certain performance measure(s). The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, many real-world scheduling problems are multi-objective by nature. Over the years there have been several approaches used to deal with the multi-objective flow shop scheduling problems (MOFSP). Hence, in this study, we provide a brief literature review of the contributions to MOFSP and identify areas of opportunity for future research.     

集装箱码头外部集卡预约优化模型与算法

针对集装箱码头闸口拥堵问题,建立集卡预约优化模型,目的是减少集卡排队等待时间和拥堵期间的碳排放。该模型在给定的集卡到达调整量水平的限制下,确定每个时段最优的预约份额,同时利用非平稳排队模型描述集卡到达随时间到达的特点。为求解模型,设计基于遗传算法与逐点固定流体近似算法(PSFFA)的求解方法,该算法利用遗传算法搜索最优解,基于PSFFA算法计算集卡排队时间。最后,利用算例对模型和算法的有效性进行了验证。结果表明,集卡预约优化模型可以有效地减少集卡排队时间,PSFFA方法可以较好地求解到达过程不平稳的排队问题。     

Trim loss and related problems

Because of the diversity of the structures of real-world trim loss (or cutting stock) problems there exist no general standard methods for solving these problems. Hence many solution methods for trim loss problems have been developed in practice, especially heuristics. Since these methods are strongly based on the particular problems to which they are applied, the study of papers on problems with a comparable structure may prove helpful. In this paper a detailed catalogue of criteria for characterization of real-world trim loss problems is developed in a differentiated and systematic manner. The main criteria are: dimension, planning situation, goal, restrictions and solution approach. The proposed system of classification is based on 34 case studies found in the relevant literature. The classification of these case studies is represented by means of a ‘classification schedule’. In view of existing formal similarities the classification system can also be of importance for (bin) packing and loading as well as some assortment problems.     

考虑交货因素的热轧无缝钢管订单排程模型与算法

无缝钢管的市场需求具有多品种、小批量的特点，为了在满足客户需求的同时保证高效连续化生产，文章在满足生产工艺特征的基础上将配送地址和交货期等合同因素引入热轧无缝钢管订单排程问题中，建立了以适期交货、订单集中生产配送和最小化机器设备调整为优化目标的订单排程优化模型，并设计了两阶段求解算法：首先，以订单交货期与配送地址差异最小为目标，基于凝聚策略设计了订单聚类算法，将具有相同工艺约束、相似合同要求的订单进行聚类，并形成初始轧制计划；然后，以设备调整和提前/拖期最小为目标，设计混合变邻域搜索算法，对初始轧制批次进行排程优化。基于实际订单数据的实验结果表明，模型和算法对问题的描述和求解是可行有效的。