State Aggregation and Lower Bound-Based ADP Approach for Dynamic Pick-Up Routing Problem With Capacity Constraint

The significant surge in e-commerce sales has made parcel delivery services exceedingly popular. In this paper, we investigate a dynamic parcel pick-up problem where a vehicle with limited capacity collects customers’ parcels on a closed tour. We consider stochastic demand, stochastic service requests, and stochastic service cancellations simultaneously. Aimed at minimizing the total travel distance of the vehicle, we formulate the problem as a Markov decision process and jointly apply state aggregation and approximate dynamic programming (ADP) to overcome the curse of dimensionality in solution solving. First, we introduce the concept of
$aggregation~granularity$
, which refers to the number of states that are combined into a single common vector. Based on the cardinalities of the post-decision state’s component sets, we propose a state aggregation method that reduces the size of the state searching space from exponential to quartic. By utilizing this aggregation, our routing policy is represented implicitly by state value functions that are stored in a lookup table in memory. Second, we develop a novel and well-performing ADP-based routing policy that differs from the general ADP-based policy. We derive a lower bound of the post-decision state value function and use it in policy development. Third, during online execution, we apply a rollout algorithm with the lower bound-based policy as its base policy, resulting in an online rollout policy. Finally, through numerical analysis, we examine the impact of
$aggregation~granularity$
and the advantages of the online rollout policy.