Choice-Based Periodic Vehicle Routing and Pricing for Urban Last-Mile Deliveries

Abstract

In urban periodic deliveries, business customers exhibit heterogeneous preferences over price, visit frequency, timing, and time window length. Ignoring such heterogeneity leads to service designs that misalign with customer needs. We propose the choice-based periodic vehicle routing and pricing problem (CB-PVRP), which incorporates stochastic customer choices into joint optimization of service offering, pricing, and vehicle routing. We formulate CB-PVRP as a two-stage stochastic mixed-integer program. The first stage determines offerings and pricing to maximize expected profit. The second stage, which embeds a bilevel structure, decides daily routing subject to revealed choices. We capture preference heterogeneity using a multinomial logit model with segmentation. We apply sample average approximation to address stochasticity and propose linear best-response sets for the bilevel reformulation. Our tailored logic-based Benders decomposition algorithm outperforms a commercial solver on solution quality and speed. By incorporating customer choice behaviors, the provider achieves higher expected profitability while customers receive improved services.