Journal Articles (Peer-Reviewed)
Goel, Asvin and Stefan Irnich (In press):An Exact Method for Vehicle Routing and Truck Driver Scheduling Problems, Transportation Science.
Abstract: 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.
Herr, Oliver and Asvin Goel (2016):Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints, European Journal of Operational Research, 248(1): 123-135.
Abstract: 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.
Goel, Asvin (2014):Hours of Service Regulations in the United States and the 2013 Rule Change, Transport Policy, 33: 48-55.
Abstract: This paper studies the revised hours of serviceregulations for truck drivers in the United States which entered intoforce in July 2013. It provides a detailed model of the new regulationand presents and a new simulation-based method to assess the impact ofthe rule change on operational costs and road safety. Unlike previousmethodologies, the proposed methodology for assessing the impact ofhours of service regulations takes into account that, by optimizingroutes and schedules, carriers can minimize the economic impact ofstricter regulations. Simulation experiments are conducted indicatingthat the monetized safety benfiet of reducing the daily driving timelimits is on the same order of magnitude as the increase in operationalcosts.
Goel, Asvin and Thibaut Vidal (2014):Hours of Service Regulations in Road Freight Transport: An Optimization-Based International Assessment, Transportation Science, 48(3): 391-412.
Abstract: 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.
Goel, Asvin and Frank Meisel (2013):Workforce Routing and Scheduling for Electricity Network Maintenance with Downtime Minimization, European Journal of Operational Research, 231(1): 210-228.
Abstract: We investigate a combined routing and scheduling problem for the maintenance of electricity networks. In electricity networks power lines must be regularly maintained to ensure a high quality of service. For safety reasons a power line must be physically disconnected from the network before maintenance work can be performed. After completing maintenance work the power line must be reconnected. Each maintenance job therefore consists of multiple tasks which must be performed at different locations in the network. The goal is to assign each task to a worker and to determine a schedule such that the downtimes of power lines and the travel effort of workers are minimized. For solving this problem, we combine a Large Neighborhood Search meta-heuristic with mathematical programming techniques. The method is evaluated on a large set of test instances which are derived from network data of a German electricity provider.
Goel, Asvin, Claudia Archetti and Martin Savelsbergh (2012):Truck Driver Scheduling in Australia, Computers & Operations Research, 39(5): 1122-1132.
Abstract: In September 2008 new regulations for managing heavy vehicle driver fatigue entered into force in Australia. According to the new regulations there is a chain of responsibility ranging from drivers to dispatchers and shippers and thus, carriers must explicitly consider driving and working hour regulations when generating truck driver schedules. This paper presents and studies the Australian Truck Driver Scheduling Problem (AUS-TDSP) which is the problem of determining whether a sequence of locations can be visited within given time windows in such a way that driving and working activities of truck drivers comply with Australian Heavy Vehicle Driver Fatigue Law.
Goel, Asvin and Leendert Kok (2012):Truck Driver Scheduling in the United States, Transportation Science, 46(3): 317-326.
Abstract: The U.S. truck driver scheduling problem (US-TDSP) is the problem of visiting a sequence of λ locations within given time windows in such a way that driving and working activities of truck drivers comply with U.S. hours-of-service regulations. In the case of single time windows it is known that the US-TDSP can be solved in O(λ3) time. In this paper, we present a scheduling method for the US-TDSP that solves the single time window problem in O(λ2) time. We show that in the case of multiple time windows the same complexity can be achieved if the gap between subsequent time windows is at least 10 hours. This situation occurs, for example, if, because of opening hours of docks, handling operations can only be performed between 8.00 a.m. and 10.00 p.m. Furthermore, we empirically show that for a wide range of other problem instances the computational effort is not much higher if multiple time windows are considered.
Goel, Asvin (2012):A Mixed Integer Programming Formulation and Effective Cuts for Minimising Schedule Durations of Australian Truck Drivers, Journal of Scheduling, 15(6): 733-741.
Abstract: 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.
Goel, Asvin (2012):The Minimum Duration Truck Driver Scheduling Problem, EURO Journal on Transportation and Logistics, 1(4): 285-306.
Abstract: Truck driver scheduling problems are important subproblems of real-life vehicle routing and scheduling problems because rest periods required by government regulations have a significant impact on travel and arrival times and vehicle routes generated without considering these regulations are often practically infeasible. This paper presents a mixed integer programming formulation and a dynamic programming approach for solving a variant of the truck driver scheduling problem in which truck drivers may only rest at customer locations and at suitable parking lots. The objective of the problem is to find a truck driver schedule with minimal duration. The model presented in this paper is very flexible and can be configured to consider different sets of rules imposed by government regulations and union contracts. The effectiveness of the dynamic programming approach is demonstrated for working hour regulations in the United States and in the European Union.
Goel, Asvin and Louis-Martin Rousseau (2012):Truck Driver Scheduling in Canada, Journal of Scheduling, 15(6): 783-799.
Abstract: This paper presents and studies the Canadian Truck Driver Scheduling Problem (CAN-TDSP) which is the problem of determining whether a sequence of locations can be visited within given time windows in such a way that driving and working activities of truck drivers comply with Canadian Commercial Vehicle Drivers Hours of Service Regulations. Canadian regulations comprise the provisions found in U.S. hours of service regulations as well as additional constraints on the maximum amount of driving and the minimum amount of off-duty time on each day. We present two heuristics and an exact approach for solving the CAN-TDSP. Computational experiments demonstrate the effectiveness of our approaches and indicate that Canadian regulations are significantly more permissive than U.S. hours of service regulations.
Goel, Asvin and Leendert Kok (2012):Efficient Scheduling of Team Truck Drivers in the European Union, Flexible Services and Manufacturing Journal, 24(1): 81-96.
Abstract: This paper studies the problem of scheduling working hours of team drivers in European road freight transport where a sequence of lambda locations must be visited within given time windows. Since April 2007 working hours of truck drivers in the European Union must comply with regulation (EC) No 561/2006. These regulations impose standard limits on the daily driving times of truck drivers and extended daily limits that may only be used twice a week for each driver. We present a depth-first-breadth-second search method which can find a feasible schedule complying with standard daily driving time limits in O(lambda^2) time, if such a schedule exists. Furthermore, we show that this method can also be used to find schedules complying with regulation (EC) No 561/2006 if daily driving times may exceed the standard limit.
Goel, Asvin (2012):The Canadian Minimum Duration Truck Driver Scheduling Problem, Computers & Operations Research, 39(10): 2359-2367.
Abstract: In Canada transport companies must ensure that truck drivers can comply with Canadian Commercial Vehicle Drivers Hours of Service Regulations. Canadian regulations comprise the provisions found in US hours of service regulations as well as additional constraints on the maximum amount of driving and the minimum amount of off-duty time on each day. This paper presents a mixed integer programming formulation and an iterative dynamic programming approach for minimising the duration of truck driver schedules complying with Canadian hours of service regulations. Computational experiments show that schedule durations can be significantly reduced compared with a previously presented approach which only focuses on feasibility.
Goel, Asvin (2010):The Value of In-Transit Visibility for Supply Chains with Multiple Modes of Transport, International Journal of Logistics, 13(6): 475-492.
Abstract: This study seeks to quantify the value of visibility over assets moving through an multi-modal transportation network. It presents a transportation model combining shipment and route choice and shows how in-transit visibility can be used to adjust the transportation plan with respect to the known state of the transportation system. By simulating the decision making process with different levels of visibility the gradual benefits of in-transit visibility are quantified. Computational experiments show that on-time delivery performance can be significantly improved by increasing the level of visibility.
Goel, Asvin (2010):Truck Driver Scheduling in the European Union, Transportation Science, 44(4): 429-441.
Abstract: Since April 2007 working hours of truck drivers in the European Union are controlled by regulation (EC) No. 561/2006. According to the new regulation, road transport undertakings must organise the work of drivers in a way that drivers are able to comply with the regulations and can be made liable for infringements committed by the drivers. Although of particular importance in long-distance haulage, regulations on working hours of truck drivers have received very little attention in the scheduling literature. This paper presents a method for scheduling driving and working hours of truck drivers with respect to regulation (EC) No. 561/2006. Given a sequence of locations to be visited within specified time windows, the approach is guaranteed to find a schedule complying with the regulation if such a schedule exists.
Goel, Asvin (2009):Vehicle Scheduling and Routing with Drivers' Working Hours, Transportation Science, 43(1): 17-26.
Abstract: Regulations regarding drivers’ working hours often have a big impact on total transit times, i.e., the time required for driving periods, breaks, and rest periods. Although of particular importance for many real-life applications, they have received only very little attention in the vehicle routing literature. This paper describes the new regulations for drivers’ working hours in the European Union that entered into force in April 2007. According to the new regulations, motor carriers must organise the work of drivers in such a way that drivers are able to comply with the respective regulations and are made liable for infringements committed by the drivers. This paper shows how motor carriers can schedule driving periods, breaks, rest periods, and handling activities, and presents a large neighbourhood search algorithm capable of generating vehicle tours complying with the new regulations.
Goel, Asvin and Volker Gruhn (2008):A General Vehicle Routing Problem, European Journal of Operational Research, 191(3): 650-660.
Abstract: In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.
Goel, Asvin (2012): Lenk- und Ruhezeitenregelungen im Straßengütertransport, Martin-Luther-Universität Halle-Wittenberg, Juristische und Wirtschaftswissenschaftliche Fakultät: Halle (Saale).
Goel, Asvin (2008): Fleet Telematics – Real-time Management and Planning of Commercial Vehicle Operations, Springer US: Boston, MA.
Abstract: 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.