Prof. Dr.
Asvin Goel

In this paper we study the problem of scheduling a given sequence of activities where each activity consumes a resource with limited availability. Activity durations as well as resource consumptions are assumed to be time-dependent. Because of the interaction of time-dependent activity durations and resource consumptions, scheduling policies based on starting each activity in the sequence as early as possible may fail due to unnecessarily high resource consumptions exceeding the limited availability of the resource. We propose a dynamic discretization discovery algorithm that generates a partially time-expanded network during the search. We propose an acceleration technique allowing to significantly reduce the computational effort if the approach is embedded in an iterative solution procedure that frequently evaluates activity sequences which start with the same activities. Furthermore, we extend our approach to the case where resources can be replenished between subsequent activities. We evaluate our approach as a route evaluation method for the case of routing a fleet of electric vehicles in which travel durations and the energy consumed when travelling from one location to another depend on the time of the day.

In most developed countries working hours of truck drivers are constrained by hours of service regulations. When optimizing vehicle routes, trucking companies must consider these constraints to assure that drivers can comply with the regulations. This paper studies the combined vehicle routing and truck driver scheduling problem (VRTDSP), which generalizes the well-known vehicle routing problem with time windows by considering working hour constraints. A branch-and-price algorithm for solving the VRTDSP is presented. This is the first algorithm that solves the VRTDSP to proven optimality.

This paper considers a single machine scheduling problem in which each job to be scheduled belongs to a family and setups are required between jobs belonging to different families. Each job requires a certain amount of resource that is supplied through upstream processes. Therefore, schedules must be generated in such a way that the total resource demand does not exceed the resource supply up to any point in time. The goal is to find a schedule minimising total tardiness with respect to the given due dates of the jobs. A mathematical formulation and a heuristic solution approach for two variants of the problem are presented. Computational experiments show that the proposed heuristic outperforms a state-of-the-art commercial mixed integer programming solver both in terms of solution quality and computation time.

Driver fatigue is internationally recognized as a significant factor in approximately 15%–20% of commercial road transport crashes. In their efforts to increase road safety and improve working conditions of truck drivers, governments worldwide are enforcing stricter limits on the amount of working and driving time without rest. This paper describes an effective optimization algorithm for minimizing transportation costs for a fleet of vehicles considering business hours of customers and hours of service regulations. The algorithm combines the exploration capacities of population-based metaheuristics, the quick improvement abilities of local search, with forward labeling procedures for checking compliance with complex hours of service regulations. Several speed-up techniques are proposed to achieve an overall efficient approach. The proposed approach is used to assess the impact of different hours of service regulations from a carrier-centric point of view. Extensive computational experiments for various sets of regulations in the United States, Canada, the European Union, and Australia are conducted to provide an international assessment of the impact of different rules on transportation costs and accident risks. Our experiments demonstrate that European Union rules lead to the highest safety, whereas Canadian regulations are the most competitive in terms of economic efficiency. Australian regulations appear to have unnecessarily high risk rates with respect to operating costs. The recent rule change in the United States reduces accident risk rates with a moderate increase in operating costs.

Due to globalisation and liberalisation of markets more goods are transported world wide than ever before. Inland transportation within the European Union has almost doubled between 1970 and 2000 and is expected to further increase by about 25% until 2010 and by almost 90% until 2030. It appears that this considerable growth is almost entirely realised by road transport. As a result, road pricing systems are increasingly deployed to reduce congestion of the road network and to finance infrastructural development. The deregulation in the European road transport market, in particular, the allowance of cabotage operations, increases competition and motor carriers from emerging countries more and more challenge motor carriers from developed countries by comparably lower wages. Global competition forces manufacturing companies to improve the quality of their products and to reduce their manufacturing costs. As a result, manufacturing companies increasingly apply just-in-time practices in order to cut down inventory costs. Obviously, just-in-time practices necessitate punctual, reliable, and flexible transportation, as with reduced inventory buffers any mismatch between supply and demand can result into significant disturbances of manufacturing processes. To face these challenges motor carriers have to increase the quality of service and reduce costs. Fleet Telematics - Real-Time Management and Planning of Commercial Vehicle Operations shows how motor carriers can increase punctuality, reliability, flexibility, and transparency of transportation services, and, at the same time, reduce empty mileage and low vehicle utilisation. The book presents a telematics-enabled information system alleviating a major obstacle for computer-based real-time decision support: the lack of timely and reliable information. A real-time decision support system is presented which achieves its strength from several specialised actors who collaboratively and concurrently modify problem data and solution, using different problem knowledge and solution techniques: dispatchers, a Messaging & Fleet Monitoring System, and a Dynamic Planning System. Several heuristic planning methods are presented which can be used to dynamically solve transportation problems incorporating a variety of real-life constraints that are not considered by the classical models found in the literature. Among those are the new regulations for drivers’ working hours in the European Union which entered into force in April 2007. With the improved availability of timely and reliable information provided by the Messaging & Fleet Monitoring System, and the real-time decision support provided by the Dynamic Planning System, this book gives an important contribution to increasing the efficiency of commercial vehicle operations.