A dynamic driver management scheme for less-than-truckload carriers

This paper describes a scheme for the dynamic management of linehaul drivers developed for a large US less-than-truckload (LTL) carrier. Virtually all scheduling problems faced by transportation service providers are complicated by time-constrained vehicle operators that can be renewed only after resting. LTL driver scheduling is further complicated by the fact that trucking moves, unlike passenger airline flights or train dispatches, are not pre-scheduled. The technology developed in this paper combines greedy search with enumeration of time-feasible driver duties, and is capable of generating in a matter of minutes cost-effective driver schedules covering 15,000–20,000 loads and satisfying a variety of real-life driver constraints. Computational results justify the algorithmic design choices made in the development of the scheme, and a comparison with real-world dispatch data indicates that the technology produces driver schedules of very high quality.     

Zone pricing for time-definite LTL freight transportation with elastic demand

Because shipments to a pair of administrative divisions are typically delivered with the same time-in-transit service level, shippers expect that they should be charged the same price. Thus, the carrier clusters operation centers located in the same administrative division into a tier-1 zone. These zones are subsequently aggregated into a set of hierarchical zones for which the carrier defines and publishes a zone tariff chart. Zone pricing is a tactical decision that simultaneously determines the zone prices and an operational plan to use its operating capacity to maximize carrier’s profit while meeting the expected service level and operational requirements. We modeled this integral-constrained concave program using link formulation and proposed an implicit enumeration embedded with Lagrangian relaxation upper bounds to determine the optimal prices and operations plan. To meet the shippers’ expectation, we proved our model mathematically and demonstrated computationally, using Taiwan’s largest time-definite LTL freight carrier, that zone pricing has a negative impact on carrier profit in the process of aggregation.     

Optimizing railway crew schedules with fairness preferences

Railway crew scheduling deals with generating duties for train drivers to cover all train movements of a given timetable while taking into account a set of work regulations. The objective is to minimize the overall costs associated with a crew schedule, which includes workforce costs and hotel costs. A cost minimal schedule often contains duties that are unpopular to train drivers, and these unpopular duties are often unevenly distributed among crew depots. At the company that motivated our research, for example, train drivers dislike duties that start in the early morning hours. Currently, some crew depots operate large numbers of these unpopular duties, while others do not have any unpopular duties at all. The train drivers perceive this situation as unfair. They prefer schedules with fewer and more evenly distributed unpopular duties across crew depots. In this paper, we define and measure unpopularity and (un)fairness in a railway crew scheduling context. We integrate fairness conditions into a column generation-based solution algorithm and analyze the effect of increased fairness on cost. We also show how increased fairness affects the unpopularity of a schedule. Our method has been applied to test instances at a large European railway freight carrier. Compared to a standard approach that penalizes only the number of unpopular duties in a schedule, we were able to significantly improve schedule fairness with only marginal increases in schedule cost.     

A mixed integer programming formulation and effective cuts for minimising schedule durations of Australian truck drivers

Transport companies seek to maximise vehicle utilisation and minimise labour costs. Both goals can be achieved if the time required to fulfil a sequence of transportation tasks is minimised. However, if schedule durations are too short drivers may not have enough time for recuperation and road safety is impaired. In Australia transport companies must ensure that truck drivers can comply with Australian Heavy Vehicle Driver Fatigue Law and schedules must give enough time for drivers to take the amount of rest required by the regulation. This paper shows how transport companies can minimise the duration of truck driver schedules complying with Australian Heavy Vehicle Driver Fatigue Law. A mixed integer programming formulation is presented and valid inequalities are given. Computational experiments show that these inequalities provide significant reduction in computational effort when using one of the most advanced commercial mixed integer programming solver.     

An anticipative scheduling approach with controllable processing times

In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decisions. In this paper, we show that if the processing times are controllable then an anticipative approach can be used to form an initial schedule so that the limited capacity of the production resources are utilized more effectively. To illustrate the anticipative scheduling idea, we consider a non-identical parallel machining environment, where processing times can be controlled at a certain compression cost. When there is a disruption during the execution of the initial schedule, a match-up time strategy is utilized such that a repaired schedule has to catch-up initial schedule at some point in future. This requires changing machine–job assignments and processing times for the rest of the schedule which implies increased manufacturing costs. We show that making anticipative job sequencing decisions, based on failure and repair time distributions and flexibility of jobs, one can repair schedules by incurring less manufacturing cost. Our computational results show that the match-up time strategy is very sensitive to initial schedule and the proposed anticipative scheduling algorithm can be very helpful to reduce rescheduling costs.     

Modeling berth allocation and quay crane assignment considering QC driver cost and operating efficiency

Due to high labour costs and difference of QC driver’s handling efficiency existing between day and night, factors concerning QC drivers can significantly impact the schedule of berth allocation and quay crane assignment. This paper tackles the berth allocation and quay crane assignment problem considering QC driver cost, difference of the operating efficiency and performance-related pay between day and night. How QC driver-related factors affect the schedules is analyzed, and the objective composition including QC driver cost is given. A mixed integer programming model with model acceleration algorithms is developed for the proposed problem, and a meta-heuristic framework including a three-stage algorithm is proposed for solving the problem. Numerical experiments are conducted to validate the effectiveness of the proposed model and performance of the meta-heuristic approach, leading to a multitude of managerial insights.     

The parcel hub scheduling problem: A simulation-based solution approach

This research presents an interesting scheduling problem common to freight consolidation terminals. This previously unstudied problem involves scheduling a set of inbound trailers to a fixed number of unload docks. The objective is to schedule the trailers to the unload docks to minimize the time span of the transfer operation. This study focuses on freight consolidation terminals in the parcel delivery industry. A simulation-based scheduling algorithm that uses a genetic algorithm to drive the search for new solutions is proposed. In addition to the introduction and discussion of the parcel hub scheduling problem, the contribution of this research is an approach that serves as the initial effort to solve this practical problem.     

On runtime parallel scheduling for processor load balancing

Parallel scheduling is a new approach for load balancing. In parallel scheduling, all processors cooperate to schedule work. Parallel scheduling is able to accurately balance the load by using global load information at compile-time or runtime. It provides high-quality load balancing. This paper presents an overview of the parallel scheduling technique. Scheduling algorithms for tree, hypercube, and mesh networks are presented. These algorithms can fully balance the load and maximize locality at runtime. Communication costs are significantly reduced compared to other existing algorithms     

An intelligent logistics support system for enhancing the airfreight forwarding business

Abstract: Recent research related to the aircraft container loading and scheduling problem for airfreight forwarding business has seen significant advances in terms of load plan optimization, taking into account the cost and volume of packed boxes. In today's competitive industrial environment, it is essential that freight forwarders are able to collaborate with carriers (airline companies) to achieve the best possible selection of logistics workflow. However, study of contemporary research publications indicates that there is a dearth of articles related to the design and implementation of an intelligent logistics system to support decision‐making on carrier selection, aircraft container loading plans as well as carrier benchmarking. This paper presents an intelligent logistics support system (ILSS) which is able to provide expert advice related to the airfreight forwarding business, enhancing the logistics operations in relevant activities within the value chain of tasks. ILSS comprises a heuristics‐based intelligent expert system which supports carrier searching and cargo trading planning as well as load plan generation. The proposed approach is meant to enhance various operations in the airfreight forwarding business, adopting computational intelligence technologies such as rule‐based reasoning to provide domain advice and heuristics to support the generation of load plans. After potential outcomes are generated by the heuristics‐based intelligent expert system, a neural network engine is applied to support prediction of unexpected events. To validate the viability of this approach, a production system using the ILSS has been developed and subsequently applied in an emulated airfreight forwarding environment. The application results indicate that the operation time from searching for potential carriers to the execution of the order is greatly reduced. In this paper, details related to the structure, design and implementation of the ILSS are also covered with the inclusion of the actual program codes for building the prototype.     

基于关键链的资源受限项目调度新方法

针对资源受限项目调度问题（RCPSPs）的实际需求建立了多目标优化调度模型，综合运用现有研究成果，设计了基于关键链的项目调度方法。该方法首先采用基于优先规则的启发式算法生成工期最小的近优项目计划，再在该计划中嵌入输入缓冲和项目缓冲，保证项目计划在非确定环境下的稳定执行。论文引用RCPSPs的标准问题库PSPLIB中大量案例对算法进行了的仿真试验，结果表明本文方法较传统项目调度方法有很大改进，论文最后对仿真结果进行了深入讨论，并指出了未来的研究方向。     

Airport Gate Scheduling with Time Windows

In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Although we minimize walking distances (or travel time) in our objective function, the model is easily adapted for other material handling costs including baggage and cargo costs. Our objectives are achieved through gate assignments, where time slots alloted to aircraft at gates deviate from scheduled slots minimally. Further, the model can be applied to cross-docking optimization in areas other than airports, such as freight terminals where material arrival times (via trucks, ships) can fluctuate. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in Tabu Search and Memetic Algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.     

Robust design of flexible manufacturing systems using, colored Petri net and genetic algorithm

A method is presented for the robust design of flexible manufacturing systems (FMS) that undergo the forecasted product plan variations. The resource allocation and the operation schedule of a FMS are modeled as a colored Petri net and an associated transition firing sequence. The robust design of the colored Petri net model is formulated as a multi-objective optimization problem that simultaneously minimizes the production costs under multiple production plans (batch sizes for all jobs), and the reconfiguration cost due to production plan changes. A genetic algorithm, coupled with the shortest imminent operation time (SIO) dispatching rule, is used to simultaneously find the near-optimal resource allocation and the event-driven schedule of a colored Petri net. The resulting Petri net is then compared with the Petri nets optimized for a particular production plan in order to address the effectiveness of the robustness optimization. The simulation results suggest that the proposed robustness optimization scheme should be considered when the products are moderately different in their job specifications so that optimizing for a particular production plan creates inevitably bottlenecks in product flow and/or deadlock under other production plans.     

汽车装配车间生产计划与调度的同时优化方法

文中提出三种新方法来解决汽车装配车间生产计划与调度的同时优化问题.首先将汽 车装配线简化为一个Flow shop问题,并建立其混合整数规划模型,以求得使各装配工位的准 备成本和空闲时间尽可能少并尽可能满足产品需求的粗生产计划.然后在粗生产计划的基础上 考虑装配线的细节,用Tabu搜索法与快速调度仿真相结合的三种不同启发式算法使生产计划 与调度同时得到优化,并给出了三种算法的复杂性.大量算例的比较研究表明了这些算法的有 效性和适用性.     

A heuristic for the quay crane scheduling problem based on contiguous bay crane operations

Quay cranes (QC) are key resources at container terminals, and the efficiency of QC operations is vital for terminal productivity. The Quay Crane Scheduling Problem (QCSP) is to schedule the work activities for a set of cranes assigned to a single berthed vessel with the objective of minimizing the completion time of all container handling tasks. The problem is complicated by special characteristics of QC operations. Considering QC moving time and interference constraints, the concept of contiguous bay operations is proposed and a heuristic is developed to generate QC schedules with this feature. The heuristic is efficient and effective: it has polynomial computational complexity, and it produces schedules with a completion time objective bounded above by a small increment over the optimal completion time. Importantly, the heuristic guarantees that no quay cranes are idle due to interference. Numerical experiments demonstrate that the optimality gap is small for practical instances.     

Truck schedule recovery for solid waste collection in Porto Alegre, Brazil

This paper considers a truck schedule recovery problem in the context of solid waste collection in the city of Porto Alegre, Brazil. When a truck on a scheduled trip breaks down, a backup truck needs to be selected to serve the cargo on that trip and other trucks might be rescheduled in order to gain the minimum operating and delay costs. The problem consists of designing, in the case of a severe disruption in a trip, new schedules taking into account the existing trucks in the system and a set of unfinished and not initiated collection trips, on which the trucks collect the solid waste in fixed routes and empty the loads in one of the several operational recycling facilities. The main objective is to minimize the total distances traveled and delay costs, as well as to obtain balanced assignments of truck unloads into the recycling facilities, due to the social benefits of the solid waste program. We modeled the problem as a mixed-integer linear problem and used CPLEX to solve it. Finally, computational experiments are conducted on real-world data. The results show that our approach successfully reduces the distances traveled and delays, simultaneously balancing the number of trucks unloading at each recycling facility, in comparison with the current manual strategy.     

A Game Theoretical Approach for Improving the Operational Efficiencies of Less-than-truckload Carriers Through Load Exchanges

Less-than-truckload (LTL) transportation offers fast, flexible and relatively low-cost transportation services to shippers. In order to cope with the effects of economic recessions, the LTL industry implemented ideas such as reducing excess capacity and increasing revenues through better yield management. In this paper, we extend these initiatives beyond the reach of individual carriers and propose a collaborative framework that facilitates load exchanges to reduce the operational costs. Even though collective solutions are proven to provide benefits to the participants by reducing the inefficiencies using a system-wide perspective, such solutions are often not attainable in real-life as the negotiating parties are seeking to maximize their individual profits rather than the overall profit and also they are unwilling to share confidential information. Therefore, a mechanism that enables collaboration among the carriers should account for the rationality of the individual participants and should require minimal information transfer between participants. Having this in mind, we propose a mechanism that facilities collaboration through a series of load exchange iterations and identifies an equilibrium among selfish carriers with limited information transfer among the participants. Our time-efficient mechanism can handle large instances with thousands of loads as well as provide significant benefits over the non-collaborative management of LTL networks.

     

A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem

We study the joint problem of scheduling passenger and freight trains for complex railway networks, where the objective is to minimize the tardiness of passenger trains at station stops and the delay of freight trains. We model the problem as a mixed integer program and propose a two-step decomposition heuristic to solve the problem. The heuristic first vertically decomposes the train schedules into a passenger train scheduling phase and then a freight train scheduling phase. In the freight train scheduling phase, we use a train-based decomposition to iteratively schedule each freight train. Experimental results show the efficiency and quality of the proposed heuristic algorithm on real world size problems.     

A multi-objective approach for robust airline scheduling

We present a memetic approach for multi-objective improvement of robustness influencing features (called robustness objectives) in airline schedules. Improvement of the objectives is obtained by simultaneous flight retiming and aircraft rerouting, subject to a fixed fleet assignment. Approximations of the Pareto optimal front are obtained by applying a multi-meme memetic algorithm. We investigate biased meme selection to encourage exploration of the boundaries of the search space and compare it with random meme selection. An external population of high quality solutions is maintained using the adaptive grid archiving algorithm.The presented approach is applied to investigate simultaneous improvement of reliability and flexibility in real world schedules from KLM Royal Dutch Airlines. Experimental results show that the approach enables us to obtain schedules with significant improvements for the considered objectives. A large scale simulation study was undertaken to quantify the influence of the robustness objectives on the operational performance of the schedules. Rigorous sensitivity analysis of the results shows that the influence of the schedule reliability is dominant and that increased schedule flexibility could improve the operational performance.     

Framework for modelling and simulating the supply process monitoring to detect and predict disruptive events

Disruptive events that take place during supply process execution produce negative effects that propagate throughout a supply chain. Event management systems for supply chains have emerged to provide functionality for monitoring schedules, managing disruption, and repairing schedules affected by a disruptive event. A Web service that provides a schedule monitoring functionality for supply chain event management was developed. This paper provides a framework to allow enterprises that hire this service to develop simulation models of monitoring processes and evaluate their ability to detect and anticipate disruptive events. The framework, based on discrete event simulation, is implemented in a library that can be used for developing and testing monitoring processes by means of a friendly interface. A marine freight transport process was used as a case study to show how a supply process and its environment can be modelled and simulated by using the library. Simulation results show the ability of this approach to anticipate disruptive events and identify critical stages of a supply process in order to prevent disruptive events.     

A multi-agent-based approach for personnel scheduling in assembly centers

This paper presents a multi-agent-based approach for personnel scheduling problems in the context of a paced multi-product assembly center. Our purpose is to elaborate daily assignment of employees to workstations in order to minimize simultaneously the operational costs and personnel dissatisfactions. The proposed approach considers the individual competencies, mobility and preferences of each employee, as well as the personnel and competency requirements associated with each assembly activity given both the current master assembly schedule and the line balancing for each product. To benchmark the performance of the multi-agent approach, we use optimal solutions obtained through a linear programming model resolution using a commercial solver. Experimental results show that our multi-agent approach can produce high-quality and efficient solutions in a short computational time.