Location-Routing for Distribution Centers
Read this article. One objective of this paper is to determine distribution center locations. Compare and contrast the two cases presented.
Numerical cases and analysis of the results
In this section, two numerical cases were generated and solved. Proposed genetic algorithm and CPLEX solver were used to solve the cases. GA coded in MATLAB software and GAMS software was used to run CPLEX software and obtained results compared. A personal laptop equipped with an Intel® Core™ i3 CPU at 2.4 GHz and 6 GB of RAM was used to process the data. Also, different cost scenarios were designed to analyze model and algorithm sensitivity.
Case 1: description
Each numerical case have two parts; a multimodal network along with a single-mode network of DCs and retailers. In case 1, the multimodal network is generated by random data. It consists of 1 supplier, 8 intermediate nodes, 2 potential DCs, 15 road links, 19 railway links and 14 seaway links. The distances between nodes along the road network were uniformly generated in [0, 400] interval (First x and y coordination generated for each node, then Euclidean distances calculated). To generate railway network distances, another uniform distribution over interval [0, 20] is used, and results added to the Euclidean distances. Adding another random number to railway network distances from interval [0, 20], generates seaway network distances. Table 2 shows the defined links and their distances along the three transportation networks.
Table 2 Multimodal network for the three numerical examples
| Node number | Exiting arc | Road | Rail | Sea | Node number | Exiting arc | Road | Rail | Sea |
|---|---|---|---|---|---|---|---|---|---|
| 1 | (1,2) | 23 | 27 | – | 4 | (4,6) | 184 | – | 204 |
| 1 | (1,3) | – | 87 | – | 4 | (4,7) | – | 136 | 146 |
| 1 | (1,4) | – | 197 | – | 4 | (4,8) | – | 373 | 390 |
| 1 | (1,5) | 331 | – | – | 5 | (5,7) | 170 | 179 | 188 |
| 2 | (2,3) | 60 | – | 70 | 5 | (5,8) | 304 | 315 | 360 |
| 2 | (2,4) | – | 179 | – | 6 | (6,8) | 214 | 220 | 227 |
| 2 | (2,5) | – | 300 | 313 | 6 | (6, DC1) | 287 | 300 | 315 |
| 2 | (2,7) | 350 | 383 | – | 7 | (7,8) | 190 | 197 | 310 |
| 3 | (3,4) | 100 | 111 | – | 7 | (7, DC1) | 259 | 260 | 268 |
| 3 | (3,6) | – | 275 | 282 | 7 | (7, DC2) | 332 | 343 | 357 |
| 3 | (3,7) | – | 320 | – | 8 | (8,DC2) | 155 | 164 | 177 |
| 4 | (4,5) | 134 | – | – |
For second part of the numerical case 1, five retailers were considered. Table 3 shows their x and y coordination and demands. This part of the numerical case extracted from LRP instances with 20 customers and 5 DCs reported by Prodhon (2010). Establishment costs of DC 1 and DC 2 were 10,841 and 11,961, respectively, with a unit on-vehicle transportation cost of 20.
Table 3 DCs, retailers coordinates, and demands for the case 1
| Coordinates | DC 1 | DC 2 | Retailer 1 | Retailer 2 | Retailer 3 | Retailer 4 | Retailer 5 |
|---|---|---|---|---|---|---|---|
| X | 6 | 19 | 20 | 8 | 29 | 18 | 19 |
| Y | 7 | 44 | 35 | 31 | 43 | 39 | 47 |
| Demand | – | – | 18 | 13 | 19 | 12 | 18 |
Table
4 displays GAMS and GA results for case 1 under different cost and
capacity scenarios. Scenarios created by making changes in
transportation cost along road, rail and sea networks, DCs' capacity and
mode changing cost. As mentioned before, mode changing cost refers to
the cost of providing facilities at multimodal terminals where
transportation modes can be changed. It should be note that constant
parameter B (B is a large constant parameter used in constraints 3 and
6) determined by solving first scenario for different values and finally
set to 100,000.
Table 4 Results of case 1 under different scenarios
| Scenario number | Shipment cost for each mode | Transfer cost between modes | Vehicle capacity | GAMS value | GAMS solution time (s) | GA values | Best multimodal path | Best route | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Road | Rail | Sea | Worst | Medium | Best | |||||||
| 1 | 3 | 2 | 1 | 100 | 100 | 64,061 | 1.06 | 64,061 | 64,061 | 64,061 | 1-R-2-S-3-S-4-S-7-S-DC1a | DC1-2-1-4-5-3-DC1b |
| 2 | 3 | 2 | 1 | 10,000 | 100 | 73,961 | 0.59 | 73,961 | 73,961 | 73,961 | 1-R-2-S-3-S-6-S-8-S-DC1 | DC1-2-1-4-5-3-DC1 |
| 3 | 3 | 2 | 1 | 50,000 | 100 | 107,801 | 0.64 | 107,801 | 107,801 | 107,801 | 1-R-4-R-7-R-DC1 | DC1-2-1-4-5-3-DC1 |
| 4 | 3 | 2 | 1 | 10,000 | 70 | 87,270 | 1.08 | 87,270 | 87,270 | 87,270 | 1-R-2-S-3-S-4-S-7-S-DC1 | DC1-2-1-5-3-DC1 |
| 1-R-2-S-3-S-4-S-7-S-DC2 | DC2-4-DC2 | |||||||||||
| 5 | 23 | 22 | 21 | 10,000 | 70 | 1,073,830 | 1.42 | 1,073,830 | 1,073,830 | 1,073,830 | 1-H-2-H-3-S-4-S-7-S-DC1 | DC1-2-1-5-3-DC1 |
| 1-H-2-H-3-S-4-S-7-S-DC2 | DC2-4-DC2 | |||||||||||
| 6 | 23 | 22 | 21 | 50,000 | 70 | 1,090,753 | 1.13 | 1,090,753 | 1,090,753 | 1,090,753 | 1-R-4-R-7-R-DC1 | DC1-2-1-5-3-DC1 |
| 1-R-4-R-7-R-DC2 | DC2-4-DC2 | |||||||||||
aMultimodal route starts from supplier (node 1) and paths nodes number 2, 3, 4, 7 and end to DC1. Transportation links between supplier and node number 2 is a railway (R) and other transportation links are seaway (S)
bRetailers delivery tour starts from DC1 and meets retailers number 2, 1, 4, 5 and 3, respectively, and returns to DC1
All best multimodal paths start from node 1 (supplier) and pass intermediate nodes to reach DCs. Notations H, R, and S between the nodes refer to road, railway, and seaway modes. Best routes start from DCs and pass through retailers (retailers numbers are different from multimodal path numbers) and eventually returning back to the original DC.
Under scenario 1, mode changing cost (cost of providing mode changing facilities at multimodal terminals) is much lower than DC establishment cost (about one hundredth). Furthermore, transportation cost on road and railway networks, compare to seaway network, are triple and twice, respectively; and considered capacity for each DC is adequate to satisfy all retailers' demands. Result show that under this scenario, only DC1 (with lower establishment cost) established. Because of high DC establishment cost, when one DC can answer to all the retailers demand (high vehicle capacity), just one DC establishes. In this scenario, seaway has the lowest cost and mode changing cost is negligible. So multimodal route is consists of four seaway and one railway links and multimodal terminal established at node 2. Under scenario 2, mode changing cost is raised to 10,000 (close to that of DC establishment cost). However, no change is seen in the results, i.e., seaway transportation still presents a costly justifiable approach, and similar to scenario 1, a multimodal terminal established at node 2. In scenario 3, mode changing cost is about five times larger than DC establishment cost. The results show that change in transportation mode is no longer economic, and multimodal route products transported from supplier to potential DC 1 along the railway network. With sufficient vehicle capacity for all the demands, only one DC is established. Under scenario 4, mode changing cost set to 10,000 and vehicle capacity decreased to 70, so that a single DC cannot answer all the demands. In this scenario, both of DCs established with a different multimodal route and delivery tour for each DC. In scenario 5, differences between transportation costs for three modes are lower than previous scenarios. Again, mode changing cost and vehicle capacity are set to 10,000 and 70, respectively. Results show that in the multimodal network, products are transport along road (due to lower distance) and seaway (due to lower cost) networks. Since DC capacity has not changed, retailer routes are the same. Sixth scenario is similar to previous scenario with raise in mode changing cost. In this scenario model, choose a multimodal route with no changing in modes, so railway network (due to its continuity from the supplier to DCs) is preferred over road network (with lower transportation distances) and seaway network (with lower costs). The results show that a change in vehicle capacity can change the number of established DCs and affect routs to retailers.
These scenarios
are further solved by genetic algorithm and the results reported in
Table 4. Results show that all runs of the algorithm reached optimum
solutions which normally achieved between iterations 5 and 15. The
results demonstrated that GA provides proper performance and solve
problem in a reasonable run time.
Case 2
Example generated by Xiong and Wang (2012) used in case 2, for multimodal part of the problem. The authors defined a multimodal network with 35 nodes and three modes including truck, rail and barges transportation. Five ending nodes (nodes 31–35) considered as potential DCs and node 1 defined as supplier location.Some modifications did on multimodal network. According to the problem assumptions, all links between potential DCs deleted. As a result, node 34 (potential DC 4) lose all of its communications to other nodes. To modify that three truck, rail and barge links from node 27–34 added to multimodal network. Also, every defined distance for multimodal network is multiplied by 10 to provide more consistency with DCs and retailers distances. For LRP part of the problem, Prodhon instance with 5 potential DCs and 20 customers used (Prodhon 2010).
Software and algorithm results for case 2 under different cost and capacity scenarios are presented in Table 5. Also, for this case, the parameter B is set to the same value (100,000).
Same scenarios defined and solved for case 2. However, in contrary to the case 1, cost of a change in transportation mode had lower impact on changing multimodal routes. This is because of significant differences between distances of transportation modes. Compared to other modes, road network has lower distances, so under these cost scenarios, using a road network is costly justifiable, even with higher transportation cost.
In the first three scenarios capacity of DCs was set to 300; so two DCs could adequately answer all of the demands. The results show that under all three scenarios, DCs 3 and 4 which had lower establishment cost, selected to establish. Under scenarios 1 and 3, mode changing cost is low, so the node 17 selected for multimodal terminal. Under scenario 2, mode changing cost is raised to 10,000; such a high cost caused a change in multimodal route to avoid mode change; however, route structure changes very slightly.
Under scenarios 4, 5 and 6, DCs' capacity was 70; as a result, all the DCs should be established to fulfill all the demands. In scenario 5, transportation costs were all close together compared to scenario 4, however, such a change had no impact on multimodal route. So in this case, transportation distance is more important than transportation cost and road transportation is the popular mode due to its lower distances. Under scenario 6, mode changing cost was 10, but yet no change was evident on multimodal route. Comparing results with scenario 3 reveals that with the same mode changing cost, a different route was attained for DC 3. In fact, when rail and road modes costs were 2 and 3, respectively, transportation mode was likely to change at node 17, but when the costs were 22 and 23, respectively, this was not the case and transportation continued along the road network.
For the same established DCs, different tours from DC to retailers were attained under different scenarios. For example, under scenarios 1 and 2, different tours were attained for DC 3 and DC 4. However, according to the same transportation cost and identical distances between retailers and DC, such a difference was not expected (similar to case 1). The situation was attributed to sub-optimality of the solutions given by the software under different scenarios. GAMS reported a feasible solution within limited run time. GA reported an equal or even better solution with lower run times, but the optimality of the answers is yet to be proved.
Although the case 2 was considered as a medium-size problem, because of high complexity of the model and NP-hard nature of the problem (Shen et al. 2003), GAMS failed to find an optimal solution within the limited run time. Existing gap within the solutions are reported in Table 5.
Comparing GA
and GAMS results indicate that for three scenarios results are identical
but for the other three scenarios, GA gave better solutions. Also, GA
run times for 100 iterations are reported in Table 5, showing that the
GA tends to gives a proper solution within a reasonable time, making the
algorithm useful for large-size cases.
Table 5 Results of the case 2 under different scenarios
| Scenario number | Shipment cost for each mode | Transfer cost between modes | Vehicle capacity | GAMS value | GAMS solution time (s) | Gap (%) | GA Values | GA solution time | Best multimodal path | Best route | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Road | Rail | Sea | Worst | Medium | Best | |||||||||
| 1 | 3 | 2 | 1 | 100 | 300 | 253,997 | 7200 | 4 | 254,837 | 254,255 | 253,997 | 565 | 1-H-2-H-7-H-11-H-15-H-17-R-22-H-26-H-29-H-DC3 | DC3-10-DC3 |
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-18-1-17-3-8-19-20-7-15-16-4-11-14-5-13-12-9-2-6-DC4 | |||||||||||||
| 2 | 3 | 2 | 1 | 10,000 | 300 | 265,947 | 7200 | 24 | 267,397 | 265,471 | 264,517 | 581 | 1-H-2-H-7-H-10-H-14-H-18-H-20-H-22-H-26-H-29-H-DC3 | DC3-15-DC3 |
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-6-2-9-12-13-5-14-11-4-10-16-7-20-19-8-3-17-1-18-DC4 | |||||||||||||
| 3 | 3 | 2 | 1 | 10 | 300 | 253,817 | 7200 | 4 | 254,297 | 254,070 | 253,817 | 531 | 1-H-2-H-7-H-11-H-15-H-17-R-22-H-26-H-29-H-DC3 | DC3-10-DC3 |
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-18-6-2-9-12-13-5-14-11-4-16-15-7-20-8-19-3-17-1-DC4 | |||||||||||||
| 4 | 3 | 2 | 1 | 10,000 | 70 | 387,904 | 7200 | 35 | 416,594 | 403,294 | 387,904 | 605 | 1-H-2-H-8-H-9-H-13-H-24-H-30-H-DC1 | DC1-3-17-4-15-DC1 |
| 1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC2-18-2-8-19-DC2 | |||||||||||||
| 1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC3 | DC3-1-11-10-14-16-DC3 | |||||||||||||
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-12-13-5-9-6-DC4 | |||||||||||||
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-28-H-DC5 | DC5-20-7-DC5 | |||||||||||||
| 5 | 23 | 22 | 21 | 10,000 | 70 | 2,499,884 | 7200 | 28 | 2,502,704 | 2,497,490 | 2,489,884 | 560 | 1-H-2-H-8-H-9-H-13-H-24-H-30-H-DC1 | DC1-19-1-18-17-DC1 |
| 1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC2-9-5-14-7-DC2 | |||||||||||||
| 1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC3-3-10-12-16-20-DC3 | |||||||||||||
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-2-4-11-13-6-DC4 | |||||||||||||
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-28-H-DC5 | DC5-15-8-DC5 | |||||||||||||
| 6 | 23 | 22 | 21 | 10 | 70 | 2,492,234 | 7200 | 29 | 2,492,714 | 2,491,766 | 2,489,894 | 621 | 1-H-2-H-8-H-9-H-13-H-24-H-30-H-DC1 | DC1-1-9-11-10-20-DC1 |
| 1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC2-6-4-16-15-8-DC2 | |||||||||||||
| 1-H-2-H-7-H-10-H-14-H-18-H-20-H -22-H-26-H-29-H-DC2 | DC3-17-2-18-3-DC3 | |||||||||||||
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-DC4 | DC4-12-5-14-7-DC4 | |||||||||||||
| 1-H-4-H-5-H-12-H-16-H-21-H-27-H-28-H-DC5 | DC5-13-19-DC5 | |||||||||||||
Relative gap percentage is reported by GAMS software
GA solution time is for '100 iterations