# A Disruption Recovery Problem with Time Windows Change in the Last Mile Delivery of Online Shopping

Authors: Li Jiang; Changyong Liang; Junfeng Dong; Wenxing Lu; Marko Mladenovic
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Frequent time window changing disruptions result in high secondary delivery rates in the last mile delivery. With the rapid growth of parcel volumes in online shopping, the time window changing disruptions could translate to substantial delivery cost-wastes. In recent years, customer pickup (CP), a new delivery mode that allows customers to pick up their parcels from shared delivery facilities, has provided a new way to deal with such disruptions. This study proposed a disruption recovery problem with time windows change in the last mile delivery in which customers can be served through home delivery (HD) or CP. A variant variable neighborhood descent (VVND) algorithm was presented to solve the problem. Computational experiments based on a set of instances were tested, and results were compared with other heuristics in the literature, which have affirmed the competitiveness of the model and algorithm.


---

## Body

## 1. Introduction

The rapid e-commerce growth results in a fast increase of parcel delivery. According to the State Post Bureau of China, the parcel volume of online shopping of 3.67 billion in 2011 increased to 40.06 billion in 2017, with an average growth rate of more than 48% within six years. This increase of parcel volume also caused the increase of the one-time delivery failure rate. Many parcels failed to be delivered at the first attempt [1], and these parcels had to be delivered the second time or even the third time. The main reason for this high delivery failure rate was the “not-at-home” problem (customers are going out); thus, the agreed delivery time between a courier and a customer commonly changes. Reducing the high delivery failure rate to deal with the frequent time window changing disruptions had become a key issue in the last mile delivery of online shopping.Previously, in terms of the last mile delivery, home delivery (HD) (that is, delivering parcels directly to customers’ homes or workplaces) was common. Recently, customer pickup (CP) has become widely popular, because it allows customers to pick up their parcels from shared delivery facilities (SDFs) near their homes or workplaces at their convenience. The SDFs widely used in more than 80 cities in China include the “CaiNiao” station established by Alibaba Company, “FengChao” established by SF-Express, and “Sposter” established by the China Post Group.The rescheduling of delivery routes [2, 3] plays a good role in solving the disruption recovery problem (DRP) in the HD mode, which is an NP-hard problem [3]. Meanwhile, for the DPR in the CP mode, deciding on the allocation of SDFs while rescheduling the delivery routes is important. The DRP in the CP mode is more complicated than that in the HP mode. Although many articles were published on the DRP in the HD mode [2–4], only a few studies explored the DRP in the CP mode. This study proposed a DRP with time windows change in the last mile delivery to solve the practical problems and bridge the gap in the literature. The customers could be served either by couriers (HD) or by SDFs (CP). The purpose was to decide on the allocation of SDFs and rescheduling of the delivery route to minimize the total delivery cost when a disruption (time windows changed) would occur. A variant variable neighborhood descent (VVND) algorithm was proposed to solve this problem.The rest of this paper is structured as follows. Section2 provides a comprehensive review of the related studies. Section 3 details the description and formulation of the proposed DRP. Section 4 discusses the proposed VVND algorithm. Section 5 displays the results of the computational experiments and the discussion. Section 6 concludes this paper.


## 2. Literature Review

One key issue related to our research was the shared delivery facilities (parcel lockers or shared reception boxes) in the last mile delivery. The SDF studies were categorized into two streams: case study and routing optimization.The case studies analyzed the benefits of the SDFs in the last mile delivery by using survey data. Punakivi et al. [5] emphasized that approximately 55%-66% of cost could be reduced from home delivery by allowing customers to pick up parcels from shared reception boxes. A similar study by Kämäräinen [6] contended that the cost reduction was 42%. Edwards et al. [7] confirmed that collecting parcels from parcel lockers could reduce carbon emission by 83%. Morganti et al. [8] focused on the self-collection networks in Europe and affirmed that the parcel lockers could reduce the operational cost of last mile logistics delivery. Meanwhile, Lemke et al. [9] analyzed the usability of the parcel lockers from customers’ perspectives by using data from Polish cities, and the results validated that most consumers prefer using lockers near their homes. Yuen et al. [10] explored customers' intention to use self-collection in the last mile delivery by using data from 164 consumers located in Singapore.The routing optimization focused on solving the SDF location and the delivery routing problem. Mainly, Deutsch et al. [11] studied the location allocation problem of parcel lockers in the last mile delivery and aimed to maximize the profit of a consignment company by deciding on the location of parcel lockers. Zhou et al. [12] proposed a location-routing problem with home delivery and customer pickup for the city distribution of online shopping to minimize the vehicle, routing, opening of SDF, and second delivery costs in the last mile delivery. Zhou et al. [13] also introduced a two-echelon vehicle routing problem with delivery options in the last mile distribution, wherein customers could be served by home delivery or customer pickup to minimize the total distribution cost.Another key issue related to our research is the disruption recovery problem (DRP), which is involved in multiple research areas, such as the passenger transport disruption recovery problem [14–16], vessel schedule recovery problem [17, 18], and logistics distribution recovery problem. In logistics, Zeimpekis et al. [19] introduced a management system framework for dealing with disruption accidents in urban logistics distribution. Protvin et al. [20] studied the disruption accidents of new customers and uncertain travel time that were frequently encountered during the collection of tasks. Mu et al. [4] proposed a disrupted vehicle routing problem (VRP) to deal with the disruptions that occur at the execution stage of a VRP plan, while Zhang el al. [21] analyzed the effect of disruptions on road networks and the recovery process by using domain wall theory.Existing literature on the DRP had produced effective solutions for various disruptions, especially the disruption that occurred in logistics. However, such literature mainly focused on the DRP in the HD mode, and no study on the disruption problem in the CP mode was available. This study explored the disruption recovery problem (DRP) with time windows change in the last mile delivery in the CP mode to solve the practical problem and bridge the gap in the literature.


## 3. Problem Formulations

### 3.1. Problem Description

A network without SDFs in the last mile delivery is described as follows.G=(V,E), V=VD∪VC, VD stands for depot, and VC stands for customer set. E=EC, EC=i,j∣i,j∈VC is a set of edges connecting each pair of nodes in VC. The travel cost and travel time of the edge in EC from i∈VC to j∈VC are cij′ and tij′, respectively. The time window of i∈VC is expressed as [eti′,lti′]. Figure 1 exhibits the network and initial route.Figure 1
Network and route without SDFs.A network with SDFs in the last mile delivery is described as follows.G=(V,E), V=VD∪VC∪VP, VD is the depot set; VC is the customer set, and VP is the SDF set. [eti,lti] stands for the changed time window of customer i∈VC. E=E1∪E2, E1=i,j∣i,j∈V is a set of directed edge connecting each pair of nodes in V; the delivery distance and time of the directed edge (i,j) in E1 are cij and tij, respectively. E2=i,p∣i∈VC,p∈VP contains the edges between SDF p∈VP and customer i∈VC, and the pickup distance and the time of the edge (i,p) in E2 are dip and sip, respectively. The unit opening cost of SDF p∈VP is μp. Figure 2 presents the network with SDFs.Figure 2
Network and route with SDFs.Couriers depart from depots and deliver parcels according to the initial optimal solution. During delivery, couriers must adjust the delivery route to obtain a good solution when a disruption occurs (customers’ time windows changed). In this paper, the objective function is to minimize the cost related to customer satisfaction, route cost, and SDF opening cost.Without losing generality, the following assumptions are made.( 1 )The capacity limit of SDFs is not considered in this paper.( 2 ) Customer satisfaction is only inversely proportional to the delivery delay time and customer pickup distance.( 3 ) Couriers must wait until eti to start the service of customer i∈VC; they can deliver parcels to SDFs at any time.( 4 ) Each customer can be served by either couriers or SDFs.


### 3.2. Notions and the Proposed Model

Table1 summarizes the notions used in the formulation.Table 1
Notions used in formulation.
Sets G Network,G=(V,A) V Node set,V=VD∪VC∪VP V D Depot set,VD={0} V C Customer set,VC={1,2,3,...,N} V P SDF set,VP={N+1,N+2,...,N+M} E Arc set,E=E1∪E2 E 1 Delivery arc set,E1=i,j∣i,j∈V E 2 Pickup arc set,E2=i,p∣i∈VC,p∈VP  Parameters  M Number of SDFs N Number of customers c i j Distance ofarc(i,j)∈E1 t i j Travel time ofarc(i,j)∈E1 d i p Pickup cost ofarc(i,p)∈E2 s i p Pickup time ofarc(i,p)∈E2 [ e t i , l t i ] Time window of customeri∈VC μ p Unit opening cost of SDFp L Large positive number α Sub-weight of delivery delay time β Sub-weight of pickup distance w 1 Weight of pickup cost w 2 Weight of routing cost w 3 Weight of SDFs opening cost R Server radius of the SDFs  Decision variables  x i j Binary variable,xij=1, if arc(i,j)∈E1 is used by courier; otherwise, xij=0 y i p Binary variable,yip=1, if customer i∈Vc is assigned to SDF p∈VP; otherwise, yip=0 a t i Integer variable, arrival time to nodei∈VWhen a disruption occurs, the influence of customers and couriers is different.( 1 ) The influence of disruption on customer is service satisfaction. According to assumption (2), service satisfaction is related to delivery delay time and customer pickup distance. Service satisfaction decreases with the increase of delivery delay time and customer pickup distance, which are shown in Figures 3 and 4, respectively.Figure 3
Relationship between customer satisfaction and delivery delay time.Figure 4
Relationship between customer satisfaction and pickup distance.The cost related to service satisfaction can be formulated as Formula (1).(1)fati,yip=α∑i∈VCmax⁡ati-lti,0+β∑i∈VC,p∈VPyipdip( 2 ) The influence of disruption on couriers is delivery route and SDF opening costs, the function related to delivery distance is shown as Formula (2), and the function related to SDF opening cost is shown as Formula (3).(2)gxij=∑i,j∈VC∪VPcijxij(3)hyip=∑i∈VCμpyip∀p∈VPOn the basis of the above statements, the model for the proposed problem can be stated as follows:(4)obj=min⁡w1fati,yip+w2gxij+w3hyipwhich is subject to(5)∑j∈VC∪VPxij+∑p∈VPyip=1∀i∈VC(6)∑j∈VC∪VPxij+∑p∈VPyip=1∀i∈VC(7)∑j∈VC∪VPxip≤∑i∈VCyip∀p∈VP(8)ati+tij-L1-xij≤atj∀i,j∈VC∪VP(9)atp+sip-L1-yip≤ati∀i∈VC,∀p∈VP(10)ati≥eti∀i∈VC(11)dipyip≤R∀i∈VC,p∈VP(12)xij=0,1∀i,j∈VC∪VP(13)yip=0,1∀i∈VC,∀p∈VPObjective function (4) minimizes the sum of the cost related to service satisfaction, route cost, and SDF opening cost. Constraints (5) and (6) ensure that each customer is served exactly once by either SDF or a courier, and once a courier enters a node, it must also leave for it. Constraint (7) ensures that the SDF that is allocated for customers must be allocated to the route. Constraints (8) and (9) guarantee that the working time of customer should be satisfied. Constraint (10) makes sure that the courier must be served only after the time window has started. Constraint (11) makes sure that the service radius of the SDF is within the allowable distance. Constraints (12) to (13) define all variables.


## 3.1. Problem Description

A network without SDFs in the last mile delivery is described as follows.G=(V,E), V=VD∪VC, VD stands for depot, and VC stands for customer set. E=EC, EC=i,j∣i,j∈VC is a set of edges connecting each pair of nodes in VC. The travel cost and travel time of the edge in EC from i∈VC to j∈VC are cij′ and tij′, respectively. The time window of i∈VC is expressed as [eti′,lti′]. Figure 1 exhibits the network and initial route.Figure 1
Network and route without SDFs.A network with SDFs in the last mile delivery is described as follows.G=(V,E), V=VD∪VC∪VP, VD is the depot set; VC is the customer set, and VP is the SDF set. [eti,lti] stands for the changed time window of customer i∈VC. E=E1∪E2, E1=i,j∣i,j∈V is a set of directed edge connecting each pair of nodes in V; the delivery distance and time of the directed edge (i,j) in E1 are cij and tij, respectively. E2=i,p∣i∈VC,p∈VP contains the edges between SDF p∈VP and customer i∈VC, and the pickup distance and the time of the edge (i,p) in E2 are dip and sip, respectively. The unit opening cost of SDF p∈VP is μp. Figure 2 presents the network with SDFs.Figure 2
Network and route with SDFs.Couriers depart from depots and deliver parcels according to the initial optimal solution. During delivery, couriers must adjust the delivery route to obtain a good solution when a disruption occurs (customers’ time windows changed). In this paper, the objective function is to minimize the cost related to customer satisfaction, route cost, and SDF opening cost.Without losing generality, the following assumptions are made.( 1 )The capacity limit of SDFs is not considered in this paper.( 2 ) Customer satisfaction is only inversely proportional to the delivery delay time and customer pickup distance.( 3 ) Couriers must wait until eti to start the service of customer i∈VC; they can deliver parcels to SDFs at any time.( 4 ) Each customer can be served by either couriers or SDFs.


## 3.2. Notions and the Proposed Model

Table1 summarizes the notions used in the formulation.Table 1
Notions used in formulation.
Sets G Network,G=(V,A) V Node set,V=VD∪VC∪VP V D Depot set,VD={0} V C Customer set,VC={1,2,3,...,N} V P SDF set,VP={N+1,N+2,...,N+M} E Arc set,E=E1∪E2 E 1 Delivery arc set,E1=i,j∣i,j∈V E 2 Pickup arc set,E2=i,p∣i∈VC,p∈VP  Parameters  M Number of SDFs N Number of customers c i j Distance ofarc(i,j)∈E1 t i j Travel time ofarc(i,j)∈E1 d i p Pickup cost ofarc(i,p)∈E2 s i p Pickup time ofarc(i,p)∈E2 [ e t i , l t i ] Time window of customeri∈VC μ p Unit opening cost of SDFp L Large positive number α Sub-weight of delivery delay time β Sub-weight of pickup distance w 1 Weight of pickup cost w 2 Weight of routing cost w 3 Weight of SDFs opening cost R Server radius of the SDFs  Decision variables  x i j Binary variable,xij=1, if arc(i,j)∈E1 is used by courier; otherwise, xij=0 y i p Binary variable,yip=1, if customer i∈Vc is assigned to SDF p∈VP; otherwise, yip=0 a t i Integer variable, arrival time to nodei∈VWhen a disruption occurs, the influence of customers and couriers is different.( 1 ) The influence of disruption on customer is service satisfaction. According to assumption (2), service satisfaction is related to delivery delay time and customer pickup distance. Service satisfaction decreases with the increase of delivery delay time and customer pickup distance, which are shown in Figures 3 and 4, respectively.Figure 3
Relationship between customer satisfaction and delivery delay time.Figure 4
Relationship between customer satisfaction and pickup distance.The cost related to service satisfaction can be formulated as Formula (1).(1)fati,yip=α∑i∈VCmax⁡ati-lti,0+β∑i∈VC,p∈VPyipdip( 2 ) The influence of disruption on couriers is delivery route and SDF opening costs, the function related to delivery distance is shown as Formula (2), and the function related to SDF opening cost is shown as Formula (3).(2)gxij=∑i,j∈VC∪VPcijxij(3)hyip=∑i∈VCμpyip∀p∈VPOn the basis of the above statements, the model for the proposed problem can be stated as follows:(4)obj=min⁡w1fati,yip+w2gxij+w3hyipwhich is subject to(5)∑j∈VC∪VPxij+∑p∈VPyip=1∀i∈VC(6)∑j∈VC∪VPxij+∑p∈VPyip=1∀i∈VC(7)∑j∈VC∪VPxip≤∑i∈VCyip∀p∈VP(8)ati+tij-L1-xij≤atj∀i,j∈VC∪VP(9)atp+sip-L1-yip≤ati∀i∈VC,∀p∈VP(10)ati≥eti∀i∈VC(11)dipyip≤R∀i∈VC,p∈VP(12)xij=0,1∀i,j∈VC∪VP(13)yip=0,1∀i∈VC,∀p∈VPObjective function (4) minimizes the sum of the cost related to service satisfaction, route cost, and SDF opening cost. Constraints (5) and (6) ensure that each customer is served exactly once by either SDF or a courier, and once a courier enters a node, it must also leave for it. Constraint (7) ensures that the SDF that is allocated for customers must be allocated to the route. Constraints (8) and (9) guarantee that the working time of customer should be satisfied. Constraint (10) makes sure that the courier must be served only after the time window has started. Constraint (11) makes sure that the service radius of the SDF is within the allowable distance. Constraints (12) to (13) define all variables.


## 4. Hybrid Approach

For the disruption recovery problem, the algorithm should focus not only on solution accuracy, but also on solution speed. If the solution time is too long, then the solution may have been infeasible. The variable neighborhood descent (VND) has been successfully applied for solving hard combinatorial optimization problems, and it particularly performs well for solving LRPs [22, 23]. This study proposes a variant variable neighborhood descent (VVND) algorithm for solving the disruption recovery problem. The innovation of the VVND includes two aspects. (1) Two new operators (addBox() anddropBox()) are added in the proposed algorithm. (2) The 2-opt operator is improved by using the location range (LR) to speed up convergence. Algorithm 1 presents an overview of the VVND.Algorithm 1:VVND.
1  k=1;iter=0; 2  S=InitalSolution(); 3  Repeat 4  rd =rand(); 5  if rd < 0.5 6  openNum=rand()%S.closeBoxNum; 7  S’ = addBox(S, openNum); 8  else 9  closeNum =rand()%S.openBoxNum; 10  S’ = dropBox(S, closeNum); 11  end 12  S’ = FindBestNeighbor(S’); 13  if f(S’) < f(S) 14  S = S’; 15  k = 1; 16  else 17  if iter < iterMax 18  iter = 0; 19  k = k + 1; 20  end 21  end 22  iter = iter + 1; 23  Until k > kMax


### 4.1. Solution Representation

A mixed encoding scheme is designed to represent a solution. In the encoding scheme, two sections are shown in Figure5.Figure 5
Encoding scheme for the solution of Figure1.First sectionS1 is an assignment used to label each customer's service options. If the value in the assignment belongs to {N+1:N+M}, then the customer picks up the parcel from the SDF. If the value is 0, then the customer receives the parcel at home or workplace.Second sectionS2 is a route consisting of customers and SDFs. In the routing, courier starts and ends at the depot and delivers parcels to customers or SDFs one by one.


### 4.2. addBox() and dropBox() Procedures

The steps of theaddBox() are as follows:(1)
Randomly selectopenNum closed SDFs (if there are any) and open them.(2)
Reallocate the customers within the service radius of the SDFs.(3)
Randomly insert the SDFs into the route.The steps ofdropBox() are as follows:(1)
Randomly selectcloseNum opened SDFs (if there are any).(2)
Delete the SDFs from the delivery route.(3)
Randomly insert the customers of the SDFs into the delivery route.Figure6 illustrates theaddBox()anddropBox().Figure 6
Illustration of theaddBox() and dropBox().
(a)
addBox() (b)
dropBox()


### 4.3. Neighborhood Structures

Insertion move (N 1 ).The insertion move is carried out by selecting everyach two nodes, that is, ith node and jth nodes of the solution, and reinserting the ith node into the position immediately before (or in) the jth node of the solution. The insertion move has two effects as follows.Case (a): If the selected node is a customer (in the route or SDF), then it can be reinserted to the route or the SDF.Case (b): If the selected node is a SDF, then it can be only reinserted to route.Figure7 illustrates the insertion move.Figure 7
Insertion move operator.
(a)
Case (a) (b)
Case (b)Improved 2-Opt move (N 2 ). A subsequence is obtained by selecting each two nodes, that is, theithandjth nodes of the solution. Reversing the order of the subsequence can obtain a new solution. Note that the selected nodeith orjthcannot be a customer in SDF. Figure 8 illustrates the 2-opt move.Figure 8
2-opt move operator.In the network with time windows, partial arcs are disconnected due to the time window constraints, which can be used to calculate each node location range (LR) in the route. By using LR, partial useless exchange can be reduced.Figure9 exhibits that the location range of customer i is [loc(i)+1,N], the useless exchange in [0,loc(i)] can be deleted, and the loc(i) can be calculated by Formula (14).(14)loci=loci+1eti+tij>ltjlociotherwisej=1,2,…,NFigure 9
Improved 2-Opt algorithm.


## 4.1. Solution Representation

A mixed encoding scheme is designed to represent a solution. In the encoding scheme, two sections are shown in Figure5.Figure 5
Encoding scheme for the solution of Figure1.First sectionS1 is an assignment used to label each customer's service options. If the value in the assignment belongs to {N+1:N+M}, then the customer picks up the parcel from the SDF. If the value is 0, then the customer receives the parcel at home or workplace.Second sectionS2 is a route consisting of customers and SDFs. In the routing, courier starts and ends at the depot and delivers parcels to customers or SDFs one by one.


## 4.2. addBox() and dropBox() Procedures

The steps of theaddBox() are as follows:(1)
Randomly selectopenNum closed SDFs (if there are any) and open them.(2)
Reallocate the customers within the service radius of the SDFs.(3)
Randomly insert the SDFs into the route.The steps ofdropBox() are as follows:(1)
Randomly selectcloseNum opened SDFs (if there are any).(2)
Delete the SDFs from the delivery route.(3)
Randomly insert the customers of the SDFs into the delivery route.Figure6 illustrates theaddBox()anddropBox().Figure 6
Illustration of theaddBox() and dropBox().
(a)
addBox() (b)
dropBox()


## 4.3. Neighborhood Structures

Insertion move (N 1 ).The insertion move is carried out by selecting everyach two nodes, that is, ith node and jth nodes of the solution, and reinserting the ith node into the position immediately before (or in) the jth node of the solution. The insertion move has two effects as follows.Case (a): If the selected node is a customer (in the route or SDF), then it can be reinserted to the route or the SDF.Case (b): If the selected node is a SDF, then it can be only reinserted to route.Figure7 illustrates the insertion move.Figure 7
Insertion move operator.
(a)
Case (a) (b)
Case (b)Improved 2-Opt move (N 2 ). A subsequence is obtained by selecting each two nodes, that is, theithandjth nodes of the solution. Reversing the order of the subsequence can obtain a new solution. Note that the selected nodeith orjthcannot be a customer in SDF. Figure 8 illustrates the 2-opt move.Figure 8
2-opt move operator.In the network with time windows, partial arcs are disconnected due to the time window constraints, which can be used to calculate each node location range (LR) in the route. By using LR, partial useless exchange can be reduced.Figure9 exhibits that the location range of customer i is [loc(i)+1,N], the useless exchange in [0,loc(i)] can be deleted, and the loc(i) can be calculated by Formula (14).(14)loci=loci+1eti+tij>ltjlociotherwisej=1,2,…,NFigure 9
Improved 2-Opt algorithm.


## 5. Computational Experiments

The proposed algorithm is compiled with C++ and runs on PC with an Intel i5-7500 3.40 GHz CPU, 8.00GB RAM.


### 5.1. Test with Time Windows Change

The test dataset consists of 100 customers (an instance n100w60.004 proposed by Dumas et al. [24]) and nine SDFs. The coordinates of the SDFs are evenly distributed in the area of 50,50: 102(10,10), 103(10,30), 104(10,45), 105(25,10), 106(25,30), 107(25,45), 108(40,10), 109(40,30), 110(40,45). The known optimal solution is 1, 94, 58, 42, 98, 82, 9, 59, 39, 75, 53, 35, 13, 84, 41, 5, 50, 70, 80, 25, 47, 55, 66, 95, 11, 23, 2, 100, 30, 67, 31, 26, 96, 21, 81, 79, 27, 38, 17, 61, 92, 86, 57, 15, 36, 19, 85, 77, 60, 20, 69, 44, 48, 64, 40, 52, 72, 73, 7, 32, 87, 29, 90, 22, 51, 65, 56, 49, 46, 91, 54, 71, 74, 78, 43, 68, 12, 18, 33, 14, 37, 88, 8, 10, 93, 16, 99, 3, 83, 97, 62, 89, 28, 45, 76, 24, 6, 4, 101, 34, 63, and the route cost is 764. When the courier delivers to the customer 98#, the courier receives the time window change information (Table 2).Table 2
Time windows change.
Customer no. Status Time window Customer no. Status Time window e t i l t i e t i l t i 6 Old TW 627 664 43 Old TW 382 413 New TW 50 100 New TW 30 80 10 Old TW 460 499 47 Old TW 34 122 New TW 100 150 New TW 500 540 13 Old TW 21 67 53 Old TW 0 68 New TW 400 440 New TW 600 668 27 Old TW 145 233 62 Old TW 510 574 New TW 350 400 New TW 110 170 34 Old TW 725 795 70 Old TW 37 128 New TW 200 260 New TW 700 758The parameters are the same as the above tests:R=20, w1=w2=w3=1, α=1, β=1, up=5. The optimal solution obtained by the proposed algorithm is shown  in Tables 3 and 4. Table 3 presents the customer assignments of the SDFs, and Table 4 presents the delivery route.Table 3
Optimal solution of customer assignment.
SDF no. Customer no. SDF no. Customer no. 102 13,62,76,89 107 / 103 28,43,45,53,59 108 4 104 12,18,24,33,68 109 26,34,37 105 63,97 110 / 106 14Table 4
Optimal solution of delivery route.
1-94-58-42-98-82-103-9-39-75-35-50-84-41-5-102-80-25-55-66-11-95-23-6-96-31-67-109-30-100-2-21-81-79-108-10-17-61-38-92-86-57-15-36-19-85-77-60-20-104-69-44-48-64-40-52-72-73-7-32-87-29-90-22-65-51-56-49-46-91-54-71-74-10678-105-27-93-3-99-16-8-88-83-47-101-70This study reports the comparisons of the reschedule route in the CP mode (RRCP) with the original delivery route (ODR) and the reschedule route in the HD mode (RRHD), where Difference = RRCP – RRHD and GAP = (RRHD - RRCP) / RRHD∗100 (see Table 5).Table 5
Comparison of the three schemes.
Item ODR RRHD RRCP Difference GAP(%) Delay time 53000 521 17 −504 96.74% Pickup cost 0 0 169 +169 – Opening cost 0 0 105 +105 – Route cost 764 703 442 −261 37.13% Total cost 53764 1224 733 −491 40.08% CPU Time (S) 0 21 22Compared with the RRHD, the RRCP increases the pickup cost and SDF opening cost by providing customer pickup services, but the total cost is reduced by 40.08%. The delay time is reduced from 521 to 17 or 96.74%; route cost is reduced from 703 to 442 or 37.13%. As carbon emission is closely related to delivery route distance, the proposed model can help effectively reduce carbon emission.


### 5.2. Sensitive Analyses

To gain additional insights, a sensitive analysis is conducted to show how the acceptable distanceR influences cost. When R ranges from 0 to 50, the results are reported in Table 6 and Figure 10.Table 6
Results of sensitive analysis ofR on cost.
Item R 0 5 10 15 20 30 40 50 Delay time 521 197 97 17 17 17 17 17 Pickup cost 0 41 97 169 169 169 169 169 Opening cost 0 60 80 105 105 105 105 105 Route cost 703 647 552 442 442 442 442 442 Total cost 1224 944 826 733 733 733 733 733Figure 10
Sensitive analysis ofR on cost.From the sensitive analysis, we can see that whenR=0, the proposed method is optimal without SDF. When 0<R≤50, the delay time and route cost are first to fall continuously and then keep invariability. The pickup cost is increased with the increase of R. From a cost optimization perspective, R=15 is the best SDF service radius in this instance.


### 5.3. Computational Results Comparison

For the evaluation of the performance of the proposed algorithm, tests based on the benchmark instance proposed by Dumas et al. [24] are used. The networks consist of one depot and 20, 40, 60, 100, and 150 customers. The width of time window is 60. The locations of SDFs are (32,5), (14,28), (48,49), (8,49), (48,25), (41,8), (22,46), (40,48), (33,2), (43,47), (34,38), (38,20), (33,9), (36,2), (14,3), (5,42), (35,16), (48,2), (22,20), (39,40), (10,25), (23,33), (36,38), and (14,34), which are generated randomly in an area of 0,50×0,50. The parameters are listed as follows: R=20, w1=w2=w3=1,α=1,β=1, up=5. The parameters of VVND are kMax = M and iterMax = M/2.


#### 5.3.1. Comparison with Other Algorithms

Table7 presents comparisons of the proposed VVND and Simulated Annealing (SA). N represents the number of customer nodes;M represents the number of SDFs. The values under the “GAP” columns are calculated by the formula [ObjSA-Obj(VVND)]/Obj(SA)∗100. The solutions obtained by SA [25] are shown in Columns 4-5. Columns 6-7 show the solutions obtained from the proposed VVND. Time is the CPU time in seconds on a PC (i5-7500@3.40 GHz, 8.00GB RAM). The parameters of SA are set as follows: T=N, alpha=0.98, and Iiter=M. All the best solutions of SA and VVND are obtained with 5 runs of the algorithms.Table 7
Comparison between SA and the proposed method.
No. N M SA VVND GAP(%) Obj Time Obj Time 1 20 1 289 0.003 289 0.002 0.00 2 20 2 261 0.008 261 0.005 0.00 3 20 3 251 0.015 251 0.017 0.00 4 20 4 238 0.027 238 0.029 0.00 5 20 5 228 0.036 228 0.053 0.00 6 40 1 477 0.046 477 0.013 0.00 7 40 3 430 0.180 421 0.089 2.09 8 40 5 385 0.358 368 0.293 4.42 9 40 7 326 0.651 326 0.772 0.00 10 40 9 326 0.957 322 1.107 1.23 11 60 1 580 0.180 580 0.042 0.00 12 60 4 532 0.920 503 0.523 5.45 13 60 7 455 2.155 449 1.301 1.32 14 60 10 440 3.580 437 2.726 0.68 15 60 13 440 5.628 437 4.802 0.68 16 100 1 629 1.111 627 0.178 0.32 17 100 5 562 7.030 551 2.647 1.96 18 100 10 561 15.604 534 10.473 4.81 19 100 15 530 28.451 528 26.282 0.38 20 100 20 530 42.368 522 42.486 1.51 21 150 1 810 4.753 801 0.590 1.11 22 150 6 800 28.851 759 17.938 5.13 23 150 12 735 67.610 705 47.126 4.08 24 150 18 732 115.203 690 76.767 5.74 25 150 24 720 169.527 678 146.271 5.83 AVG   490.68 19.81 479.28 15.30 1.87Table7 indicates that the proposed algorithm outperforms SA in terms of solution quality. The VVND produces the best solutions to all 25 instances, while SA produces only 8 best solutions. The average gap between the two algorithms is 1.87%.


#### 5.3.2. Comparison with HD

Table8 exhibits the results.N represents the number of customers;M represents the number of SDFs; GAP = (Total cost1-Total cost2) / Total cost1∗100. The values of column “Total cost1” are the best known solution proposed by Dumas et al.[24]. The values of column “Total cost2” are the best solution obtained by 5 runs.Table 8
Comparison between HD and the proposed method.
No. N M HD Proposed method GAP Totalcost1 Totalcost2 Routecost Delaytime Pickupcost Openingcost (%) 1 20 1 335 289 263 0 16 10 13.73 2 20 2 335 261 211 0 35 15 22.09 3 20 3 335 251 177 0 54 20 25.07 4 20 4 335 238 216 0 12 10 28.96 5 20 5 335 228 195 0 23 10 31.94 6 40 1 494 477 477 0 0 0 3.44 7 40 3 494 421 352 0 49 20 14.78 8 40 5 494 368 277 0 66 25 25.51 9 40 7 494 326 253 0 48 25 34.01 10 40 9 494 322 253 0 44 25 34.82 11 60 1 609 580 561 0 14 5 4.76 12 60 4 609 503 386 0 72 45 17.41 13 60 7 609 449 331 0 63 55 26.27 14 60 10 609 437 334 0 53 50 28.24 15 60 13 609 437 334 0 53 50 28.24 16 100 1 655 627 587 0 25 15 4.27 17 100 5 655 551 489 0 37 25 15.88 18 100 10 655 534 454 0 45 35 18.47 19 100 15 655 528 447 0 46 35 19.39 20 100 20 655 522 447 0 40 35 20.31 21 150 1 859 801 747 0 39 15 6.75 22 150 6 859 759 577 0 112 70 11.64 23 150 12 859 705 541 0 94 70 17.93 24 150 18 859 690 597 0 53 40 19.67 25 150 24 859 678 504 0 89 85 21.07 AVG   590 479     19.79Table8 shows the following. (1) Compared with HD, the proposed method has a significant improvement, and the total cost is reduced by 3.44% to 34.82% with the increased SDFs. (2) When the service radius of the SDF is fixed, with the increased SDFs, pickup and the opening costs increase, but the total cost decreases.


## 5.1. Test with Time Windows Change

The test dataset consists of 100 customers (an instance n100w60.004 proposed by Dumas et al. [24]) and nine SDFs. The coordinates of the SDFs are evenly distributed in the area of 50,50: 102(10,10), 103(10,30), 104(10,45), 105(25,10), 106(25,30), 107(25,45), 108(40,10), 109(40,30), 110(40,45). The known optimal solution is 1, 94, 58, 42, 98, 82, 9, 59, 39, 75, 53, 35, 13, 84, 41, 5, 50, 70, 80, 25, 47, 55, 66, 95, 11, 23, 2, 100, 30, 67, 31, 26, 96, 21, 81, 79, 27, 38, 17, 61, 92, 86, 57, 15, 36, 19, 85, 77, 60, 20, 69, 44, 48, 64, 40, 52, 72, 73, 7, 32, 87, 29, 90, 22, 51, 65, 56, 49, 46, 91, 54, 71, 74, 78, 43, 68, 12, 18, 33, 14, 37, 88, 8, 10, 93, 16, 99, 3, 83, 97, 62, 89, 28, 45, 76, 24, 6, 4, 101, 34, 63, and the route cost is 764. When the courier delivers to the customer 98#, the courier receives the time window change information (Table 2).Table 2
Time windows change.
Customer no. Status Time window Customer no. Status Time window e t i l t i e t i l t i 6 Old TW 627 664 43 Old TW 382 413 New TW 50 100 New TW 30 80 10 Old TW 460 499 47 Old TW 34 122 New TW 100 150 New TW 500 540 13 Old TW 21 67 53 Old TW 0 68 New TW 400 440 New TW 600 668 27 Old TW 145 233 62 Old TW 510 574 New TW 350 400 New TW 110 170 34 Old TW 725 795 70 Old TW 37 128 New TW 200 260 New TW 700 758The parameters are the same as the above tests:R=20, w1=w2=w3=1, α=1, β=1, up=5. The optimal solution obtained by the proposed algorithm is shown  in Tables 3 and 4. Table 3 presents the customer assignments of the SDFs, and Table 4 presents the delivery route.Table 3
Optimal solution of customer assignment.
SDF no. Customer no. SDF no. Customer no. 102 13,62,76,89 107 / 103 28,43,45,53,59 108 4 104 12,18,24,33,68 109 26,34,37 105 63,97 110 / 106 14Table 4
Optimal solution of delivery route.
1-94-58-42-98-82-103-9-39-75-35-50-84-41-5-102-80-25-55-66-11-95-23-6-96-31-67-109-30-100-2-21-81-79-108-10-17-61-38-92-86-57-15-36-19-85-77-60-20-104-69-44-48-64-40-52-72-73-7-32-87-29-90-22-65-51-56-49-46-91-54-71-74-10678-105-27-93-3-99-16-8-88-83-47-101-70This study reports the comparisons of the reschedule route in the CP mode (RRCP) with the original delivery route (ODR) and the reschedule route in the HD mode (RRHD), where Difference = RRCP – RRHD and GAP = (RRHD - RRCP) / RRHD∗100 (see Table 5).Table 5
Comparison of the three schemes.
Item ODR RRHD RRCP Difference GAP(%) Delay time 53000 521 17 −504 96.74% Pickup cost 0 0 169 +169 – Opening cost 0 0 105 +105 – Route cost 764 703 442 −261 37.13% Total cost 53764 1224 733 −491 40.08% CPU Time (S) 0 21 22Compared with the RRHD, the RRCP increases the pickup cost and SDF opening cost by providing customer pickup services, but the total cost is reduced by 40.08%. The delay time is reduced from 521 to 17 or 96.74%; route cost is reduced from 703 to 442 or 37.13%. As carbon emission is closely related to delivery route distance, the proposed model can help effectively reduce carbon emission.


## 5.2. Sensitive Analyses

To gain additional insights, a sensitive analysis is conducted to show how the acceptable distanceR influences cost. When R ranges from 0 to 50, the results are reported in Table 6 and Figure 10.Table 6
Results of sensitive analysis ofR on cost.
Item R 0 5 10 15 20 30 40 50 Delay time 521 197 97 17 17 17 17 17 Pickup cost 0 41 97 169 169 169 169 169 Opening cost 0 60 80 105 105 105 105 105 Route cost 703 647 552 442 442 442 442 442 Total cost 1224 944 826 733 733 733 733 733Figure 10
Sensitive analysis ofR on cost.From the sensitive analysis, we can see that whenR=0, the proposed method is optimal without SDF. When 0<R≤50, the delay time and route cost are first to fall continuously and then keep invariability. The pickup cost is increased with the increase of R. From a cost optimization perspective, R=15 is the best SDF service radius in this instance.


## 5.3. Computational Results Comparison

For the evaluation of the performance of the proposed algorithm, tests based on the benchmark instance proposed by Dumas et al. [24] are used. The networks consist of one depot and 20, 40, 60, 100, and 150 customers. The width of time window is 60. The locations of SDFs are (32,5), (14,28), (48,49), (8,49), (48,25), (41,8), (22,46), (40,48), (33,2), (43,47), (34,38), (38,20), (33,9), (36,2), (14,3), (5,42), (35,16), (48,2), (22,20), (39,40), (10,25), (23,33), (36,38), and (14,34), which are generated randomly in an area of 0,50×0,50. The parameters are listed as follows: R=20, w1=w2=w3=1,α=1,β=1, up=5. The parameters of VVND are kMax = M and iterMax = M/2.


### 5.3.1. Comparison with Other Algorithms

Table7 presents comparisons of the proposed VVND and Simulated Annealing (SA). N represents the number of customer nodes;M represents the number of SDFs. The values under the “GAP” columns are calculated by the formula [ObjSA-Obj(VVND)]/Obj(SA)∗100. The solutions obtained by SA [25] are shown in Columns 4-5. Columns 6-7 show the solutions obtained from the proposed VVND. Time is the CPU time in seconds on a PC (i5-7500@3.40 GHz, 8.00GB RAM). The parameters of SA are set as follows: T=N, alpha=0.98, and Iiter=M. All the best solutions of SA and VVND are obtained with 5 runs of the algorithms.Table 7
Comparison between SA and the proposed method.
No. N M SA VVND GAP(%) Obj Time Obj Time 1 20 1 289 0.003 289 0.002 0.00 2 20 2 261 0.008 261 0.005 0.00 3 20 3 251 0.015 251 0.017 0.00 4 20 4 238 0.027 238 0.029 0.00 5 20 5 228 0.036 228 0.053 0.00 6 40 1 477 0.046 477 0.013 0.00 7 40 3 430 0.180 421 0.089 2.09 8 40 5 385 0.358 368 0.293 4.42 9 40 7 326 0.651 326 0.772 0.00 10 40 9 326 0.957 322 1.107 1.23 11 60 1 580 0.180 580 0.042 0.00 12 60 4 532 0.920 503 0.523 5.45 13 60 7 455 2.155 449 1.301 1.32 14 60 10 440 3.580 437 2.726 0.68 15 60 13 440 5.628 437 4.802 0.68 16 100 1 629 1.111 627 0.178 0.32 17 100 5 562 7.030 551 2.647 1.96 18 100 10 561 15.604 534 10.473 4.81 19 100 15 530 28.451 528 26.282 0.38 20 100 20 530 42.368 522 42.486 1.51 21 150 1 810 4.753 801 0.590 1.11 22 150 6 800 28.851 759 17.938 5.13 23 150 12 735 67.610 705 47.126 4.08 24 150 18 732 115.203 690 76.767 5.74 25 150 24 720 169.527 678 146.271 5.83 AVG   490.68 19.81 479.28 15.30 1.87Table7 indicates that the proposed algorithm outperforms SA in terms of solution quality. The VVND produces the best solutions to all 25 instances, while SA produces only 8 best solutions. The average gap between the two algorithms is 1.87%.


### 5.3.2. Comparison with HD

Table8 exhibits the results.N represents the number of customers;M represents the number of SDFs; GAP = (Total cost1-Total cost2) / Total cost1∗100. The values of column “Total cost1” are the best known solution proposed by Dumas et al.[24]. The values of column “Total cost2” are the best solution obtained by 5 runs.Table 8
Comparison between HD and the proposed method.
No. N M HD Proposed method GAP Totalcost1 Totalcost2 Routecost Delaytime Pickupcost Openingcost (%) 1 20 1 335 289 263 0 16 10 13.73 2 20 2 335 261 211 0 35 15 22.09 3 20 3 335 251 177 0 54 20 25.07 4 20 4 335 238 216 0 12 10 28.96 5 20 5 335 228 195 0 23 10 31.94 6 40 1 494 477 477 0 0 0 3.44 7 40 3 494 421 352 0 49 20 14.78 8 40 5 494 368 277 0 66 25 25.51 9 40 7 494 326 253 0 48 25 34.01 10 40 9 494 322 253 0 44 25 34.82 11 60 1 609 580 561 0 14 5 4.76 12 60 4 609 503 386 0 72 45 17.41 13 60 7 609 449 331 0 63 55 26.27 14 60 10 609 437 334 0 53 50 28.24 15 60 13 609 437 334 0 53 50 28.24 16 100 1 655 627 587 0 25 15 4.27 17 100 5 655 551 489 0 37 25 15.88 18 100 10 655 534 454 0 45 35 18.47 19 100 15 655 528 447 0 46 35 19.39 20 100 20 655 522 447 0 40 35 20.31 21 150 1 859 801 747 0 39 15 6.75 22 150 6 859 759 577 0 112 70 11.64 23 150 12 859 705 541 0 94 70 17.93 24 150 18 859 690 597 0 53 40 19.67 25 150 24 859 678 504 0 89 85 21.07 AVG   590 479     19.79Table8 shows the following. (1) Compared with HD, the proposed method has a significant improvement, and the total cost is reduced by 3.44% to 34.82% with the increased SDFs. (2) When the service radius of the SDF is fixed, with the increased SDFs, pickup and the opening costs increase, but the total cost decreases.


## 5.3.1. Comparison with Other Algorithms

Table7 presents comparisons of the proposed VVND and Simulated Annealing (SA). N represents the number of customer nodes;M represents the number of SDFs. The values under the “GAP” columns are calculated by the formula [ObjSA-Obj(VVND)]/Obj(SA)∗100. The solutions obtained by SA [25] are shown in Columns 4-5. Columns 6-7 show the solutions obtained from the proposed VVND. Time is the CPU time in seconds on a PC (i5-7500@3.40 GHz, 8.00GB RAM). The parameters of SA are set as follows: T=N, alpha=0.98, and Iiter=M. All the best solutions of SA and VVND are obtained with 5 runs of the algorithms.Table 7
Comparison between SA and the proposed method.
No. N M SA VVND GAP(%) Obj Time Obj Time 1 20 1 289 0.003 289 0.002 0.00 2 20 2 261 0.008 261 0.005 0.00 3 20 3 251 0.015 251 0.017 0.00 4 20 4 238 0.027 238 0.029 0.00 5 20 5 228 0.036 228 0.053 0.00 6 40 1 477 0.046 477 0.013 0.00 7 40 3 430 0.180 421 0.089 2.09 8 40 5 385 0.358 368 0.293 4.42 9 40 7 326 0.651 326 0.772 0.00 10 40 9 326 0.957 322 1.107 1.23 11 60 1 580 0.180 580 0.042 0.00 12 60 4 532 0.920 503 0.523 5.45 13 60 7 455 2.155 449 1.301 1.32 14 60 10 440 3.580 437 2.726 0.68 15 60 13 440 5.628 437 4.802 0.68 16 100 1 629 1.111 627 0.178 0.32 17 100 5 562 7.030 551 2.647 1.96 18 100 10 561 15.604 534 10.473 4.81 19 100 15 530 28.451 528 26.282 0.38 20 100 20 530 42.368 522 42.486 1.51 21 150 1 810 4.753 801 0.590 1.11 22 150 6 800 28.851 759 17.938 5.13 23 150 12 735 67.610 705 47.126 4.08 24 150 18 732 115.203 690 76.767 5.74 25 150 24 720 169.527 678 146.271 5.83 AVG   490.68 19.81 479.28 15.30 1.87Table7 indicates that the proposed algorithm outperforms SA in terms of solution quality. The VVND produces the best solutions to all 25 instances, while SA produces only 8 best solutions. The average gap between the two algorithms is 1.87%.


## 5.3.2. Comparison with HD

Table8 exhibits the results.N represents the number of customers;M represents the number of SDFs; GAP = (Total cost1-Total cost2) / Total cost1∗100. The values of column “Total cost1” are the best known solution proposed by Dumas et al.[24]. The values of column “Total cost2” are the best solution obtained by 5 runs.Table 8
Comparison between HD and the proposed method.
No. N M HD Proposed method GAP Totalcost1 Totalcost2 Routecost Delaytime Pickupcost Openingcost (%) 1 20 1 335 289 263 0 16 10 13.73 2 20 2 335 261 211 0 35 15 22.09 3 20 3 335 251 177 0 54 20 25.07 4 20 4 335 238 216 0 12 10 28.96 5 20 5 335 228 195 0 23 10 31.94 6 40 1 494 477 477 0 0 0 3.44 7 40 3 494 421 352 0 49 20 14.78 8 40 5 494 368 277 0 66 25 25.51 9 40 7 494 326 253 0 48 25 34.01 10 40 9 494 322 253 0 44 25 34.82 11 60 1 609 580 561 0 14 5 4.76 12 60 4 609 503 386 0 72 45 17.41 13 60 7 609 449 331 0 63 55 26.27 14 60 10 609 437 334 0 53 50 28.24 15 60 13 609 437 334 0 53 50 28.24 16 100 1 655 627 587 0 25 15 4.27 17 100 5 655 551 489 0 37 25 15.88 18 100 10 655 534 454 0 45 35 18.47 19 100 15 655 528 447 0 46 35 19.39 20 100 20 655 522 447 0 40 35 20.31 21 150 1 859 801 747 0 39 15 6.75 22 150 6 859 759 577 0 112 70 11.64 23 150 12 859 705 541 0 94 70 17.93 24 150 18 859 690 597 0 53 40 19.67 25 150 24 859 678 504 0 89 85 21.07 AVG   590 479     19.79Table8 shows the following. (1) Compared with HD, the proposed method has a significant improvement, and the total cost is reduced by 3.44% to 34.82% with the increased SDFs. (2) When the service radius of the SDF is fixed, with the increased SDFs, pickup and the opening costs increase, but the total cost decreases.


## 6. Conclusions

This study proposed a disruption recovery problem with time window changes in the last mile delivery of online shopping. One characteristic of the problem is that the delivery route could be rescheduled by using SDFs when time window changing disruptions occurred during the delivery process. The VVND algorithm was presented, which included a 2-opt algorithm improved by LR to speed up its convergence, to solve this problem. The proposed method and algorithm were tested on a set of instances. The results corroborated that the proposed method could quickly recover the delivery and reduce the total delivery cost when time window changing disruptions occurred in the last mile delivery. Meanwhile, the proposed algorithm had an evident competitiveness compared with other heuristics, and the total delivery cost could be reduced by approximately 3% to 34% with the increasing number of SDFs compared with the solution of the HD mode.



---

*Source: 2096416-2018-12-10.xml*