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.     

Cross dock scheduling: Classification,literature review and research agenda

At cross docking terminals incoming deliveries of inbound trucks are unloaded, sorted, moved across the dock and finally loaded onto outbound trucks, which immediately leave the terminal towards their next destination in the distribution chain. Accordingly, a cross dock is a consolidation point in a distribution network, where multiple smaller shipments can be merged to full truck loads in order to realize economies in transportation. In this context, the truck scheduling problem, which decides on the succession of truck processing at the dock doors, is especially important to ensure a rapid turnover and on-time deliveries. Due to its high real-world significance, several truck scheduling procedures have been introduced during recent years, which all treat specific cross dock settings. In order to structure and promote scientific progress, this paper introduces a classification of deterministic truck scheduling. With the help of this classification, existing literature is reviewed and future research needs are identified. Moreover, we represent a yet unexplored class of truck scheduling problems which is highly relevant in real-world distribution networks.     

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.     

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

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

Managing Logistics in Regional Banknote Supply Chain Under Security Concerns

We study the logistics problem faced by Regional Branches (RBs) of a central bank in managing the currency supply under security concerns. While making banknote supply decisions to Sub‐Branches (SBs), the management of RB must achieve two goals simultaneously: (i) guarantee that each SB has sufficient inventories of all denominations of banknotes to satisfy the demands from all commercial banks within its service area, and (ii) control the annual spending on this banknote supply operation. Due to security concerns, the following methods are implemented in the process of transporting banknotes: (i) the capacity of a cash truck is limited by the total face value (instead of the physical space) of banknotes, and (ii) empty decoy trucks are deployed along with the trucks filled with banknotes. After deriving a polynomial‐time strategy to guarantee an optimal solution for the special Bin‐Packing Problem faced in this study, we provide an exact formulation for the RB's supply planning problem. We also propose several polynomial‐time algorithms for deriving either optimal or near‐optimal solutions for the problem under different settings. Using the weekly demand data obtained from the central bank, we verify the performance of our algorithms, and analyze the impacts of changes in these features and in the fleet capacity on the total cost incurred by an RB under various scenarios.     

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.     

Vehicle Emission Unit Risk Factors for Transportation Risk Assessments

When the transportation risk posed by shipments of hazardous chemical and radioactive materials is being assessed, it is necessary to evaluate the risks associated with both vehicle emissions and cargo-related risks. Diesel exhaust and fugitive dust emissions from vehicles transporting hazardous shipments lead to increased air pollution, which increases the risk of latent fatalities in the affected population along the transport route. The estimated risk from these vehicle-related sources can often be as large or larger than the estimated risk associated with the material being transported. In this paper, data from the U.S. Environmental Protection Agency's Motor Vehicle-Related Air Toxics Study are first used to develop latent cancer fatality estimates per kilometer of travel in rural and urban areas for all diesel truck classes. These unit risk factors are based on studies investigating the carcinogenic nature of diesel exhaust. With the same methodology, the current per-kilometer latent fatality risk factor used in transportation risk assessments for heavy diesel trucks in urban areas is revised and the analysis expanded to provide risk factors for rural areas and all diesel truck classes. These latter fatality estimates may include, but are not limited to, cancer fatalities and are based primarily on the most recent epidemiological data available on mortality rates associated with ambient air PM-10 concentrations.     

Appointment Scheduling with No‐Shows and Overbooking

We study an overbooking model for scheduling arrivals at a medical facility under no‐show behavior, with patients having different no‐show probabilities and different weights. The scheduler has to assign the patients to time slots in such a way that she minimizes the expected weighted sum of the patients' waiting times and the doctor's idle time and overtime. We first consider the static problem, where the set of patients to be scheduled and their characteristics are known in advance. We partially characterize the optimal schedule and introduce a new sequencing rule that schedules patients according to a single index that is a function of their characteristics. Then we apply our theoretical results and conclusions from numerical experiments to sequential scheduling procedures. We propose a heuristic solution to the sequential scheduling problem, where requests for appointments come in gradually over time and the scheduler has to assign each patient to one of the remaining slots that are available in the schedule for a given day. We find that the no‐show rate and patients' heterogeneity have a significant impact on the optimal schedule and should be taken under consideration.     

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.     

Options Contracts with Overbooking in the Air Cargo Industry

In today's world economy, which is marked by intensified international trade, air cargo acts as a key facilitator. However, cargo airlines continue to struggle to be profitable because of very high asset costs and substantial demand uncertainty. To improve upon this situation, we propose an options contract. Our model captures the main features of cargo trade between an airline and a freight forwarder and allows us to derive an optimal reservation policy. We then go on to analyze the impact of overbooking on the profit of the cargo capacity provider. The model is subsequently applied to real‐life booking data provided by a major cargo carrier. This enables us to compare current contractual arrangements with the ones proven optimal in the model. A numerical study provides insights about the impact of overbooking on contract parameters and profitability. Managerial insights to be drawn conclude this study.     

Managing appointments with waiting time targets and random walk-ins

The random arrivals of walk-in patients significantly affect the daily operations of healthcare facilities. To improve the performance of outpatient departments, this paper attempts to make an appointment schedule by considering walk-ins and the waiting time target (WTT) for appointment patients. A stochastic programming model is proposed to solve this problem with the objective of minimizing the weighted patient waiting and makespan cost. A non-decreasing waiting cost function is used to capture the WTT fulfillment of appointment patients, whereas walk-ins incur a linear waiting cost. A finite-horizon Markov Decision Process model is formulated to establish the optimal real-time scheduling policy under a given appointment schedule. The appointment schedule is determined by a two-stage stochastic programming approximation and a local search improvement. Structural properties of the optimal appointment scheduling and real-time scheduling policies are established. In particular, it is shown that appointment overbooking is allowed only at the end of the regular session, and the optimal real-time scheduling policy is an easy-to-implement threshold policy with bounded sensitivity. Numerical experiments based on real data are performed to investigate the influence of different parameters and to compare different schedules. The optimal schedule demonstrates superior performance by allowing reasonable waiting times for appointment patients depending on their WTTs. Managerial insights are also provided to hospital managers. Finally, the basic model is extended by incorporating random service times and random arrivals of appointment patients. The latter includes the random number of patients that show up for service or call for appointments, and the random arrival time (unpunctuality). Appointment overbooking strategies are shown to have different structures under some stochastic factors.     

Priority Rules for Multi‐Task Due‐Date Scheduling under Varying Processing Costs

We study the scheduling of multiple tasks under varying processing costs and derive a priority rule for optimal scheduling policies. Each task has a due date, and a non‐completion penalty cost is incurred if the task is not completely processed before its due date. We assume that the task arrival process is stochastic and the processing rate is capacitated. Our work is motivated by both traditional and emerging application domains, such as construction industry and freelance consulting industry. We establish the optimality of Shorter Slack time and Longer remaining Processing time (SSLP) principle that determines the priority among active tasks. Based on the derived structural properties, we also propose an effective cost‐balancing heuristic policy and demonstrate the efficacy of the proposed policy through extensive numerical experiments. We believe our results provide operators/managers valuable insights on how to devise effective service scheduling policies under varying costs.     

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.     

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

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

Sequencing and Scheduling Appointments with Potential Call‐In Patients

This paper studies appointment scheduling for a combination of routine patients who book well in advance and last‐minute patients who call for an appointment later that same day. We determine when these same‐day patients should be scheduled throughout the day, and how the prospect of their arrivals affects the appointment times of the routine patients. By formulating the problem as a stochastic linear program, we are able to incorporate random and heterogeneous service times and no‐show rates, ancillary physician tasks, and appointment delay costs for same‐day patients who prefer to see the doctor as early as possible. We find that the optimal patient sequence is quite sensitive to the no‐show probabilities and the expected number of same‐day patients. We also develop two simple heuristic solutions to this combinatorial sequencing problem.     

Schedule Recovery: Unplanned Absences in Service Operations*

The U.S. service sector loses 2.3% of all scheduled labor hours to unplanned absences, but in some industries, the total cost of unplanned absences approaches 20% of payroll expense. The principal reasons for unscheduled absences (personal illness and family issues) are unlikely to abate anytime soon. Despite this, most labor scheduling systems continue to assume perfect attendance. This oversight masks an important but rarely addressed issue in services management: how to recover from short‐notice, short‐term reductions in planned capacity. In this article, we model optimal responses to unplanned employee absences in multi‐server queueing systems that provide discrete, pay‐per‐use services for impatient customers. Our goal is to assess the performance of alternate absence recovery strategies under various staffing and scheduling regimes. We accomplish this by first developing optimal labor schedules for hypothetical service environments with unreliable workers. We then simulate unplanned employee absences, apply an absence recovery model, and compute system profits. Our absence recovery model utilizes recovery strategies such as holdover overtime, call‐ins, and temporary workers. We find that holdover overtime is an effective absence recovery strategy provided sufficient reserve capacity (maximum allowable work hours minus scheduled hours) exists. Otherwise, less precise and more costly absence recovery methods such as call‐ins and temporary help service workers may be needed. We also find that choices for initial staffing and scheduling policies, such as planned overtime and absence anticipation, significantly influence the likelihood of successful absence recovery. To predict the effectiveness of absence recovery policies under alternate staffing/scheduling strategies and operating environments, we propose an index based on initial capacity reserves.     

Approximations to Optimal k‐Unit Cycles for Single‐Gripper and Dual‐Gripper Robotic Cells

We consider the problem of scheduling operations in bufferless robotic cells that produce identical parts using either single‐gripper or dual‐gripper robots. The objective is to find a cyclic sequence of robot moves that minimizes the long‐run average time to produce a part or, equivalently, maximizes the throughput. Obtaining an efficient algorithm for an optimum k‐unit cyclic solution (k ≥ 1) has been a longstanding open problem. For both single‐gripper and dual‐gripper cells, the approximation algorithms in this paper provide the best‐known performance guarantees (obtainable in polynomial time) for an optimal cyclic solution. We provide two algorithms that have a running time linear in the number of machines: for single‐gripper cells (respectively, dual‐gripper cells), the performance guarantee is 9/7 (respectively, 3/2). The domain considered is free‐pickup cells with constant intermachine travel time. Our structural analysis is an important step toward resolving the complexity status of finding an optimal cyclic solution in either a single‐gripper or a dual‐gripper cell. We also identify optimal cyclic solutions for a variety of special cases. Our analysis provides production managers valuable insights into the schedules that maximize productivity for both single‐gripper and dual‐gripper cells for any combination of processing requirements and physical parameters.     

Capacity rationing in rental systems with two customer classes and batch arrivals

Service differentiation is an emerging method to improve profit and to better serve high-priority customers. Such an approach has recently been introduced by one of Europe's leading rail cargo companies. Under this approach, customers can choose between classic and premium services. Premium service is priced above classic service and premium customers receive a service guarantee which classic customers do not receive. The company has to decide under which conditions it should ration its fleet capacity to classic customers in order to increase service of premium customers. We model such a situation as a batch-arrival queuing loss system. We describe the model, solve it optimally, and derive quantities of interest such as service probabilities. We further analyze it by performing numerical experiments based on the data from the company that motivated our research. We show that the potential of capacity rationing can be substantial in situations like the one we analyzed. We also derive conditions under which rationing is especially beneficial, such as under high unit fleet holding costs or in the presence of batch arrivals compared to single arrivals.     

An Integrated Logistic Model for Predictable Disasters

In the aftermath of a disaster, the relief items are transported from temporary warehouses (Staging Areas, SAs) to the Points of Distribution (PODs). Reducing the response time to provide relief items to disaster victims and cost minimization are two important objectives of this study. We propose an integrated optimization model for simultaneously determining (1) locations of staging areas, (2) inventory assignments to these SAs, (3) selecting sizes and numbers of trucks, and (4) routing of trucks from SAs to PODs. We also introduce another variable, a value function, which forces the model to reduce the logistics response time. We study the interactions among these variables through extensive sensitivity analysis. The time horizon for supply of relief items to disaster areas is usually limited to six days after the disaster occurs. Therefore, we use the proposed optimization model in a rolling‐horizon manner, one day at a time. This reduces daily demand uncertainty. We analyze three disaster scenarios: (1) a low impact disaster, (2) a medium impact disaster, and (3) a high impact disaster. We conduct 720 experiments with different parameter values, and provide answers to the following questions that are useful for the logistic managers: (i) What are the right sizes (in terms of storage capacities) of SAs closer to the PODs? (ii) How should the budget be allocated in a disaster scenario? (iii) What mix of different types (in terms of sizes) of trucks should be selected in a given scenario? The most important managerial insights include: (i) operational budget beyond a limit does not improve the operational efficiency, (ii) when the budget is very low, it is essential to select smaller SAs close to the PODs in order to carry out operations in a feasible manner, (iii) when the impact of disaster is high, it is always beneficial to select larger SAs close to the PODs (as long as the budget is not very low), (iv) when the budget is high and the impact of disaster is not very high, the emergency management administrators need to select SAs prudently based on the tradeoff between the operational cost and the humanitarian value, and (v) the cost of operations is higher when all the trucks are of the same type compared to the case when there is a mix of different types of trucks. Also, we find that the optimal selection of SAs is not impacted by different combinations of the types of trucks. The focus of this study is on disasters that can be forecasted in advance and provide some lead time for preparations, for example, hurricanes. In order to understand the disaster management process of such disasters and develop our model, we (i) interviewed several emergency management administrators, and (ii) studied the disaster management processes available in documents released by various government agencies.