Policies for multi-trip route planning in time-sensitive environments
摘要
This paper considers time-sensitive situations that require transporting items from their current locations to a central processing facility using a single capacitated vehicle, where transportation service duration has a negative impact on the items. Such situations arise when collecting perishable products, e.g., milk or fresh-cut flowers, or in time-sensitive service systems. In such cases, a dispatcher wishes to determine a route plan that minimizes the total negative impact on the collected items during transportation. Motivated by the time-sensitive nature of the problem, in this paper, we focus on developing efficient closed-form policies for the dispatcher to determine how to allocate nodes to multiple routes operated by a single vehicle, which we call the Time-Sensitive Collection Allocation Problem. We introduce a formulation that employs the traveling salesman tour length estimation model from Beardwood et al. (Math. Proc. Camb. Philos. Soc. 55(4):299–327, 1959). Assuming a linear negative effect over time, we characterize an optimal solution to the allocation decision for both uncapacitated and capacitated versions of the relaxed model and devise a heuristic using this characterization to obtain a near-optimal integer solution quickly. Our closed-form allocation policy enables solving the underlying routing problems more efficiently in real time.