# Metaheuristics for a Large-Scale Vehicle Routing Problem of Same-Day Delivery in E-Commerce Logistics System

Authors: Yi Tao; Changhui Lin; Lijun Wei
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

In this paper, we introduce a new variant of large-scale vehicle routing problem that arises in the goods distribution of city e-commerce logistics, the multi-depot vehicle routing problem with order split and allocation (MD-CVRP-OSA), which incorporates the issue of split and allocation of online orders into traditional VRP. A mathematical formulation is constructed for the MD-CVRP-OSA, and an efficient metaheuristics algorithm based on a variable neighborhood search (VNS) solution framework is designed to solve it. The proposed method is tested on a large family of instances, including real-world data collected from JD.com, and the effectiveness of the VNS algorithm and also the algorithm components are analyzed.


---

## Body

## 1. Introduction

Global retail e-commerce market has been witnessing a rapid expansion on account of the shifting habits of internet users towards new shopping channels. According to Statista Digital Market Outlook, a market research firm, retail e-commerce sales worldwide in 2021 amounted to 3.78 trillion US dollars, a 16.7% increase over the previous year, and e-retail revenues are projected to grow to 5.73 trillion US dollars in 2025 (https://www.statista.com/outlook/dmo/ecommerce/worldwide). E-retail made up 17.6% of total retail sales worldwide in 2021, up from 15.9% a year prior. This growth in share is largely driven by Asia-Pacific, where e-commerce contributes 14.6% of overall retail spending. Statistics from China E-Commerce Research Center show that the transactions of retail e-commerce market in China reached $2.1 trillion in 2021, an increase of 17.2% year on year, accounting for 25.3% of the total retail sales (https://www.globaldata.com/chinese-e-commerce-market-reach-us3-3-trillion-2025-says-globaldata).In order to succeed in the highly competitive market, e-retail platforms have been striving to optimize order fulfilment operations and ensure a speedy, flexible, secure, and low-cost delivery service for customers [1]. To meet the increasing customer expectations towards shorter delivery time, many leading e-retailers started in recent years to offer same-day delivery (SDD) service in metropolitan areas that consolidates, dispatches, and delivers orders to customers on the same day the orders are placed [2]. For example, JD.com started its speedy SDD service since 2010 that delivers the orders received prior to 11 AM on the same day and the ones received before 11 PM the next day (before 3 PM) (https://ir.jd.com/news-releases/news-release-details/jdcom-launched-its-speedy-211-program-which-provides-same-day). Amazon’s SDD service has now covered major cities in over 20 countries as of May 2022. Moreover, the recently launched Prime Now Program allows customers to receive their orders on selected items within two hours for free and in one hour for $7.99 (https://primenow.amazon.com/).Management of the SDD system is costly and logistically complicated for e-retailers as it aggravates the inherent issues in urban delivery operations, such as tight delivery deadlines, small-sized orders, and low rate of order consolidations [3–5]. The logistics system of SDD service generally consists of a two-echelon network where the first level are distribution centers/warehouses for massive product storage and the second level are delivery stations or pickup stations for end customer distribution. For a guarantee of fast delivery and high service level, it is common for an SDD service provider to operate multiple warehouses closely located to metropolitan area. For example, JD.com builds four warehouses in urban district of Guangzhou, the third largest city of China. Amazon recently opened a series of so-called mini-fulfillment centers closer to four big U.S. cities as an action to guarantee packages arrive by several set times daily (https://www.reuters.com/article/us-amazon-com-delivery/amazon-adds-warehouse-network-closer-to-cities-to-speed-up-same-day-delivery-idUSKBN20Q0T3 ). Each warehouse is equipped with a fleet of vehicles. During the course of operating time, vehicles are loaded with parcels and dispatched from warehouses to visit customers’ locations [4]. In the operation of SDD, vehicles are usually not dispatched simultaneously in the beginning and may be reused multiple times during a service day [2, 6].The strategy of maintaining multiple warehouses poses challenges on the operational efficiency of SDD logistics system. Due to the limit of storage space, a single warehouse located in urban area usually cannot cover all stock keeping units (SKUs), but only keeps a certain range of them instead. For example, the four warehouses of JD.com in Guangzhou mainly store 3C products, shoes and clothing, and health care products; snacks, grain and oil, and books; home appliances and 3C products; and clothing and groceries, respectively. Given this, there is high chance that no single warehouse contains all requested SKUs for a customer order. This causes a serious issue that SKUs of an order may need to be split up and separately satisfied by more than one warehouses. Order split issue frequently arises during the order fulfillment process of SDD service under multi-warehouse mode. Even if a warehouse stores all SKUs in an order, inventory of certain SKU of that order may go below the requested amount. Another case is that as a way of promoting sales, tie-in sale strategy is often applied by the marketing department that offers discounts or deals to customers if they buy a specific combination of different SKUs. However, when the sales promotion is planned and executed, the marketing department may not be aware of the availability of the combined SKUs in the same warehouse. Under such circumstances, order split is inevitable. Figure1 illustrates an order split example where SKUs of order O1 are split and allocated to warehouses W1 and W3 because none of the three warehouses can provide all requested items of O1 at the same time.Figure 1
An illustrative example of orders split among different warehouses.In this work, we address a new goods distribution problem of SDD logistic system with order split issue under multi-warehouse mode. Each warehouse keeps a limited range of SKUs and may not be able to satisfy all order requests. Each customer order contains a number of different SKUs and requests certain amount for each SKU. Due to aforementioned reasons, orders often need to be split up and are allocated to more than one warehouses. In the actual SDD logistics operation, items of the same SKU in an order are usually packaged together as a whole for the convenience of handling, which implies that a single order can only be split on SKU level instead of being split up arbitrarily. That is, items that are of different SKUs in an order is allowed to be separated, but items of the same SKU cannot be further parted. The logistics activities involve two core processes: (1) upon receiving and accumulating online orders, splitting each of them and allocating to different warehouses if necessary and (2) designing a route for each vehicle that is assigned delivery task. The goal is to minimize the total routing cost of all vehicles. It is assumed that all the needed information of the SDD system is known to us and the VRP problem considered in our work is static.The problem studied in this paper extends the traditional vehicle routing problem (VRP) [7] by incorporating order split and allocation issue under multi-warehouse mode, which makes it essentially a multi-depot capacitated vehicle routing problem with order split and allocation (MD-CVRP-OSA). The review papers (Braekers et al. [8] and Tan & Yeh [9]) survey the most recent works on variants of vehicle routing problem and proposed exact and heuristic methods for the VRP in the literature. Related problem to the MD-CVRP-OSA are the location-routing problem (LRP) and the multi-depot VRP (MDVRP). Reviews about variants and heuristic and exact algorithms for these problems can be found in Drexl and Schneider [10], Prodhon and Prins [11], Montoya-Torres et al. [12], and Chen and Yang [13]. Besides the traditional solution approaches, there is also a recent trend to apply machine learning methods, such as deep (reinforcement) learning as a new type of heuristic to solve VRP. Interested readers may refer to Li et al. [14], Ma et al. [15], and Li et al. [16].A closely related work to the MD-CVRP-OSA is the multi-depot split delivery vehicle routing problem (MDSDVRP) introduced by Gulczynski et al. [17]. Gulczynski et al. [17] consider that the customers are not necessarily assigned to depots and allow serving customers from multiple depots. Thus, how the split of products and which depots to be assigned need to be decided. The authors developed an integer programming based heuristic for the MDSDVRP. Ray et al. [18] investigated a same problem as Gulczynski et al. [17]. They proposed an integer linear programming model and used an heuristic search method to solve the problem. Izar and Suwilo [19] studied the MDSDVRP with time windows (MDVRPSDTW), whereas Wang et al. [20] proposed the min-max split delivery multi-depot vehicle routing problem with minimum service time requirement (min-max SDMDVRP-MSTR), which allows the split of service time for each customer. However, we point out that this work differs from the aforementioned ones because SKUs cannot be further split and not all SKUs are available at all depots. Therefore, our problem cannot be considered the SDMDVRP.To the best of our knowledge, our work is the first to introduce a new and practical logistics problem that combines the joint optimization of vehicle routing and order split and allocation, which is now a big challenge in the logistics system of e-retailers. To solve the problem, we formulate it as an integer programming model and propose an efficient variable neighborhood search (VNS) [21] algorithm. Extensive numerical experiments are conducted on instances derived from classical capacitated VRP instances and on real-world instances.The rest of the paper is organized as follows. In Section2, we describe the MD-CVRP-OSA and introduce a mathematical formulation. In Section 3, we apply a VNS technique to solve the MD-CVRP-OSA. Computational results are presented in Section 4, and Section 5 concludes the paper and indicates future research directions.


## 2. Problem Description and Mathematical Formulation

The MD-CVRP-OSA addressed in this paper can be described as follows. We are given a complete directed graphG=V,A, where the node set V is further partitioned as V=Vw∪Vs. Set Vw=1,2,3,⋯,K represents K warehouses, and Vs=K+1,K+2,K+3,⋯,K+I represents I delivery stations. The arc set E is defined as A=k,j,j,k:k∈Vw,j∈Vs∪i,j,j,i:i,j∈Vs,i≠j. We assume that each warehouse k∈Vw has one vehicle to deliver the goods, and all the K vehicles are homogeneous with the same vehicle capacity Q. Each arc i,j∈A is associated with a non-negative cost cij which represents the routing cost between node i and j. Each delivery station i∈Vs serves a set Mi of customers. Figure 2 illustrates an example of the MD-CVRP-OSA.Figure 2
An example of MD-CVRP-OSA vehicle routes.In the MD-CVRP-OSA, each customer’s order is sent to the associated delivery station first and then delivered to its location. The distribution of goods from the delivery station to the individual customers can be regarded as a classical VRP, so the corresponding planning problem is not explicitly considered in the MD-CVRP-OSA.LetN be the set of all SKUs provided by the e-retailer and let qn be the weight of n-th SKU. Further, we denote the amount of n-th SKU requested by the m-th customer of station i as simn. We assume that a customer’s order is allowed to be split and allocated to multiple warehouses, each of which may only store a limited number of SKUs, but the amount of a single SKU cannot be further split up. This means that if a warehouse accepts a request on a specific SKU, it must fully satisfy it. Define pnk as a binary parameter that takes 1 if the n-th SKU is stored in warehouse k, and 0 otherwise.A vehicle route is a simple cycleR=Wk,Si,Sj,⋯,Wk in graph G passing through a warehouse Wk∈Vw and sequentially visiting stations Si,Sj,⋯⊆Vs. The cost of a route is equal to the sum of the routing costs of the arcs forming the route. The MD-CVRP-OSA consists of determining a set of at most K vehicle routes of minimum cost such that:
(i)
Each warehouse operates at most one vehicle route(ii)
A customer’s demand for an SKU must be fully serviced by the same warehouse but customer’s requests for different SKUs can be satisfied by different warehouses(iii)
The total demand of each vehicle route does not exceed the vehicle capacity


### 2.1. Mathematical Formulation

In this section, we describe a mathematical formulation for the MD-CVRP-OSA. The mathematical model defines the following decisions variables:(i)
xijk: binary variable equals to 1 if arc i, is traversed by warehouse k’s vehicle, and 0 otherwise(ii)
zimnk: binary variable equals to 1 if the n-th SKU requested by the m-th customer of station i is allocated to warehouse k, and 0 otherwiseThe MD-CVRP-OSA can be formulated as the following integer programming problem:(1)min∑k∈Vw∑i,j∈Acijxijk,s.t.(2)∑k∈Vwpnkzimnk=1,∀i∈Vs,m∈Mi,n∈N,(3)∑m∈Mi∑n∈Nzimnk≤M∑j∈V,j≠ixjik,∀k∈Vw,i∈Vs,(4)∑j∈V,j≠ixjik≤∑m∈Mi∑n∈Nzimnk,∀k∈Vw,i∈Vs,(5)∑i∈V,i≠jxijk=∑i∈V,i≠jxjik,∀k∈Vw,j∈V,(6)∑i∈V,i≠jxijk≤1,∀k∈Vw,j∈Vs,(7)∑m∈Mi∑n∈Nzimnk≤M∑j∈Vsxkjk,∀k∈Vw,i∈Vs,(8)xijk=0,∀k∈Vw,i∈Vw,j∈Vw,(9)∑n∈Nqn∑i∈Vs∑m∈Misimnzimnk≤Q,∀k∈Vw,(10)∑i∈S∑j∈V\S\Vw∪kxijk≥zimnk,∀k∈Vw,i∈Vs,m∈Mi,n∈N,S⊆V\Vw,i∈S,S∅,(11)xijk,zimnk∈0,1,k∈Vw,i∈V,j∈V,m∈Mi,n∈N.Objective (1) is to minimize the total routing cost of all vehicles. Constraint (2) indicates that the demand of each SKU of a customer order must be satisfied by one and only one warehouse. Constraints (3) and (4) state that the demand of the m-th customer of delivery station i for the n-th SKU can be fulfilled by warehouse k only when the vehicle of warehouse k visits station i, where M is a large constant. Constraint (5) guarantees that any vehicle that enters a node must also depart from that node. Constraint (6) ensures that each vehicle visits any given delivery station at most once. Constraint (7) states that if the vehicle of a warehouse is assigned delivery task, it should start its tour from the warehouse. Constraint (8) ensures that no vehicle is allowed to travel between two warehouses. Constraint (9) limits the capacity of any vehicle. Constraint (10) imposes the connectivity of the route performed by vehicle k by eliminating subtours involving stations only. Constraint (11) defines the domains of decision variables.The MD-CVRP-OSA isNP-hard. Indeed, its special case where K=1, N=1, and Mi=1 for all i∈Vs is the classical CVRP, a well-known NP-hard problem.


## 2.1. Mathematical Formulation

In this section, we describe a mathematical formulation for the MD-CVRP-OSA. The mathematical model defines the following decisions variables:(i)
xijk: binary variable equals to 1 if arc i, is traversed by warehouse k’s vehicle, and 0 otherwise(ii)
zimnk: binary variable equals to 1 if the n-th SKU requested by the m-th customer of station i is allocated to warehouse k, and 0 otherwiseThe MD-CVRP-OSA can be formulated as the following integer programming problem:(1)min∑k∈Vw∑i,j∈Acijxijk,s.t.(2)∑k∈Vwpnkzimnk=1,∀i∈Vs,m∈Mi,n∈N,(3)∑m∈Mi∑n∈Nzimnk≤M∑j∈V,j≠ixjik,∀k∈Vw,i∈Vs,(4)∑j∈V,j≠ixjik≤∑m∈Mi∑n∈Nzimnk,∀k∈Vw,i∈Vs,(5)∑i∈V,i≠jxijk=∑i∈V,i≠jxjik,∀k∈Vw,j∈V,(6)∑i∈V,i≠jxijk≤1,∀k∈Vw,j∈Vs,(7)∑m∈Mi∑n∈Nzimnk≤M∑j∈Vsxkjk,∀k∈Vw,i∈Vs,(8)xijk=0,∀k∈Vw,i∈Vw,j∈Vw,(9)∑n∈Nqn∑i∈Vs∑m∈Misimnzimnk≤Q,∀k∈Vw,(10)∑i∈S∑j∈V\S\Vw∪kxijk≥zimnk,∀k∈Vw,i∈Vs,m∈Mi,n∈N,S⊆V\Vw,i∈S,S∅,(11)xijk,zimnk∈0,1,k∈Vw,i∈V,j∈V,m∈Mi,n∈N.Objective (1) is to minimize the total routing cost of all vehicles. Constraint (2) indicates that the demand of each SKU of a customer order must be satisfied by one and only one warehouse. Constraints (3) and (4) state that the demand of the m-th customer of delivery station i for the n-th SKU can be fulfilled by warehouse k only when the vehicle of warehouse k visits station i, where M is a large constant. Constraint (5) guarantees that any vehicle that enters a node must also depart from that node. Constraint (6) ensures that each vehicle visits any given delivery station at most once. Constraint (7) states that if the vehicle of a warehouse is assigned delivery task, it should start its tour from the warehouse. Constraint (8) ensures that no vehicle is allowed to travel between two warehouses. Constraint (9) limits the capacity of any vehicle. Constraint (10) imposes the connectivity of the route performed by vehicle k by eliminating subtours involving stations only. Constraint (11) defines the domains of decision variables.The MD-CVRP-OSA isNP-hard. Indeed, its special case where K=1, N=1, and Mi=1 for all i∈Vs is the classical CVRP, a well-known NP-hard problem.


## 3. A VNS Algorithm for the MD-CVRP-OSA

To solve the MD-CVRP-OSA efficiently, a VNS algorithm is proposed in this section. The VNS algorithm introduced in Mladenovi´c and Hansen [21] and Hansen et al. [22] makes use of a series of random and improving local searches based on systematically changed neighborhoods and a shaking process that escapes from local optimum by choosing a new starting point for running an improving search. The reason that VNS is chosen to solve the MD-CVRP-OSA is because VNS and its variants are simple and effective. They have been widely applied in solving compelx combinatorial optimization problems, such VRP [23–25], and other related problems [26]. The idea of VNS is generally easy to implement with a limited number of parameters. Moreover, several groups of neighborhood structures are designed with the aim of facilitating the local searches, and the VNS approach has been proven to be very effective in combining different neighborhood structures.Algorithm 1: VNS for the MD-CVRP-OSA.
1 Construct an initial solutionS2 Define a set of local search operatorsOPTkk=1,⋯,O3S∗=S, nonImp=04whilenonImp≤maxNonImp5k=16whilek≤O7     Generate a random neighboring solutionS′ of S using OPTk8ifS′ is better than S9S=S′,k=110else11k=k+112ifS is better than S∗13S∗=S,nonImp=014else15S=S∗,nonImp=nonImp+116S=DIVERSIFYS17returnS∗The VNS algorithm proposed for the MD-CVRP-OSA is given in Algorithm1. The algorithm starts with an initial solution and employs a set of local search operators OPT. Two nested loops are used to improve the solution, where the inner loop uses the local search operators to generate random neighbouring solutions and the outer loop generates different starting points for the inner loop by a diversification mechanism. In the algorithm, variable S∗ is used to store the best-found solution, and variable nonImp records the number of outer loops during which S∗ has not been improved.At each iteration of the inner loop (lines 7-11), given the current solutionS, a random solution S′ of S is generated with an operator OPTk (k is set to equal to 1 initially). If the new solution S′ is better than the S, the algorithm accepts S′ and replaces S with S′. Then, the loop continues after having set k equal to 1, i.e., a new random solution is generated from S according to operator OPT1 in the next iteration. Otherwise, S remains unchanged, and a new random solution is generated according to neighborhood NSk+1 in the next iteration. This loop repeats until all local search operators are used and no new better solution is found.In the outer loop, a diversification procedure is introduced to produce a new initial solution based on the best-found solution (line 16). The inner loop resumes the search with the new initial solution. This process is repeated until the best-found solution is not improved duringmaxNonImp iterations.The initial solution generation, local search operator, and diversification procedure are described in details as follows.


### 3.1. Generating an Initial Solution

In this work, a three-stage method is employed to generate initial solutions for the MD-CVRP-OSA. In the first stage, for each delivery stationi∈Vs, we rank the routing cost between the location of station i and each warehouse k∈Vw, i.e., cik, in an increasing order. Hence, each delivery station i is associated with a sorted list of warehouses. In the second stage, we allocate warehouses for each delivery station. The warehouses in the sorted list of station i are sequentially selected to satisfy the SKUs requested by the customers associated with station i, the demands of which are fulfilled customer by customer, and SKU by SKU for each customer. If there are still customers with unsatisfied demand because the current warehouse does not contain the requested SKUs or the vehicle of the warehouse is fully loaded, the next warehouse in the list will be chosen. Such process continues until all demands of the customers in station i are fully satisfied. The same process is repeated to assign warehouses to all delivery stations.As a result of the first two stages, a certain number of warehouses are assigned delivery jobs to serve a given set of stations. In the last stage, we apply the well-known cost saving algorithm [27, 28] to separately determine the sequence of service for each warehouse. Define V~sk as the set of stations that are to be visited by warehouse k’s vehicle. For each station i∈V~sk, a simple route k,i,k is constructed in the first step. In the second step, for each pair of routes k,⋯,i,k and k,j,⋯,k, we calculate the cost saving ci,k+ck,j−ci,j. The pair of routes that have the largest cost saving are merged into a new route k,⋯,i,j,⋯,k in the third step. The second and third steps are repeated until all stations are included in one single route, and such cost saving algorithm is applied for each warehouse with delivery jobs.


### 3.2. Description of the Local Search Operators

The effectiveness of a VNS algorithm strongly relies on the structure of the local search operators. In this paper, we designed seven operators to generate random neighboring solutions from the current solution. In the following, we refer to a routeRk that is associated with warehouse k, Rk=r1k,r2k,⋯,rRk, where r1k=rRk∈Vw represents a warehouse and rik1≤i≤R−1∈Vs represents the stations visited by the vehicle associated with the route. Besides, for each station rik1≤i≤R−1, there is a corresponding SKU number set skuink, where skuink1≤n≤N is the number of the n-th SKU provided by warehouse r1k for station rik. According to our assumption, skuink=∑m∈Mixmnsimn (xmn is an 0-1 variable that takes 1 if the n-th SKU of the m-th order in station rik is provided by r1k and 0 otherwise), which is the combination of the number of n-th SKU requested by the customers in station rik. We define the set of SKUs whose value skuink is larger than one as the SKUs provided by r1k for station rik.The seven operators are defined as follows:(1)
Intra-swap: The operator swaps the positions of two selected stations within the same route(2)
Intra-move: The operator shifts a subtour from its position to a different position within the same route(3)
Inter-swap: The operator swaps the positions of two stations from different routes, as depicted in Figure3(4)
Inter-shift: The operator shifts a station from its position to a different route (see Figure4)(5)
Order-split: The operator moves the SKUs provided by one route for a station to a different route visiting the same station. Note that this operator is only used to split the SKUs and the travel cost of these route remains unchanged (if a station is removed from one route, all the SKUs are also moved). In Figure5, the SKU3 provided by route a is moved to route b(6)
Station-remove: The operator removes a station from one route and shift its provided SKUs for this station to another route that visits the same station. In Figure6, the station r4b is original served by routes a and b (a provides SKU3 and SKU5, while b provides SKU1). After the application of the station-remove operation, the station r4b is only served by route b. The difference between station-remove and order-split is that all the SKUs provided by one route for this station are moved to another route(7)
Super-move: The operator tries to move the stations visited by a route to another route. Firstly, it selects two routesa and b. For each station rib, it tries to move rib from b to a step by step. If rib is already in a, it just increases the SKUs number of station rib in a. Otherwise, it inserts rib into a randomly selected position in a. In Figure 7, the stations r2b, r4b and r5b are originally served by route b. After the super-move operation, these stations are moved from the route b to that of warehouse aFigure 3
Inter-swap operator.Figure 4
Inter-shift operator.Figure 5
Order-split operator.Figure 6
Station-remove operator.Figure 7
Super-move operator.Note that in the first four operators, only the position of the station is changed, while the corresponding SKUs number set remains unchanged. The resulting route is feasible only if the total demand is not larger than the vehicle capacityQ and all the SKUs provided by this route for each station must be available in the warehouse.


### 3.3. Diversification Mechanism

Diversification helps to prevent the search from trapping in local optima, and the mechanism adopted in our algorithm works as follows. Firstly, it selects two routesa and b. Then, a subsequence rsb is selected from route b, and an insert position k is selected from route a. For each station rib∈rs′b, it tries to move rib from route b to route a step by step. If rib is already in a, it just increases the SKU number of station rib in a. Otherwise, it inserts rib behind the last inserted items (the first item is inserted into position k). In Figure 8, the stations r4b and r5b are moved from route b to that of warehouse a.Figure 8
The diversification mechanism.


## 3.1. Generating an Initial Solution

In this work, a three-stage method is employed to generate initial solutions for the MD-CVRP-OSA. In the first stage, for each delivery stationi∈Vs, we rank the routing cost between the location of station i and each warehouse k∈Vw, i.e., cik, in an increasing order. Hence, each delivery station i is associated with a sorted list of warehouses. In the second stage, we allocate warehouses for each delivery station. The warehouses in the sorted list of station i are sequentially selected to satisfy the SKUs requested by the customers associated with station i, the demands of which are fulfilled customer by customer, and SKU by SKU for each customer. If there are still customers with unsatisfied demand because the current warehouse does not contain the requested SKUs or the vehicle of the warehouse is fully loaded, the next warehouse in the list will be chosen. Such process continues until all demands of the customers in station i are fully satisfied. The same process is repeated to assign warehouses to all delivery stations.As a result of the first two stages, a certain number of warehouses are assigned delivery jobs to serve a given set of stations. In the last stage, we apply the well-known cost saving algorithm [27, 28] to separately determine the sequence of service for each warehouse. Define V~sk as the set of stations that are to be visited by warehouse k’s vehicle. For each station i∈V~sk, a simple route k,i,k is constructed in the first step. In the second step, for each pair of routes k,⋯,i,k and k,j,⋯,k, we calculate the cost saving ci,k+ck,j−ci,j. The pair of routes that have the largest cost saving are merged into a new route k,⋯,i,j,⋯,k in the third step. The second and third steps are repeated until all stations are included in one single route, and such cost saving algorithm is applied for each warehouse with delivery jobs.


## 3.2. Description of the Local Search Operators

The effectiveness of a VNS algorithm strongly relies on the structure of the local search operators. In this paper, we designed seven operators to generate random neighboring solutions from the current solution. In the following, we refer to a routeRk that is associated with warehouse k, Rk=r1k,r2k,⋯,rRk, where r1k=rRk∈Vw represents a warehouse and rik1≤i≤R−1∈Vs represents the stations visited by the vehicle associated with the route. Besides, for each station rik1≤i≤R−1, there is a corresponding SKU number set skuink, where skuink1≤n≤N is the number of the n-th SKU provided by warehouse r1k for station rik. According to our assumption, skuink=∑m∈Mixmnsimn (xmn is an 0-1 variable that takes 1 if the n-th SKU of the m-th order in station rik is provided by r1k and 0 otherwise), which is the combination of the number of n-th SKU requested by the customers in station rik. We define the set of SKUs whose value skuink is larger than one as the SKUs provided by r1k for station rik.The seven operators are defined as follows:(1)
Intra-swap: The operator swaps the positions of two selected stations within the same route(2)
Intra-move: The operator shifts a subtour from its position to a different position within the same route(3)
Inter-swap: The operator swaps the positions of two stations from different routes, as depicted in Figure3(4)
Inter-shift: The operator shifts a station from its position to a different route (see Figure4)(5)
Order-split: The operator moves the SKUs provided by one route for a station to a different route visiting the same station. Note that this operator is only used to split the SKUs and the travel cost of these route remains unchanged (if a station is removed from one route, all the SKUs are also moved). In Figure5, the SKU3 provided by route a is moved to route b(6)
Station-remove: The operator removes a station from one route and shift its provided SKUs for this station to another route that visits the same station. In Figure6, the station r4b is original served by routes a and b (a provides SKU3 and SKU5, while b provides SKU1). After the application of the station-remove operation, the station r4b is only served by route b. The difference between station-remove and order-split is that all the SKUs provided by one route for this station are moved to another route(7)
Super-move: The operator tries to move the stations visited by a route to another route. Firstly, it selects two routesa and b. For each station rib, it tries to move rib from b to a step by step. If rib is already in a, it just increases the SKUs number of station rib in a. Otherwise, it inserts rib into a randomly selected position in a. In Figure 7, the stations r2b, r4b and r5b are originally served by route b. After the super-move operation, these stations are moved from the route b to that of warehouse aFigure 3
Inter-swap operator.Figure 4
Inter-shift operator.Figure 5
Order-split operator.Figure 6
Station-remove operator.Figure 7
Super-move operator.Note that in the first four operators, only the position of the station is changed, while the corresponding SKUs number set remains unchanged. The resulting route is feasible only if the total demand is not larger than the vehicle capacityQ and all the SKUs provided by this route for each station must be available in the warehouse.


## 3.3. Diversification Mechanism

Diversification helps to prevent the search from trapping in local optima, and the mechanism adopted in our algorithm works as follows. Firstly, it selects two routesa and b. Then, a subsequence rsb is selected from route b, and an insert position k is selected from route a. For each station rib∈rs′b, it tries to move rib from route b to route a step by step. If rib is already in a, it just increases the SKU number of station rib in a. Otherwise, it inserts rib behind the last inserted items (the first item is inserted into position k). In Figure 8, the stations r4b and r5b are moved from route b to that of warehouse a.Figure 8
The diversification mechanism.


## 4. Numerical Experiments

This section reports on the computational results of the VNS algorithm described in Section3. The algorithm was implemented in C++ and tested on a computer equipped with an Intel(R) Core(TM) CPU i7-7920HQ @3.10Ghz with 32GB RAM. The general purpose mixed-integer programming solver CPLEX was used to solve the integer model described in Section 2.1, where the subtour elimination constraints (10) have been handled in a cutting-plane fashion using the CPLEX callable library. A time limit of 7200 seconds was imposed on the CPLEX solver. The number of iterations iterCount of the VNS algorithm was set to 300000, and a time limit of 7200 seconds was also imposed to its execution. Besides, to show the performance of our VNS algorithm, we also compare it with another well-known meta-heuristic, tabu search. Similarly, the number of iterations of tabu search is 300000, and a time limit of 7200 second is imposed. Each of the local search operators in the proposed VNS algorithm is randomly selected with the same possibility during the execution. The length of tabu list is set to 50, and the number of candidate solutions during the search is 300.In our experiments, we considered both random and real-life instances.


### 4.1. Random Instances

We randomly generated eight classes or sets of instances by varying the number of warehouses and of stations. In the first 5 sets, the number of warehouses is set equal to 2, 4, 6, 8, and 10, respectively, and the corresponding number of stations is set equal to 5, 10, 15, 20, and 25, respectively. The number of warehouses in the last three sets is set equal to 12, and the number of stations is set equal to 30, 60 and 120, respectively. For each set, 10 instances were generated, thus providing a total of 80 instances.In each instance, the number of SKUs is set equal to 20, and the weight of each SKU is set to an integer random number between 1 and 3. The coordinatesx and y of the warehouses and the stations are randomly sampled in the range of 1,1000. The availability of the n-th SKUs at warehouse k (i.e., value pnk) is also randomly defined. The number of orders for each station and the number of SKUs for each order are randomly generated in the ranges 1,10 and 1,3, respectively. For each order, the SKUs are randomly selected from the 20 types until the requested number is reached. The number of each selected SKU is randomly selected from the range 1,3. Let the total weight of the SKUs required by all customers is Qsum; then, the vehicle capacity Q is set equal to q×Qsum/K, where q is a constant factor which is set equal to 1.25.


#### 4.1.1. Results on Random Instances

Tables1 and 2 give the results obtained for small-sized and large-sized instances, respectively. The tables show the percentage of improvement of the solution cost computed by the VNS and tabu search with respect to the solution cost provided by the CPLEX solver (“IVNS%” and “ITS%”), computed as 100×1−costVNS/costcplex and 100×1−costTS/costcplex, where costVNS,costTS, and costcplex are the solution costs found by the VNS algorithm, tabu search algorithm and by CPLEX, respectively. In addition, for each method, the tables show the computing time in seconds (“ts”).Table 1
Results on randomly generated small-sized instances.
SetIdCPLEXTSVNScostcplext (s)costTSITS (%)t (s)costVNSIVNS (%)t (s)1K=2;I=514401.604401.60.0534401.60.04921955.501955.50.0481955.50.04332674.502674.50.0462674.50.05042292.502292.50.0582292.50.04953317.713321.8-0.1473317.70.05162494.502494.50.0552494.50.04872061.902061.90.0512061.90.04683595.5233595.50.0623595.50.05792380.502380.50.0582380.50.047103313.4383316.2-0.1543313.40.045Avg2848.862849.5-0.02472848.80.0492K=4;I=1016838.572026833.30.11586831.40.116727697.272017428.53.51357044.28.512736383.472006383.40.01986383.40.022546400.672026387.00.22016387.00.221255419.172015302.42.21515216.33.710667011.872016725.14.11536613.35.714275198.272015198.20.02055198.20.023186734.672016684.20.71476684.20.713595141.072005141.00.01565141.00.0124105664.972015664.90.01695664.90.0172Avg6248.972016174.81.11676116.41.71643K=6;I=1517784.372027251.86.82937050.09.427128703.272028488.52.52958461.02.826436100.372095896.63.33155865.73.822746710.072066712.10.02846705.20.139757059.772026995.00.94976995.00.952568312.872127205.313.32587193.013.524076279.572015915.35.82185859.16.732787079.572016431.89.12636488.68.325796977.872076912.40.92646905.11.0247108633.372098125.65.94288091.46.3440Avg7364.072066993.44.93286961.45.33364K=8;I=2018192.472118015.32.26207941.03.156829335.772157938.615.05127526.419.4490310744.072158125.324.44887876.526.745349506.272019410.31.04689321.01.940358530.472188284.62.94728218.83.751068276.872027648.97.64157599.78.247677201.372127015.32.65616904.44.157588201.472187529.88.23687363.210.2397910527.772168564.218.78108298.821.2774108235.272097771.35.66237574.28.0559Avg8875.172128030.48.85547862.410.6554Table 2
Results on randomly generated large-sized instances.
SetIdCPLEXTSVNScostcplext (s)costTSITS (%)t (s)costVNSIVNS (%)t (s)5K=10;I=2518157.072137548.67.59577399.89.3108629635.072008842.38.26558073.916.2630310847.772229899.28.79319408.713.394949072.372288321.48.312068146.610.21127511067.372078902.519.66308305.825.064269904.472219328.65.86029167.17.463578639.772257425.314.16847478.113.463088904.472218518.64.311248420.15.4119898928.372298215.38.07987813.612.5776109697.972018962.07.66588623.711.1609Avg9485.472178596.49.28808283.712.48846K=12;I=30116404.4721511053.232.6142310135.038.21342214227.272028925.337.315118745.838.51438316787.872019563.243.011029030.146.21061416888.472199847.341.79848700.848.51012511812.1721910642.59.9210610708.59.32008614900.4721411254.924.5265810661.428.42836727326.9720413478.650.7102810213.962.6109788421.872108210.62.519878149.23.21819915415.072009102.541.010898965.441.811651013331.3721810894.518.3138410649.320.11464Avg15551.5721410297.330.115279595.933.715247K=12;I=60133768.6722311673.665.4716711324.866.57200241853.6721412868.469.3720012897.369.27200338638.8721813546.064.9720012988.866.47200439574.1721212023.869.6720011266.771.57200564875.9722211675.482.0720011367.082.57200617687.5725913245.225.1720013515.523.67200748120.1723013845.271.2720012389.074.37200839105.5721614265.363.5715713987.164.27077936150.2720511547.868.1720011363.468.672001056085.3722512875.677.0720012530.777.77200Avg41586.0721512756.665.6719212363.066.471888K=12;I=1201166196.7720220144.387.8720019794.088.172002100338.8720218125.481.9720017859.782.272003118469.2720321425.381.9720021192.282.172004115770.5720220015.682.7720019568.683.172005166901.8720121546.887.1720020921.287.572006137609.3720120571.385.1720020250.385.372007124766.9720117785.685.7720017334.386.172008137447.7721121445.784.4720021093.284.772009119388.4720322863.480.8720022197.981.4720010130576.4720317557.686.6720017425.986.77200Avg131746.6720620148.184.4719919763.784.77199On the small-sized instances, Table1 shows that both CPLEX and VNS computed the optimal solutions for all the instances of set 1. Tabu search can find eight optimal solutions out of ten. On the remaining sets, the table shows that the VNS algorithm and tabu search algorithm greatly improved the solutions provided by CPLEX. The improvement increases as the size of instances becomes larger. Meanwhile, our proposed VNS algorithm outperformed tabu search algorithm on almost all instances. Further, the computing time spent by the VNS and tabu search is on average limited, being equal to less than 800 seconds.On the large-sized instances, the VNS algorithm and tabu search algorithm found better solutions than CPLEX for all the instances. None of the instances was solved to optimality by CPLEX within the imposed time limit, and the VNS and tabu search were capable of greatly improving the solutions provided by CPLEX, especially for the instances of sets 7 and 8. Similarly, as the case of small-sized instances, our proposed VNS algorithm outperformed tabu search algorithm on almost all instances. On the larger instances, the VNS and tabu search algorithm reached the time limit imposed to its execution.In summary, the VNS approach improves the results significantly compared to CPLEX, especially for the large-sized instances.To investigate the convergence behavior of the VNS algorithm on difficult instances of sets 7 and 8, we ran the VNS algorithm without any time limit, and we recorded the cost of the best solution found after every 10000 iterations. The results obtained for each instances of the two sets are given in Figures9(a) and 9(b), respectively, where the xaxis reports the number of iterations (the unit is 104) and the yaxis reports the percentage of the improvement of the solution cost with respect to the previous best solution. The results show that VNS converges quite quickly for instances of set 7, whereas a slower converge rate can be observed for instances of set 8.Figure 9
Convergence of the VNS algorithm on sets of instances 7 and 8.
(a)
Instances in set 7(b)
Instances in set 8


### 4.2. Real-World Instances

This work was motivated by a real-world problem. In this section, a case study from JD.com, one of China’s biggest e-commerce companies, is analyzed and solved with the proposed VNS approach.


#### 4.2.1. A Case Study from JD.com: Problem Description

To serve online customer demands in Guangzhou, the third largest city of China, JD.com maintains four warehouses located within or very close to the urban area. The locations of the fours warehouses are depicted in Figure10: Asia No. 1 warehouse, South China Logistics Center Foshan Park (FS warehouse), the 2nd South China Logistics Center Machong Park (MC warehouse), and South China Logistics Center Luogang Park (LG warehouse). In the figure, the black circles represent the warehouses, and the empty circles are the delivery stations. The following categories of SKUs are stored in the warehouses: 3C products, shoes and clothing, and health care products; snacks, grain and oil, and books; home appliances and 3C products; and clothing and groceries, respectively.Figure 10
Real-world instance: locations of warehouses and stations points.Parcel deliveries are handled by means of a fleet of vehicles from the warehouses to the delivery stations that are scattered over the urban area. At each station, orders placed by nearby residents are accumulated. To fulfill the demands in these delivery stations, logistics manager should simultaneously optimize the order allocation and routing with the aim of minimizing the total travelling distance. As one of the largest e-retailers of China, JD.com faces massive amount of online orders everyday. Upon receiving orders, the handling system needs to split and allocate it immediately and delivers it within very short time once the vehicle is available.In this case study, we consider five real cases in Guangzhou city. The following assumptions were made in considering the data provided by JD.com:(i)
The travelling distances between each pair of points of the distribution network were approximated with the Euclidean measure(ii)
Time windows constrains were ignored, and also all returned orders were not considered(iii)
The vehicle fleet is assumed to be homogeneousThe number of the delivery stations with delivery demands ranges between 13 and 33, and the total number of orders from all delivery stations that need to be fulfilled in each case ranges from 157 to 396. The vehicle capacity of the vehicles is set equal to 6,800 KG.


#### 4.2.2. Results Obtained

The results obtained by applying the VNS algorithm are summarized in Table1. The first five columns of the table give the instance name, the number of warehouses K, the number of delivery stations I, the total number of orders OTOT=∑i∈VsMi, and the vehicle capacityQ.Due to the huge amount of daily delivery orders and the latest service options, such as “deliver within one hour” and “deliver within three hours,” launched in many big cities by JD.com, the decision on the order split, allocation, and routing needs to be made within a very limited computing time. For this reason, we record the values of the solutions generated by the VNS algorithm after 15, 30, and 60 minutes, and we compare the obtained values with respect to the cost of the initial solution.For each instance, Table3 reports the total distance (in kilometers) corresponding to the cost of the initial solution computed by the VNS (“z0”), and the solution costs after 15, 30, and 60 minutes (“z1, z2, z3”), respectively. The table also shows the percentage gap of solutions z1, z2, and z3 with respect to solution “z0”.Table 3
Results on real-world instances: the JD.com case.
IndexKIOTQz0z1gap1z2gap2z3gap3Case14131576,80065.7454.3720.91%54.3720.91%54.3720.91%Case24182186,800114.8691.9724.89%91.0926.10%91.0926.10%Case34232766,800126.01103.7621.44%102.3923.07%100.6325.22%Case44283366,800144.69119.2121.37%116.7923.89%114.1826.72%Case54333966,800173.52143.5520.88%140.2123.76%132.0431.41%Average124.96102.5721.83%100.9723.76%98.4626.92%The results shown in Table3 can be commented as follows. The initial heuristic finds feasible solutions for all the instances with an average value of 124.96 kilometers. Starting from the initial solutions, the VNS algorithm improves this value by 21.83%, 23.76%, and 26.92% on average for the 15, 30, and 60 minutes runs, respectively. The results have shown that the proposed VNS algorithm can be an effective tool to deal with the fast decisions needed by the order fulfillment process in JD.com.As an example of the solutions obtained, Figure11 gives the solution obtained after 60 minutes by the VNS regarding instance Case1 depicted in Figure 10. In instance Case1, four warehouses are used to serve customers in Guangzhou city, and 13 delivery stations are associated with the customer orders that need to be fulfilled at that time. The SKUs stored in each warehouse and the SKUs requested by each station are also shown in Figure 10. Note that for each warehouse, we only show the SKUs that may be needed in this case. Figure 11 displays the four routes designed by the algorithm to deliver parcels to the delivery stations. Among these stations, Xinshi, Longgui, Taihe, Longdong, Huapu, Yonghe, Xincun, Luotou, Xintang, Xietong, and Luoxi need to be visited twice which means that the customer orders associated with these stations are spilt up and allocated to more than one warehouses.Figure 11
Vehicle routes for real-world instance Case1.


### 4.3. Impact of the Main VNS Components

We conducted additional experiments to measure the contribution of each operator of the VNS. More precisely, from each of the 5, 6, 7, and 8 instance sets, we selected two instances and ran the VNS algorithm by selectively disabling one of the following three operators: order-split, station-remove and supper-move.Table4 gives the results obtained. In the table, column head “VNS” reports the best results obtained by the VNS algorithm, whereas column heads “NoOrderSplit,” “NoStationRemove,” and “NoSupperMove” give the results obtained by the VNS without the order-split, station-remove, and supper-move operators, respectively. Column Imp% reports the percentage of improvement of the different VNS variants considered; a negative value means that the corresponding solution is worse than the solution computed by the VNS with all operators.Table 4
Impact of the main VNS operators.
SetIdVNSNoOrderSplitNoStationRemoveNoSupperMoveCostt (s)CostImp%t (s)CostImp%t (s)CostImp%t (s)519408.794910210.6− 8.583110775.6− 14.55589827.7− 4.5579108146.611278225.5− 1.011728316.4− 2.19668357.0− 2.6936619030.110619078.7− 0.510749648.4− 6.816559255.0− 2.51260108700.818829284.8− 6.79548873.6− 2.010028955.6− 2.918877112988.8720013357.3− 2.8654815115.6− 16.4298812794.31.559051011266.7720011931.7− 5.9720012905.6− 14.5494411449.0− 1.672008121192.2720021749.6− 2.6720021532.7− 1.6720023694.8− 11.872001019568.6720020638.5− 5.5720020283.7− 3.7720019491.10.47200The table clearly shows that all operators are affective and that in only two cases improved solutions have been computed.


### 4.4. Sensitivity Analysis-Vehicle Capacity and SKUs Availability

In this section, we perform a second set of experiments focused on the impact of the vehicle capacity and the SKUs availability. Also for these experiments, we considered two instances from each of the 5, 6, 7, and 8 instance sets.


#### 4.4.1. Vehicle Capacity

We recall that the vehicle capacityQ is set equal to q×Qsum/K, where q is a parameter, and Qsum is the total weight of all the required SKUs. In our experiments, we set the value of q equal to 1.1, 1.15, 1.2, 1.25, 1.3, 1.35, and 1.4, respectively. The results obtained are summarized in Table 5 for the different values of q, where column Imp% gives the percentage of the improvement of the solution cost with respect to the solution cost computed with q=1.1.Table 5
Impact of the vehicle capacityQ.
SetIdq=1:1q=1:15q=1:2q=1:25q=1:3q=1:35q=1:4CostCostImp%CostImp%CostImp%CostImp%CostImp%CostImp%519450.18461.810.57853.116.97478.120.97471.220.97397.321.77355.022.2109529.69284.42.69209.93.48420.111.68227.913.77925.316.87746.618.76112142.711012.29.310896.910.310135.016.510085.216.99789.319.49728.419.91010198.69966.02.39363.68.28745.814.28519.616.58378.017.98193.419.77110198.69966.02.39363.68.28745.814.28519.616.58378.017.98193.419.71013886.913588.12.212997.46.412897.37.112535.89.712349.811.112094.912.98123603.023603.00.021144.110.419794.016.119573.617.119178.718.718392.822.11021297.719905.66.518067.415.217859.716.117617.817.317606.217.316245.423.7The table shows that, as expected, the smaller the valueq, the more expensive the delivery cost and hence implies that the right trade off between the distribution cost and the vehicle capacity needs to be done.


#### 4.4.2. SKUs Availability

We recall that when the (0-1) coefficientpnk is equal to 1, it means that the n-th SKUs is stored or available at warehouse k. In the results reported in Section 4.1, the probability of stockout (i.e., pnk=0) was set equal to 1/K. In the new experiments reported in this section, we compare the case where all SKUs are available to all warehouses (“NoStockOut” case), i.e., pnk=1∀i∈N, k∈Vw, with the case where the probability of stockout is set equal to 1/K (as in Section 4.1 (“StockOut(1/K)” case)) and the case where the probability is set equal to 0.5 (“StockOut(0.5)” case)).The results obtained are summarized in Table6, where column Imp% gives the percentage of improvement computed with respect to the solution cost obtained for case “NoStockOut.”Table 6
Sensitivity analysis on probability of stock out.
SetIdNoStockOutStockOut (1/K)StockOut (0.5)CostCostImp%CostImp%515748.87399.8− 28.716796.3− 192.2106156.29408.7− 52.815638.5− 154.0618760.110135.0− 15.722336.9− 155.0106847.68745.8− 27.720300.6− 196.5718122.111324.8− 39.431633.1− 289.5109320.312897.3− 38.433695.7− 261.58113687.319794.0− 44.649911.2− 264.71014308.017859.7− 24.850973.9− 256.3The results clearly show that the probability of stock out has a significant effect on the total distribution cost. When the probability increases to 0.5, the cost increases up to almost 4 times the cost of no “NoStockOut,” and the right trade off between the distribution cost and SKUs availability at the different warehouses needs to be done.


## 4.1. Random Instances

We randomly generated eight classes or sets of instances by varying the number of warehouses and of stations. In the first 5 sets, the number of warehouses is set equal to 2, 4, 6, 8, and 10, respectively, and the corresponding number of stations is set equal to 5, 10, 15, 20, and 25, respectively. The number of warehouses in the last three sets is set equal to 12, and the number of stations is set equal to 30, 60 and 120, respectively. For each set, 10 instances were generated, thus providing a total of 80 instances.In each instance, the number of SKUs is set equal to 20, and the weight of each SKU is set to an integer random number between 1 and 3. The coordinatesx and y of the warehouses and the stations are randomly sampled in the range of 1,1000. The availability of the n-th SKUs at warehouse k (i.e., value pnk) is also randomly defined. The number of orders for each station and the number of SKUs for each order are randomly generated in the ranges 1,10 and 1,3, respectively. For each order, the SKUs are randomly selected from the 20 types until the requested number is reached. The number of each selected SKU is randomly selected from the range 1,3. Let the total weight of the SKUs required by all customers is Qsum; then, the vehicle capacity Q is set equal to q×Qsum/K, where q is a constant factor which is set equal to 1.25.


### 4.1.1. Results on Random Instances

Tables1 and 2 give the results obtained for small-sized and large-sized instances, respectively. The tables show the percentage of improvement of the solution cost computed by the VNS and tabu search with respect to the solution cost provided by the CPLEX solver (“IVNS%” and “ITS%”), computed as 100×1−costVNS/costcplex and 100×1−costTS/costcplex, where costVNS,costTS, and costcplex are the solution costs found by the VNS algorithm, tabu search algorithm and by CPLEX, respectively. In addition, for each method, the tables show the computing time in seconds (“ts”).Table 1
Results on randomly generated small-sized instances.
SetIdCPLEXTSVNScostcplext (s)costTSITS (%)t (s)costVNSIVNS (%)t (s)1K=2;I=514401.604401.60.0534401.60.04921955.501955.50.0481955.50.04332674.502674.50.0462674.50.05042292.502292.50.0582292.50.04953317.713321.8-0.1473317.70.05162494.502494.50.0552494.50.04872061.902061.90.0512061.90.04683595.5233595.50.0623595.50.05792380.502380.50.0582380.50.047103313.4383316.2-0.1543313.40.045Avg2848.862849.5-0.02472848.80.0492K=4;I=1016838.572026833.30.11586831.40.116727697.272017428.53.51357044.28.512736383.472006383.40.01986383.40.022546400.672026387.00.22016387.00.221255419.172015302.42.21515216.33.710667011.872016725.14.11536613.35.714275198.272015198.20.02055198.20.023186734.672016684.20.71476684.20.713595141.072005141.00.01565141.00.0124105664.972015664.90.01695664.90.0172Avg6248.972016174.81.11676116.41.71643K=6;I=1517784.372027251.86.82937050.09.427128703.272028488.52.52958461.02.826436100.372095896.63.33155865.73.822746710.072066712.10.02846705.20.139757059.772026995.00.94976995.00.952568312.872127205.313.32587193.013.524076279.572015915.35.82185859.16.732787079.572016431.89.12636488.68.325796977.872076912.40.92646905.11.0247108633.372098125.65.94288091.46.3440Avg7364.072066993.44.93286961.45.33364K=8;I=2018192.472118015.32.26207941.03.156829335.772157938.615.05127526.419.4490310744.072158125.324.44887876.526.745349506.272019410.31.04689321.01.940358530.472188284.62.94728218.83.751068276.872027648.97.64157599.78.247677201.372127015.32.65616904.44.157588201.472187529.88.23687363.210.2397910527.772168564.218.78108298.821.2774108235.272097771.35.66237574.28.0559Avg8875.172128030.48.85547862.410.6554Table 2
Results on randomly generated large-sized instances.
SetIdCPLEXTSVNScostcplext (s)costTSITS (%)t (s)costVNSIVNS (%)t (s)5K=10;I=2518157.072137548.67.59577399.89.3108629635.072008842.38.26558073.916.2630310847.772229899.28.79319408.713.394949072.372288321.48.312068146.610.21127511067.372078902.519.66308305.825.064269904.472219328.65.86029167.17.463578639.772257425.314.16847478.113.463088904.472218518.64.311248420.15.4119898928.372298215.38.07987813.612.5776109697.972018962.07.66588623.711.1609Avg9485.472178596.49.28808283.712.48846K=12;I=30116404.4721511053.232.6142310135.038.21342214227.272028925.337.315118745.838.51438316787.872019563.243.011029030.146.21061416888.472199847.341.79848700.848.51012511812.1721910642.59.9210610708.59.32008614900.4721411254.924.5265810661.428.42836727326.9720413478.650.7102810213.962.6109788421.872108210.62.519878149.23.21819915415.072009102.541.010898965.441.811651013331.3721810894.518.3138410649.320.11464Avg15551.5721410297.330.115279595.933.715247K=12;I=60133768.6722311673.665.4716711324.866.57200241853.6721412868.469.3720012897.369.27200338638.8721813546.064.9720012988.866.47200439574.1721212023.869.6720011266.771.57200564875.9722211675.482.0720011367.082.57200617687.5725913245.225.1720013515.523.67200748120.1723013845.271.2720012389.074.37200839105.5721614265.363.5715713987.164.27077936150.2720511547.868.1720011363.468.672001056085.3722512875.677.0720012530.777.77200Avg41586.0721512756.665.6719212363.066.471888K=12;I=1201166196.7720220144.387.8720019794.088.172002100338.8720218125.481.9720017859.782.272003118469.2720321425.381.9720021192.282.172004115770.5720220015.682.7720019568.683.172005166901.8720121546.887.1720020921.287.572006137609.3720120571.385.1720020250.385.372007124766.9720117785.685.7720017334.386.172008137447.7721121445.784.4720021093.284.772009119388.4720322863.480.8720022197.981.4720010130576.4720317557.686.6720017425.986.77200Avg131746.6720620148.184.4719919763.784.77199On the small-sized instances, Table1 shows that both CPLEX and VNS computed the optimal solutions for all the instances of set 1. Tabu search can find eight optimal solutions out of ten. On the remaining sets, the table shows that the VNS algorithm and tabu search algorithm greatly improved the solutions provided by CPLEX. The improvement increases as the size of instances becomes larger. Meanwhile, our proposed VNS algorithm outperformed tabu search algorithm on almost all instances. Further, the computing time spent by the VNS and tabu search is on average limited, being equal to less than 800 seconds.On the large-sized instances, the VNS algorithm and tabu search algorithm found better solutions than CPLEX for all the instances. None of the instances was solved to optimality by CPLEX within the imposed time limit, and the VNS and tabu search were capable of greatly improving the solutions provided by CPLEX, especially for the instances of sets 7 and 8. Similarly, as the case of small-sized instances, our proposed VNS algorithm outperformed tabu search algorithm on almost all instances. On the larger instances, the VNS and tabu search algorithm reached the time limit imposed to its execution.In summary, the VNS approach improves the results significantly compared to CPLEX, especially for the large-sized instances.To investigate the convergence behavior of the VNS algorithm on difficult instances of sets 7 and 8, we ran the VNS algorithm without any time limit, and we recorded the cost of the best solution found after every 10000 iterations. The results obtained for each instances of the two sets are given in Figures9(a) and 9(b), respectively, where the xaxis reports the number of iterations (the unit is 104) and the yaxis reports the percentage of the improvement of the solution cost with respect to the previous best solution. The results show that VNS converges quite quickly for instances of set 7, whereas a slower converge rate can be observed for instances of set 8.Figure 9
Convergence of the VNS algorithm on sets of instances 7 and 8.
(a)
Instances in set 7(b)
Instances in set 8


## 4.1.1. Results on Random Instances

Tables1 and 2 give the results obtained for small-sized and large-sized instances, respectively. The tables show the percentage of improvement of the solution cost computed by the VNS and tabu search with respect to the solution cost provided by the CPLEX solver (“IVNS%” and “ITS%”), computed as 100×1−costVNS/costcplex and 100×1−costTS/costcplex, where costVNS,costTS, and costcplex are the solution costs found by the VNS algorithm, tabu search algorithm and by CPLEX, respectively. In addition, for each method, the tables show the computing time in seconds (“ts”).Table 1
Results on randomly generated small-sized instances.
SetIdCPLEXTSVNScostcplext (s)costTSITS (%)t (s)costVNSIVNS (%)t (s)1K=2;I=514401.604401.60.0534401.60.04921955.501955.50.0481955.50.04332674.502674.50.0462674.50.05042292.502292.50.0582292.50.04953317.713321.8-0.1473317.70.05162494.502494.50.0552494.50.04872061.902061.90.0512061.90.04683595.5233595.50.0623595.50.05792380.502380.50.0582380.50.047103313.4383316.2-0.1543313.40.045Avg2848.862849.5-0.02472848.80.0492K=4;I=1016838.572026833.30.11586831.40.116727697.272017428.53.51357044.28.512736383.472006383.40.01986383.40.022546400.672026387.00.22016387.00.221255419.172015302.42.21515216.33.710667011.872016725.14.11536613.35.714275198.272015198.20.02055198.20.023186734.672016684.20.71476684.20.713595141.072005141.00.01565141.00.0124105664.972015664.90.01695664.90.0172Avg6248.972016174.81.11676116.41.71643K=6;I=1517784.372027251.86.82937050.09.427128703.272028488.52.52958461.02.826436100.372095896.63.33155865.73.822746710.072066712.10.02846705.20.139757059.772026995.00.94976995.00.952568312.872127205.313.32587193.013.524076279.572015915.35.82185859.16.732787079.572016431.89.12636488.68.325796977.872076912.40.92646905.11.0247108633.372098125.65.94288091.46.3440Avg7364.072066993.44.93286961.45.33364K=8;I=2018192.472118015.32.26207941.03.156829335.772157938.615.05127526.419.4490310744.072158125.324.44887876.526.745349506.272019410.31.04689321.01.940358530.472188284.62.94728218.83.751068276.872027648.97.64157599.78.247677201.372127015.32.65616904.44.157588201.472187529.88.23687363.210.2397910527.772168564.218.78108298.821.2774108235.272097771.35.66237574.28.0559Avg8875.172128030.48.85547862.410.6554Table 2
Results on randomly generated large-sized instances.
SetIdCPLEXTSVNScostcplext (s)costTSITS (%)t (s)costVNSIVNS (%)t (s)5K=10;I=2518157.072137548.67.59577399.89.3108629635.072008842.38.26558073.916.2630310847.772229899.28.79319408.713.394949072.372288321.48.312068146.610.21127511067.372078902.519.66308305.825.064269904.472219328.65.86029167.17.463578639.772257425.314.16847478.113.463088904.472218518.64.311248420.15.4119898928.372298215.38.07987813.612.5776109697.972018962.07.66588623.711.1609Avg9485.472178596.49.28808283.712.48846K=12;I=30116404.4721511053.232.6142310135.038.21342214227.272028925.337.315118745.838.51438316787.872019563.243.011029030.146.21061416888.472199847.341.79848700.848.51012511812.1721910642.59.9210610708.59.32008614900.4721411254.924.5265810661.428.42836727326.9720413478.650.7102810213.962.6109788421.872108210.62.519878149.23.21819915415.072009102.541.010898965.441.811651013331.3721810894.518.3138410649.320.11464Avg15551.5721410297.330.115279595.933.715247K=12;I=60133768.6722311673.665.4716711324.866.57200241853.6721412868.469.3720012897.369.27200338638.8721813546.064.9720012988.866.47200439574.1721212023.869.6720011266.771.57200564875.9722211675.482.0720011367.082.57200617687.5725913245.225.1720013515.523.67200748120.1723013845.271.2720012389.074.37200839105.5721614265.363.5715713987.164.27077936150.2720511547.868.1720011363.468.672001056085.3722512875.677.0720012530.777.77200Avg41586.0721512756.665.6719212363.066.471888K=12;I=1201166196.7720220144.387.8720019794.088.172002100338.8720218125.481.9720017859.782.272003118469.2720321425.381.9720021192.282.172004115770.5720220015.682.7720019568.683.172005166901.8720121546.887.1720020921.287.572006137609.3720120571.385.1720020250.385.372007124766.9720117785.685.7720017334.386.172008137447.7721121445.784.4720021093.284.772009119388.4720322863.480.8720022197.981.4720010130576.4720317557.686.6720017425.986.77200Avg131746.6720620148.184.4719919763.784.77199On the small-sized instances, Table1 shows that both CPLEX and VNS computed the optimal solutions for all the instances of set 1. Tabu search can find eight optimal solutions out of ten. On the remaining sets, the table shows that the VNS algorithm and tabu search algorithm greatly improved the solutions provided by CPLEX. The improvement increases as the size of instances becomes larger. Meanwhile, our proposed VNS algorithm outperformed tabu search algorithm on almost all instances. Further, the computing time spent by the VNS and tabu search is on average limited, being equal to less than 800 seconds.On the large-sized instances, the VNS algorithm and tabu search algorithm found better solutions than CPLEX for all the instances. None of the instances was solved to optimality by CPLEX within the imposed time limit, and the VNS and tabu search were capable of greatly improving the solutions provided by CPLEX, especially for the instances of sets 7 and 8. Similarly, as the case of small-sized instances, our proposed VNS algorithm outperformed tabu search algorithm on almost all instances. On the larger instances, the VNS and tabu search algorithm reached the time limit imposed to its execution.In summary, the VNS approach improves the results significantly compared to CPLEX, especially for the large-sized instances.To investigate the convergence behavior of the VNS algorithm on difficult instances of sets 7 and 8, we ran the VNS algorithm without any time limit, and we recorded the cost of the best solution found after every 10000 iterations. The results obtained for each instances of the two sets are given in Figures9(a) and 9(b), respectively, where the xaxis reports the number of iterations (the unit is 104) and the yaxis reports the percentage of the improvement of the solution cost with respect to the previous best solution. The results show that VNS converges quite quickly for instances of set 7, whereas a slower converge rate can be observed for instances of set 8.Figure 9
Convergence of the VNS algorithm on sets of instances 7 and 8.
(a)
Instances in set 7(b)
Instances in set 8


## 4.2. Real-World Instances

This work was motivated by a real-world problem. In this section, a case study from JD.com, one of China’s biggest e-commerce companies, is analyzed and solved with the proposed VNS approach.


### 4.2.1. A Case Study from JD.com: Problem Description

To serve online customer demands in Guangzhou, the third largest city of China, JD.com maintains four warehouses located within or very close to the urban area. The locations of the fours warehouses are depicted in Figure10: Asia No. 1 warehouse, South China Logistics Center Foshan Park (FS warehouse), the 2nd South China Logistics Center Machong Park (MC warehouse), and South China Logistics Center Luogang Park (LG warehouse). In the figure, the black circles represent the warehouses, and the empty circles are the delivery stations. The following categories of SKUs are stored in the warehouses: 3C products, shoes and clothing, and health care products; snacks, grain and oil, and books; home appliances and 3C products; and clothing and groceries, respectively.Figure 10
Real-world instance: locations of warehouses and stations points.Parcel deliveries are handled by means of a fleet of vehicles from the warehouses to the delivery stations that are scattered over the urban area. At each station, orders placed by nearby residents are accumulated. To fulfill the demands in these delivery stations, logistics manager should simultaneously optimize the order allocation and routing with the aim of minimizing the total travelling distance. As one of the largest e-retailers of China, JD.com faces massive amount of online orders everyday. Upon receiving orders, the handling system needs to split and allocate it immediately and delivers it within very short time once the vehicle is available.In this case study, we consider five real cases in Guangzhou city. The following assumptions were made in considering the data provided by JD.com:(i)
The travelling distances between each pair of points of the distribution network were approximated with the Euclidean measure(ii)
Time windows constrains were ignored, and also all returned orders were not considered(iii)
The vehicle fleet is assumed to be homogeneousThe number of the delivery stations with delivery demands ranges between 13 and 33, and the total number of orders from all delivery stations that need to be fulfilled in each case ranges from 157 to 396. The vehicle capacity of the vehicles is set equal to 6,800 KG.


### 4.2.2. Results Obtained

The results obtained by applying the VNS algorithm are summarized in Table1. The first five columns of the table give the instance name, the number of warehouses K, the number of delivery stations I, the total number of orders OTOT=∑i∈VsMi, and the vehicle capacityQ.Due to the huge amount of daily delivery orders and the latest service options, such as “deliver within one hour” and “deliver within three hours,” launched in many big cities by JD.com, the decision on the order split, allocation, and routing needs to be made within a very limited computing time. For this reason, we record the values of the solutions generated by the VNS algorithm after 15, 30, and 60 minutes, and we compare the obtained values with respect to the cost of the initial solution.For each instance, Table3 reports the total distance (in kilometers) corresponding to the cost of the initial solution computed by the VNS (“z0”), and the solution costs after 15, 30, and 60 minutes (“z1, z2, z3”), respectively. The table also shows the percentage gap of solutions z1, z2, and z3 with respect to solution “z0”.Table 3
Results on real-world instances: the JD.com case.
IndexKIOTQz0z1gap1z2gap2z3gap3Case14131576,80065.7454.3720.91%54.3720.91%54.3720.91%Case24182186,800114.8691.9724.89%91.0926.10%91.0926.10%Case34232766,800126.01103.7621.44%102.3923.07%100.6325.22%Case44283366,800144.69119.2121.37%116.7923.89%114.1826.72%Case54333966,800173.52143.5520.88%140.2123.76%132.0431.41%Average124.96102.5721.83%100.9723.76%98.4626.92%The results shown in Table3 can be commented as follows. The initial heuristic finds feasible solutions for all the instances with an average value of 124.96 kilometers. Starting from the initial solutions, the VNS algorithm improves this value by 21.83%, 23.76%, and 26.92% on average for the 15, 30, and 60 minutes runs, respectively. The results have shown that the proposed VNS algorithm can be an effective tool to deal with the fast decisions needed by the order fulfillment process in JD.com.As an example of the solutions obtained, Figure11 gives the solution obtained after 60 minutes by the VNS regarding instance Case1 depicted in Figure 10. In instance Case1, four warehouses are used to serve customers in Guangzhou city, and 13 delivery stations are associated with the customer orders that need to be fulfilled at that time. The SKUs stored in each warehouse and the SKUs requested by each station are also shown in Figure 10. Note that for each warehouse, we only show the SKUs that may be needed in this case. Figure 11 displays the four routes designed by the algorithm to deliver parcels to the delivery stations. Among these stations, Xinshi, Longgui, Taihe, Longdong, Huapu, Yonghe, Xincun, Luotou, Xintang, Xietong, and Luoxi need to be visited twice which means that the customer orders associated with these stations are spilt up and allocated to more than one warehouses.Figure 11
Vehicle routes for real-world instance Case1.


## 4.2.1. A Case Study from JD.com: Problem Description

To serve online customer demands in Guangzhou, the third largest city of China, JD.com maintains four warehouses located within or very close to the urban area. The locations of the fours warehouses are depicted in Figure10: Asia No. 1 warehouse, South China Logistics Center Foshan Park (FS warehouse), the 2nd South China Logistics Center Machong Park (MC warehouse), and South China Logistics Center Luogang Park (LG warehouse). In the figure, the black circles represent the warehouses, and the empty circles are the delivery stations. The following categories of SKUs are stored in the warehouses: 3C products, shoes and clothing, and health care products; snacks, grain and oil, and books; home appliances and 3C products; and clothing and groceries, respectively.Figure 10
Real-world instance: locations of warehouses and stations points.Parcel deliveries are handled by means of a fleet of vehicles from the warehouses to the delivery stations that are scattered over the urban area. At each station, orders placed by nearby residents are accumulated. To fulfill the demands in these delivery stations, logistics manager should simultaneously optimize the order allocation and routing with the aim of minimizing the total travelling distance. As one of the largest e-retailers of China, JD.com faces massive amount of online orders everyday. Upon receiving orders, the handling system needs to split and allocate it immediately and delivers it within very short time once the vehicle is available.In this case study, we consider five real cases in Guangzhou city. The following assumptions were made in considering the data provided by JD.com:(i)
The travelling distances between each pair of points of the distribution network were approximated with the Euclidean measure(ii)
Time windows constrains were ignored, and also all returned orders were not considered(iii)
The vehicle fleet is assumed to be homogeneousThe number of the delivery stations with delivery demands ranges between 13 and 33, and the total number of orders from all delivery stations that need to be fulfilled in each case ranges from 157 to 396. The vehicle capacity of the vehicles is set equal to 6,800 KG.


## 4.2.2. Results Obtained

The results obtained by applying the VNS algorithm are summarized in Table1. The first five columns of the table give the instance name, the number of warehouses K, the number of delivery stations I, the total number of orders OTOT=∑i∈VsMi, and the vehicle capacityQ.Due to the huge amount of daily delivery orders and the latest service options, such as “deliver within one hour” and “deliver within three hours,” launched in many big cities by JD.com, the decision on the order split, allocation, and routing needs to be made within a very limited computing time. For this reason, we record the values of the solutions generated by the VNS algorithm after 15, 30, and 60 minutes, and we compare the obtained values with respect to the cost of the initial solution.For each instance, Table3 reports the total distance (in kilometers) corresponding to the cost of the initial solution computed by the VNS (“z0”), and the solution costs after 15, 30, and 60 minutes (“z1, z2, z3”), respectively. The table also shows the percentage gap of solutions z1, z2, and z3 with respect to solution “z0”.Table 3
Results on real-world instances: the JD.com case.
IndexKIOTQz0z1gap1z2gap2z3gap3Case14131576,80065.7454.3720.91%54.3720.91%54.3720.91%Case24182186,800114.8691.9724.89%91.0926.10%91.0926.10%Case34232766,800126.01103.7621.44%102.3923.07%100.6325.22%Case44283366,800144.69119.2121.37%116.7923.89%114.1826.72%Case54333966,800173.52143.5520.88%140.2123.76%132.0431.41%Average124.96102.5721.83%100.9723.76%98.4626.92%The results shown in Table3 can be commented as follows. The initial heuristic finds feasible solutions for all the instances with an average value of 124.96 kilometers. Starting from the initial solutions, the VNS algorithm improves this value by 21.83%, 23.76%, and 26.92% on average for the 15, 30, and 60 minutes runs, respectively. The results have shown that the proposed VNS algorithm can be an effective tool to deal with the fast decisions needed by the order fulfillment process in JD.com.As an example of the solutions obtained, Figure11 gives the solution obtained after 60 minutes by the VNS regarding instance Case1 depicted in Figure 10. In instance Case1, four warehouses are used to serve customers in Guangzhou city, and 13 delivery stations are associated with the customer orders that need to be fulfilled at that time. The SKUs stored in each warehouse and the SKUs requested by each station are also shown in Figure 10. Note that for each warehouse, we only show the SKUs that may be needed in this case. Figure 11 displays the four routes designed by the algorithm to deliver parcels to the delivery stations. Among these stations, Xinshi, Longgui, Taihe, Longdong, Huapu, Yonghe, Xincun, Luotou, Xintang, Xietong, and Luoxi need to be visited twice which means that the customer orders associated with these stations are spilt up and allocated to more than one warehouses.Figure 11
Vehicle routes for real-world instance Case1.


## 4.3. Impact of the Main VNS Components

We conducted additional experiments to measure the contribution of each operator of the VNS. More precisely, from each of the 5, 6, 7, and 8 instance sets, we selected two instances and ran the VNS algorithm by selectively disabling one of the following three operators: order-split, station-remove and supper-move.Table4 gives the results obtained. In the table, column head “VNS” reports the best results obtained by the VNS algorithm, whereas column heads “NoOrderSplit,” “NoStationRemove,” and “NoSupperMove” give the results obtained by the VNS without the order-split, station-remove, and supper-move operators, respectively. Column Imp% reports the percentage of improvement of the different VNS variants considered; a negative value means that the corresponding solution is worse than the solution computed by the VNS with all operators.Table 4
Impact of the main VNS operators.
SetIdVNSNoOrderSplitNoStationRemoveNoSupperMoveCostt (s)CostImp%t (s)CostImp%t (s)CostImp%t (s)519408.794910210.6− 8.583110775.6− 14.55589827.7− 4.5579108146.611278225.5− 1.011728316.4− 2.19668357.0− 2.6936619030.110619078.7− 0.510749648.4− 6.816559255.0− 2.51260108700.818829284.8− 6.79548873.6− 2.010028955.6− 2.918877112988.8720013357.3− 2.8654815115.6− 16.4298812794.31.559051011266.7720011931.7− 5.9720012905.6− 14.5494411449.0− 1.672008121192.2720021749.6− 2.6720021532.7− 1.6720023694.8− 11.872001019568.6720020638.5− 5.5720020283.7− 3.7720019491.10.47200The table clearly shows that all operators are affective and that in only two cases improved solutions have been computed.


## 4.4. Sensitivity Analysis-Vehicle Capacity and SKUs Availability

In this section, we perform a second set of experiments focused on the impact of the vehicle capacity and the SKUs availability. Also for these experiments, we considered two instances from each of the 5, 6, 7, and 8 instance sets.


### 4.4.1. Vehicle Capacity

We recall that the vehicle capacityQ is set equal to q×Qsum/K, where q is a parameter, and Qsum is the total weight of all the required SKUs. In our experiments, we set the value of q equal to 1.1, 1.15, 1.2, 1.25, 1.3, 1.35, and 1.4, respectively. The results obtained are summarized in Table 5 for the different values of q, where column Imp% gives the percentage of the improvement of the solution cost with respect to the solution cost computed with q=1.1.Table 5
Impact of the vehicle capacityQ.
SetIdq=1:1q=1:15q=1:2q=1:25q=1:3q=1:35q=1:4CostCostImp%CostImp%CostImp%CostImp%CostImp%CostImp%519450.18461.810.57853.116.97478.120.97471.220.97397.321.77355.022.2109529.69284.42.69209.93.48420.111.68227.913.77925.316.87746.618.76112142.711012.29.310896.910.310135.016.510085.216.99789.319.49728.419.91010198.69966.02.39363.68.28745.814.28519.616.58378.017.98193.419.77110198.69966.02.39363.68.28745.814.28519.616.58378.017.98193.419.71013886.913588.12.212997.46.412897.37.112535.89.712349.811.112094.912.98123603.023603.00.021144.110.419794.016.119573.617.119178.718.718392.822.11021297.719905.66.518067.415.217859.716.117617.817.317606.217.316245.423.7The table shows that, as expected, the smaller the valueq, the more expensive the delivery cost and hence implies that the right trade off between the distribution cost and the vehicle capacity needs to be done.


### 4.4.2. SKUs Availability

We recall that when the (0-1) coefficientpnk is equal to 1, it means that the n-th SKUs is stored or available at warehouse k. In the results reported in Section 4.1, the probability of stockout (i.e., pnk=0) was set equal to 1/K. In the new experiments reported in this section, we compare the case where all SKUs are available to all warehouses (“NoStockOut” case), i.e., pnk=1∀i∈N, k∈Vw, with the case where the probability of stockout is set equal to 1/K (as in Section 4.1 (“StockOut(1/K)” case)) and the case where the probability is set equal to 0.5 (“StockOut(0.5)” case)).The results obtained are summarized in Table6, where column Imp% gives the percentage of improvement computed with respect to the solution cost obtained for case “NoStockOut.”Table 6
Sensitivity analysis on probability of stock out.
SetIdNoStockOutStockOut (1/K)StockOut (0.5)CostCostImp%CostImp%515748.87399.8− 28.716796.3− 192.2106156.29408.7− 52.815638.5− 154.0618760.110135.0− 15.722336.9− 155.0106847.68745.8− 27.720300.6− 196.5718122.111324.8− 39.431633.1− 289.5109320.312897.3− 38.433695.7− 261.58113687.319794.0− 44.649911.2− 264.71014308.017859.7− 24.850973.9− 256.3The results clearly show that the probability of stock out has a significant effect on the total distribution cost. When the probability increases to 0.5, the cost increases up to almost 4 times the cost of no “NoStockOut,” and the right trade off between the distribution cost and SKUs availability at the different warehouses needs to be done.


## 4.4.1. Vehicle Capacity

We recall that the vehicle capacityQ is set equal to q×Qsum/K, where q is a parameter, and Qsum is the total weight of all the required SKUs. In our experiments, we set the value of q equal to 1.1, 1.15, 1.2, 1.25, 1.3, 1.35, and 1.4, respectively. The results obtained are summarized in Table 5 for the different values of q, where column Imp% gives the percentage of the improvement of the solution cost with respect to the solution cost computed with q=1.1.Table 5
Impact of the vehicle capacityQ.
SetIdq=1:1q=1:15q=1:2q=1:25q=1:3q=1:35q=1:4CostCostImp%CostImp%CostImp%CostImp%CostImp%CostImp%519450.18461.810.57853.116.97478.120.97471.220.97397.321.77355.022.2109529.69284.42.69209.93.48420.111.68227.913.77925.316.87746.618.76112142.711012.29.310896.910.310135.016.510085.216.99789.319.49728.419.91010198.69966.02.39363.68.28745.814.28519.616.58378.017.98193.419.77110198.69966.02.39363.68.28745.814.28519.616.58378.017.98193.419.71013886.913588.12.212997.46.412897.37.112535.89.712349.811.112094.912.98123603.023603.00.021144.110.419794.016.119573.617.119178.718.718392.822.11021297.719905.66.518067.415.217859.716.117617.817.317606.217.316245.423.7The table shows that, as expected, the smaller the valueq, the more expensive the delivery cost and hence implies that the right trade off between the distribution cost and the vehicle capacity needs to be done.


## 4.4.2. SKUs Availability

We recall that when the (0-1) coefficientpnk is equal to 1, it means that the n-th SKUs is stored or available at warehouse k. In the results reported in Section 4.1, the probability of stockout (i.e., pnk=0) was set equal to 1/K. In the new experiments reported in this section, we compare the case where all SKUs are available to all warehouses (“NoStockOut” case), i.e., pnk=1∀i∈N, k∈Vw, with the case where the probability of stockout is set equal to 1/K (as in Section 4.1 (“StockOut(1/K)” case)) and the case where the probability is set equal to 0.5 (“StockOut(0.5)” case)).The results obtained are summarized in Table6, where column Imp% gives the percentage of improvement computed with respect to the solution cost obtained for case “NoStockOut.”Table 6
Sensitivity analysis on probability of stock out.
SetIdNoStockOutStockOut (1/K)StockOut (0.5)CostCostImp%CostImp%515748.87399.8− 28.716796.3− 192.2106156.29408.7− 52.815638.5− 154.0618760.110135.0− 15.722336.9− 155.0106847.68745.8− 27.720300.6− 196.5718122.111324.8− 39.431633.1− 289.5109320.312897.3− 38.433695.7− 261.58113687.319794.0− 44.649911.2− 264.71014308.017859.7− 24.850973.9− 256.3The results clearly show that the probability of stock out has a significant effect on the total distribution cost. When the probability increases to 0.5, the cost increases up to almost 4 times the cost of no “NoStockOut,” and the right trade off between the distribution cost and SKUs availability at the different warehouses needs to be done.


## 5. Conclusions and Future Research

In this paper, we proposed a new variant of vehicle routing problem motivated by real-world applications arising in the e-commerce logistics. The problem, called the multi-depot vehicle routing problem with order split and allocation (MD-CVRP-OSA) considers the split and allocation issue of online customer orders in traditional vehicle routing problem. We formally introduced the new problem and formulated it as an integer programming problem. To solve the MD-CVRP-OSA, we proposed an effective variable neighborhood search (VNS) algorithm that makes use of seven elaborately designed operators and a diversification mechanism.The VNS algorithm was extensively tested on both randomly generated and real-life instances. In particular, a case study from JD.com, one of China’s biggest e-commerce companies, was analyzed and solved with the proposed VNS approach. The computational results obtained showed the effectiveness of the VNS approach and also different components of the algorithm.The future research perspectives are multiple. Firstly, we recommend to pursue the study of exact methods for the MD-CVRP-OSA. Secondly, our problem definition and solution method could be extended to incorporate additional operational constraints, such as time window constraints, the use of an heterogeneous vehicle fleet, and order returns.



---

*Source: 8253175-2022-09-29.xml*