# Transshipment Vehicle Routing with Pickup and Delivery for Cross-Filling

Authors: Suk-Chul Rim; Hang T. T. Vu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Distribution centers (DCs) typically receive orders from the customers (mostly retail stores) located in their vicinity and deliver the ordered goods the next day morning. To maintain high item fill rate, DCs have to hold a high level of inventory, which will increase inventory cost. As an alternative, cross-filling is that, after closing the daily order receipt, DCs exchange surplus items during the night to reduce the shortage. The economic justification of such cross-filling will depend on the tradeoff between extra transshipment and handling cost versus saved shortage cost. In this paper, as an extension of Rim and Jiang, 2019, vehicles are allowed to drop and pick up items at the intermediate DCs in the route. We present a genetic algorithm to determine the routes and amount to pick up/drop at each DC to minimize the total cost.


---

## Body

## 1. Problem Description

The landscape of the logistics industry has been rapidly changing in recent years due to the evolution of the information technology. Quick delivery of goods to the consumers is becoming the key of the fast logistics business. Factories, distribution centers (DCs), and retailers are physical entities of the most manufacturers’ supply chain. Moreover, online commerce also employs DCs as an important element of its supply chain for efficient storage and order fulfillment for fast delivery of goods. Order fulfillment has been one of the critical performance indicators in most DCs [1]. Besides, the shortage at DCs will very likely lead to the shortage of the item at the retail stores, which will result in sales loss and negative impact on the consumers’ satisfaction.To avoid shortage, DCs are forced to hold high level of inventory, which will incur significant cost. As an alternative, cross-filling has been studied in academia and practiced in business for decades. Cross-filling is, after closing the daily order receipt, to ship the surplus items to other DCs that lack the same item to avoid shortage with relatively lower level of inventory. Such a lateral transshipment is also referred to as lateral resupply, reallocation of stock, and stock transfer [2]. Since extra trucking and handling during the night will clearly incur cost, a major concern is whether such a cross-filling can be economical or not, which will depend on the cost parameters such as shortage penalty, trucking, and handling cost. Also, we need to be able to determine the optimal transshipment routes of trucks within a very short length of time. This paper presents a viable solution procedure for this problem.The problem we address in this paper is as follows: consider a set of DCs of a company and multiple stores. Each DC supplies multiple items to multiple retail stores located in its own geographical area. Each DC receives orders from its retail stores during a day, closes the receipt of orders at a certain time in the late afternoon, processes the received orders, and tries to fulfill the orders using its own inventory. For shortage items, DCs try to find a surplus of the same item from other DCs. To minimize the total cost, we need to determine how many of which items to transship from which DC to which DC in what sequence. Trucks transship the items among the DCs during the night and deliver the items to the retail stores the next morning.In determining the transshipment routes, we assume that a truck may depart from any DC, but must return to its starting DC. Except the starting DCs, each intermediate DC in the routes can be visited by at most one truck, mainly due to the short length of transshipment time window. Also, trucks can not only drop some items but also pick up some items at the intermediate DCs, which makes the problem more complicated, but will improve the performance of the cross-filling. Transshipment must be completed within a certain time window so that transshipped items can be used for delivery to the retail stores along with the inventory stored in the DC.Before the transshipment trucks depart, each DC places orders to the factory for replenishment of items, which arrive the next day morning. Each DC may use various replenishment policies. In this paper, we assume that all DCs use base stock policy, that is, to order up to a certain level for each item every day since it is known to be optimal [3]. Figure 1 shows an example of the resulting routes among ten DCs for cross-filling, where shaded DCs 3, 5, and 9 represent the DCs the transshipment trucks depart from. Recall that the truck departing from DC 3 can pick up some items at DC 10 and drop some of them at DC 8, 1, or 3.Figure 1
An example of three transshipment routes among ten DCs.Unlike most existing research on this problem where transshipment cost is considered to be proportional to the number of transshipped items, to be more realistic, we assume that the transshipment cost comprises two elements; trucking cost is proportional to the travel distance of trucks, regardless of the quantity loaded in them; and material handling cost is proportional to the number of transshipped items. We assume that each DC is visited at most once, and only one truck can depart from any DC because moving more than one truckload a day for cross-filling seems unrealistic.We name this problem as the transshipment vehicle routing with simultaneous pickup and delivery (TVRSPD) problem. In this paper, we propose a genetic algorithm, in which a chromosome defines a set of routes; and we present an algorithm to determine the optimal amount to pick up/drop each item at each intermediate DC for each route so as to minimize the total cost for a day. Since the system regenerates every day, the optimal decision for one day will result in the optimal average performance over the infinite horizon [3].This paper is organized as follows: Section2 reviews the related research in the literature.Section 3 describes a genetic algorithm-based solution procedure, along with illustrative numerical examples.Section 4 reports the average performance of the proposed method. Conclusion and future research are given in Section 5.


## 2. Related Literature

To the best of our knowledge, the problem we address in this paper has not been presented in the literature. Our problem TVRSPD is positioned at the overlapping area of the two well-known problems: vehicle routing problem (VRP) and the transshipment problem. VRP has long been studied over six decades since the first work of Dantzig and Ramser [4]. For a comprehensive review on VRP including its variants, formulations, and solution methods, readers may refer to Toth and Vigo [5]. Among many variations, VRP with simultaneous pickup and delivery (VRPSPD) was introduced by Min [6]. Its comprehensive review is available in Berbeglia et al. [7] and Koc et al. [8]. TVRSPD has clear distinctions from VRPSPD as follows: (1) for the objective function, most of the VRP and its variants try to minimize the total travel distance. However, from the business viewpoint, we believe that the total travel distance of vehicles does not appropriately represent the total cost. Instead, to be more realistic, TVRSPD considers the total cost comprising shortage cost and handling cost, in addition to the trucking cost proportional to the travel distance of vehicles. (2) In VRPSPD, items are supplied from depot to the customers, while in TVRSPD, no depot is involved, and items are supplied from some DCs which have surplus. (3) In VRPSPD, vehicles must bring all the pickup amount to the depot, while in TVRSPD, vehicles are allowed to reallocate items, that is, to drop the items that are picked up from the DCs visited earlier at any DC to visit later. (4) In VRPSPD, all pickup and delivery demands at each customer must be met as constraints, while in TVRSPD, it is not a constraint but only the objective function of minimizing the total cost will determine how many of which items to pick up and drop at where.TVRSPD is different from multiple depot VRP [9, 10] in which the locations of the multiple depot are predetermined, whereas in TVRSPD, any DC can be selected as the starting node of the route. TVRSPD is also different from the location-routing problem [11] which involves simultaneously locating a number of facilities among candidate sites and establishing delivery routes to a set of users in such a way that the total system cost is minimized.Among many related research studies, Zhang et al. [12] studied a real-world problem found in fast fashion business with a warehouse and multiple retail outlets, where trucks depart from the warehouse and visit a sequence of outlets to drop and pick up items for possible reallocation to other outlets. Tasan and Gen [13] proposed a genetic algorithm approach to VRPSPD. The volume feasibility is guaranteed with a proper decoding procedure, and routes are determined due to the vehicle capacity. Nagy and Salhi [10] proposed insertion-based heuristics for VRPSPD. They introduced the idea of weak and strong feasibility and extended the algorithm to the problems with multiple depots.The VRP with backhauls (VRPB) is a related problem with TVRSPD, where a vehicle picks up goods after finishing all deliveries, and both actions are in one route [14]. VRPB can be separated as two capacitated vehicle routing problems, in which the demands of each customer must be fulfilled within the vehicle’s capacity. Customers who require deliveries from the depot are known as line hauls, and customers who require pick-ups or send goods are backhauls [15]. Several studies related to VRPB have been conducted in the literature [16, 17]. The mixing of line hauls and backhauls has proven to be very beneficial to the industry. The “milk run” is a well-known concept that is obtained from the achievements with VRPB. By applying milk runs, transportation costs and total travel distance can be significantly reduced, and the vehicle loading rate is increased [18].The other avenue related with TVRSPD is the transshipment problem. Transshipment can be classified by many criteria. One of the classifications is that it is either a centralized or decentralized problem. Centralized transshipment problem is to minimize the total cost incurred on all locations, while the decentralized one is that each location tries to maximize its own profit by determining the quantity and price of items for transshipment. Another classification is that transshipment can be either proactive or reactive. Proactive transshipment takes place at fixed points in time before observing the demand and periodically rebalances the whole system’s stock levels. For example, Van der Heide and Roodbergen [19] addressed the problem of transshipping and rebalancing books in libraries. They presented a stochastic dynamic programming formulation and heuristic algorithm. Contrarily, reactive transshipment responds to the stocking points which face a shortage, while another has surplus stock on hand [2]. The transshipment can be classified as either complete pooling or partial pooling. While DCs are willing to share all of their stock in the complete pooling [2] or complete network [20], partial pooling transship only when its inventory level is above a fixed threshold [21].Among many research results, Wong et al. [22] proposed a simple and efficient solution procedure to obtain a near-optimal solution with lateral transshipments for the single-item problem. The model is further extended to the case with multiple locations. Bhatnagar and Lin [23] developed two heuristic policies for the multilocation production/inventory system problem with the joint transshipment and production control policies, in which items are manufactured and stocked at each location to meet the demand. Wei et al. [24] explored the impacts of lateral transshipments on the stability, bullwhip effect, and other performance measurements in the context of a two-tiered supply chain system composed of one supplier and two retailers. Zhao and Sen [25] presented a comparison of sample-path-based simulation and stochastic decomposition for multilocation transshipment problems considering one supplier and N nonidentical retailers who face uncertain customer demands, as proposed by Herer et al. [3]. Archibald et al. [26] addressed a multiperiod periodic review model of a pair of retailers in which lateral transshipments can occur during the period. Smirnov and Gerchak [27] presented the single-period circular unidirectional chain problem, assuming that a location cannot both receive and ship items. They analyzed the optimality of the problem and compared its performance to that of no pooling and “pooling among all nodes” (namely, “complete pooling”). Axsäter [28] addressed the unidirectional lateral transshipment problem where transshipment is allowed only in one direction. Tagaras [29] and Herer et al. [30] addressed the problem of group configuration where transshipment is allowed only within groups. Kukreja and Schmidt [31] presented a model for lumpy demand parts in a multisite inventory system with feeders using analytical and simulation techniques.Wong et al. [32] proposed an integer programming model with a nonlinear objective function and nonlinear constraints for multi-item, multilocation spare part systems. Rim and Jiang [33] proposed a linear programming model for the simplified multi-item, multi-DC problem where transshipment is allowed only between pairs of DCs. The proposed LP model determines the optimal number of items and number of trucks to transship. The model also allows the “simultaneous chain transshipment,” which enables distant locations to supply surplus to the location that faces shortage. This simultaneous chain transshipment of items can be a practical tool for the cases where surplus is not available in its vicinity, but surplus from far distant sites can reach the needing site by simultaneously moving the items in a supply chain.


## 3. Solution Procedure

In this section, we will present a genetic algorithm as a solution procedure for the TVRSPD. We do not attempt to develop a mathematical formulation for the TVRSPD since it will not be able to obtain the optimal solution within an acceptable length of time for the problems of realistic size, as TVRSPD is NP-hard. Among many, we chose genetic algorithm (GA) since one of the features of our problem that each truck must return to its original location can be suitably modeled by designing the chromosomes in GA, as mentioned in the first paragraph ofSection 3.2.


### 3.1. Framework of the Genetic Algorithm

Genetic algorithm is a heuristic search based on the theory of biological evolution, Darwinism. By continuously generating the candidate solutions, evaluating how well the solutions fit with the desired objective, and refining the best solutions, GA obtains a good answer to the large search space problems. Depending on the problem type, the chromosome is designed to operate in the most appropriate way for the GA engine. At the crossover operator, two chromosomes are randomly selected and mated at each generation; and at the mutation operator, one of the best chromosomes in the current population is selected and mutated. The two parent chromosomes generate two child chromosomes using the crossover operator, and then only the best chromosomes enter the next generation. To boost the diversity of the population, a mutation procedure is applied. Only the following three individuals advance to the next iteration: one current best, one from crossover, and one from mutation. The rest ofN − 3 chromosomes are randomly generated to form the next population of size N. The GA engine stops when M generations have been iterated or any stopping rule applies.Letn° and n denote the population size and the number of feasible chromosomes in the population, respectively. The following steps represent the basic framework of the proposed genetic algorithm:n = 0Step 1: ifn = n°, go to Step 3; else, randomly generate a chromosome.Step 2: determine the optimal pickup/delivery amount at each DC for all routes in the chromosome. If volume-wise and distance-wise feasible, add it to the population,n = n + 1; else, discard it.Go to Step 1.Step 3: randomly select two parent chromosomes from the population.Step 4: execute the crossover to create two child chromosomes; choose the better one (c1), and discard the other. Select the best chromosome (c2) in the currentn° chromosomes, and execute the mutation to obtain a new chromosome (c3). Update c2 as the current best chromosome.Step 5: if any stopping rule applies, stop; else, initialize the population, and put c1, c2, and c3 in the population. Setn = 3; go to Step 1.Stopping rules include the number of iterations or computation time limit.


### 3.2. Generating a Chromosome

In Step 1, to randomly generate a chromosome which represents a set of routes, we first select a set of promising DCs as the “starting” DCs so that the remaining DCs are defined as the intermediate DCs and arrange the selected starting DCs in an arbitrary sequence. Since trucks must return to their starting DC, we duplicate each starting DC and randomly assign the intermediate DCs in the space between the pair of identical starting DCs. Figure2 shows an example of a chromosome that represents the routes shown in Figure 1, in which DCs 3, 5, 7, and 9 are selected as the starting DCs. Note that some starting DCs may have no intermediate DCs, as DC 7 in Figure 2.Figure 2
An example of a chromosome representing three routes shown in Figure1.To describe the heuristic algorithm to select a set of starting DCs, we will use the notations given in Table1.Table 1
Notations.
kItem (k = 1, 2, …, K)i,jDistribution center (i,j = 1, 2, …, Y)UkOrder-up-to-level of itemk at all DCsI0=iik0Initial inventory matrix of a dayD=dikDaily demand matrix of a daypkUnit price of itemkIik−,Sik−Inventory and shortage, respectively, of itemk at DC i before transshipment after assigning on-hand inventory to the daily demandIik+,Sik+Inventory and shortage, respectively, of itemk at DC i after transshipment is completedFigure3 illustrates the meaning of I and S in the daily operation schedule of DCs [33].Figure 3
Daily operation schedule and corresponding inventory/shortage notations.In selecting the starting DCs, it is desirable to select DCs that have larger value of weighted maximum possible transshipment. LetX−=xik− denote the inventory-shortage matrix before transshipment, where xik−=iik0−dik. Note that xik−=, Iik− if xik− > 0, and xik−=−Sik− if xik− ≤ 0. Similarly, let X+=xik+ denote the inventory-shortage matrix after transshipment is completed. We propose a heuristic algorithm to select a set of starting DCs as follows:(1)
ComputeX−=I0−D(2)
Compute the maximum possible transshipment matrixZ = zik, where zik = min{Iik−,∑j≠iSjk−} if xik− > 0; or 0 if xik− ≤ 0(3)
ComputeW = wi, where wi=∑kpkzik(4)
Selectm largest wi values to determine the corresponding DCs as the set of starting DCsWe suggest that the valuem can be arbitrarily selected as an integer close to 0.4Y. Table 2 shows an example of ten DCs and seven items to illustrate the above procedure. For m = 4, DCs 3, 5, 7, and 9 are selected as the starting DCs, as already shown in Figures 1 and 2.Table 2
An example of selecting a set of starting DCs out of 10 DCs with 7 items.
kvkpkDC1234567891010.3300−20150−5−310−5−54−14X−20.85000361015−4820−2330.0450−28464149−629625−2540.550−10−10203115−6271549−3850.35200−22−1028−215−1259−38433060.210002−102310144215402070.4801025−53854548−17−1014015000100040Z0360150810030459149029625000203115027154900028015059043300201010101010101010250323232800148008,40012,5505,16017,2606,56020,2407,05014,5009,620W


### 3.3. Crossover

We randomly select two parent chromosomes from the current population to generate two child chromosomes by the crossover operator. We use the partial mapped crossover (PMX, [34]) method for the crossover operator. It constructs the offspring by randomly selecting two crossing sites. The two points are used to define the mapping relationship. The numbers that follow the relationship represent which numbers are swapped in the parent chromosomes. The example shown in the following will help to explain our special PMX feature in detail. Unlike the conventional way of PMX, we allow “null” as a gene. The proposed crossover operator is as follows:(1)
Randomly select two blocks of adjacent intermediate DCs of any length (0, 1, 2, …) from each parent chromosome. Note that the lengths of the two blocks do not have to be equal. A length of zero means that no intermediate DC is selected.(2)
Exchange these two blocks to create two offsprings.(3)
Determine the mapping relationship of the two offsprings.(4)
Validate the two offsprings.(a)
If a gene appears twice in a chromosome, then change one of the two genes according to the mapping relationship(b)
If a gene is missing (this happens when two blocks of unequal length are selected in Step (1)), then insert the missing gene at a random location in the chromosome according to the mapping relationshipTo illustrate case (a), in Figure4, Step 1 selects (8, 6) and (4, 1) in parents 1 and 2, respectively. Step 2 creates children 1 and 2. Step 3 determines the mapping relationship, where number 8 is exchanged with 4 and 6 with 1. As the genes of child 1 in Step 2 are examined, numbers 4 and 1 are found to appear twice. So, in Step 4, we swap genes 4 and 8 and genes 1 and 6 to obtain two valid children.Figure 4
An example of validating two offsprings when a number appears twice.To illustrate case (b), in Figure5, Step 1 selects “null” gene between two 7s and (4, 1) from parents 1 and 2, respectively. Step 2 creates children 1 and 2. Step 3 determines the mapping relationship, where genes 4 and 1 are exchanged with the null gene, respectively. In Step 4, as the genes of child 1 are examined, genes 4 and 1 are found to appear twice, so we change numbers 4 and 1 to the null gene. In child 2, genes 4 and 1 are missing, so we insert genes 4 and 1 at random locations.Figure 5
An example of validating two offsprings when some genes are missing.


### 3.4. Mutation

Among many ways to implement mutation (see Soni and Kumar [35] for comprehensive reference), we use the following approach, as shown in Figure 6:(1)
Select the current best chromosome in the population(2)
Randomly select two genes in the chromosome, which can be either intermediate DC or “null” between the two adjacent identical starting DCs(3)
Swap the two selected genes to form a new chromosomeFigure 6
An example of the mutation operator (current best chromosome, new chromosome).


### 3.5. Optimal Pickup/Delivery Amount of a Route

In order to evaluate the fitness of a chromosome, we present an algorithm to determine the optimal pickup/drop quantity of each item at every visit in each route defined in a chromosome as follows. Letv0 and vk denote the volume capacity of a truck and unit volume of item k, respectively. A chromosome is volume-wise feasible if the trucks of all routes defined in the chromosome satisfy the volume constraint at all times during the trip since pickup is allowed during the trip. To illustrate, consider the first route 3-10-8-1-3 in Figure 2. The corresponding seven columns of X− are shown in Table 3. Let Q∗=qik∗ denote the quantity of item k in the truck of a route after finishing drop and pickup at DC i. Once Q∗ is obtained, the chromosome is volume-wise feasible if vr=∑kqrk∗vk≤v0 for all DCs r for 1≤r≤R (where R is the number of DCs in the route including the ending DC) and for all routes defined in the chromosome. Table 3 shows an example where route 3-10-8-1-3 is volume-wise feasible, when v0 = 32 m3.Table 3
An illustrative example of route 3-10-8-1-3.
kDC310813X−10−14−5−2002631006364256−28644203815−102052830−38−22286−1020150−107−514−1710−5Q10000020000034722280043801000530602200600101007317050Q∗10000020000034722280042001000528582000600101007014050A21.6826.7815.1240X+10−14−5−20026310063170001740−185005000−206020500700−350H1000002000003470600420010005283000060010007014050Before the numerical example in Table3, the flowchart in Figure 7 will help understand the logic of the algorithm. In computing Q∗, we need a temporary matrix Q for the backward computation. Once Q is obtained by the heuristic algorithm described in Figure 7, then Q is forward adjusted to obtain valid Q∗. Recall that R denotes the number of DCs in a route including the ending DC. Let g denote the first index such that xgk−>0 for g = 1, 2, …, R. Since excessive quantity loaded in the truck will unnecessarily increase the handling cost, each truck must have no leftover in it when it returns to its starting DC, that is, qRk=0 for all k, for all routes.Figure 7
Flowchart to determine the optimal pickup/delivery amount.Starting from the ending node,qik is calculated backwardly as qik=max0,qi+1,k−xi+1,k−. To calculate the total volume of items in the truck at each DC, we consider each item’s status for all DCs in the route. In order to not carry too much from the starting DC to transship (it may violate the volume constraint), we only load enough amount of each item that is already calculated based on the next DCs’ status. The following cases illustrate how Q∗ is determined using X− and Q under various situations.(1)
Item 1:qi1∗ = 0 for all i since xi1− ≤ 0 for all i(2)
Item 2:qi2∗ = 0 for all i since xi2− > 0 for all i(3)
Item 3:q53 = 0, q43 = max (0, q53−x53−) = max (0, 0–64) = 0, q33 = max (0, q43−x43−) = max(0, 0 + 28) = 28, q23 = max (0, q33−x33−) = max (0, 28–6) = 22, and q13 = max (0, q23−x23−) = max (0, 22 + 25) = 47 < x13−, so it is valid; we set qi3∗ = qi3 for all i(4)
Item 4: calculate backwardly as same as item 3, and we found thatq14 = max (0, q24−x24−) = max (0, 0 + 38) = 38 > x14− and x14− > 0 and q14 = −x24− = 38, so it is invalid. Then, we only change q14∗ = x14− = 20 and keep qi4∗ = qi4 for 2≤i≤R.(5)
Item 5: calculate backwardly, and we haveq15 = max (0, q25−x25−) = max (0, 60–30) = 30 > x15− and x15− > 0 and q15 ≠ −x25−, so it is invalid. Using forward adjustment A, h = 4, q15∗ = x15− = 28, q25∗ = max (0, q15∗+x25−) = max (0, 28 + 30) = 58, q35∗ = max (0, q25∗+x35−) = max(0, 58–38) = 20, and q45∗ = max (0, q35∗+x45−) = max(0, 20–22) = 0, and keep qi5∗ = qi5 for h<i≤R.(6)
Item 6:q16 = 0 since x16− < 0 and g = 2 and q26 < x26−, so no further changes are needed.(7)
Item 7:q17 = 3 since x17− < 0 and g=2 and q27 > x27− (17 > 14), so it is invalid. Using forward adjustment B, set q17∗ = 0 (all values before the first positive value of xi7− are set to be zero), b = 2, q27∗ = max (0, q17∗+x27−) = max (0, 0 + 14) = 14, and q37∗ = max (0, q27∗+x37−) = max (0, 14–17) = 0, and keep the other qi7∗ for b+g≤i≤R.The pseudo-codes of forward adjustment A and B are given in Appendix. Usingv=vk, the array of unit volume of item k, we obtain A=ai, the array of the total volume at DC i after pickup and drop as A=vQ∗. For example, for v=0.3,0.8,0.04,0.5,0.35,0.2,0.4, ai≤v0 = 32 m3 for all i, as shown in Table 3; the route in Table 3 is volume-wise feasible. If all routes defined in a chromosome are volume-wise feasible, then the chromosome is volume-wise feasible. If not, the infeasible chromosome is discarded.Regarding the distance constraint of a route, the total distance,d, of a given route can be readily computed by adding all Euclidean (straight line) distances between adjacent DCs in the route, given the coordinates of DCs. Let d0 denote the distance limit of the routes due to the limited time for transshipment. Ignoring the handling time, a route is distance-wise feasible if d ≤ d0. A chromosome is distance-wise feasible if all its routes are distance-wise feasible.


### 3.6. Fitness Function

To define the fitness function for a feasible chromosome, we use the cost parameters given in Table4.Table 4
Cost parameter notations.
βInventory cost rateγShortage cost rateδTrucking cost per unit distanceθHandling cost to load and unload an itemShortage cost is the sum of shortage after the transshipment is completed (Sik+) multiplied by its price and shortage cost rate. Trucking cost incurs proportionally to the total distance of the route, regardless of the loaded quantity. Extra material handling for transshipment includes picking, loading, and unloading. We assume that the unit handling cost θ for any item at any DC is equal. Note that θ includes both one loading and one unloading operation, as a loaded item will be eventually unloaded somewhere in the route. Let H=hik denote the quantity of item k additionally loaded in the truck at DC i (see Table 3). Then, h1k=q1k∗; and for 2≤i≤R, hik=max0,qik∗−qi−1k∗, for all k. Then, the total handling cost is θ∑i∑khik.Lett1 and t2 denote the number of routes (having at least one intermediate DC) and isolated DCs (having no intermediate DC), respectively. Let Rs and ds denote the number of DCs and total travel distance of route s, respectively. Now, we define the fitness function Z of a chromosome as equation (1). Note that the last term representing inventory cost is a constant and can be eliminated.(1)Z=∑s=1t1θ∑i=1Rs∑k=1Khik+δds+∑s=1t1+t2γ∑i=1Rs∑k=1KpkSik++βY∑k=1KpkUk.


## 3.1. Framework of the Genetic Algorithm

Genetic algorithm is a heuristic search based on the theory of biological evolution, Darwinism. By continuously generating the candidate solutions, evaluating how well the solutions fit with the desired objective, and refining the best solutions, GA obtains a good answer to the large search space problems. Depending on the problem type, the chromosome is designed to operate in the most appropriate way for the GA engine. At the crossover operator, two chromosomes are randomly selected and mated at each generation; and at the mutation operator, one of the best chromosomes in the current population is selected and mutated. The two parent chromosomes generate two child chromosomes using the crossover operator, and then only the best chromosomes enter the next generation. To boost the diversity of the population, a mutation procedure is applied. Only the following three individuals advance to the next iteration: one current best, one from crossover, and one from mutation. The rest ofN − 3 chromosomes are randomly generated to form the next population of size N. The GA engine stops when M generations have been iterated or any stopping rule applies.Letn° and n denote the population size and the number of feasible chromosomes in the population, respectively. The following steps represent the basic framework of the proposed genetic algorithm:n = 0Step 1: ifn = n°, go to Step 3; else, randomly generate a chromosome.Step 2: determine the optimal pickup/delivery amount at each DC for all routes in the chromosome. If volume-wise and distance-wise feasible, add it to the population,n = n + 1; else, discard it.Go to Step 1.Step 3: randomly select two parent chromosomes from the population.Step 4: execute the crossover to create two child chromosomes; choose the better one (c1), and discard the other. Select the best chromosome (c2) in the currentn° chromosomes, and execute the mutation to obtain a new chromosome (c3). Update c2 as the current best chromosome.Step 5: if any stopping rule applies, stop; else, initialize the population, and put c1, c2, and c3 in the population. Setn = 3; go to Step 1.Stopping rules include the number of iterations or computation time limit.


## 3.2. Generating a Chromosome

In Step 1, to randomly generate a chromosome which represents a set of routes, we first select a set of promising DCs as the “starting” DCs so that the remaining DCs are defined as the intermediate DCs and arrange the selected starting DCs in an arbitrary sequence. Since trucks must return to their starting DC, we duplicate each starting DC and randomly assign the intermediate DCs in the space between the pair of identical starting DCs. Figure2 shows an example of a chromosome that represents the routes shown in Figure 1, in which DCs 3, 5, 7, and 9 are selected as the starting DCs. Note that some starting DCs may have no intermediate DCs, as DC 7 in Figure 2.Figure 2
An example of a chromosome representing three routes shown in Figure1.To describe the heuristic algorithm to select a set of starting DCs, we will use the notations given in Table1.Table 1
Notations.
kItem (k = 1, 2, …, K)i,jDistribution center (i,j = 1, 2, …, Y)UkOrder-up-to-level of itemk at all DCsI0=iik0Initial inventory matrix of a dayD=dikDaily demand matrix of a daypkUnit price of itemkIik−,Sik−Inventory and shortage, respectively, of itemk at DC i before transshipment after assigning on-hand inventory to the daily demandIik+,Sik+Inventory and shortage, respectively, of itemk at DC i after transshipment is completedFigure3 illustrates the meaning of I and S in the daily operation schedule of DCs [33].Figure 3
Daily operation schedule and corresponding inventory/shortage notations.In selecting the starting DCs, it is desirable to select DCs that have larger value of weighted maximum possible transshipment. LetX−=xik− denote the inventory-shortage matrix before transshipment, where xik−=iik0−dik. Note that xik−=, Iik− if xik− > 0, and xik−=−Sik− if xik− ≤ 0. Similarly, let X+=xik+ denote the inventory-shortage matrix after transshipment is completed. We propose a heuristic algorithm to select a set of starting DCs as follows:(1)
ComputeX−=I0−D(2)
Compute the maximum possible transshipment matrixZ = zik, where zik = min{Iik−,∑j≠iSjk−} if xik− > 0; or 0 if xik− ≤ 0(3)
ComputeW = wi, where wi=∑kpkzik(4)
Selectm largest wi values to determine the corresponding DCs as the set of starting DCsWe suggest that the valuem can be arbitrarily selected as an integer close to 0.4Y. Table 2 shows an example of ten DCs and seven items to illustrate the above procedure. For m = 4, DCs 3, 5, 7, and 9 are selected as the starting DCs, as already shown in Figures 1 and 2.Table 2
An example of selecting a set of starting DCs out of 10 DCs with 7 items.
kvkpkDC1234567891010.3300−20150−5−310−5−54−14X−20.85000361015−4820−2330.0450−28464149−629625−2540.550−10−10203115−6271549−3850.35200−22−1028−215−1259−38433060.210002−102310144215402070.4801025−53854548−17−1014015000100040Z0360150810030459149029625000203115027154900028015059043300201010101010101010250323232800148008,40012,5505,16017,2606,56020,2407,05014,5009,620W


## 3.3. Crossover

We randomly select two parent chromosomes from the current population to generate two child chromosomes by the crossover operator. We use the partial mapped crossover (PMX, [34]) method for the crossover operator. It constructs the offspring by randomly selecting two crossing sites. The two points are used to define the mapping relationship. The numbers that follow the relationship represent which numbers are swapped in the parent chromosomes. The example shown in the following will help to explain our special PMX feature in detail. Unlike the conventional way of PMX, we allow “null” as a gene. The proposed crossover operator is as follows:(1)
Randomly select two blocks of adjacent intermediate DCs of any length (0, 1, 2, …) from each parent chromosome. Note that the lengths of the two blocks do not have to be equal. A length of zero means that no intermediate DC is selected.(2)
Exchange these two blocks to create two offsprings.(3)
Determine the mapping relationship of the two offsprings.(4)
Validate the two offsprings.(a)
If a gene appears twice in a chromosome, then change one of the two genes according to the mapping relationship(b)
If a gene is missing (this happens when two blocks of unequal length are selected in Step (1)), then insert the missing gene at a random location in the chromosome according to the mapping relationshipTo illustrate case (a), in Figure4, Step 1 selects (8, 6) and (4, 1) in parents 1 and 2, respectively. Step 2 creates children 1 and 2. Step 3 determines the mapping relationship, where number 8 is exchanged with 4 and 6 with 1. As the genes of child 1 in Step 2 are examined, numbers 4 and 1 are found to appear twice. So, in Step 4, we swap genes 4 and 8 and genes 1 and 6 to obtain two valid children.Figure 4
An example of validating two offsprings when a number appears twice.To illustrate case (b), in Figure5, Step 1 selects “null” gene between two 7s and (4, 1) from parents 1 and 2, respectively. Step 2 creates children 1 and 2. Step 3 determines the mapping relationship, where genes 4 and 1 are exchanged with the null gene, respectively. In Step 4, as the genes of child 1 are examined, genes 4 and 1 are found to appear twice, so we change numbers 4 and 1 to the null gene. In child 2, genes 4 and 1 are missing, so we insert genes 4 and 1 at random locations.Figure 5
An example of validating two offsprings when some genes are missing.


## 3.4. Mutation

Among many ways to implement mutation (see Soni and Kumar [35] for comprehensive reference), we use the following approach, as shown in Figure 6:(1)
Select the current best chromosome in the population(2)
Randomly select two genes in the chromosome, which can be either intermediate DC or “null” between the two adjacent identical starting DCs(3)
Swap the two selected genes to form a new chromosomeFigure 6
An example of the mutation operator (current best chromosome, new chromosome).


## 3.5. Optimal Pickup/Delivery Amount of a Route

In order to evaluate the fitness of a chromosome, we present an algorithm to determine the optimal pickup/drop quantity of each item at every visit in each route defined in a chromosome as follows. Letv0 and vk denote the volume capacity of a truck and unit volume of item k, respectively. A chromosome is volume-wise feasible if the trucks of all routes defined in the chromosome satisfy the volume constraint at all times during the trip since pickup is allowed during the trip. To illustrate, consider the first route 3-10-8-1-3 in Figure 2. The corresponding seven columns of X− are shown in Table 3. Let Q∗=qik∗ denote the quantity of item k in the truck of a route after finishing drop and pickup at DC i. Once Q∗ is obtained, the chromosome is volume-wise feasible if vr=∑kqrk∗vk≤v0 for all DCs r for 1≤r≤R (where R is the number of DCs in the route including the ending DC) and for all routes defined in the chromosome. Table 3 shows an example where route 3-10-8-1-3 is volume-wise feasible, when v0 = 32 m3.Table 3
An illustrative example of route 3-10-8-1-3.
kDC310813X−10−14−5−2002631006364256−28644203815−102052830−38−22286−1020150−107−514−1710−5Q10000020000034722280043801000530602200600101007317050Q∗10000020000034722280042001000528582000600101007014050A21.6826.7815.1240X+10−14−5−20026310063170001740−185005000−206020500700−350H1000002000003470600420010005283000060010007014050Before the numerical example in Table3, the flowchart in Figure 7 will help understand the logic of the algorithm. In computing Q∗, we need a temporary matrix Q for the backward computation. Once Q is obtained by the heuristic algorithm described in Figure 7, then Q is forward adjusted to obtain valid Q∗. Recall that R denotes the number of DCs in a route including the ending DC. Let g denote the first index such that xgk−>0 for g = 1, 2, …, R. Since excessive quantity loaded in the truck will unnecessarily increase the handling cost, each truck must have no leftover in it when it returns to its starting DC, that is, qRk=0 for all k, for all routes.Figure 7
Flowchart to determine the optimal pickup/delivery amount.Starting from the ending node,qik is calculated backwardly as qik=max0,qi+1,k−xi+1,k−. To calculate the total volume of items in the truck at each DC, we consider each item’s status for all DCs in the route. In order to not carry too much from the starting DC to transship (it may violate the volume constraint), we only load enough amount of each item that is already calculated based on the next DCs’ status. The following cases illustrate how Q∗ is determined using X− and Q under various situations.(1)
Item 1:qi1∗ = 0 for all i since xi1− ≤ 0 for all i(2)
Item 2:qi2∗ = 0 for all i since xi2− > 0 for all i(3)
Item 3:q53 = 0, q43 = max (0, q53−x53−) = max (0, 0–64) = 0, q33 = max (0, q43−x43−) = max(0, 0 + 28) = 28, q23 = max (0, q33−x33−) = max (0, 28–6) = 22, and q13 = max (0, q23−x23−) = max (0, 22 + 25) = 47 < x13−, so it is valid; we set qi3∗ = qi3 for all i(4)
Item 4: calculate backwardly as same as item 3, and we found thatq14 = max (0, q24−x24−) = max (0, 0 + 38) = 38 > x14− and x14− > 0 and q14 = −x24− = 38, so it is invalid. Then, we only change q14∗ = x14− = 20 and keep qi4∗ = qi4 for 2≤i≤R.(5)
Item 5: calculate backwardly, and we haveq15 = max (0, q25−x25−) = max (0, 60–30) = 30 > x15− and x15− > 0 and q15 ≠ −x25−, so it is invalid. Using forward adjustment A, h = 4, q15∗ = x15− = 28, q25∗ = max (0, q15∗+x25−) = max (0, 28 + 30) = 58, q35∗ = max (0, q25∗+x35−) = max(0, 58–38) = 20, and q45∗ = max (0, q35∗+x45−) = max(0, 20–22) = 0, and keep qi5∗ = qi5 for h<i≤R.(6)
Item 6:q16 = 0 since x16− < 0 and g = 2 and q26 < x26−, so no further changes are needed.(7)
Item 7:q17 = 3 since x17− < 0 and g=2 and q27 > x27− (17 > 14), so it is invalid. Using forward adjustment B, set q17∗ = 0 (all values before the first positive value of xi7− are set to be zero), b = 2, q27∗ = max (0, q17∗+x27−) = max (0, 0 + 14) = 14, and q37∗ = max (0, q27∗+x37−) = max (0, 14–17) = 0, and keep the other qi7∗ for b+g≤i≤R.The pseudo-codes of forward adjustment A and B are given in Appendix. Usingv=vk, the array of unit volume of item k, we obtain A=ai, the array of the total volume at DC i after pickup and drop as A=vQ∗. For example, for v=0.3,0.8,0.04,0.5,0.35,0.2,0.4, ai≤v0 = 32 m3 for all i, as shown in Table 3; the route in Table 3 is volume-wise feasible. If all routes defined in a chromosome are volume-wise feasible, then the chromosome is volume-wise feasible. If not, the infeasible chromosome is discarded.Regarding the distance constraint of a route, the total distance,d, of a given route can be readily computed by adding all Euclidean (straight line) distances between adjacent DCs in the route, given the coordinates of DCs. Let d0 denote the distance limit of the routes due to the limited time for transshipment. Ignoring the handling time, a route is distance-wise feasible if d ≤ d0. A chromosome is distance-wise feasible if all its routes are distance-wise feasible.


## 3.6. Fitness Function

To define the fitness function for a feasible chromosome, we use the cost parameters given in Table4.Table 4
Cost parameter notations.
βInventory cost rateγShortage cost rateδTrucking cost per unit distanceθHandling cost to load and unload an itemShortage cost is the sum of shortage after the transshipment is completed (Sik+) multiplied by its price and shortage cost rate. Trucking cost incurs proportionally to the total distance of the route, regardless of the loaded quantity. Extra material handling for transshipment includes picking, loading, and unloading. We assume that the unit handling cost θ for any item at any DC is equal. Note that θ includes both one loading and one unloading operation, as a loaded item will be eventually unloaded somewhere in the route. Let H=hik denote the quantity of item k additionally loaded in the truck at DC i (see Table 3). Then, h1k=q1k∗; and for 2≤i≤R, hik=max0,qik∗−qi−1k∗, for all k. Then, the total handling cost is θ∑i∑khik.Lett1 and t2 denote the number of routes (having at least one intermediate DC) and isolated DCs (having no intermediate DC), respectively. Let Rs and ds denote the number of DCs and total travel distance of route s, respectively. Now, we define the fitness function Z of a chromosome as equation (1). Note that the last term representing inventory cost is a constant and can be eliminated.(1)Z=∑s=1t1θ∑i=1Rs∑k=1Khik+δds+∑s=1t1+t2γ∑i=1Rs∑k=1KpkSik++βY∑k=1KpkUk.


## 4. Performance Evaluation

### 4.1. Parameters

To evaluate the average performance of the proposed approach by simulation, we use the realistic cost parameters as shown in Table5. Demand for item k of all DCs is assumed to follow normal distribution N (μk,σk2), where μk follows uniform (10, 100) and σk = 0.3μk. The order-up-to-level for item k is determined as Uk=μk+zασk, where zα is the coefficient from the standard normal distribution table with in-stock probability α.Table 5
Parameters used for simulation with 10 DCs and 10 items.
k12345678910vk0.30.80.40.040.050.20.50.30.450.7pk3005002005030015050400100200DC12345678910Coordinate (units of 5 km)(2, 5)(6, 4)(4, 3)(8, 1.5)(5, 6)(8, 5)(10, 3.5)(1, 3)(2, 0)(5.5, 1.5)pkU($10∼$500)vkU(0.03 m3∼1 m3)v032 m3β0.25/365 = 0.00068 per dayθ$0.5d0100 kmγ0.1, 0.2, and 0.3 per shortageδ$0.5, $1, and $2 per km


### 4.2. Average Performance

For a given inventory level, we compare the average total cost when transshipment is not applied against the one when transshipment is applied. The former will suffer substantial shortage cost, and the latter will have less shortage cost but additional trucking and handling cost. Using target in-stock probabilityα and corresponding Uk = μk+σkzα, daily demand and resulting X− are generated. With a population size of 100, stopping rule of 500 iterations, and 20 replications, Figures 8–10 show dramatic average cost savings by using the proposed approach. The cost saving is larger as α is smaller, γ is larger, and δ is smaller. For a practical value of α = 0.95, the average total cost is saved by 30.8% to 63.3%. Even for very high α = 99%, the average total cost saving ranges between 9.7% and 28.68%, which is significant. The item fill rate is 100% in most cases as transshipment is applied.Figure 8
The average total cost saving by transshipment whenδ = $0.5/km.Figure 9
The average total cost saving by transshipment whenδ = $1.0/km.Figure 10
The average total cost saving by transshipment whenδ = $2/km.


### 4.3. Computation Time

In order for the proposed GA to be practical, the computation time has to be within a reasonable range. Using MATLAB R2019a on a personal computer with 16.0 GB RAM and base speed 3.60 GHz, Table6 shows that, for 10 DCs and selected 100 items for transshipment, it takes less than 6 minutes, which can be further reduced if the number of iterations, population size, and/or the number of items are reduced.Table 6
Sample computation times.
Number of itemsComputation time (sec)Number of itemsComputation time (sec)1087.5580337.1020147.7790369.7430185.73100407.6240206.00200802.8750233.583001123.4560266.634001291.4670300.845001825.83


## 4.1. Parameters

To evaluate the average performance of the proposed approach by simulation, we use the realistic cost parameters as shown in Table5. Demand for item k of all DCs is assumed to follow normal distribution N (μk,σk2), where μk follows uniform (10, 100) and σk = 0.3μk. The order-up-to-level for item k is determined as Uk=μk+zασk, where zα is the coefficient from the standard normal distribution table with in-stock probability α.Table 5
Parameters used for simulation with 10 DCs and 10 items.
k12345678910vk0.30.80.40.040.050.20.50.30.450.7pk3005002005030015050400100200DC12345678910Coordinate (units of 5 km)(2, 5)(6, 4)(4, 3)(8, 1.5)(5, 6)(8, 5)(10, 3.5)(1, 3)(2, 0)(5.5, 1.5)pkU($10∼$500)vkU(0.03 m3∼1 m3)v032 m3β0.25/365 = 0.00068 per dayθ$0.5d0100 kmγ0.1, 0.2, and 0.3 per shortageδ$0.5, $1, and $2 per km


## 4.2. Average Performance

For a given inventory level, we compare the average total cost when transshipment is not applied against the one when transshipment is applied. The former will suffer substantial shortage cost, and the latter will have less shortage cost but additional trucking and handling cost. Using target in-stock probabilityα and corresponding Uk = μk+σkzα, daily demand and resulting X− are generated. With a population size of 100, stopping rule of 500 iterations, and 20 replications, Figures 8–10 show dramatic average cost savings by using the proposed approach. The cost saving is larger as α is smaller, γ is larger, and δ is smaller. For a practical value of α = 0.95, the average total cost is saved by 30.8% to 63.3%. Even for very high α = 99%, the average total cost saving ranges between 9.7% and 28.68%, which is significant. The item fill rate is 100% in most cases as transshipment is applied.Figure 8
The average total cost saving by transshipment whenδ = $0.5/km.Figure 9
The average total cost saving by transshipment whenδ = $1.0/km.Figure 10
The average total cost saving by transshipment whenδ = $2/km.


## 4.3. Computation Time

In order for the proposed GA to be practical, the computation time has to be within a reasonable range. Using MATLAB R2019a on a personal computer with 16.0 GB RAM and base speed 3.60 GHz, Table6 shows that, for 10 DCs and selected 100 items for transshipment, it takes less than 6 minutes, which can be further reduced if the number of iterations, population size, and/or the number of items are reduced.Table 6
Sample computation times.
Number of itemsComputation time (sec)Number of itemsComputation time (sec)1087.5580337.1020147.7790369.7430185.73100407.6240206.00200802.8750233.583001123.4560266.634001291.4670300.845001825.83


## 5. Conclusion

In this paper, we proposed a solution procedure for the transshipment vehicle routing problem for cross-filling multiple items among multiple DCs, where simultaneous pickup and delivery is allowed in the routes (TVRSPD). Any DC can be selected as a starting DC, and trucks must return to their starting DC. We present an algorithm to determine the optimal amount of each item to be picked up and/or delivered at each DC in the route. Volume feasibility of the truck is considered in the algorithm. Distance feasibility is also considered in the stage of generating chromosomes. Trucking cost is assumed to be proportional to the travel distance of the truck.Instead of maintaining higher level of inventory to avoid shortage, cross-filling effectively reduces the shortage with relatively lower level of inventory. For practical parameter values, the proposed approach obtains significant saving of 9.7% to 63.3% in the average total cost, which includes the shortage cost and extra trucking and handling cost. Computation time required for the proposed algorithm is acceptable for the problem of reasonable size such as 10 DCs and 100 items.Despite its successful GA modeling, our approach has the following limitations: the number of items for transshipment is limited to about one hundred major items due to computational time; truck drivers may not be available around the midnight for transshipment; or DCs may be too dispersed in the rural area to apply this model.In the near future, advanced transportation devices such as drones and driverless trucks will make our model practically more useful. Furthermore, a new distribution channel called microfulfillment center, which is relatively small but automated distribution centers densely located in the urban area to serve consumers in shorter response time, will promote implementing our model to exchange the shortage items among the microfulfillment centers. For further research, one may allow each DC to be visited more than once by trucks from more than one starting DC.



---

*Source: 6667765-2021-01-18.xml*