# A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations
## 2 Literature Review
### The Vehicle Routing Problem Considering Customer Satisfaction  
Nowadays, e-commerce platforms in the market have established an online delivery service evaluation system, which prompts logistics providers to pay attention to customer satisfaction and take improving customer satisfaction as a major key to improving their competitiveness. Therefore, the study of customer satisfaction has also become an important research direction for related researchers and practitioners in the field of logistics service supply chain. In the research field of the VRP, some scholars have conducted research on customer satisfaction. Unlike delivery time, customer satisfaction is an abstract concept, and scholars have proposed different approaches to analyze customer satisfaction. Early studies mainly associated customer satisfaction with delivery punctuality. [PERSON] [16] considers customer satisfaction in a VRP with simultaneous pickup and delivery; they argue that customer satisfaction is inversely proportional to the amount of time the customer waits for the vehicle, that each delivery has to be met as early as possible, and that their problem aims to improve total customer satisfaction. [PERSON] et al. [17] use delivery punctuality as an evaluation criterion for customer satisfaction: when the delivery occurswithin the time window, the customer feels fully satisfied; otherwise, the customer will feel dissatisfied. In their study, they use average satisfaction as the target, which effectively improves the average customer satisfaction by a small increase in the cost. To better capture subjective perceptions, some scholars introduced piecewise functions to model customer satisfaction. [PERSON] et al. [18] propose a segmented linear fuzzy time window service level function by using a combination of soft- and hard-time windows combined with delivery time to explain subjective customer satisfaction. [PERSON] et al. [19] aimed to ensure customer satisfaction by improving time consistency and driver consistency, while also taking driver fairness into account. They proposed an adaptive large neighborhood search algorithm to address this problem, effectively ensuring consistency in drivers' travel distances. [PERSON] et al. [20], on the other hand, proposed a segmented linear function incorporating a time window to assess customer satisfaction. For customers who complete the delivery before the time window, they show complete satisfaction; for customers who complete the delivery after the time window, their satisfaction is minimized. Within the time window, satisfaction decreases linearly as delivery is delayed. In this way, customer satisfaction can be assessed based on the specific time when delivery occurs. [PERSON] et al. [21] proposed a segmented rating method for assessing customer satisfaction. Completion of deliveries in different time windows produces different satisfaction ratings, which are used as an evaluation metric for customer satisfaction. [PERSON] et al. [22] considered dual aspects of customer satisfaction in community group buying, including time satisfaction and freshness satisfaction. They used a piecewise function to evaluate customer satisfaction corresponding to different service times. However, these piecewise linear models often oversimplify customer psychology. [PERSON] [23] considers customer satisfaction in a consistent vehicle routing problem with heterogeneous fleet, and they use the consistency of the service and the consistency of the delivery time as the target as a way of improving overall customer satisfaction to ensure customer retention and brand loyalty. [PERSON] et al. [24] investigated the impact of delivery timeliness on customer satisfaction and observed that customer satisfaction exhibits different trends when delivery occurs in the early versus the late stages of the customer's time window. [PERSON] et al. [25] categorized customers based on their delivery time preferences and proposed a fuzzy clustering optimization approach to guide logistics enterprises in effective distribution management.