Modeling and optimizing routing problems with customer satisfaction under stochastic travel times

Customer satisfaction is crucial in fostering loyalty and trust, serving as a fundamental pillar in contemporary business strategies. However, in routing problems, achieving high customer satisfaction often incurs significant operating costs. Delivery time, defined as the moment when services are provided to customers, emerges as a vital component influencing the satisfaction level. This paper introduces a novel delivery rule and formulates a model incorporating a chance constraint. The proposed model optimizes the total operational costs while maintaining high customer satisfaction levels in the vehicle routing problems with random travel times. Furthermore, this paper considers that the relationship between the delivery time and the satisfaction level is nonlinear. We employ the piece-wise linear techniques to approximate the nonlinear satisfaction function, thus improving realism and tractability. Moreover, we extend our model to include considerations for the vehicle waiting time and overtime, which enhances vehicle resource utilization. We use the sample average approximation method to address the proposed stochastic model. Subsequently, we develop a tailored solution procedure based on the Large Neighborhood Search (LNS) algorithm to solve the resulting large-scale mixed integer problem. Numerical experiments demonstrate the efficacy of our proposed model and the computational efficiency of our tailored LNS-based algorithm.