# A Multi-Strategy ALNS for the VRP with Flexible Time Windows and Delivery Locations
## 3 Problem Description and Formulation of the VRP-CS
### Problem Description  
The VRP-CS addressed in this paper seeks to optimize last-mile delivery operations by designing efficient vehicle routes while maximizing customer satisfaction. Formally, the problem can be defined as follows: Given a central depot, a fleet of homogeneous vehicles with limited capacity, and a set of customers each with specific demands and multiple potential delivery locations (each associated with a time window and influencing customer satisfaction based on arrival time), the objective is to determine a set of minimum cost vehicle routes originating and terminating at the depot such that all customer demands are met exactly once at one of their specified locations within its time window, vehicle capacities are not exceeded, route constraints are respected, and overall customer satisfaction (modeled using prospect theory) is maximized alongside cost minimization. The specific components of the problem are detailed below:  
* **Depot:** There is a single central depot (indexed as 0) from which all deliveries originate and where all vehicles must return after completing their routes. The depot has a specific operating time window, \([e_{0},l_{0}]\), defining the earliest departure time (\(e_{0}\)) and the latest allowed return time (\(l_{0}\)) for all vehicles. * **Vehicles:** A fleet of \(K\) homogeneous vehicles is available at the depot. Each vehicle \(k\in K\) has an identical maximum load capacity \(Q\) and operates at the same average travel speed \(v\). A fixed operating cost \(\theta_{k}\) may be associated with using each vehicle. * **Customers and Demands:** A set \(N=\{1,2,\ldots,m\}\) of customers requires delivery service. Each customer \(i\in N\) has a known demand \(q_{i}\), which must be fully satisfied by a single delivery (split deliveries are not allowed). The demand of each customer is assumed to be less than the vehicle capacity (\(q_{i}<Q\)). * **Delivery Options and Time Windows:** A key feature of the VRP-CS is delivery flexibility. Each customer \(i\in N\) provides a set \(L_{i}\) of acceptable optional delivery locations. For each potential delivery location \(a\in L_{i}\), there is a specific time window \([e_{ia},l_{ia}]\) during which the delivery must be started. If a vehicle arrives at a location before the earliest time \(e_{ia}\), it must wait until \(e_{ia}\) to begin service. Service at each location takes a constant time \(s\). The selection of a specific location \(a\in L_{i}\) and the timing of the service within \([e_{ia},l_{ia}]\) influences the route planning and customer satisfaction. Figure 1 illustrates this concept of multiple locations per customer itinerary. * **Costs:** The primary cost objective is to minimize the total operational cost. This includes the total distance traveled by all vehicles, calculated based on the distances \(d_{iajb}\) between the chosen delivery location \(a\) for customer \(i\) and location \(b\) for customer \(j\) (or the depot). Additionally, there is a cost component \(\theta_{e}\) associated with deviations from desired customer satisfaction levels, integrated into the objective function. * **Satisfaction Objective:** Distinct from traditional VRPs, the VRP-CS explicitly incorporates customer satisfaction as a second, conflicting objective to be optimized (maximized). Customer satisfaction \(\varepsilon_{ia}\) for customer \(i\) at location \(a\) is modeled as a nonlinear function based on prospect theory. It depends crucially on the actual service start time \(r_{ia}\) relative to the customer's psychological reference point \(w_{ia}\) for that location, capturing the asymmetric perception of gains (early/on-time arrival) versus losses (late arrival). The formal definition of this satisfaction function is provided in Section 3.4. The VRP-CS aims to find feasible routes and select one delivery option (location and associated time) for each customer to minimize the combined costs related to travel, vehicle usage, and customer dissatisfaction. As shown in Figure 1, each customer has their own itinerary.