Scheduling and routing of service trucks and planning of resource replenishment locations for winter roadway maintenance

Routing Optimization;Dynamic Fleet Scheduling;Facility Location Design;Approximate Dynamic Programming;Concave Adaptive Value Function Estimation;Continuous Approximation;Genetic Algorithm;Transportation Planning and Logistics Systems

Hajibabai Dizaji, Leila

关键词: Routing Optimization;    Dynamic Fleet Scheduling;    Facility Location Design;    Approximate Dynamic Programming;    Concave Adaptive Value Function Estimation;    Continuous Approximation;    Genetic Algorithm;    Transportation Planning and Logistics Systems;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/72782/Leila_Hajibabai%20Dizaji.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Routing of snow plow trucks in urban and regional areas encompasses a variety of complex decisions, especially for jurisdictions with heavy snowfall. The main activities involve dispatching a fleet of plow trucks from a central depot and/or satellite facilities to clean and spread salt/chemicals on the network links (a.k.a. snow routes). We propose a mixed integer linear program (MILP) model to minimize the total operation time of all snow plow trucks needed to complete a given set of snow routes with multiple plowing priorities, and to reduce the longest individual truck operation time in order to balance the distribution of such travel times for multiple classes of priority. The objective of the formulation includes the weighted sum of the total deadhead travel time and longest individual snow plow truck cycle time. A set of customized construction and local search methods are developed to effectively solve the problem. Empirical case study with real-world data shows that the proposed solution approach is able to optimize snow routes (with or without considering priorities of plowing tasks) in a short amount of time and the model result outperforms the current solution in practice. We also develop a state-of-art snow plow routing software with optimization modules and user-friendly GIS interfaces for snow route analysis and design. This decision-support software optimizes a set of snow plow routes based on a set of user input parameters, and it can help stake-holders, engineers, and planners evaluate snow plow options (such as salt usage, vehicle capacities, fleet size, plowing time during the day) and provide recommendations on vehicle assignments to snow routes. It also includes sufficient flexibility such that experts can further fine-tune the results before field implementation.Furthermore, it is sometimes challenging to plan winter maintenance operations in advance because snow storms are stochastic with respect to, e.g. start time, duration, impact area, and severity. Based on progression of the snow storm, additional maintenance demand is arising either periodically or randomly over time and space. Besides, maintenance trucks may not be readily available at all times due to stochastic service disruptions. For instance, the operations of trucks are sometimes subject to failure, possibly due to traffic congestion or mechanical breakdowns. A stochastic dynamic fleet management model is developed to assign available trucks to cover uncertain snow plowing demand. Some tasks, especially those on critical roadway links (such as emergency routes), often have priority and impose a strict service time window constraints (i.e., one or more time periods during which these tasks could be completed) to the fleet schedule. Violation to these time windows may result in severe penalties. In addition, in case service disruption occurs, the backlogged tasks will be counted as new tasks that must be addressed in the next time period. A truck in one specific location and time can be dynamically “repositioned”, to a different location, but at a cost. This could occur to in-service trucks which would leave currently assigned tasks in order to serve potentially high priority regions (especially in case of service disruptions), replenish salt or chemicals, etc.). This could also occur to idling vehicles in anticipation of future tasks in certain regions. For simplicity, we assume that all truck repositioning requires exactly one time period. The objective is to simultaneously minimize the cost for truck deadheading and repositioning, as well as to maximize the benefits (i.e., level of service) of plowing. The problem is formulated into a dynamic programming model and solved using an approximate dynamic programming (ADP) algorithm. Piece-wise linear functional approximations are used to estimate the value function of system states (i.e., snow plow trucks location over time). We apply our model and solution approach to a snow plow operation scenario for Lake County, Illinois. Numerical results show that the proposed algorithm can solve the problem effectively and outperforms a rolling-horizon heuristic solution.On the other hand, efficiency of winter maintenance service can be affected by the number and location of resource replenishment facilities that snow plow trucks visit during maintenance operations. Hence, it is beneficial to simultaneously consider a strategic plan for facility location design as well as transportation network expansion (especially in the neighborhood of the salt replenishment locations, i.e., network bottlenecks) to facilitate truck routing/traffic operations. Furthermore, routing cost of service trucks under these strategic network decisions shall also be considered. Therefore, an integrated mathematical model for salt dome facility location design is developed, which determines the optimum number and location of the salt domes, optimal traffic assignment, snow plow trucks routing cost based on the optimal network design, and possible roadway capacity expansion. The objective is to minimize the total cost for salt dome facility construction, transportation infrastructure expansion, transportation delay (for both snow plow truck movements and public travel), as well as deadhead travel. A genetic algorithm (GA) framework (with embedded traffic assignment and continuous approximation (CA) algorithms) is developed. The numerical results show that the integrated solution technique can solve the problem effectively. It shall be noted that although this part of the dissertation research focuses on the strategic network design for salt dome facilities and snow plow roadway transportation, the model and solution techniques are suitable for a number of application contexts that simultaneously involve network traffic equilibrium, truck routing, infrastructure expansion, and facility location choices (which determine the origin/destination of multi-commodity flow).