Scheduling and shortest path for trucks with working hours and parking availability constraints

摘要

The US Hours-of-Service (HOS) regulations require truck drivers to take regular breaks. However, drivers often have difficulty finding appropriate rest locations due to truck parking shortages. This may have a significant impact on drivers' safety and productivity, cost to industry and environment. In this paper, we propose a model that takes into account parking availability when planning long-haul truck shipments in addition to HOS constraints. Given an ordered set of clients, the proposed method plans a minimum cost route and schedule such that the itinerary is regulation-compliant, and the driver is guaranteed to find parking at all scheduled stops. The problem is modeled as a shortest path problem with resource constraints, and a label correcting algorithm is used to generate optimal solutions. Computational experiments are used to compare the cost of solutions that use parking availability information with ones that do not. The cost of disregarding parking information was estimated by simulating drivers' behavior when parking is unavailable and applying time and cost penalties. The effect of parking availability and alternative routes on trip costs is also studied, aiming to illustrate that disregarding these factors can lead to significant errors in cost estimates. Results show that, although imposing parking constraints can significantly increase costs, preventing accident-related costs can make it advantageous in the long-term. (c) 2021 Elsevier Ltd. All rights reserved.In 2015, a survey by the Federal Highway Administration identified truck parking shortages in 36 US states, with more pronounced issues along major trade corridors ( U.S. Department of Transportation, 2015 ). The lack of truck parking can have significant impact on road safety, industry costs, and the environment ( Rodier et al., 2010; Sochor and Mbiydzenyuy, 2013 ), and ranked among the trucking industry's top concerns in recent surveys by the American Transportation Research Institute (ATRI) ( American Transportation Research Institute, 2019 ). Due to the Hours-of-Service (HOS) regulations, truck drivers are required to take regular breaks. These rules aim to