Scheduling of inbound and outbound trucks in cross docking systems with temporary storage

Cross docking is a warehouse management concept in which items delivered to a warehouse by inbound trucks are immediately sorted out, reorganized based on customer demands, routed and loaded into outbound trucks for delivery to customers without the items being actually held in inventory at the warehouse. If any item is held in storage, it is usually for a brief period of time that is generally less than 24 hours. This way, the turnaround times for customer orders, inventory management cost, and warehouse space requirements are reduced. One of the objectives for cross docking systems is how well the trucks can be scheduled at the dock and how the items in inbound trucks can be allocated to the outbound trucks to optimize on some measure of system performance. The objective of this research is to find the best truck docking or scheduling sequence for both inbound and outbound trucks to minimize total operation time when a temporary storage buffer to hold items temporarily is located at the shipping dock. The product assignment to trucks and the docking sequences of the inbound and outbound trucks are all determined simultaneously.     

Manufacturer’s mixed pallet design problem

We study a problem faced by a major beverage producer. The company produces and distributes several brands to various customers from its regional distributors. For some of these brands, most customers do not have enough demand to justify full pallet shipments. Therefore, the company decided to design a number of mixed or “rainbow” pallets so that its customers can order these unpopular brands without deviating too much from what they initially need. We formally state the company’s problem as determining the contents of a pre-determined number of mixed pallets so as to minimize the total inventory holding and backlogging costs of its customers over a finite horizon. We first show that the problem is NP-hard. We then formulate the problem as a mixed integer linear program, and incorporate valid inequalities to strengthen the formulation. Finally, we use company data to conduct a computational study to investigate the efficiency of the formulation and the impact of mixed pallets on customers’ total costs.     

A heuristic algorithm for the truckload and less-than-truckload problem

The delivery of goods from a warehouse to local customers is an important and practical problem of a logistics manager. In reality, we are facing the fluctuation of demand. When the total demand is greater than the whole capacity of owned trucks, the logistics managers may consider using an outsider carrier.Logistics managers can make a selection between a truckload (a private truck) and a less-than-truckload carrier (an outsider carrier). Selecting the right mode to transport a shipment may bring significant cost savings to the company.In this paper, we address the problem of routing a fixed number of trucks with limited capacity from a central warehouse to customers with known demand. The objective of this paper is developing a heuristic algorithm to route the private trucks and to make a selection of less-than-truckload carriers by minimizing a total cost function. Both the mathematical model and the heuristic algorithm are developed. Finally, some computational results and suggestions for future research are presented.     

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50?000 instances). It is also effective for solving the instances of problem set Cover III (almost 100?000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes.     

Scheduling incoming and outgoing trucks at cross docking terminals to minimize the storage cost

Cross docking terminals allow companies to reduce storage and transportation costs in a supply chain. At these terminals, products of different types from incoming trucks are unloaded, sorted, and loaded to outgoing trucks for delivery. If the designated outgoing truck is not immediately available for some products, they are temporarily stocked in a small storage area available at the terminal. This paper focuses on the operational activities at a cross docking terminal with two doors: one for incoming trucks and another one for outgoing trucks. We consider the truck scheduling problem with the objective to minimize the storage usage during the product transfer inside the terminal. Our interest in this problem is mainly theoretical. We show that it is NP-hard in the strong sense even if there are only two product types. For a special case with fixed subsequences of incoming and outgoing trucks, we propose a dynamic programming algorithm, which is the first polynomial algorithm for this case. The results of numerical tests of the algorithm on randomly generated instances are also presented.     

Linear programming based decomposition methods for inventory distribution systems

We consider an inventory distribution system consisting of one warehouse and multiple retailers. The retailers face random demand and are supplied by the warehouse. The warehouse replenishes its stock from an external supplier. The objective is to minimize the total expected replenishment, holding and backlogging cost over a finite planning horizon. The problem can be formulated as a dynamic program, but this dynamic program is difficult to solve due to its high dimensional state variable. It has been observed in the earlier literature that if the warehouse is allowed to ship negative quantities to the retailers, then the problem decomposes by the locations. One way to exploit this observation is to relax the constraints that ensure the nonnegativity of the shipments to the retailers by associating Lagrange multipliers with them, which naturally raises the question of how to choose a good set of Lagrange multipliers. In this paper, we propose efficient methods that choose a good set of Lagrange multipliers by solving linear programming approximations to the inventory distribution problem. Computational experiments indicate that the inventory replenishment policies obtained by our approach can outperform several standard benchmarks by significant margins.     

Integrated location and two-echelon inventory network design under uncertainty

In this paper, we propose a two-stage stochastic model to address the design of an integrated location and two-echelon inventory network under uncertainty. The central issue in this problem is to design and operate an effective and efficient multi-echelon supply chain distribution network and to minimize the expected system-wide cost of warehouse location, the allocation of warehouses to retailers, transportation, and two-echelon inventory over an infinite planning horizon. We structure this problem as a two-stage nonlinear discrete optimization problem. The first stage decides the warehouses to open and the second decides the warehouse-retailer assignments and two-echelon inventory replenishment strategies. Our modeling strategy incorporates various probable scenarios in the integrated multi-echelon supply chain distribution network design to identify solutions that minimize the first stage costs plus the expected second stage costs. The two-echelon inventory cost considerations result in a nonlinear objective which we linearize with an exponential number of variables. We solve the problem using column generation. Our computational study indicates that our approach can solve practical problems of moderate-size with up to twenty warehouse candidate locations, eighty retailers, and ten scenarios efficiently.     

Scheduling the truckload operations in automatic warehouses

This work presents a scheduling problem that arises in an automatic storage/retrieval warehouse system AS/RS involving the scheduling of the truck load operations. The truck loading operations are modelled as job shop problem with recirculation. The loads are considered as jobs, the pallets of a load are seen as the job’s operations. The forklifts are the machines. The minimization of the makespan allows minimizing the idle time of the warehouse’s equipments.     

The stop-and-drop problem in nonprofit food distribution networks

In this paper, we introduce the stop-and-drop problem (SDRP), a new variant of location-routing problems, that is mostly applicable to nonprofit food distribution networks. In these distribution problems, there is a central warehouse that contains food items to be delivered to agencies serving the people in need. The food is delivered by trucks to multiple sites in the service area and partner agencies travel to these sites to pick up their food. The tactical decision problem in this setting involves how to jointly select a set of delivery sites, assign agencies to these sites, and schedule routes for the delivery vehicles. The problem is modeled as an integrated mixed-integer program for which we delineate a two-phase sequential solution approach. We also propose two Benders decomposition-based solution procedures, namely a linear programming relaxation based Benders implementation and a logic-based Benders decomposition heuristic. We show through a set of realistic problem instances that given a fixed time limit, these decomposition based methods perform better than both the standard branch-and-bound solution and the two-phase approach. The general problem and the realistic instances used in the computational study are motivated by interactions with food banks in southeastern United States.     

Capacity planning and warehouse location in supply chains with uncertain demands

We discuss the strategic capacity planning and warehouse location problem in supply chains operating under uncertainty. In particular, we consider situations in which demand variability is the only source of uncertainty. We first propose a deterministic model for the problem when all relevant parameters are known with certainty, and discuss related tractability and computational issues. We then present a robust optimization model for the problem when the demand is uncertain, and demonstrate how robust solutions may be determined with an efficient decomposition algorithm using a special Lagrangian relaxation method in which the multipliers are constructed from dual variables of a linear program.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

Timetabling of sorting slots in a logistic warehouse

We study a problem that occurs at the end of a logistic stream in a warehouse and which concerns the timetabling of the sorting slots that are used to accommodate the prepared orders before they are dispatched. We consider a set of orders to be prepared in a certain number of preparation shops over a given time horizon. Each order is associated with the truck that will transport it to the customer. A sorting slot is an accumulation area where processed orders wait to be loaded onto a truck. For a given truck a known number of sorting slots is needed from the time the first order for this truck begins to be prepared, right up until the truck’s scheduled departure time. Since several orders destined for different trucks are processed simultaneously, and since the number of sorting slots is limited, the timetabling of these resources is necessary to ensure that all orders can be processed over the considered time horizon. In this paper we describe the general industrial context of the problem and we formalize it. We state that some particular cases of the problem are polynomially solvable while the general problem is NP-complete. We then propose optimization methods for solving the problem.     

A column generation algorithm for tactical timber transportation planning

We present a tactical wood flow model that appears in the context of the Canadian forestry industry, and describe the implementation of a decision support system created for use by an industrial partner. In this problem, mill demands and harvested volumes of a heterogeneous set of log types are given over a multi-period planning horizon. Wood can be stored at the forest roadside before delivery at a financial cost. Rather than solve this as a network linear programme on the basis of out-and-back deliveries, we choose to model this problem as a generalization of a log-truck scheduling problem. By routing and scheduling the trucks in the resolution, this allows us to both anticipate potential backhaul opportunities for cost and fuel savings, and also minimize queuing times at log-loaders, management of which is a major concern in the industry. We model this problem as a mixed integer linear programme and solve it via column generation. The methodology is tested on several case studies.     

Capacitated location model with online demand pooling in a multi-channel supply chain

This paper presents a location model that assigns online demands to the capacitated regional warehouses currently serving in-store demands in a multi-channel supply chain. The model explicitly considers the trade-off between the risk pooling effect and the transportation cost in a two-echelon inventory/logistics system. Keeping the delivery network of the in-store demands unchanged, the model aims to minimize the transportation cost, inventory cost, and fixed handling cost in the system when assigning the online demands. We formulate the assignment problem as a non-linear integer programming model. Lagrangian relaxation based procedures are proposed to solve the model, both the general case and an important special case. Numerical experiments show the efficiency of our algorithms. Furthermore, we find that because of the pooling effect the variance of in-store demands currently served by a warehouse is an important parameter of the warehouse when it is considered as a candidate for supplying online demands. Highly uncertain in-store demands, as well as low transportation cost per unit, can make a warehouse appealing. We illustrate with numerical examples the trade-off between the pooling effect and the transportation cost in the assignment problem. We also evaluate the cost savings between the policy derived from the model, which integrates the transportation cost with the pooling effect, and the commonly used policy, which is based only on the transportation cost. Results show that the derived policy can reduce 1.5–7.5% cost in average and in many instances the percentage of cost savings is more than 10%.     

Forward-reserve allocation in a warehouse with unit-load replenishments

Many companies configure their warehouse with a forward area and a reserve area. The former is used for efficient order-picking, the latter for replenishing the forward area. We consider a situation in which orders are picked during a certain time period, referred to as the picking period. Prior to the picking period there is sufficient time to replenish the forward area. Our objective is to determine which replenishments minimize the expected amount of labor during the picking period. Further, we present a second model with a constraint on the replenishment activity. We model the problem as a binary programming problem and present efficient heuristics that provide tight performance guarantees. We compare the heuristics with procedures that are popular in practice and show that significant labor-savings are possible.     

A linear model for surface mining haul truck allocation incorporating shovel idle probabilities

We present models of trucks and shovels in oil sand surface mines. The models are formulated to minimize the number of trucks for a given set of shovels, subject to throughput and ore grade constraints. We quantify and validate the nonlinear relation between a shovel’s idle probability (which determines the shovel’s productivity) and the number of trucks assigned to the shovel via a simple approximation, based on the theory of finite source queues. We use linearization to incorporate this expression into linear integer programs. We assume in our integer programs that each shovel is assigned a single truck size but we outline how one could account for multiple truck sizes per shovel in an approximate fashion. The linearization of shovel idle probabilities allows us to formulate more accurate truck allocation models that are easily solvable for realistic-sized problems.     

Modeling and solution of the joint quay crane and truck scheduling problem

This paper addresses the joint quay crane and truck scheduling problem at a container terminal, considering the coordination of the two types of equipment to reduce their idle time between performing two successive tasks. For the unidirectional flow problem with only inbound containers, in which trucks go back to quayside without carrying outbound containers, a mixed-integer linear programming model is formulated to minimize the makespan. Several valid inequalities and a property of the optimal solutions for the problem are derived, and two lower bounds are obtained. An improved Particle Swarm Optimization (PSO) algorithm is then developed to solve this problem, in which a new velocity updating strategy is incorporated to improve the solution quality. For small sized problems, we have compared the solutions of the proposed PSO with the optimal solutions obtained by solving the model using the CPLEX software. The solutions of the proposed PSO for large sized problems are compared to the two lower bounds because CPLEX could not solve the problem optimally in reasonable time. For the more general situation considering both inbound and outbound containers, trucks may go back to quayside with outbound containers. The model is extended to handle this problem with bidirectional flow. Experiment shows that the improved PSO proposed in this paper is efficient to solve the joint quay crane and truck scheduling problem.     

Loading Multiple Pallets

This paper addresses the problem of loading pallets with non-identical items, i.e. what has been called the ‘Distributor's Pallet Packing Problem’. It concentrates on the situation where the consignment to be loaded cannot be accommodated on a single pallet. A greedy procedure for tackling this problem, which is based on a published approach for loading single pallets, is described and evaluated. Also discussed is a series of possible modifications of the basic method, whereby the pallets involved are packed simultaneously. A detailed performance analysis is undertaken. The paper concludes with suggestions for further work in this area.     

“第三方代管”参与下的共享单车回收路线优化问题

以共享单车回收为背景,研究了“第三方代管”参与下的回收路线优化问题。针对代管员和调度卡车的特征,提出激励代管员将零散分布的损坏单车运送至附近的中转点,然后派遣卡车将这些集中起来的损坏单车从中转点运送至维修中心。以总成本最小为目标建立混合整数规划模型,针对问题特性设计改进遗传算法。数值实验论证了问题特性,并论证得出在所提回收策略下及时回收损坏单车,不仅可以减轻公共空间被损坏单车挤占的问题,还可以有效减少回收成本。实验结果还表明所设计算法在短时间内能获得高质量解。     

Determining the Pareto set in a bicriteria two-echelon inventory/distribution system

This article concerns two-echelon inventory/distribution system, consisting of a warehouse and a retailer. We assume that the demand is deterministic and stockouts are not permitted. Two criteria are considered: to minimize the annual inventory cost and the annual total number of damaged items by improper shipment handling. The problem consists of determining the non-dominated inventory policies in such a way that the trade-off between both criteria is achieved. We present the characterization of the non-dominated optimal solution set and we use this result to correct the solution method previously proposed by other authors for a problem with identical cost structure. An efficient algorithm to calculate the non-dominated solution set is introduced. Computational results on several randomly generated problems are reported.