Vehicle Rescheduling with Delivery Delay Considering Perceived Waiting Cost of Heterogeneous Customers

Abstract

The original schedule may not be optimal or feasible due to delivery delay caused by disruption. To solve the vehicle rescheduling problem with delivery delay based on loss aversion in prospect theory and customer heterogeneity, a mathematical model is established to minimize the sum of distance cost and penalty cost. Next, an improved compressed annealing algorithm with heterogeneous pressure is proposed to solve the model. Finally, numerical experiments are executed on the basis of 30 classic Solomon benchmarks to test the performance of the proposed solution approach. Sensitivity tests are carried out for the customer waiting sensitivity parameter, the length of delay time, and the time when the delivery delay occurs. The computational results show that, compared to the traditional rescheduling method, the higher the degree of customer heterogeneity, the longer the length of delay time, and, the earlier the distribution delay occurs, the stronger the validity and practicability of the model and algorithm proposed in this paper.

1. Introduction

Distribution service is one of the important parts of modern logistics management. The question of how to provide timely and satisfactory distribution service for customers is the concern of every logistics and distribution provider. However, because of the complication of distribution circumstances, there are often random or unpredictable disruptions, such as vehicle failure, road congestion, bad weather, and other events, which eventually lead to delivery delay. Therefore, the original schedule may not be feasible, resulting in failure of order fulfillment and negative effects on service quality. In reality, customers are not completely rational when facing delivery delay. Their perception of delivery delay will be affected by psychological behaviors, such as reference dependence, loss aversion, and judgmental distortion. Customers are of bounded rationality. At the same time, customers themselves are heterogeneous; different customers react differently to the same delivery delay. Therefore, when delivery delay occurs, how to generate a new schedule fully considering the bounded rationality and heterogeneity of customers is a significant but challenging problem.

Due to the randomness, dynamics, and unpredictability of the events that lead to delivery delay, vehicle rescheduling after the delivery delay will be a complex optimization problem. To solve this problem, researchers have conducted a great deal of work. There are two strategies to deal with the disruption: the pro-active strategy and the reactive strategy. The pro-active strategy is to treat the events and delay time that lead to delay as random variables before the occurrence of disruption. For example, Gao et al. [1] regard driving time as a random variable with a certain distribution and study the strategies for vehicle routing under a random time-dependent road network. Schmid [2] applies relocation strategies to solve the dynamic ambulance relocation and dispatching problem using approximate dynamic programming. There are studies on request assignment strategies dealing with real-time vehicle routing problems [3,4,5].

The reactive strategy is to generate a new schedule after the delay occurs, which is called rescheduling. There are two rescheduling strategies to deal with delivery delay: local optimization and global optimization. Local optimization is based on disruption management, which tries to adjust the original schedule dynamically and generate a new schedule that reflects the changed environment while minimizing the deviation [6]. Potvin et al. [7] construct a mathematical model with the objective of minimizing vehicle travel time, lateness at customer locations, and lateness at the depot, with the disruption of new customer demand and travel time delay. Jiang et al. [8] construct an attitude-based model of disruption management to cope with delivery delay and put forward an improved ant colony optimization to obtain the solution. Hu and Sun [9] set up knowledge-based modeling for disruption management in urban distribution. Mu and Eglese [10] try to solve the disrupted capacitated vehicle routing problem with order release delay. Wang et al. [11] construct a recovery model for combinational disruptions in logistics delivery with the consideration of real-world participants. Disruption management can also be applied in flow shop scheduling and post-disaster medical assistance team scheduling [12,13].

Global optimization is based on global rescheduling. The related studies are as follows: Huisman et al. [14] propose a robust method to solve the multi-vehicle scheduling problem with travel time delay; Li et al. [15,16] study the real-time vehicle rescheduling problem under the condition of vehicle damage and propose a Lagrange relaxation algorithm based on an insertion heuristic; Larsen et al. [17] propose an effective waiting strategy to deal with dynamic customers and set up a mathematical model with the objective of minimizing delivery delay and total distance for a vehicle rescheduling problem; Yang et al. [18] build a general framework of dynamic vehicle scheduling for dynamic customers.

The existing research provides ideas for solving the vehicle routing problem with disruption from different perspectives, most of which focus on the field of operation research. However, distribution is a typical human–machine service system that includes many participants; it is necessary to consider human psychological behavior. Meanwhile, the existing research has overlooked the bounded rationality and heterogeneity of customers, and psychological behavior is neglected in the existing studies. The fact is that customers are heterogeneous and react differently to the same disruption. Delivery delay would lead to customer waiting. In the field of marketing research, a large number of studies have been conducted on waiting from the perspective of empirical research, indicating that waiting caused by service delay will reduce customer satisfaction, service quality, customer loyalty, and the profits of service providers in the long run [19,20,21]. Customer satisfaction for distribution service is influenced by customer waiting caused by delivery delay. Taking into account the bounded rationality and heterogeneity of customers, customer waiting would be measured by the perceived waiting cost for heterogeneous customers facing delivery delay. Therefore, it could help generate the more satisfactory schedule that combines the perceived waiting cost. There are two ways to measure waiting cost [22]: one is to build a corresponding mathematical model based on queueing theory, which is also the basis of most research in the area of operation research; the other is to build a psychological model of waiting; that is, absolute waiting time is replaced by perceived waiting time, and the relevant psychological factors (fairness, fear, separated waiting) that affect perceived waiting time are fully considered. In this paper, a psychological model of waiting is established to quantify the perceived waiting cost of customers facing delivery delay. Speaking of bounded rationality, prospect theory [23] is pioneering research. The main finding is that individuals assess their loss and gain perspectives in an asymmetric manner, which is also called loss aversion. Customers show risk aversion in the face of loss, risk preference in the face of gain, and are more sensitive to loss than gain. Prospect theory has been applied in many fields of operation and management. Hsu et al. [24] have shown that the relationship between service quality and customer loyalty has the characteristics of loss aversion; that is, in the face of different service quality, customers have an asymmetric response. Suzuki et al. [25] have established a mathematical model to study the asymmetric influence of customer behavior on service quality by using loss aversion theory. Jiang et al. [26] present an approach that combines prospect theory and fuzzy theory to measure the deviation and demonstrate a recovery model by taking human behavior into account. Xu et al. [27] develop a general travel decision-making rule utilizing cumulative prospect theory as a measure of commute utility and establish a general utility measurement system. Liu et al. [28] present a method for risk decision-making considering the decision-maker’s behavior in emergency response based on cumulative prospect theory. Liu et al. [29] focus on a rescheduling problem dealing with the disruption that a quay crane breaks down unexpectedly in the middle of the execution of a planned schedule, and behavior perception-based disruption models are constructed based on prospect theory. Yang et al. [30] deal with a capacitated lot-sizing and scheduling problem under a disruption environment and a non-linear mixed integer programming model is constructed with the objective of minimizing the negative deviation based on prospect theory. To sum up, prospect theory has been widely used to solve various decision-making problems. Therefore, how to incorporate prospect theory into vehicle rescheduling with delivery delay deserves more attention.

To address the resulting time-constrained routing problem, we focus on a traveling-salesman problem with time windows (TSPTW). Solution approaches for the TSPTW range from exact mathematical programming techniques to various heuristic approaches. Exact methods have been studied extensively [31,32,33,34,35]. Because of limitations with exact formulations, there exist many studies focusing on heuristic techniques for TSPTW [36,37,38,39,40,41]. Karunanidy et al. [42] propose a novel Java macaque algorithm based on the genetic and social behavior of Java macaque monkeys to solve an intelligent optimized route-discovery model. Xu et al. [43] demonstrate an improved ant colony algorithm based on the rank 2 matrix approximation method for an aircraft scheduling problem. Kovács et al. [44] investigate the fitness landscape of a complex vehicle routing problem and propose a novel genetic algorithm optimization variant for the traveling salesman problem. Bai et al. [45] propose effective algorithms for single-machine learning-effect scheduling to minimize completion-time-based criteria with release dates. Bai [46] investigates the performance of two online algorithms based on the shortest processing time among available jobs rule and provides a new lower bound with performance guarantee for a flow shop scheduling problem with release dates.

Ohlmann and Thomas [47] present a solution approach to TSPTW utilizing compressed annealing. Using a variable penalty function and stochastic search, they consider solutions infeasible with respect to time windows during a search for optimal or near-optimal solutions. Computational testing shows that the variable penalty approach generally outperforms simulated annealing with a suitable static penalty method. They use a single penalty term to penalize time-window violation for n customers. López-Ibánez et al. [48] present an adaptation of the compressed annealing algorithm from the travel time variant of the traveling salesman problem with time windows to the variant that considers makespan optimization. Comprehensive experimental analysis has shown that compressed annealing performs significantly better than algorithms recently proposed specifically for makespan optimization. Basdere and Bilge [49] apply a heuristic method based on compressed annealing to the aircraft maintenance routing problem that verifies compressed annealing is very effective in finding high-quality solutions quickly. In the large-scale instances where exact methods fail to find even feasible solutions, the compressed annealing method returns feasible solutions within the first two minutes. Zhang and Ni [50] study the traveling salesman problem with multiple time windows and design a two-stage heuristic algorithm based on the compressed annealing algorithm. Motivated by this, our solution approach has some similarity but two essential differences: (1) the time-window violation in our model is the perceived waiting cost quantitatively represented using loss aversion in the sense that customers are of bounded rationality; and (2) the penalty multiplier is variable not only according to pressure but also according to individual waiting sensitivity in the sense that customers are heterogeneous.

In this paper, we try to cope with delivery delay under TSPTW from a behavioral perspective. First, we describe the bounded rationality of customers using loss aversion, which is modeling of the perceived waiting cost in terms of delivery delay. Second, the mathematical model is formulated for TSPTW with perceived waiting cost (TSPTW-PWC). Then, this paper aims to propose an algorithm to achieve a reactive schedule to cope with delivery delay. For this purpose, an improved compressed annealing algorithm with heterogeneous pressure (ICAHP) is developed. The remainder of this paper is summarized below. Section 2 analyzes the problem and presents an approach combining loss aversion to measure the perceived waiting cost for delivery delay, based on which the rescheduling model is constructed. In Section 3, we present an improved compressed annealing algorithm and discuss related parameters. The numerical experiment is conducted in Section 4, where comparative studies are made in terms of distance cost, penalty cost, and total cost. We conclude by summarizing our research and identifying areas for further study in Section 5.

2. Problem Description and Formulation

2.1. Model for Original Scheduling

2.1.1. Definition of the Problem before Disruption

The enterprise selects self-operated or third-party logistics to fulfill the order, and the logistics owner sets up the delivery plan that meets the customer’s requirements. To highlight the research questions, the problem is confined to the following conditions:

• A distribution center has only one vehicle to deliver goods to multiple customers. The vehicle starts from the distribution center, distributes the loaded goods to the designated customers, and then returns to the distribution center, which is the classic TSP problem;
• The vehicle has a fixed loading capacity that cannot be exceeded when fully loaded; demand and load capacity are not considered;
• Each customer has a time window during which customer i must be visited and the service must be finished. If the vehicle arrives before the earliest service time, waiting is permitted, which is the classic TSPTW problem;
• The original schedule has been given and the initial plan can satisfy the time windows of all customers.

2.1.2. Notations

To formally define the TSPTW, let $G=\left(N,R\right)$ be an undirected graph, where $N=\left\{0,1,2,\cdots ,n,n+1\right\}$ is the finite set of nodes or customers; let customer 0 denote the depot and assume that every tour begins and ends at the depot $n+1$. We assume that there exists an arc set $R=\left\{\left(i,j\right)\mid i\in N\backslash \left\{n+1\right\}, j\in N\backslash \left\{0\right\}, i\ne j\right\}$. A tour is defined by the order in which n customers are visited and denoted by $s=\left\{p_0,p_1,p_2,\cdots ,p_n,p_{n+1}\right\}$, where p_i denotes the index of the customer in the ith position of the tour.

$c_{ij}$: cost for traversing from customer $i$ to customer $j$;

$t_{ij}$: traveling time from customer $i$ to customer $j$;

$t_i$: arrival time at customer $i$;

$b_i$: the time at which service starts at the ith customer;

$s_i$: service time for customer $i$;

$[t_i^l,t_i^u]$: time window for customer $i$;

$x_{ij=}\{\begin{array}{ll}1,& vehicle traveling from customer i to customerj\\ 0,& otherwise\end{array}$

2.1.3. Mathematical Model

The TSPTW model is constructed as follows:

$$\min g\left(s\right)={\displaystyle \sum }_{i=0}^n{\displaystyle \sum }_{j=1}^{n+1}{c}_{ij}*x_{ij}$$

(1)

Subject to:

$$x_{ij}\in \left\{0,1\right\}\forall i\in N\backslash \left\{n+1\right\}, j\in N\backslash \left\{0\right\}, i\ne j$$

(2)

$${\displaystyle \sum }_{j\in N\backslash \left\{0,i\right\}}{x}_{ij}=1 \forall i\in N\backslash \left\{n+1\right\}$$

(3)

$${\displaystyle \sum }_{i\in N\backslash \left\{j,n+1\right\}}{x}_{ij}=1 \forall j\in N\backslash \left\{0\right\}$$

(4)

$$b_i+s_i+t_{ij}\le b_j$$

(5)

$$t_i^l\le b_i+s_i\le t_i^u$$

(6)

$$b_0=s_{0 }=s_{n+1}=0$$

(7)

The objective function (1) aims to minimize the distance cost; function (2) is about the decision variable; function (3) and function (4) indicate that every customer must be visited and only once; function (5) defines a connection between the TSP model and the time component; function (6) simply defines time window constraints, indicating that the service must finish within the time window, which also implies the service starts within the time window; function (7) indicates the time at which service starts at depot is zero and the service time at the depot is also zero.

2.2. Model for Rescheduling

2.2.1. Problem Assumptions with Disruption

If delivery is delayed due to disruptions, the original schedule will not be optimal or feasible. This study has the following assumptions:

• There are many reasons for the delivery delay, such as random demand, change in distribution location, road congestion, vehicle failure, weather, etc. This paper will not consider the reasons leading to the delivery delay, assuming that the delivery delay has occurred;
• The original schedule is known and the distribution center cannot provide excess capacity for rescue, so the unfinished distribution task must be completed by the current vehicle in transit;
• The current location of the vehicle is the virtual distribution center, and the vehicle returns to the distribution center after completing the distribution task;
• During rescheduling, ensure that all customers can be served;
• If the disruption occurs when the vehicle is on its way to customer j after completing the distribution task of customer i, this delay will inevitably result in customer j or its subsequent customers, who have not been served, being unsatisfied within the time window;
• The infeasible solution with respect to the time windows is accepted with the penalty method approach. If the vehicle reaches customer i and finishes the service after the late time of the time window, there will be a penalty cost.

2.2.2. Notations

Here, we add new notations on the basis of Section 2.1.2.

${\mu }_i$: waiting sensitivity parameter for customer $i$(${\mu }_i\ge 0, i\in N\backslash \left\{0,n+1\right\}$), which represents the sensitivity for waiting time caused by delivery delay and holds the distribution function $Ф(·)$ with the range of $[{\mu }_{min},{\mu }_{max}]$;

$T_i$: waiting time of customer $i$ due to delivery delay;

${\rho }_j^s$: penalty multiplier for customer $j$ due to delivery delay;

$c\left( · , ·\right)$: perceived waiting cost function of customer $i$ due to delivery delay, which is the function of ${\mu }_i$ and $T_i$;

2.2.3. Perceived Waiting Cost for Heterogeneous Customers

Customers are heterogeneous, and different customers will suffer different waiting costs due to delivery delay. Further, this waiting cost is not a proportional function of delay time but is also affected by customer heterogeneity and loss aversion behavior. Here, we try to model two kinds of customer behaviors; one is customer heterogeneity and the other is loss aversion when facing delivery delay.

For the first kind of behavior, this paper sets a customer waiting sensitivity parameter ${\mu }_i$ to indicate the customer’s heterogeneity. The larger the value of waiting sensitivity parameter, the more sensitive the customer to the waiting time, and, therefore, the higher the perceived waiting cost to the customer.

For the second kind of behavior, the value function caused by waiting time is constructed referring to the loss aversion of prospect theory [23], which indicates that the utility function facing loss is convex. The expression form of the value function proposed by Kahneman et al. [23], which is the most widely used, is shown in formula (8):

$$V\left(\mathsf{\Delta }r\right)=\{\begin{array}{cc}\mathsf{\Delta }{r}^{\alpha },& \mathsf{\Delta }r\ge 0\\ -\lambda {\left(-\mathsf{\Delta }r\right)}^{\beta },& \mathsf{\Delta }r<0\end{array}$$

(8)

where $\alpha$, $\beta$, and $\lambda$ are the parameters related to gains and losses. Kahneman et al. [23] believed that the values of $\alpha$, $\beta$ are between 0 and 1, and, the higher the parameter value, the weaker the sensitivity of the decision-maker to the value; $\lambda >1$ means that customers are more sensitive to loss than gain.

Many researchers have conducted empirical studies on the coefficient $\beta$ of loss aversion in prospect theory, but there is still no universally recognized parameter value. Furthermore, the loss aversion coefficient $\beta$ currently obtained assumes that people are homogeneous and does not reflect the heterogeneity of people. Therefore, when constructing the perceived waiting cost function, based on the existing conclusion that “customers are risk averse when facing losses, that is, the function when facing losses is convex function”, this study integrates the heterogeneity of customers and expresses the perceived waiting cost of customer i for delivery delay as $c\left( · , ·\right)=c\left({\mu }_i,T_i\right)={\mu }_i*\lambda {\left(T_i\right)}^{\beta },$ among which the function is convex related to waiting time $T_i$.

As shown in Figure 1, the black S-shaped curve is the utility function that represents gain and loss in prospect theory. This study only considers the utility of the loss part shown in the dashed box (the delivery delay only involves loss). The sensitivity coefficient to loss in prospect theory is a fixed value, $\lambda$. In this study, this sensitivity coefficient is expressed as the heterogeneity of customers, and different sensitivity coefficients are used to express the sensitivity of different customers to waiting (shown in the red curves in Figure 1). Therefore, the function $c\left( · , ·\right)=c\left({\mu }_i,T_i\right)$ can represent the perceived waiting cost of heterogeneous customers. More generally, the following assumptions are made.

Assumption 1: $Ф(·)$ is a continuous quadratic differentiable increasing concave function;

Assumption 2: $c\left(\mu ,T\right)$ is a quadratic continuous differentiable increasing convex function related to μ and T.

2.2.4. Mathematical Model for Rescheduling

When the disruption occurs, the original scheduling approach would not be feasible. Using a penalty method approach, we consider infeasible solutions by relaxing the time window constraints ($b_i+s_i\le t_i^u, i=1,\dots ,n_{ }$) into the objective function with a penalty function of the form p(s).

In the traditional rescheduling model, penalty cost is affected by the delay time and penalty coefficient. Therefore, we obtain the penalty function of rescheduling in formulation (9):

$$p^1\left(s\right)=\rho {\displaystyle \sum }_{i=1}^n[max\left\{0, b_i+s_i-t_i^u\right\}]$$

(9)

In the new rescheduling model, penalty cost is affected by perceived waiting cost for heterogeneous customers. Therefore, we obtain the penalty function of rescheduling in formulation (10):

$$p^2\left(s\right)={\rho }_i^s{\displaystyle \sum }_{i=1}^n[c\left({\mu }_i,max\left\{0, b_i+s_i-t_i^u\right\}\right)]$$

(10)

The rescheduling model is constructed as shown in formulation (11); it is called TSPTW rescheduling when $p\left(s\right)=p^1\left(s\right)$ and TSPTW-PWC rescheduling when $p\left(s\right)=p^2\left(s\right):$

$$\min g(s,\rho )={\displaystyle \sum }_{i=0}^n{\displaystyle \sum }_{j=1}^{n+1}\left\{c_{ij}*x_{ij}+p\left(s\right)\right\}$$

(11)

Subject to:

$$x_{ij}\in \left\{0,1\right\}\forall i\in N\backslash \left\{n+1\right\}, j\in N\backslash \left\{0\right\}, i\ne j$$

(12)

$${\displaystyle \sum }_{j\in N\backslash \left\{0,i\right\}}{x}_{ij}=1 \forall i\in N\backslash \left\{n+1\right\}$$

(13)

$${\displaystyle \sum }_{i\in N\backslash \left\{j,n+1\right\}}{x}_{ij}=1 \forall j\in N\backslash \left\{0\right\}$$

(14)

$$b_0=s_{0 }=s_{n+1}=0$$

(15)

$$b_i+s_i+t_{ij}\le b_j$$

(16)

The objective function (11) aims to minimize the total cost; first term is the distance cost denoted by f(s), and second term is the penalty cost denoted by p(s). The second part is zero if no disruption occurs; functions (12–16) are the same as functions (2–5) and function (7).

3. Algorithm

The TSPTW problem has been proven to be an NP-hard problem, and the rescheduling model considering the perceived waiting cost for a heterogeneous customer will be more difficult to solve. Therefore, based on the compressed annealing heuristic for TSPTW proposed by Ohlmann et al. [47], we illustrate an improved compressed annealing algorithm with heterogeneous pressure (ICAHP) to solve the problem.

3.1. ICAHP

Compressed annealing heuristics is a solution approach to TSPTW. With the addition of the temperature from simulated annealing with the concept of pressure (analogous to the value of the penalty multiplier), compressed annealing relaxes the constraints of the time window by integrating a penalty method within a stochastic search procedure. Its value corresponds to the penalty coefficient in the model, which means that the solution falling outside the time window should be accepted with a certain probability. With increasing pressure, the acceptance probability will decrease, improving the probability of finding the optimal solution. Although the pressure value corresponds to the penalty coefficient in the model, it does not set different penalty coefficients for heterogeneous customers.

In the TSPTW-PWC model, we consider the perceived waiting cost for heterogeneous customers; accordingly, the penalty coefficient will be affected by waiting sensitivity parameter. Therefore, in terms of pressure representation, ICAHP algorithm will propose a new pressure representation method to express the penalty coefficient, as shown in Equation (17):

$${\rho }_{kj}^s={\rho }_k*{\mu }_j$$

(17)

Here, ${\rho }_{kj}^s$ is the penalty multiplier for customer $j$ due to delivery delay from iteration kd + 1 to iteration (k + 1)d, which is also the pressure value. The pressure during each iteration of ICAHP algorithm is set to ρ_i (i.e., the initial pressure is ρ₀, the pressure during the first iteration is ρ₁, and the pressure in the k_th iteration process is ρ_k). In addition, the actual penalty coefficient for customer j is ${\rho }_{kj}^s$ under solution s with the consideration of customer heterogeneity. The penalty cost coefficients of different customers are affected by the customer waiting sensitivity parameter. The larger the customer waiting factor is, the greater the penalty coefficient is.

3.2. Cooling and Compression

The search behavior of compressed annealing is directly affected by the manner in which the temperature and pressure parameters are, respectively, decreased and increased during the annealing run. This paper adopts the cooling schedule proposed by Reeves [51] and a limited exponential compression schedule proposed by Ohlmann et al. [52]. The specific expression is shown in formulas (18) and (19):

$${\tau }_{k+1}=\phi {\tau }_k$$

(18)

$${\rho }_{k+1}=\widehat{\rho }\left(1-\frac{\widehat{\rho }-{\rho }_0}{\widehat{\rho }}\right)e^{-\gamma k}$$

(19)

τ represents temperature, $\phi$ indicates cooling rate, ρ₀ is the initial pressure, and $\widehat{\rho }$ represents the threshold value of the pressure, that is, the maximum pressure. γ is the rate of increase in pressure; k is the number of iterations at each temperature and pressure, where 0 ≤$\phi$ ≤ 1, γ ≥ 0, ρ₀ ≥ 0, $\widehat{\rho }$≥ 0. The value of cooling parameter $\phi$ typically ranges from 0.80 to 0.99, and the value of compression parameter γ usually varies from 0.01 to 0.1; ρ₀ can be set to 0, but more care must be taken in setting τ₀ and $\widehat{\rho }$.

As for setting τ₀, referring to Ohlmann and Thomas [47], first, we generate R, a set of 2r solutions obtained by randomly sampling r (r = 5000) pairs of neighbor solutions. m is the percentage of proposed uphill transitions that we require to be accepted at ${\tau }_0. \left|\overline{\mathsf{\Delta }v}\right|$ is the average absolute difference in objective function over the n sample transitions composing R, and then we obtain the initial temperature as Equation (20):

$${\tau }_0=\frac{\left|\overline{\mathsf{\Delta }v}\right|}{\ln \left(1/m\right)}$$

(20)

To approximate the pressure cap, another parameter, ω, is introduced by referring to the existing literature [47], ω ∈ [0,1]; the value of ω ranges usually from 0.75 to 0.9. Therefore, the pressure cap $\widehat{\rho }$ is given in Equation (21):

$$\widehat{\rho }=max\left\{\frac{f\left(s\right)}{p\left(s\right)} \frac{\omega }{1-\omega }\right\}$$

(21)

3.3. Termination Criterion

In the literature, numerous stopping conditions have been reported. Bonomi and Lutton [53] fix the number of temperature values for which the algorithm is executed. Johnson et al. [54] terminate the algorithm when the percentage of accepted moves drops below a threshold for a number of iterations. We implement a hybrid of these two approaches by monitoring the mobility of the algorithm while also requiring minimum cooling times q. Precisely, we terminate the compressed annealing runs when the best tour found has not been updated in the last 75 temperature/pressure changes while requiring a minimum of 100 total temperature changes.

3.4. Solution Steps

The complete ICAHP algorithm is explained as follows, shown in Figure 2.

The solution steps are as follows.

Step 1: Input benchmark problem and the initial solution; initialize the values for ICAHP parameters.

Step 2: When the disruption occurs, the nodes of undelivered customer form a new problem. The current schedule is set as both the initial solution s₀ and the optimal solution s_best.

Step 3: Generate the neighborhood solution s₁. Calculate the value of objective function and accept the neighborhood solution with a certain probability.

Step 4: Check whether to accept according to the state acceptance function: if f(s₁) + p(s₁) < f(s₀) + p(s₀), accept the new state s₁ as the current optimal solution s_best = s₁. If f(s₁) + p(s₁) > f(s₀) + p(s₀), decide whether to accept it according to Metropolis standards with probability exp($g\left(s_0,\rho \right)-g\left(s_1,\rho \right)/{\tau }_k$). If accepted, the current optimal solution s_best = s₁. If not accepted, the current optimal solution is still s_best.

Step 5: Check if the cycle is completed. If so, go to Step 6; otherwise, go to Step 3.

Step 6: Update τ and ρ according to the cooling and compression schedules.

Step 7: Check whether the compressed annealing run is terminated or not according to the termination criteria. If the termination conditions are met, the search process is completed and the results are output; otherwise, go to Step 3.

4. Numerical Experiments

First, the classic benchmark example is selected to test the effectiveness of the proposed ICAHP algorithm in solving the rescheduling model considering heterogeneous customer-perceived waiting costs. Second, a sensitivity analysis is carried out for the customer waiting factor, length of delivery delay time, and occurrence point of delay time to determine which parameters have a greater impact on the model and how these parameters affect the results.

4.1. Parameter Setting

The ICAHP is tested using the classical benchmark sets of Solomon TSPTW, with a total of 30 groups of examples. The scale of the problem varies from 3 to 44 customers. The main parameters include waiting sensitivity parameter, cooling rate, pressure rising rate, pressure threshold coefficient, percentage of proposed uphill transitions that we require to be accepted at ${\tau }_0$, cycles at each temperature and pressure, minimum cooling times, etc. According to experimental tests and references [51,52,53,54], the algorithm parameters are set in

Table 1. ICAHP parameters for TSPTW-PWC.

Parameters	μ (Uniform Distribution)	φ	γ	ω	m	d	q
values	[0,30]	0.95	0.05	0.8	0.94	30,000	100

.

Functional form of $c=\left(\mu ,T\right)$ can be different depending on the identified problems. In this paper, we refer to prospect theory, setting $c\left({\mu }_i,T_i\right)={\mu }_i*\lambda {\left(T_i\right)}^{\beta }$, where β = 0.88, λ = 2.25.

4.2. Comparison between the TSPTW and TSPTW-PWC Rescheduling Models

When distribution delay occurs, the aim of TSPTW is to minimize the sum of distance cost and penalty cost caused by delay time. The penalty cost of TSPTW is caused by absolute waiting time, while the penalty cost of TSPTW-PWC is caused by the perceived waiting time of heterogeneous customers, which is the main difference between those two models. Both of the objectives of the two models include two parts, but the main differences are as follows in detail. TSPTW treats the delay time as the absolute time, and the value of penalty coefficient is the same for all the customers, while TSPTW-PWC converts absolute delay time into perceived value for delay time, and the penalty coefficient has different values for different customers. This is the core of this study, that TSPTW-PWC is formulated from behavioral perspective embedding loss aversion of prospect theory and customer heterogeneity. Based on this, we specifically analyze two different costs in detail, especially the penalty cost between these two models. We carry out experiments to illustrate the effectiveness of IAHCP on two models.

Table 2. Comparison of TSPTW and TSPTW-PWC.

Instances	Distance Cost			Penalty Cost			Total Cost
	TSPTW	TSPTW -PWC	Δ (%)	TSPTW	TSPTW -PWC	Δ (%)	TSPTW	TSPTW -PWC	Δ (%)
RC203.1	405	409	0.83%	15	14	−7.09%	420	423	0.55%
RC202.2	237	259	9.19%	123	111	−10.03%	361	370	2.55%
RC203.4	349	355	1.85%	230	220	−4.35%	579	575	−0.62%
RC203.2	642	656	2.14%	650	542	−16.66%	1293	1198	−7.89%
RC202.1	498	615	23.31%	1203	876	−27.16%	1701	1491	−14.12%
RC201.1	259	290	12.13%	1022	922	−9.78%	1281	1212	−5.66%
RC201.3	543	558	2.70%	1163	956	−17.80%	1706	1514	−12.71%
RC203.3	549	551	0.42%	1161	974	−16.11%	1710	1525	−12.11%
RC202.4	617	641	3.95%	1347	1067	−20.81%	1964	1708	−14.99%
RC202.3	646	669	3.62%	1300	1127	−13.29%	1945	1796	−8.32%
RC201.2	483	521	7.95%	2268	1853	−18.31%	2751	2374	−15.87%
RC201.4	542	574	5.83%	2177	1860	−14.56%	2719	2434	−11.73%

lists the comparative results of 12 instances of RC201, RC202, and RC203 in the benchmark of Solomon TSPTW. The scale of the instances varies from 13–36 customers. The time at which the delay occurs is set at the point of 1/3 of the original schedule, and the delay time is set as 1/3 of the total time of the original schedule. The original schedule adopts the results of the benchmark instances.

To show the results more intuitively, Table 2 is sorted according to the penalty cost of TSPTW-PWC. Compared to the TSPTW, the distance cost of TSPTW-PWC increases, while the penalty cost decreases. The reduction in penalty cost is greater than the increase in distance cost. Most instances show that the total cost is decreasing.

As shown in Figure 3, when the penalty cost is smaller, the total cost is almost the same. As the penalty cost increases, there will be a gap in the total cost, and the total cost of TSPTW-PWC is lower than that of TSPTW.

The penalty cost of TSPTW-PWC is integrated into the perceived waiting time of heterogeneous customers. Therefore, the higher the penalty cost is, the better the result of the TSPTW-PWC model is compared to that of the TSPTW model. When the penalty cost is very small, the difference between the two models is not obvious, and, in some instances, the TSPTW-PWC results are worse, as shown in the results of examples RC203.1 and RC202.2 in Table 2.

4.3. Sensitivity Analysis

In this paper, sensitivity analysis is conducted for the waiting sensitivity parameter, the length of the delay time, and the time when the delay occurs.

Table 3. Sensitivity analysis of waiting sensitivity parameter.

Value Range of μ	Distance Cost			Penalty Cost			Total Cost
	TSPTW	TSPTW-PWC	Δ (%)	TSPTW	TSPTW-PWC	Δ (%)	TSPTW	TSPTW-PWC
[0–10]	273	281	2.93%	59	52	−11.86%	332	333
[0–20]	273	281	2.93%	75	62	−17.33%	348	343
[0–30]	273	305	11.72%	162	85	−47.53%	435	390
[0–40]	273	274	0.37%	86	20	−76.74%	359	294
[0–50]	273	274	0.37%	104	23	−77.88%	377	297

shows the results of the sensitivity analysis of the customer waiting sensitivity parameter, taking the instance RC203.1 as an example. The range of values of the customer waiting sensitivity parameter is set to five different intervals, [0–10], [0–20], [0–30], [0–40], [0–50]. The time in which the delay occurs is set to 200, and the delay time is set to 160. The results of the benchmark instances are used for the original schedule; Table 3 demonstrates that the results are similar to those in Table 2. Compared to the results of TSPTW, the distance cost of TSPTW-PWC is greater than the distance cost of TSPTW, but the change is not obvious, and the reduction in penalty cost is greater than the increase in distance cost. Compared to the change in penalty cost, the change in distance cost can be ignored. As the value range of the customer waiting sensitivity parameter becomes wider, the distance cost does not change significantly and the reduction range of penalty cost is increasing, which makes the total cost of TSPTW-PWC compared to that of TSPTW decrease as the waiting factor range becomes larger. Therefore, it can be seen from the results that, the larger the interval of customer waiting sensitivity parameter is, the higher the degree of customer heterogeneity, and the more advantages TSPTW-PWC has over TSPTW.

Table 4. Sensitivity analysis of the length of delay time.

Length of Delay Time	Distance Cost			Penalty Cost			Total Cost
	TSPTW	TSPTW -PWC	Δ (%)	TSPTW	TSPTW -PWC	Δ (%)	TSPTW	TSPTW -PWC
150	278	272	−2.16%	114	102	−10.53%	392	374
160	272	306	12.50%	163	86	−47.24%	435	392
170	280	301	7.50%	275	155	−43.64%	555	456
180	269	274	1.86%	345	247	−28.41%	614	521
190	264	266	0.76%	498	280	−43.78%	762	546

takes RC203.1 as an example to analyze the sensitivity of the length of delay time. Set the delay time as five increasing values, namely 150, 160, 170, 180, and 190; set the value range of the customer waiting sensitivity parameter as [0–30], and set the time when the delay occurs to be 200. The results of the benchmark instance are used for the original schedule; it can be seen from Table 4 that, with the increase in length of delay time, the penalty costs of TSPTW and TSPTW-PWC are increasing. Compared to the change in penalty cost, the change in distance cost can be ignored. As the length of delay time increases, the penalty cost of TSPTW grows faster than that of TSPTW-PWC.

As shown in Figure 4, we compare the penalty costs under TSPTW and TSPTW-PWC with different delay times. For example, when the length of delay time is 150, the penalty costs of TSPTW and TSPTW-PWC are 114 and 102, respectively. As the length of delay time increases to 190, the penalty costs of TSPTW and TSPTW-PWC are 498 and 280, respectively. The penalty costs of TSPTW are nearly 5 times the initial penalty costs, while the penalty cost of TSPTW-PWC is 2–3 times the initial penalty cost. The penalty cost of TSPTW increases faster than that of TSPTW-PWC so difference between the penalty costs of the two models becomes larger. As we mentioned above, the distance cost changes little, which results that the total cost of TSPTW is much higher than that of TSPTW-PWC. Therefore, we can obtain that TSPTW-PWC performs better than TSPTW mainly because they treat penalty cost differently, and, as the delay time becomes longer, the penalty cost increases in different degrees.

As shown in Table 4, when the length of delay time is 150, the total costs of TSPTW and TSPTW-PWC are 392 and 374, respectively. When the length of delay time increases to 190, the total costs of TSPTW and TSPTW-PWC become 762 and 546, respectively. Therefore, the longer the length of delay time is, the more advantages TSPTW-PWC has compared to TSPTW.

Table 5. Sensitivity analysis of delay occurring time.

The Time When the Delay Occurs	Distance Cost			Penalty Cost			Total Cost
	TSPTW	TSPTW- PWC	Δ (%)	TSPTW	TSPTW- PWC	Δ (%)	TSPTW	TSPTW- PWC
early	639	649	1.56%	1224	983	−19.70%	1863	1632
middle	584	590	1.03%	1387	1281	−7.59%	1971	1871
late	567	572	0.88%	1086	1085	−0.13%	1653	1657

takes the instance RC201.4 as an example to analyze the sensitivity of time when the delay occurs. The value range of waiting sensitivity parameter is set to be [0–30], the delay time is set to be 200, and the time when the delay occurs is set to be [early, middle, late]; that is, the delay is randomly generated in the three time periods [0,1/3] [1/3,2/3] [2/3,1] of the original schedule operation, where the results of the benchmark example are used for original schedule; it can be seen from Table 5 that, when the delay occurs earlier, the distance cost between TSPTW and TSPTW-PWC is not much different. The penalty cost of TSPTW-PWC is obviously lower than the penalty cost of TSPTW, so the total cost of TSPTW-PWC is much lower than the total cost of TSPTW. The scheduling result of TSPTW-PWC has obvious advantages. However, as the delay occurs later, the penalty cost of TSPTW-PWC is not significantly lower than the penalty cost of TSPTW, which sharply reduces the advantage of TSPTW-PWC scheduling. As shown in Figure 5, the difference in distance cost between two models can be ignored, and, when the delay occurs earlier, the difference in penalty cost is obvious. As the delay occurs later, the penalty cost and the total cost converge almost to the same point. Therefore, the earlier the delay occurs, the better the scheduling results of TSPTW-PWC will be. As the delay occurs later, the difference between the scheduling results of the two models will not be obvious.

Results can be drawn from the above numerical experiments and sensitivity analysis. First, rescheduling from behavioral perspective can reduce penalty costs and improve customer satisfaction while total costs decrease, and the algorithm proposed in this paper can effectively solve this problem. Second, TSPTW-PWC has better performance than the TSPTW as the interval of waiting sensitivity parameter becomes larger. Third, TSPTW-PWC performs better than TSPTW as the delay increases. The main reason is that the penalty costs increase with the long delay, and the penalty cost of TSPTW grows faster than that of TSPTW-PWC because the main difference between the two models lies in the way they treat the penalty cost. Last, the earlier the delay occurs, the greater the advantage of TSPTW-PWC.

It can be seen from the above sensitivity analysis that, the higher the degree of customer heterogeneity, the longer the length of delay time, and, the earlier the delivery delay occurs, the more obvious the advantages of TSPTW-PWC. The essence of the TSPTW-PWC model is that, in the solution process, customers with large value of waiting sensitivity parameter have a reduced probability of being delayed due to a large penalty coefficient, thus reducing the relatively high penalty cost caused by delays to customers with large value of waiting sensitivity parameter. This benefit can be fully reflected in the current rescheduling process; in addition, in the long run, logistics service providers can use TSPTW-PWC to solve the problem of delivery delay, greatly reduce the penalty cost, and improve service quality, customer satisfaction, and customer loyalty, thus creating potential and long-term economic benefits for logistics service providers. Therefore, compared to TSPTW, the models and methods in this paper are more effective and practical.

5. Conclusions

This paper studies the vehicle rescheduling problem with delivery delay based on TSPTW, fully considering the bounded rationality and heterogeneity of customers. Quantifying customer behavior and embedding it into the rescheduling model make the problem much more challenging and different from classical vehicle rescheduling literature.

We propose a behavior-based rescheduling model embedding loss aversion of prospect theory and customer heterogeneity and illustrate ICAHP to solve the problem. By setting the customer waiting sensitivity parameter to quantify the customer heterogeneity and using the loss aversion from prospect theory to construct the customer’s perceived waiting cost function, based on this, a TSPTW model considering heterogeneous customers and perceived waiting cost is constructed. ICAHP has a new penalty term to penalize time-window violation for n customers. The numerical results show that, the higher the degree of customer heterogeneity, the longer the length of delay time and, the earlier the delivery delay occurs, the more obvious the advantages of the results obtained by solving TSPTW-PWC with ICAHP.

Considering the bounded rationality and heterogeneity of customers, the behavior-based rescheduling method is an extension of the traditional vehicle rescheduling method. It is the result of the intersection of traditional operations research and behavioral science, which is conducive to formation of a new behavior-based rescheduling theory and can enrich and improve the relevant theories of behavioral operations research.

Because of the complexity of individual behavior, this paper only depicts the customer’s behavior characteristics from one side, so direct expansion of this study can consider other customer behavior characteristics, such as customer fairness, fear, and other psychological characteristics, when constructing the waiting perception cost function for delivery delay. In addition, this paper assumes that the waiting factor of customers follows a uniform distribution, while, in practical applications, setting the waiting factor will be affected by other factors, such as in relation to the size of the customer’s time window width. Customers with a large time window width are less sensitive than customers with a narrow time window width. Therefore, there is still much work to be completed to study rescheduling of delivery delays from the perspective of behavior.