American Institute of Mathematical Sciences

Advanced
March  2020, 16(2): 669-705. doi: 10.3934/jimo.2018173

Shipper collaboration in forward and reverse logistics

Xiaohui Lyu 1, , Nengmin Wang 1,, , Zhen Yang 1, and  Haoxun Chen 2,

1. 

School of Management, Xi'an Jiaotong University, 710049, NO.28 Xianning Road, Xian Shaanxi, China, ERC for Process Mining of Manufacturing Services in Shaanxi Province
2. 

Industrial Systems Optimization Laboratory, Charles Delaunay Institute and UMR CNRS, 6281, University of Technology of Troyes, 12 rue Marie Curie, CS 42060, 10004 Troyes, France

* Corresponding author: Nengmin Wang

Received  April 2018 Revised  June 2018 Published  October 2018

In less than truckload transportation, shippers collaborate to reduce their logistics costs by consolidating their transportation requests in the procurement of transportation services from a carrier for serving the requests. In this paper, we study shipper collaboration in forward and reverse logistics, in which multiple shippers with forward or/and reverse logistics operations consolidate their transportation requests. In the forward and reverse logistics, manufacturers deliver new products to their customers and used products are collected from customers and transported to remanufacturers for repair or reproduction. This gives rise to a new vehicle routing problem with pickup and delivery requests and three different types of depots (product depots, vehicle depots and recycle depots). A hybrid approach combining greedy randomized adaptive search procedure (GRASP) and iterated local search (ILS) is proposed to find a near optimal solution of the problem. Numerical experiments on a large set of randomly generated instances with different problem sizes demonstrate that shipper collaboration in forward and reverse logistics can realize significant cost savings compared with the isolated operation of each shipper without cooperation, and the proposed approach is effective in the sense that it can find a high quality solution in a reasonable computation time.

Keywords: Collaborative transportation planning, less than truckload transportation, shipper collaboration, forward and reverse logistics, vehicle routing, meta-heuristics.
Mathematics Subject Classification: Primary: 90BXX; Secondary: 90B06.
Citation: Xiaohui Lyu, Nengmin Wang, Zhen Yang, Haoxun Chen. Shipper collaboration in forward and reverse logistics. Journal of Industrial & Management Optimization, 2020, 16 (2) : 669-705. doi: 10.3934/jimo.2018173
References:
[1]

C. Archetti and M. G. Speranza, Vehicle routing problems with split deliveries, International Transactions in Operational Research, 19 (2012), 3-22.  doi: 10.1111/j.1475-3995.2011.00811.x.  Google Scholar

[2]

J. F. Audy, S. D'Amours and L. M. Rousseau, Cost allocation in the establishment of a collaborative transportation agreement-an application in the furniture industry, Journal of the Operational Research Society, 62 (2011), 960-970.   Google Scholar

[3]

M. Battarra, J. F. Cordeau and M. Iori, Pickup-and-delivery problems for goods transportation, Vehicle routing: problems, methods, and applications. MOS/SIAM series on optimization, (2014), 161-192.   Google Scholar

[4]

R. Bent and P. Van Hentenryck, A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research, 33 (2006), 875-893.   Google Scholar

[5]

G. Berbeglia, J. F. Cordeau, I. Gribkovskaia and G. Laporte, Static pickup and delivery problems: a classification scheme and survey, Top, 15 (2007), 1-31.  doi: 10.1007/s11750-007-0009-0.  Google Scholar

[6]

S. Berger and C. Bierwirth, Solutions to the request reassignment problem in collaborative carrier networks, Transportation Research Part E: Logistics and Transportation Review, 46 (2010), 627-638.   Google Scholar

[7]

N. Bianchessi and G. Righini, Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery, Computers & Operations Research, 34 (2007), 578-594.   Google Scholar

[8]

J. Crispim and J. Brandão, Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls, Journal of the Operational Research Society, 34 (2005), 1296-1302.   Google Scholar

[9]

B. Dai and H. Chen, Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation, Computers & Industrial Engineering, 2009. CIE 2009. International Conference on IEEE, (2009), 767-772.   Google Scholar

[10]

J. Dethloff, Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, Operations Research-Spektrum, 23 (2001), 79-96.  doi: 10.1007/PL00013346.  Google Scholar

[11]

M. Dror and P. Trudeau, Savings by split delivery routing, Transportation Science, 23 (1989), 141-145.   Google Scholar

[12]

O. Ergun, G. Kuyzu and M. Savelsbergh, Shipper collaboration, Computers & Operations Research, 34 (2007a), 1551-1560.   Google Scholar

[13]

O. Ergun, G. Kuyzu and M. Savelsbergh, Reducing truckload transportation costs through collaboration, Transportation Science, 41 (2007b), 206-221.   Google Scholar

[14]

T. A. Feo and J. F. Bard, Flight scheduling and maintenance base planning, Management Science, 35 (1989), 1415-1432.   Google Scholar

[15]

M. Frisk, M. Göthe-Lundgren, K. Jörnsten and M. Rönnqvist, Cost allocation in collaborative forest transportation, European Journal of Operational Research, 205 (2010), 448-458.   Google Scholar

[16]

Y. Gajpal and P. Abad, An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup, Computers & Operations Research, 36 (2009), 3215-3223.   Google Scholar

[17]

F. P. Goksal, I. Karaoglan and F. Altiparmak, A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery, Computers & Industrial Engineering, 65 (2013), 39-53.   Google Scholar

[18]

M. Y. Lai, C. S. Liu and X. J. Tong, A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows, Journal of Industrial & Management Optimization, 6 (2010), 435-451.  doi: 10.3934/jimo.2010.6.435.  Google Scholar

[19]

H. Li and A. Lim, A metaheuristic for the pickup and delivery problem with time windows, International Journal on Artificial Intelligence Tools, 12 (2003), 173-186.   Google Scholar

[20]

J. Li, P. M. Pardalos, H. Sun, J. Pei and Y. Zhang, Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups, Expert Systems with Applications, 42 (2015), 3551-3561.   Google Scholar

[21]

R. Liu, X. Xie, V. Augusto and C. Rodriguez, Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, European Journal of Operational Research, 230 (2013), 475-486.  doi: 10.1016/j.ejor.2013.04.044.  Google Scholar

[22]

H. R. Lourenço, O. C. Martin and T. Stützle, Iterated local search, in In Handbook of metaheuristics, Springer US, 57 (2003), 321–353.  Google Scholar

[23]

Q. Lu and M. M. Dessouky, A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows, European Journal of Operational Research, 175 (2006), 672-687.   Google Scholar

[24]

H. Min, The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research Part A: General, 23 (1989), 377-386.   Google Scholar

[25]

S. Mitra, An algorithm for the generalized vehicle routing problem with backhauling, Asia-Pacific Journal of Operational Research, 22 (2005), 153-169.  doi: 10.1142/S0217595905000522.  Google Scholar

[26]

S. Mitra, A parallel clustering technique for the vehicle routing problem with split deliveries and pickups, Journal of the operational Research Society, 59 (2008), 1532-1546.   Google Scholar

[27]

G. Nagy and S. Salhi, Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research, 162 (2005), 126-141.   Google Scholar

[28]

W. P. Nanry and J. W. Barnes, Solving the pickup and delivery problem with time windows using reactive tabu search, Transportation Research Part B: Methodological, 34 (2000), 107-121.   Google Scholar

[29]

M. Nowak, Ö Ergun and C. C. White Ⅲ, Pickup and delivery with split loads, Transportation Science, 42 (2008), 32-43.   Google Scholar

[30]

M. Nowak, Ö Ergun and C. C. White Ⅲ, An empirical study on the benefit of split loads with the pickup and delivery problem, European Journal of Operational Research, 198 (2009), 734-740.   Google Scholar

[31]

G. Pankratz, A grouping genetic algorithm for the pickup and delivery problem with time windows, Or Spectrum, 27 (2005), 21-41.  doi: 10.1007/s00291-004-0173-7.  Google Scholar

[32]

P. Pelagagge, L. Fratocchi and A. C. Caputo, A genetic approach for freight transportation planning, Industrial Management & Data Systems, 106 (2006), 719-738.   Google Scholar

[33]

D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Computers & operations research, 34 (2007), 2403-2435.  doi: 10.1016/j.cor.2005.09.012.  Google Scholar

[34]

C. Prins, N. Labadi and M. Reghioui, Tour splitting algorithms for vehicle routing problems, International Journal of Production Research, 47 (2009), 507-535.   Google Scholar

[35]

M. Reghioui, C. Prins and N. Labadi, GRASP with path relinking for the capacitated arc routing problem with time windows, InWorkshops on Applications of Evolutionary Computation, (2007), 722-731.   Google Scholar

[36]

J. Renaud, F. F. Boctor and G. Laporte, Perturbation heuristics for the pickup and delivery traveling salesman problem, Computers & Operations Research, 29 (2002), 1129-1141.  doi: 10.1016/S0305-0548(99)00066-0.  Google Scholar

[37]

S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006a), 455-472.   Google Scholar

[38]

S. Ropke and D. Pisinger, A unified heuristic for a large class of vehicle routing problems with backhauls, European Journal of Operational Research, 171 (2006), 750-775.  doi: 10.1016/j.ejor.2004.09.004.  Google Scholar

[39]

S. Salhi and G. Nagy, A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the operational Research Society, 50 (1999), 1034-1042.   Google Scholar

[40]

R. Sprenger and L. Monch, A methodology to solve large-scale cooperative transportation planning problems, European Journal of Operational Research, 223 (2012), 626-636.   Google Scholar

[41]

A. Subramanian, L. M. Drummond, L. M. D. A., C. Bentes, L. S. Ochi and R. Farias, A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 223 (2010), 1899-1911.   Google Scholar

[42]

A. Subramanian, E. Uchoa and L. S. Ochi, A hybrid algorithm for a class of vehicle routing problems, Computers & Operations Research, 40 (2013), 2519-2531.   Google Scholar

[43]

A. S. Tasan and M. Gen, A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries, Computers & Industrial Engineering, 62 (2012), 755-761.   Google Scholar

[44]

F. L. Usberti, P. M. França and A. L. M. França, GRASP with evolutionary path-relinking for the capacitated arc routing problem, Computers & Operations Research, 40 (2013), 3206-3217.  doi: 10.1016/j.cor.2011.10.014.  Google Scholar

[45]

N. A. Wassan, A. H. Wassan and G. Nagy, A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries, Journal of Combinatorial Optimization, 15 (2008), 368-386.  doi: 10.1007/s10878-007-9090-4.  Google Scholar

[46]

O. Yilmaz and S. Savasaneril, Collaboration among small shippers in a transportation market, European Journal of Operational Research, 218 (2012), 408-415.  doi: 10.1016/j.ejor.2011.11.018.  Google Scholar

[47]

T. Zhang, W. A. Chaovalitwongse and Y. Zhang, Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery, Journal of Combinatorial Optimization, 28 (2014), 288-309.  doi: 10.1007/s10878-014-9741-1.  Google Scholar

show all references

References:
[1]

C. Archetti and M. G. Speranza, Vehicle routing problems with split deliveries, International Transactions in Operational Research, 19 (2012), 3-22.  doi: 10.1111/j.1475-3995.2011.00811.x.  Google Scholar

[2]

J. F. Audy, S. D'Amours and L. M. Rousseau, Cost allocation in the establishment of a collaborative transportation agreement-an application in the furniture industry, Journal of the Operational Research Society, 62 (2011), 960-970.   Google Scholar

[3]

M. Battarra, J. F. Cordeau and M. Iori, Pickup-and-delivery problems for goods transportation, Vehicle routing: problems, methods, and applications. MOS/SIAM series on optimization, (2014), 161-192.   Google Scholar

[4]

R. Bent and P. Van Hentenryck, A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research, 33 (2006), 875-893.   Google Scholar

[5]

G. Berbeglia, J. F. Cordeau, I. Gribkovskaia and G. Laporte, Static pickup and delivery problems: a classification scheme and survey, Top, 15 (2007), 1-31.  doi: 10.1007/s11750-007-0009-0.  Google Scholar

[6]

S. Berger and C. Bierwirth, Solutions to the request reassignment problem in collaborative carrier networks, Transportation Research Part E: Logistics and Transportation Review, 46 (2010), 627-638.   Google Scholar

[7]

N. Bianchessi and G. Righini, Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery, Computers & Operations Research, 34 (2007), 578-594.   Google Scholar

[8]

J. Crispim and J. Brandão, Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls, Journal of the Operational Research Society, 34 (2005), 1296-1302.   Google Scholar

[9]

B. Dai and H. Chen, Mathematical model and solution approach for collaborative logistics in less than truckload (LTL) transportation, Computers & Industrial Engineering, 2009. CIE 2009. International Conference on IEEE, (2009), 767-772.   Google Scholar

[10]

J. Dethloff, Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, Operations Research-Spektrum, 23 (2001), 79-96.  doi: 10.1007/PL00013346.  Google Scholar

[11]

M. Dror and P. Trudeau, Savings by split delivery routing, Transportation Science, 23 (1989), 141-145.   Google Scholar

[12]

O. Ergun, G. Kuyzu and M. Savelsbergh, Shipper collaboration, Computers & Operations Research, 34 (2007a), 1551-1560.   Google Scholar

[13]

O. Ergun, G. Kuyzu and M. Savelsbergh, Reducing truckload transportation costs through collaboration, Transportation Science, 41 (2007b), 206-221.   Google Scholar

[14]

T. A. Feo and J. F. Bard, Flight scheduling and maintenance base planning, Management Science, 35 (1989), 1415-1432.   Google Scholar

[15]

M. Frisk, M. Göthe-Lundgren, K. Jörnsten and M. Rönnqvist, Cost allocation in collaborative forest transportation, European Journal of Operational Research, 205 (2010), 448-458.   Google Scholar

[16]

Y. Gajpal and P. Abad, An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup, Computers & Operations Research, 36 (2009), 3215-3223.   Google Scholar

[17]

F. P. Goksal, I. Karaoglan and F. Altiparmak, A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery, Computers & Industrial Engineering, 65 (2013), 39-53.   Google Scholar

[18]

M. Y. Lai, C. S. Liu and X. J. Tong, A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows, Journal of Industrial & Management Optimization, 6 (2010), 435-451.  doi: 10.3934/jimo.2010.6.435.  Google Scholar

[19]

H. Li and A. Lim, A metaheuristic for the pickup and delivery problem with time windows, International Journal on Artificial Intelligence Tools, 12 (2003), 173-186.   Google Scholar

[20]

J. Li, P. M. Pardalos, H. Sun, J. Pei and Y. Zhang, Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups, Expert Systems with Applications, 42 (2015), 3551-3561.   Google Scholar

[21]

R. Liu, X. Xie, V. Augusto and C. Rodriguez, Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care, European Journal of Operational Research, 230 (2013), 475-486.  doi: 10.1016/j.ejor.2013.04.044.  Google Scholar

[22]

H. R. Lourenço, O. C. Martin and T. Stützle, Iterated local search, in In Handbook of metaheuristics, Springer US, 57 (2003), 321–353.  Google Scholar

[23]

Q. Lu and M. M. Dessouky, A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows, European Journal of Operational Research, 175 (2006), 672-687.   Google Scholar

[24]

H. Min, The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research Part A: General, 23 (1989), 377-386.   Google Scholar

[25]

S. Mitra, An algorithm for the generalized vehicle routing problem with backhauling, Asia-Pacific Journal of Operational Research, 22 (2005), 153-169.  doi: 10.1142/S0217595905000522.  Google Scholar

[26]

S. Mitra, A parallel clustering technique for the vehicle routing problem with split deliveries and pickups, Journal of the operational Research Society, 59 (2008), 1532-1546.   Google Scholar

[27]

G. Nagy and S. Salhi, Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research, 162 (2005), 126-141.   Google Scholar

[28]

W. P. Nanry and J. W. Barnes, Solving the pickup and delivery problem with time windows using reactive tabu search, Transportation Research Part B: Methodological, 34 (2000), 107-121.   Google Scholar

[29]

M. Nowak, Ö Ergun and C. C. White Ⅲ, Pickup and delivery with split loads, Transportation Science, 42 (2008), 32-43.   Google Scholar

[30]

M. Nowak, Ö Ergun and C. C. White Ⅲ, An empirical study on the benefit of split loads with the pickup and delivery problem, European Journal of Operational Research, 198 (2009), 734-740.   Google Scholar

[31]

G. Pankratz, A grouping genetic algorithm for the pickup and delivery problem with time windows, Or Spectrum, 27 (2005), 21-41.  doi: 10.1007/s00291-004-0173-7.  Google Scholar

[32]

P. Pelagagge, L. Fratocchi and A. C. Caputo, A genetic approach for freight transportation planning, Industrial Management & Data Systems, 106 (2006), 719-738.   Google Scholar

[33]

D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Computers & operations research, 34 (2007), 2403-2435.  doi: 10.1016/j.cor.2005.09.012.  Google Scholar

[34]

C. Prins, N. Labadi and M. Reghioui, Tour splitting algorithms for vehicle routing problems, International Journal of Production Research, 47 (2009), 507-535.   Google Scholar

[35]

M. Reghioui, C. Prins and N. Labadi, GRASP with path relinking for the capacitated arc routing problem with time windows, InWorkshops on Applications of Evolutionary Computation, (2007), 722-731.   Google Scholar

[36]

J. Renaud, F. F. Boctor and G. Laporte, Perturbation heuristics for the pickup and delivery traveling salesman problem, Computers & Operations Research, 29 (2002), 1129-1141.  doi: 10.1016/S0305-0548(99)00066-0.  Google Scholar

[37]

S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006a), 455-472.   Google Scholar

[38]

S. Ropke and D. Pisinger, A unified heuristic for a large class of vehicle routing problems with backhauls, European Journal of Operational Research, 171 (2006), 750-775.  doi: 10.1016/j.ejor.2004.09.004.  Google Scholar

[39]

S. Salhi and G. Nagy, A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the operational Research Society, 50 (1999), 1034-1042.   Google Scholar

[40]

R. Sprenger and L. Monch, A methodology to solve large-scale cooperative transportation planning problems, European Journal of Operational Research, 223 (2012), 626-636.   Google Scholar

[41]

A. Subramanian, L. M. Drummond, L. M. D. A., C. Bentes, L. S. Ochi and R. Farias, A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 223 (2010), 1899-1911.   Google Scholar

[42]

A. Subramanian, E. Uchoa and L. S. Ochi, A hybrid algorithm for a class of vehicle routing problems, Computers & Operations Research, 40 (2013), 2519-2531.   Google Scholar

[43]

A. S. Tasan and M. Gen, A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries, Computers & Industrial Engineering, 62 (2012), 755-761.   Google Scholar

[44]

F. L. Usberti, P. M. França and A. L. M. França, GRASP with evolutionary path-relinking for the capacitated arc routing problem, Computers & Operations Research, 40 (2013), 3206-3217.  doi: 10.1016/j.cor.2011.10.014.  Google Scholar

[45]

N. A. Wassan, A. H. Wassan and G. Nagy, A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries, Journal of Combinatorial Optimization, 15 (2008), 368-386.  doi: 10.1007/s10878-007-9090-4.  Google Scholar

[46]

O. Yilmaz and S. Savasaneril, Collaboration among small shippers in a transportation market, European Journal of Operational Research, 218 (2012), 408-415.  doi: 10.1016/j.ejor.2011.11.018.  Google Scholar

[47]

T. Zhang, W. A. Chaovalitwongse and Y. Zhang, Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery, Journal of Combinatorial Optimization, 28 (2014), 288-309.  doi: 10.1007/s10878-014-9741-1.  Google Scholar

Figure 1.  Isolated transportation planning of each shipper in forward and reverse logistics
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Collaborative transportation planning of all shippers in forward and reverse logistics
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Illustration of the insertion positions for a product depot
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Illustration of the insertion positions for a customer
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Illustration of the insertion positions for a recycle depot
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  The comparison of the first improvement and the best improvement
Instance set Best improvement First improvement
CPU Gap CPU Gap
I40 827.63 5.20 29.22 5.18
O40 796.54 0.62 35.18 0.58
Table Options

Download as excel

Instance set Best improvement First improvement
CPU Gap CPU Gap
I40 827.63 5.20 29.22 5.18
O40 796.54 0.62 35.18 0.58
Table 2.  The comparison of two strategies
Instance set General strategy Speedup strategy
CPU Gap CPU Gap
I40 327.63 5.18 29.22 5.18
O40 296.54 0.61 35.18 0.58
Table Options

Download as excel

Instance set General strategy Speedup strategy
CPU Gap CPU Gap
I40 327.63 5.18 29.22 5.18
O40 296.54 0.61 35.18 0.58
Table 3.  Parameter tuning according to instance size
Description Parameter Value
Small instances
(20 requests)		 Medium instances
(40 requests)		 Large instances
(60 requests)		 Large instances
(100 requests)
Number of GRASP iterations np 10 10 15 15
Number of ILS iterations ni 5 10 15 20
RCL size nrcl 3 5 7 7
Table Options

Download as excel

Description Parameter Value
Small instances
(20 requests)		 Medium instances
(40 requests)		 Large instances
(60 requests)		 Large instances
(100 requests)
Number of GRASP iterations np 10 10 15 15
Number of ILS iterations ni 5 10 15 20
RCL size nrcl 3 5 7 7
Table 5.  Results for comparison of GRASP-ILS and CPLEX solver
Instance set CPLEX GRASP-ILS
ImpIni GapLB CPU ImpIni ImpCplex GapLB CPU
I20 -- 0.00 2101.07 -- 0.00 0.00 3.17
O20 -- 0.00 1077.42 -- 0.00 0.00 1.92
A20 -- 0.00 1350.15 -- 0.00 0.00 2.49
Average 0.00 1509.55 0.00 0.00 2.53
I40 1.44 28.47 21600.00 6.57 5.18 24.58 29.22
O40 6.02 10.78 21600.00 6.37 0.58 10.27 35.18
A40 3.33 20.89 21600.00 6.61 3.58 17.91 29.94
Average 3.60 20.05 21600.00 6.52 3.11 17.59 31.45
I60 2.74 34.25 21600.00 12.45 9.99 26.73 125.42
O60 4.77 28.38 21600.00 16.85 12.63 18.00 144.84
A60 3.35 28.74 21600.00 14.78 11.81 19.18 148.35
Average 3.62 30.46 21600.00 13.70 12.47 21.30 139.54
I100 1.62 40.24 21600.00 16.85 13.00 31.27 246.32
O100 2.57 38.25 21600.00 21.11 15.24 23.55 292.72
A100 1.83 34.56 21600.00 19.52 14.68 23.17 282.45
Average 2.01 37.68 21600.00 19.16 14.31 26.00 273.83
Table Options

Download as excel

Instance set CPLEX GRASP-ILS
ImpIni GapLB CPU ImpIni ImpCplex GapLB CPU
I20 -- 0.00 2101.07 -- 0.00 0.00 3.17
O20 -- 0.00 1077.42 -- 0.00 0.00 1.92
A20 -- 0.00 1350.15 -- 0.00 0.00 2.49
Average 0.00 1509.55 0.00 0.00 2.53
I40 1.44 28.47 21600.00 6.57 5.18 24.58 29.22
O40 6.02 10.78 21600.00 6.37 0.58 10.27 35.18
A40 3.33 20.89 21600.00 6.61 3.58 17.91 29.94
Average 3.60 20.05 21600.00 6.52 3.11 17.59 31.45
I60 2.74 34.25 21600.00 12.45 9.99 26.73 125.42
O60 4.77 28.38 21600.00 16.85 12.63 18.00 144.84
A60 3.35 28.74 21600.00 14.78 11.81 19.18 148.35
Average 3.62 30.46 21600.00 13.70 12.47 21.30 139.54
I100 1.62 40.24 21600.00 16.85 13.00 31.27 246.32
O100 2.57 38.25 21600.00 21.11 15.24 23.55 292.72
A100 1.83 34.56 21600.00 19.52 14.68 23.17 282.45
Average 2.01 37.68 21600.00 19.16 14.31 26.00 273.83
Table 6.  Summarized results for comparison among GRASP-ILS, GRASP and ILS
Instance set
ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I20 6.51 3.17
O20 1.87 0.86
A20 7.65 3.68
Average 5.34 2.57
I40 3.95 3.71
O40 3.00 3.23
A40 6.75 3.62
Average 4.57 3.52
I60 4.09 2.65
O60 7.42 0.73
A60 6.35 4.64
Average 5.95 2.67
I100 7.20 4.19
O100 6.59 3.78
A100 5.00 4.06
Average 6.26 4.01
Table Options

Download as excel

Instance set
ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I20 6.51 3.17
O20 1.87 0.86
A20 7.65 3.68
Average 5.34 2.57
I40 3.95 3.71
O40 3.00 3.23
A40 6.75 3.62
Average 4.57 3.52
I60 4.09 2.65
O60 7.42 0.73
A60 6.35 4.64
Average 5.95 2.67
I100 7.20 4.19
O100 6.59 3.78
A100 5.00 4.06
Average 6.26 4.01
Table 7.  Summarized results for deviations among GRASP-ILS, GRASP and ILS
Instance set GRASP ILS GRASP-ILS
Dev Dev Dev
I20 1.93 4.31 0.37
O20 0.26 0.43 0.01
A20 1.21 5.23 0.76
Average 1.13 3.32 0.38
I40 4.46 7.73 0.42
O40 3.81 7.01 0.44
A40 3.68 8.65 0.89
Average 3.98 7.80 0.58
I60 6.92 11.58 0.51
O60 4.80 6.72 0.81
A60 4.09 8.66 0.92
Average 5.27 8.99 0.75
I100 7.04 12.38 0.88
O100 5.25 8.96 1.16
A100 5.40 9.31 1.12
Average 5.90 10.22 1.05
Table Options

Download as excel

Instance set GRASP ILS GRASP-ILS
Dev Dev Dev
I20 1.93 4.31 0.37
O20 0.26 0.43 0.01
A20 1.21 5.23 0.76
Average 1.13 3.32 0.38
I40 4.46 7.73 0.42
O40 3.81 7.01 0.44
A40 3.68 8.65 0.89
Average 3.98 7.80 0.58
I60 6.92 11.58 0.51
O60 4.80 6.72 0.81
A60 4.09 8.66 0.92
Average 5.27 8.99 0.75
I100 7.04 12.38 0.88
O100 5.25 8.96 1.16
A100 5.40 9.31 1.12
Average 5.90 10.22 1.05
Table 8.  Summarized results of geographical distributions of customers on cost savings
Geographical distributions of customers Non-collaboration Nv Collaboration Nv $\phi$
I20 4.3 2.3 22.57
O20 4.1 2 17.90
A20 4.2 2.1 10.76
I40 8 6 31.02
O40 7.3 3.5 24.19
A40 7.5 3.9 16.35
I60 11 6.3 33.31
O60 10.1 4.9 28.22
A60 10.1 5.2 24.42
I100 17.8 9.8 41.37
O100 14.1 8.4 33.79
A100 13.8 8.7 30.96
Table Options

Download as excel

Geographical distributions of customers Non-collaboration Nv Collaboration Nv $\phi$
I20 4.3 2.3 22.57
O20 4.1 2 17.90
A20 4.2 2.1 10.76
I40 8 6 31.02
O40 7.3 3.5 24.19
A40 7.5 3.9 16.35
I60 11 6.3 33.31
O60 10.1 4.9 28.22
A60 10.1 5.2 24.42
I100 17.8 9.8 41.37
O100 14.1 8.4 33.79
A100 13.8 8.7 30.96
Table 9.  Summarized results of number of requests on the cost savings
Customer Requests Non-collaboration Nv Collaboration Nv $\phi$
I20 4.3 2.3 22.57
I40 8 6 31.02
I60 11 6.3 33.31
I100 17.8 9.8 41.37
Average 4.2 2.1 17.08
O20 4.1 2 17.90
O40 7.3 3.5 24.19
O60 10.1 4.9 28.22
O100 14.1 8.4 33.79
Average 7.6 4.4 23.85
A20 4.2 2.1 10.76
A40 7.5 3.9 16.35
A60 10.1 5.2 24.42
A100 13.8 8.7 30.96
Average 10.4 5.5 28.65
Table Options

Download as excel

Customer Requests Non-collaboration Nv Collaboration Nv $\phi$
I20 4.3 2.3 22.57
I40 8 6 31.02
I60 11 6.3 33.31
I100 17.8 9.8 41.37
Average 4.2 2.1 17.08
O20 4.1 2 17.90
O40 7.3 3.5 24.19
O60 10.1 4.9 28.22
O100 14.1 8.4 33.79
Average 7.6 4.4 23.85
A20 4.2 2.1 10.76
A40 7.5 3.9 16.35
A60 10.1 5.2 24.42
A100 13.8 8.7 30.96
Average 10.4 5.5 28.65
Table 10.  Detailed results of CPLEX solver and GRASP-ILS for instances with 20 requests
Instance CPLEX GRASP-ILS
Ini UB LB CPU GapLB Zmin CPU Zavg CPUavg ImpCplex GapLB
I20-2-1-0 / 459.26 459.26 6727.61 0.00 459.26 6.24 459.26 7.25 0.00 0.00
I20-2-1-1 / 366.66 366.66 142.44 0.00 366.66 2.23 366.66 4.47 0.00 0.00
I20-2-1-2 / 478.19 478.19 1360.56 0.00 478.19 6.64 478.19 8.24 0.00 0.00
I20-2-1-3 / 360.24 360.24 128.19 0.00 360.24 1.86 365.33 1.89 0.00 0.00
I20-2-1-4 / 383.24 383.24 8933.10 0.00 383.24 1.67 383.24 2.01 0.00 0.00
I20-2-1-5 / 343.70 343.70 369.21 0.00 343.70 1.41 350.76 1.81 0.00 0.00
I20-2-1-6 / 344.51 344.51 366.51 0.00 344.51 1.59 344.51 1.77 0.00 0.00
I20-2-1-7 / 354.59 354.59 266.03 0.00 354.59 1.75 355.59 3.11 0.00 0.00
I20-2-1-8 / 351.37 351.37 2202.84 0.00 351.37 1.40 351.37 1.77 0.00 0.00
I20-2-1-9 / 476.32 476.32 514.23 0.00 476.32 6.97 476.32 8.15 0.00 0.00
Avg 2101.07 0.00 3.17
O20-2-1-0 / 240.46 240.46 817.75 0.00 240.46 2.18 240.46 2.51 0.00 0.00
O20-2-1-1 / 260.84 260.84 727.20 0.00 260.84 1.84 260.84 2.13 0.00 0.00
O20-2-1-2 / 250.62 250.62 945.73 0.00 250.62 2.50 250.62 2.66 0.00 0.00
O20-2-1-3 / 254.79 254.79 1213.25 0.00 254.79 1.50 254.79 1.83 0.00 0.00
O20-2-1-4 / 273.79 273.79 563.98 0.00 273.79 2.03 273.85 1.99 0.00 0.00
O20-2-1-5 / 269.61 269.61 2227.00 0.00 269.61 1.46 269.61 2.05 0.00 0.00
O20-2-1-6 / 260.31 260.31 1456.89 0.00 260.31 1.64 260.41 2.33 0.00 0.00
O20-2-1-7 / 245.95 245.95 1323.50 0.00 245.95 1.69 246.06 2.32 0.00 0.00
O20-2-1-8 / 240.28 240.28 685.00 0.00 240.28 1.70 240.28 2.28 0.00 0.00
O20-2-1-9 / 229.92 229.92 813.89 0.00 229.92 2.70 229.96 2.41 0.00 0.00
Avg 1077.42 0.00 1.92 0.00 0.00
A20-2-1-0 / 362.31 362.31 987.80 0.00 362.31 1.59 366.24 1.85 0.00 0.00
A20-2-1-1 / 444.80 444.80 1188.06 0.00 444.80 7.26 444.80 8.29 0.00 0.00
A20-2-1-2 / 329.67 329.67 2358.72 0.00 329.67 1.37 334.31 1.85 0.00 0.00
A20-2-1-3 / 363.62 363.62 1206.36 0.00 363.62 4.06 372.23 5.38 0.00 0.00
A20-2-1-4 / 343.77 343.77 2440.98 0.00 343.77 1.66 343.77 1.91 0.00 0.00
A20-2-1-5 / 287.74 287.74 1266.59 0.00 287.74 1.99 294.17 1.55 0.00 0.00
A20-2-1-6 / 338.23 338.23 821.69 0.00 338.23 1.56 338.23 1.70 0.00 0.00
A20-2-1-7 / 290.21 290.21 985.11 0.00 290.21 1.40 292.05 1.59 0.00 0.00
A20-2-1-8 / 314.20 314.20 1324.84 0.00 314.20 2.13 314.20 1.70 0.00 0.00
A20-2-1-9 / 323.60 323.60 921.38 0.00 323.60 1.93 323.60 2.18 0.00 0.00
Avg 1350.15 0.00 2.49 0.00 0.00
Table Options

Download as excel

Instance CPLEX GRASP-ILS
Ini UB LB CPU GapLB Zmin CPU Zavg CPUavg ImpCplex GapLB
I20-2-1-0 / 459.26 459.26 6727.61 0.00 459.26 6.24 459.26 7.25 0.00 0.00
I20-2-1-1 / 366.66 366.66 142.44 0.00 366.66 2.23 366.66 4.47 0.00 0.00
I20-2-1-2 / 478.19 478.19 1360.56 0.00 478.19 6.64 478.19 8.24 0.00 0.00
I20-2-1-3 / 360.24 360.24 128.19 0.00 360.24 1.86 365.33 1.89 0.00 0.00
I20-2-1-4 / 383.24 383.24 8933.10 0.00 383.24 1.67 383.24 2.01 0.00 0.00
I20-2-1-5 / 343.70 343.70 369.21 0.00 343.70 1.41 350.76 1.81 0.00 0.00
I20-2-1-6 / 344.51 344.51 366.51 0.00 344.51 1.59 344.51 1.77 0.00 0.00
I20-2-1-7 / 354.59 354.59 266.03 0.00 354.59 1.75 355.59 3.11 0.00 0.00
I20-2-1-8 / 351.37 351.37 2202.84 0.00 351.37 1.40 351.37 1.77 0.00 0.00
I20-2-1-9 / 476.32 476.32 514.23 0.00 476.32 6.97 476.32 8.15 0.00 0.00
Avg 2101.07 0.00 3.17
O20-2-1-0 / 240.46 240.46 817.75 0.00 240.46 2.18 240.46 2.51 0.00 0.00
O20-2-1-1 / 260.84 260.84 727.20 0.00 260.84 1.84 260.84 2.13 0.00 0.00
O20-2-1-2 / 250.62 250.62 945.73 0.00 250.62 2.50 250.62 2.66 0.00 0.00
O20-2-1-3 / 254.79 254.79 1213.25 0.00 254.79 1.50 254.79 1.83 0.00 0.00
O20-2-1-4 / 273.79 273.79 563.98 0.00 273.79 2.03 273.85 1.99 0.00 0.00
O20-2-1-5 / 269.61 269.61 2227.00 0.00 269.61 1.46 269.61 2.05 0.00 0.00
O20-2-1-6 / 260.31 260.31 1456.89 0.00 260.31 1.64 260.41 2.33 0.00 0.00
O20-2-1-7 / 245.95 245.95 1323.50 0.00 245.95 1.69 246.06 2.32 0.00 0.00
O20-2-1-8 / 240.28 240.28 685.00 0.00 240.28 1.70 240.28 2.28 0.00 0.00
O20-2-1-9 / 229.92 229.92 813.89 0.00 229.92 2.70 229.96 2.41 0.00 0.00
Avg 1077.42 0.00 1.92 0.00 0.00
A20-2-1-0 / 362.31 362.31 987.80 0.00 362.31 1.59 366.24 1.85 0.00 0.00
A20-2-1-1 / 444.80 444.80 1188.06 0.00 444.80 7.26 444.80 8.29 0.00 0.00
A20-2-1-2 / 329.67 329.67 2358.72 0.00 329.67 1.37 334.31 1.85 0.00 0.00
A20-2-1-3 / 363.62 363.62 1206.36 0.00 363.62 4.06 372.23 5.38 0.00 0.00
A20-2-1-4 / 343.77 343.77 2440.98 0.00 343.77 1.66 343.77 1.91 0.00 0.00
A20-2-1-5 / 287.74 287.74 1266.59 0.00 287.74 1.99 294.17 1.55 0.00 0.00
A20-2-1-6 / 338.23 338.23 821.69 0.00 338.23 1.56 338.23 1.70 0.00 0.00
A20-2-1-7 / 290.21 290.21 985.11 0.00 290.21 1.40 292.05 1.59 0.00 0.00
A20-2-1-8 / 314.20 314.20 1324.84 0.00 314.20 2.13 314.20 1.70 0.00 0.00
A20-2-1-9 / 323.60 323.60 921.38 0.00 323.60 1.93 323.60 2.18 0.00 0.00
Avg 1350.15 0.00 2.49 0.00 0.00
Table 11.  Detailed results of CPLEX solver and GRASP-ILS for instances with 40 requests
Instance CPLEX GRASP-ILS
Ini UB LB CPU ImpIni GapLB Zmin CPU Zavg CPUavg ImpIni ImpCplex GapLB
I40-2-1-0 764.73 733.02 554.38 21600.00 4.15 24.37 706.64 31.77 722.04 35.64 7.60 3.60 21.55
I40-2-1-1 617.81 617.81 432.47 21600.00 0.00 30.00 600.90 30.07 607.03 33.09 2.74 2.74 28.03
I40-2-1-2 776.04 776.04 526.08 21600.00 0.00 32.21 729.24 31.07 729.24 33.12 6.03 6.03 27.86
I40-2-1-3 718.16 702.54 545.94 21600.00 2.18 22.29 651.55 26.00 651.55 28.16 9.28 7.26 16.21
I40-2-1-4 720.41 716.43 519.91 21600.00 0.55 27.43 699.59 26.37 699.59 27.97 2.89 2.35 25.68
I40-2-1-5 748.66 748.66 475.02 21600.00 0.00 36.55 647.36 27.67 647.36 31.16 13.53 13.53 26.62
I40-2-1-6 615.92 615.92 435.58 21600.00 0.00 29.28 590.24 29.90 591.42 32.15 4.17 4.17 26.20
I40-2-1-7 664.83 662.64 432.11 21600.00 0.33 34.79 612.68 28.53 613.44 29.29 7.84 7.54 29.47
I40-2-1-8 634.10 594.85 447.33 21600.00 6.19 24.80 573.59 32.61 574.75 34.14 9.54 3.57 22.01
I40-2-1-9 611.25 604.84 466.03 21600.00 1.05 22.95 598.44 28.16 601.82 31.40 2.10 1.06 22.13
Avg 21600.00 1.44 28.47 29.22 31.61 6.57 5.18 24.58
O40-2-1-0 590.88 494.73 486.52 21600.00 16.27 1.66 494.73 30.31 497.25 32.04 16.27 0.00 1.66
O40-2-1-1 484.61 443.19 390.45 21600.00 9.99 11.90 434.04 36.80 439.23 35.30 10.44 2.06 10.04
O40-2-1-2 452.71 445.80 401.58 21600.00 1.53 9.92 445.80 34.44 445.80 36.68 1.53 0.00 9.92
O40-2-1-3 604.15 529.67 456.10 21600.00 12.33 13.89 523.35 36.44 523.35 37.24 13.37 1.19 12.85
O40-2-1-4 551.18 550.47 458.60 21600.00 0.13 16.69 549.35 37.96 549.35 41.00 0.33 0.20 16.52
O40-2-1-5 627.43 576.14 486.90 21600.00 8.17 15.49 573.11 34.70 573.11 36.25 8.66 0.53 15.04
O40-2-1-6 496.89 492.06 422.04 21600.00 0.97 14.23 489.14 39.24 489.14 41.56 1.56 0.59 13.72
O40-2-1-7 545.21 532.03 492.50 21600.00 2.78 7.43 528.80 31.72 542.87 36.13 3.01 0.61 6.86
O40-2-1-8 441.62 427.55 427.55 21600.00 3.19 0.00 427.55 32.20 427.82 40.79 3.19 0.00 0.00
O40-2-1-9 611.65 582.21 485.50 21600.00 4.81 16.61 578.85 37.98 579.14 37.03 5.36 0.58 16.13
Avg 21600.00 6.02 10.78 35.18 37.40 6.37 0.58 10.27
A40-2-1-0 595.16 581.93 463.33 21600.00 2.22 20.38 550.20 26.67 563.08 29.48 7.55 5.45 15.79
A40-2-1-1 617.54 617.54 428.57 21600.00 0.00 30.60 597.17 29.64 601.48 32.31 3.30 3.30 28.23
A40-2-1-2 685.71 593.58 508.05 21600.00 13.44 14.41 582.03 32.10 582.03 36.22 15.12 1.95 12.71
A40-2-1-3 511.22 511.22 383.62 21600.00 0.00 24.96 505.21 31.86 505.21 34.47 1.18 1.18 24.07
A40-2-1-4 574.55 569.49 460.72 21600.00 0.88 19.10 567.77 33.23 568.40 33.13 1.18 0.30 18.85
A40-2-1-5 626.75 626.75 484.73 21600.00 0.00 22.66 617.34 28.18 617.38 30.09 1.50 1.50 21.48
A40-2-1-6 574.52 572.59 457.56 21600.00 1.90 20.09 537.91 32.50 560.92 37.04 6.37 6.06 14.94
A40-2-1-7 615.58 552.47 494.52 21600.00 10.90 10.49 542.06 30.23 548.20 28.19 11.94 1.88 8.77
A40-2-1-8 642.09 630.61 480.02 21600.00 1.79 23.88 600.61 27.93 600.61 29.57 6.46 4.76 20.08
A40-2-1-9 714.16 698.33 542.39 21600.00 2.22 22.33 632.33 27.06 635.86 30.86 11.46 9.45 14.22
Avg 21600.00 3.33 20.89 29.94 32.14 6.61 3.58 17.91
Table Options

Download as excel

Instance CPLEX GRASP-ILS
Ini UB LB CPU ImpIni GapLB Zmin CPU Zavg CPUavg ImpIni ImpCplex GapLB
I40-2-1-0 764.73 733.02 554.38 21600.00 4.15 24.37 706.64 31.77 722.04 35.64 7.60 3.60 21.55
I40-2-1-1 617.81 617.81 432.47 21600.00 0.00 30.00 600.90 30.07 607.03 33.09 2.74 2.74 28.03
I40-2-1-2 776.04 776.04 526.08 21600.00 0.00 32.21 729.24 31.07 729.24 33.12 6.03 6.03 27.86
I40-2-1-3 718.16 702.54 545.94 21600.00 2.18 22.29 651.55 26.00 651.55 28.16 9.28 7.26 16.21
I40-2-1-4 720.41 716.43 519.91 21600.00 0.55 27.43 699.59 26.37 699.59 27.97 2.89 2.35 25.68
I40-2-1-5 748.66 748.66 475.02 21600.00 0.00 36.55 647.36 27.67 647.36 31.16 13.53 13.53 26.62
I40-2-1-6 615.92 615.92 435.58 21600.00 0.00 29.28 590.24 29.90 591.42 32.15 4.17 4.17 26.20
I40-2-1-7 664.83 662.64 432.11 21600.00 0.33 34.79 612.68 28.53 613.44 29.29 7.84 7.54 29.47
I40-2-1-8 634.10 594.85 447.33 21600.00 6.19 24.80 573.59 32.61 574.75 34.14 9.54 3.57 22.01
I40-2-1-9 611.25 604.84 466.03 21600.00 1.05 22.95 598.44 28.16 601.82 31.40 2.10 1.06 22.13
Avg 21600.00 1.44 28.47 29.22 31.61 6.57 5.18 24.58
O40-2-1-0 590.88 494.73 486.52 21600.00 16.27 1.66 494.73 30.31 497.25 32.04 16.27 0.00 1.66
O40-2-1-1 484.61 443.19 390.45 21600.00 9.99 11.90 434.04 36.80 439.23 35.30 10.44 2.06 10.04
O40-2-1-2 452.71 445.80 401.58 21600.00 1.53 9.92 445.80 34.44 445.80 36.68 1.53 0.00 9.92
O40-2-1-3 604.15 529.67 456.10 21600.00 12.33 13.89 523.35 36.44 523.35 37.24 13.37 1.19 12.85
O40-2-1-4 551.18 550.47 458.60 21600.00 0.13 16.69 549.35 37.96 549.35 41.00 0.33 0.20 16.52
O40-2-1-5 627.43 576.14 486.90 21600.00 8.17 15.49 573.11 34.70 573.11 36.25 8.66 0.53 15.04
O40-2-1-6 496.89 492.06 422.04 21600.00 0.97 14.23 489.14 39.24 489.14 41.56 1.56 0.59 13.72
O40-2-1-7 545.21 532.03 492.50 21600.00 2.78 7.43 528.80 31.72 542.87 36.13 3.01 0.61 6.86
O40-2-1-8 441.62 427.55 427.55 21600.00 3.19 0.00 427.55 32.20 427.82 40.79 3.19 0.00 0.00
O40-2-1-9 611.65 582.21 485.50 21600.00 4.81 16.61 578.85 37.98 579.14 37.03 5.36 0.58 16.13
Avg 21600.00 6.02 10.78 35.18 37.40 6.37 0.58 10.27
A40-2-1-0 595.16 581.93 463.33 21600.00 2.22 20.38 550.20 26.67 563.08 29.48 7.55 5.45 15.79
A40-2-1-1 617.54 617.54 428.57 21600.00 0.00 30.60 597.17 29.64 601.48 32.31 3.30 3.30 28.23
A40-2-1-2 685.71 593.58 508.05 21600.00 13.44 14.41 582.03 32.10 582.03 36.22 15.12 1.95 12.71
A40-2-1-3 511.22 511.22 383.62 21600.00 0.00 24.96 505.21 31.86 505.21 34.47 1.18 1.18 24.07
A40-2-1-4 574.55 569.49 460.72 21600.00 0.88 19.10 567.77 33.23 568.40 33.13 1.18 0.30 18.85
A40-2-1-5 626.75 626.75 484.73 21600.00 0.00 22.66 617.34 28.18 617.38 30.09 1.50 1.50 21.48
A40-2-1-6 574.52 572.59 457.56 21600.00 1.90 20.09 537.91 32.50 560.92 37.04 6.37 6.06 14.94
A40-2-1-7 615.58 552.47 494.52 21600.00 10.90 10.49 542.06 30.23 548.20 28.19 11.94 1.88 8.77
A40-2-1-8 642.09 630.61 480.02 21600.00 1.79 23.88 600.61 27.93 600.61 29.57 6.46 4.76 20.08
A40-2-1-9 714.16 698.33 542.39 21600.00 2.22 22.33 632.33 27.06 635.86 30.86 11.46 9.45 14.22
Avg 21600.00 3.33 20.89 29.94 32.14 6.61 3.58 17.91
Table 12.  Detailed results of CPLEX solver and GRASP-ILS for instances with 60 requests
Instance CPLEX GRASP-ILS
Ini UB LB CPU ImpIni GapLB Zmin CPU Zavg CPUavg ImpIni ImpCplex GapLB
I60-2-1-0 1075.15 1011.77 647.03 21600.00 5.89 36.05 911.77 99.40 914.95 114.83 15.20 9.88 29.04
I60-2-1-1 1190.63 1187.76 774.42 21600.00 0.24 34.80 987.76 118.70 988.14 130.24 17.04 16.84 21.60
I60-2-1-2 950.96 939.23 602.05 21600.00 1.23 35.90 877.23 131.62 879.37 139.26 7.75 6.60 31.37
I60-2-1-3 1088.70 1082.44 690.16 21600.00 0.57 36.24 882.44 137.82 889.93 122.66 18.95 18.48 21.79
I60-2-1-4 1047.69 1000.73 685.00 21600.00 4.48 31.55 896.87 108.94 900.72 119.33 14.40 10.38 23.62
I60-2-1-5 1026.03 1026.03 632.75 21600.00 0.00 38.33 996.95 138.59 997.19 135.02 2.83 2.83 36.53
I60-2-1-6 1214.28 1143.88 758.39 21600.00 5.80 33.70 1043.88 119.96 1046.20 126.73 14.03 8.74 27.35
I60-2-1-7 993.02 993.02 642.58 21600.00 0.00 35.29 944.32 132.32 960.94 137.32 4.90 4.90 31.95
I60-2-1-8 946.14 918.94 625.61 21600.00 2.87 31.92 818.94 132.87 826.45 119.74 13.44 10.88 23.61
I60-2-1-9 1029.63 965.24 687.93 21600.00 6.25 28.73 865.24 133.94 867.75 135.43 15.97 10.36 20.49
Avg 21600.00 2.74 34.25 125.42 12.45 9.99 26.73
O60-2-1-0 778.81 742.35 556.24 21600.00 4.68 25.07 652.35 146.37 672.06 140.72 16.24 12.12 14.73
O60-2-1-1 860.37 792.55 585.30 21600.00 7.88 26.15 746.22 144.23 750.48 150.35 13.27 5.85 21.56
O60-2-1-2 883.39 832.49 606.55 21600.00 5.76 27.14 732.49 138.82 736.08 137.72 17.08 12.01 17.19
O60-2-1-3 975.67 897.76 686.25 21600.00 7.99 23.56 787.76 128.96 795.54 144.19 19.26 12.25 12.89
O60-2-1-4 889.25 832.01 565.60 21600.00 6.44 32.02 727.32 159.57 734.02 163.88 18.21 12.58 22.24
O60-2-1-5 891.08 852.47 631.60 21600.00 4.33 25.91 752.74 150.60 755.68 145.87 15.53 11.70 16.09
O60-2-1-6 813.00 813.00 542.76 21600.00 0.00 33.24 680.46 129.71 680.46 147.45 16.30 16.30 20.24
O60-2-1-7 935.69 881.76 640.60 21600.00 5.76 27.35 752.96 162.61 761.11 172.49 19.53 14.61 14.92
O60-2-1-8 850.19 835.58 571.37 21600.00 1.72 31.62 695.58 134.58 696.81 139.18 18.19 16.75 17.86
O60-2-1-9 850.23 823.61 562.61 21600.00 3.13 31.69 723.61 152.90 727.63 150.04 14.89 12.14 22.25
Avg 21600.00 4.77 28.38 144.84 16.85 12.63 18.00
A60-2-1-0 936.24 936.24 594.70 21600.00 0.00 36.48 836.54 161.45 836.60 163.57 10.65 10.65 28.91
A60-2-1-1 1072.31 1072.31 663.76 21600.00 0.00 38.1 911.33 161.93 941.39 158.79 15.01 15.01 27.17
A60-2-1-2 859.84 803.79 620.37 21600.00 6.52 22.82 703.79 135.40 703.85 151.11 18.15 12.44 11.85
A60-2-1-3 950.17 881.73 663.68 21600.00 7.20 24.73 781.73 122.15 782.94 123.85 17.73 11.34 15.10
A60-2-1-4 912.08 902.08 622.80 21600.00 1.10 30.96 793.69 148.34 806.85 147.38 12.98 12.02 21.53
A60-2-1-5 908.24 908.24 611.25 21600.00 0.00 32.7 740.28 148.01 741.38 148.81 18.49 18.49 17.43
A60-2-1-6 919.06 854.71 676.50 21600.00 7.00 20.85 754.71 146.15 756.53 157.06 17.88 11.70 10.36
A60-2-1-7 942.98 880.28 647.62 21600.00 6.65 26.43 780.28 155.59 796.40 155.86 17.25 11.36 17.00
A60-2-1-8 799.61 799.61 594.75 21600.00 0.00 25.62 751.38 140.81 757.58 142.27 6.03 6.03 20.85
A60-2-1-9 817.71 776.45 553.61 21600.00 5.05 28.7 705.99 163.67 712.95 157.17 13.66 9.07 21.58
Avg 21600.00 3.35 28.74 148.35 14.78 11.81 19.18
Table Options

Download as excel

Instance CPLEX GRASP-ILS
Ini UB LB CPU ImpIni GapLB Zmin CPU Zavg CPUavg ImpIni ImpCplex GapLB
I60-2-1-0 1075.15 1011.77 647.03 21600.00 5.89 36.05 911.77 99.40 914.95 114.83 15.20 9.88 29.04
I60-2-1-1 1190.63 1187.76 774.42 21600.00 0.24 34.80 987.76 118.70 988.14 130.24 17.04 16.84 21.60
I60-2-1-2 950.96 939.23 602.05 21600.00 1.23 35.90 877.23 131.62 879.37 139.26 7.75 6.60 31.37
I60-2-1-3 1088.70 1082.44 690.16 21600.00 0.57 36.24 882.44 137.82 889.93 122.66 18.95 18.48 21.79
I60-2-1-4 1047.69 1000.73 685.00 21600.00 4.48 31.55 896.87 108.94 900.72 119.33 14.40 10.38 23.62
I60-2-1-5 1026.03 1026.03 632.75 21600.00 0.00 38.33 996.95 138.59 997.19 135.02 2.83 2.83 36.53
I60-2-1-6 1214.28 1143.88 758.39 21600.00 5.80 33.70 1043.88 119.96 1046.20 126.73 14.03 8.74 27.35
I60-2-1-7 993.02 993.02 642.58 21600.00 0.00 35.29 944.32 132.32 960.94 137.32 4.90 4.90 31.95
I60-2-1-8 946.14 918.94 625.61 21600.00 2.87 31.92 818.94 132.87 826.45 119.74 13.44 10.88 23.61
I60-2-1-9 1029.63 965.24 687.93 21600.00 6.25 28.73 865.24 133.94 867.75 135.43 15.97 10.36 20.49
Avg 21600.00 2.74 34.25 125.42 12.45 9.99 26.73
O60-2-1-0 778.81 742.35 556.24 21600.00 4.68 25.07 652.35 146.37 672.06 140.72 16.24 12.12 14.73
O60-2-1-1 860.37 792.55 585.30 21600.00 7.88 26.15 746.22 144.23 750.48 150.35 13.27 5.85 21.56
O60-2-1-2 883.39 832.49 606.55 21600.00 5.76 27.14 732.49 138.82 736.08 137.72 17.08 12.01 17.19
O60-2-1-3 975.67 897.76 686.25 21600.00 7.99 23.56 787.76 128.96 795.54 144.19 19.26 12.25 12.89
O60-2-1-4 889.25 832.01 565.60 21600.00 6.44 32.02 727.32 159.57 734.02 163.88 18.21 12.58 22.24
O60-2-1-5 891.08 852.47 631.60 21600.00 4.33 25.91 752.74 150.60 755.68 145.87 15.53 11.70 16.09
O60-2-1-6 813.00 813.00 542.76 21600.00 0.00 33.24 680.46 129.71 680.46 147.45 16.30 16.30 20.24
O60-2-1-7 935.69 881.76 640.60 21600.00 5.76 27.35 752.96 162.61 761.11 172.49 19.53 14.61 14.92
O60-2-1-8 850.19 835.58 571.37 21600.00 1.72 31.62 695.58 134.58 696.81 139.18 18.19 16.75 17.86
O60-2-1-9 850.23 823.61 562.61 21600.00 3.13 31.69 723.61 152.90 727.63 150.04 14.89 12.14 22.25
Avg 21600.00 4.77 28.38 144.84 16.85 12.63 18.00
A60-2-1-0 936.24 936.24 594.70 21600.00 0.00 36.48 836.54 161.45 836.60 163.57 10.65 10.65 28.91
A60-2-1-1 1072.31 1072.31 663.76 21600.00 0.00 38.1 911.33 161.93 941.39 158.79 15.01 15.01 27.17
A60-2-1-2 859.84 803.79 620.37 21600.00 6.52 22.82 703.79 135.40 703.85 151.11 18.15 12.44 11.85
A60-2-1-3 950.17 881.73 663.68 21600.00 7.20 24.73 781.73 122.15 782.94 123.85 17.73 11.34 15.10
A60-2-1-4 912.08 902.08 622.80 21600.00 1.10 30.96 793.69 148.34 806.85 147.38 12.98 12.02 21.53
A60-2-1-5 908.24 908.24 611.25 21600.00 0.00 32.7 740.28 148.01 741.38 148.81 18.49 18.49 17.43
A60-2-1-6 919.06 854.71 676.50 21600.00 7.00 20.85 754.71 146.15 756.53 157.06 17.88 11.70 10.36
A60-2-1-7 942.98 880.28 647.62 21600.00 6.65 26.43 780.28 155.59 796.40 155.86 17.25 11.36 17.00
A60-2-1-8 799.61 799.61 594.75 21600.00 0.00 25.62 751.38 140.81 757.58 142.27 6.03 6.03 20.85
A60-2-1-9 817.71 776.45 553.61 21600.00 5.05 28.7 705.99 163.67 712.95 157.17 13.66 9.07 21.58
Avg 21600.00 3.35 28.74 148.35 14.78 11.81 19.18
Table 13.  Detailed results of CPLEX solver and GRASP-ILS for instances with 100 requests
Instance CPLEX GRASP-ILS
Ini UB LB CPU ImpIni GapLB Zmin CPU Zavg CPUavg ImpIni ImpCplex GapLB
I100-2-1-0 1735.62 1680.34 1041.47 21600.00 3.29 38.02 1500.16 242.56 1509.42 254.82 15.70 10.72 30.58
I100-2-1-1 1651.57 1634.89 1015.27 21600.00 1.02 37.90 1399.61 244.23 1409.80 271.59 18.00 14.39 27.46
I100-2-1-2 1668.99 1668.99 907.93 21600.00 0.00 45.60 1481.37 264.12 1491.31 270.40 12.67 11.24 38.71
I100-2-1-3 1764.60 1689.42 1077.17 21600.00 4.45 36.24 1406.15 200.51 1412.52 228.29 25.49 16.77 23.40
I100-2-1-4 1686.00 1686.00 985.47 21600.00 0.00 41.55 1471.77 231.05 1479.38 237.84 14.56 12.71 33.04
I100-2-1-5 1700.66 1700.66 878.73 21600.00 0.00 48.33 1465.71 265.97 1488.23 273.44 16.03 13.82 40.05
I100-2-1-6 1692.38 1691.53 1017.12 21600.00 0.05 39.87 1482.92 258.92 1503.80 271.70 14.12 12.33 31.41
I100-2-1-7 1645.66 1645.66 900.34 21600.00 0.00 45.29 1439.77 227.63 1442.38 242.32 14.30 12.51 37.47
I100-2-1-8 1505.41 1478.50 927.61 21600.00 1.82 37.26 1277.58 261.05 1283.99 274.56 17.83 13.59 27.39
I100-2-1-9 1541.52 1460.33 987.62 21600.00 5.56 32.37 1286.29 267.15 1315.68 277.42 19.84 11.92 23.22
Avg 21600.00 1.62 40.24 246.32 16.85 13.00 31.27
O100-2-1-0 1467.93 1420.49 950.02 21600.00 3.34 33.12 1215.92 278.27 1225.50 288.86 20.73 14.40 21.87
O100-2-1-1 1309.79 1309.79 836.30 21600.00 0.00 36.15 1113.13 316.97 1124.36 328.01 17.67 15.01 24.87
O100-2-1-2 1283.48 1230.45 831.54 21600.00 4.31 32.42 1066.12 254.79 1068.68 263.26 20.39 13.36 22.00
O100-2-1-3 1284.46 1321.90 810.99 21600.00 0.00 38.65 1166.47 300.23 1186.02 278.56 13.32 11.76 30.48
O100-2-1-4 1382.26 1338.36 909.82 21600.00 3.28 32.02 1146.62 287.89 1151.50 298.72 20.55 14.33 20.65
O100-2-1-5 1494.38 1431.12 903.18 21600.00 4.42 36.89 1223.53 294.71 1245.41 298.48 22.14 14.51 26.18
O100-2-1-6 1318.96 1264.83 831.75 21600.00 4.28 34.24 1062.43 311.91 1064.81 321.69 24.15 16.00 21.71
O100-2-1-7 1435.95 1432.51 894.75 21600.00 0.24 37.54 1224.31 306.67 1230.86 324.67 17.29 14.53 26.92
O100-2-1-8 1254.70 1221.48 779.18 21600.00 2.72 36.21 971.56 296.99 1002.10 317.68 29.14 20.46 19.80
O100-2-1-9 1381.18 1339.26 866.90 21600.00 3.13 35.27 1098.25 278.80 1119.88 283.29 25.76 18.00 21.06
Avg 21600.00 2.57 35.25 292.72 21.11 15.24 23.55
A100-2-1-0 1415.28 1404.33 863.94 21600.00 0.78 38.48 1212.68 235.67 1230.21 256.89 16.71 13.65 28.76
A100-2-1-1 1696.07 1627.24 1168.36 21600.00 4.23 28.20 1271.73 269.87 1291.68 279.07 33.37 21.85 8.13
A100-2-1-2 1328.88 1283.69 849.55 21600.00 3.52 33.82 1129.63 308.04 1132.34 325.42 17.64 12.00 24.79
A100-2-1-3 1364.97 1360.34 865.59 21600.00 0.34 36.37 1162.85 263.527 1179.11 269.85 17.38 14.52 25.56
A100-2-1-4 1433.15 1417.56 886.68 21600.00 1.10 37.45 1190.23 270.33 1197.46 281.37 20.41 16.04 25.50
A100-2-1-5 1320.79 1320.79 802.64 21600.00 0.00 39.23 1093.48 267.46 1116.72 344.65 20.79 17.21 26.60
A100-2-1-6 1450.78 1400.91 972.51 21600.00 3.56 30.58 1208.76 258.22 1212.17 356.84 20.02 13.72 19.54
A100-2-1-7 1404.69 1371.23 920.23 21600.00 2.44 32.89 1174.24 364.28 1193.54 380.21 19.63 14.37 21.63
A100-2-1-8 1334.8 1321.19 847.28 21600.00 1.03 35.87 1154.51 266.66 1177.15 345.79 15.62 12.62 26.61
A100-2-1-9 1382.94 1365.60 918.36 21600.00 1.27 32.75 1217.18 320.42 1218.88 329.73 13.62 10.87 24.55
Avg 21600.00 1.83 34.56 282.45 19.52 14.68 23.17
Table Options

Download as excel

Instance CPLEX GRASP-ILS
Ini UB LB CPU ImpIni GapLB Zmin CPU Zavg CPUavg ImpIni ImpCplex GapLB
I100-2-1-0 1735.62 1680.34 1041.47 21600.00 3.29 38.02 1500.16 242.56 1509.42 254.82 15.70 10.72 30.58
I100-2-1-1 1651.57 1634.89 1015.27 21600.00 1.02 37.90 1399.61 244.23 1409.80 271.59 18.00 14.39 27.46
I100-2-1-2 1668.99 1668.99 907.93 21600.00 0.00 45.60 1481.37 264.12 1491.31 270.40 12.67 11.24 38.71
I100-2-1-3 1764.60 1689.42 1077.17 21600.00 4.45 36.24 1406.15 200.51 1412.52 228.29 25.49 16.77 23.40
I100-2-1-4 1686.00 1686.00 985.47 21600.00 0.00 41.55 1471.77 231.05 1479.38 237.84 14.56 12.71 33.04
I100-2-1-5 1700.66 1700.66 878.73 21600.00 0.00 48.33 1465.71 265.97 1488.23 273.44 16.03 13.82 40.05
I100-2-1-6 1692.38 1691.53 1017.12 21600.00 0.05 39.87 1482.92 258.92 1503.80 271.70 14.12 12.33 31.41
I100-2-1-7 1645.66 1645.66 900.34 21600.00 0.00 45.29 1439.77 227.63 1442.38 242.32 14.30 12.51 37.47
I100-2-1-8 1505.41 1478.50 927.61 21600.00 1.82 37.26 1277.58 261.05 1283.99 274.56 17.83 13.59 27.39
I100-2-1-9 1541.52 1460.33 987.62 21600.00 5.56 32.37 1286.29 267.15 1315.68 277.42 19.84 11.92 23.22
Avg 21600.00 1.62 40.24 246.32 16.85 13.00 31.27
O100-2-1-0 1467.93 1420.49 950.02 21600.00 3.34 33.12 1215.92 278.27 1225.50 288.86 20.73 14.40 21.87
O100-2-1-1 1309.79 1309.79 836.30 21600.00 0.00 36.15 1113.13 316.97 1124.36 328.01 17.67 15.01 24.87
O100-2-1-2 1283.48 1230.45 831.54 21600.00 4.31 32.42 1066.12 254.79 1068.68 263.26 20.39 13.36 22.00
O100-2-1-3 1284.46 1321.90 810.99 21600.00 0.00 38.65 1166.47 300.23 1186.02 278.56 13.32 11.76 30.48
O100-2-1-4 1382.26 1338.36 909.82 21600.00 3.28 32.02 1146.62 287.89 1151.50 298.72 20.55 14.33 20.65
O100-2-1-5 1494.38 1431.12 903.18 21600.00 4.42 36.89 1223.53 294.71 1245.41 298.48 22.14 14.51 26.18
O100-2-1-6 1318.96 1264.83 831.75 21600.00 4.28 34.24 1062.43 311.91 1064.81 321.69 24.15 16.00 21.71
O100-2-1-7 1435.95 1432.51 894.75 21600.00 0.24 37.54 1224.31 306.67 1230.86 324.67 17.29 14.53 26.92
O100-2-1-8 1254.70 1221.48 779.18 21600.00 2.72 36.21 971.56 296.99 1002.10 317.68 29.14 20.46 19.80
O100-2-1-9 1381.18 1339.26 866.90 21600.00 3.13 35.27 1098.25 278.80 1119.88 283.29 25.76 18.00 21.06
Avg 21600.00 2.57 35.25 292.72 21.11 15.24 23.55
A100-2-1-0 1415.28 1404.33 863.94 21600.00 0.78 38.48 1212.68 235.67 1230.21 256.89 16.71 13.65 28.76
A100-2-1-1 1696.07 1627.24 1168.36 21600.00 4.23 28.20 1271.73 269.87 1291.68 279.07 33.37 21.85 8.13
A100-2-1-2 1328.88 1283.69 849.55 21600.00 3.52 33.82 1129.63 308.04 1132.34 325.42 17.64 12.00 24.79
A100-2-1-3 1364.97 1360.34 865.59 21600.00 0.34 36.37 1162.85 263.527 1179.11 269.85 17.38 14.52 25.56
A100-2-1-4 1433.15 1417.56 886.68 21600.00 1.10 37.45 1190.23 270.33 1197.46 281.37 20.41 16.04 25.50
A100-2-1-5 1320.79 1320.79 802.64 21600.00 0.00 39.23 1093.48 267.46 1116.72 344.65 20.79 17.21 26.60
A100-2-1-6 1450.78 1400.91 972.51 21600.00 3.56 30.58 1208.76 258.22 1212.17 356.84 20.02 13.72 19.54
A100-2-1-7 1404.69 1371.23 920.23 21600.00 2.44 32.89 1174.24 364.28 1193.54 380.21 19.63 14.37 21.63
A100-2-1-8 1334.8 1321.19 847.28 21600.00 1.03 35.87 1154.51 266.66 1177.15 345.79 15.62 12.62 26.61
A100-2-1-9 1382.94 1365.60 918.36 21600.00 1.27 32.75 1217.18 320.42 1218.88 329.73 13.62 10.87 24.55
Avg 21600.00 1.83 34.56 282.45 19.52 14.68 23.17
Table 14.  Meta-heuristics results for instances with 20 requests
Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I20-2-1-0 459.26 459.26 459.26 459.26 459.26 0.00 0.00
I20-2-1-1 449.88 449.88 366.66 366.66 366.66 22.70 0.00
I20-2-1-2 478.19 478.19 478.19 478.19 478.19 0.00 0.00
I20-2-1-3 449.29 459.44 360.24 415.28 360.24 24.72 0.00
I20-2-1-4 387.33 413.78 387.33 412.08 383.24 1.07 1.07
I20-2-1-5 364.89 370.22 364.89 373.59 343.70 6.17 6.17
I20-2-1-6 344.51 344.51 344.51 344.51 344.51 0.00 0.00
I20-2-1-7 379.50 407.70 426.47 479.74 354.59 7.03 20.27
I20-2-1-8 363.34 368.28 366.19 376.44 351.37 3.41 4.22
I20-2-1-9 476.32 476.32 476.32 494.04 476.32 0.00 0.00
Avg 6.51 3.17
O20-2-1-0 240.46 240.46 240.46 240.46 240.46 0.00 0.00
O20-2-1-1 261.02 261.02 278.50 278.56 260.84 0.07 6.77
O20-2-1-2 250.62 250.62 251.75 251.75 250.62 0.00 0.45
O20-2-1-3 254.79 254.79 254.79 254.79 254.79 0.00 0.00
O20-2-1-4 273.98 274.99 275.45 275.56 273.79 0.07 0.61
O20-2-1-5 269.61 269.61 269.61 269.61 269.61 0.00 0.00
O20-2-1-6 260.87 260.92 260.87 261.21 260.31 0.22 0.22
O20-2-1-7 245.95 246.37 246.97 246.97 245.95 0.00 0.41
O20-2-1-8 265.74 265.74 240.28 244.44 240.28 10.60 0.00
O20-2-1-9 247.82 247.97 230.15 235.51 229.92 7.79 0.10
Avg 1.87 0.86
A20-2-1-0 367.97 367.97 367.91 379.79 362.31 1.56 1.55
A20-2-1-1 444.8 444.80 444.80 444.80 444.80 0.00 0.00
A20-2-1-2 364.77 375.31 364.77 404.68 329.67 10.65 10.65
A20-2-1-3 412.44 439.21 423.93 456.66 363.62 13.43 16.59
A20-2-1-4 415.4 415.40 343.77 397.64 343.77 20.84 0.00
A20-2-1-5 295.37 297.82 299.91 305.22 287.74 2.65 4.23
A20-2-1-6 340.74 340.74 338.23 338.74 338.23 0.74 0.00
A20-2-1-7 298.51 304.03 301.26 304.94 290.21 2.86 3.81
A20-2-1-8 314.20 314.20 314.20 314.20 314.20 0.00 0.00
A20-2-1-9 400.40 400.40 323.60 361.33 323.60 23.73 0.00
Avg 7.65 3.68
Table Options

Download as excel

Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I20-2-1-0 459.26 459.26 459.26 459.26 459.26 0.00 0.00
I20-2-1-1 449.88 449.88 366.66 366.66 366.66 22.70 0.00
I20-2-1-2 478.19 478.19 478.19 478.19 478.19 0.00 0.00
I20-2-1-3 449.29 459.44 360.24 415.28 360.24 24.72 0.00
I20-2-1-4 387.33 413.78 387.33 412.08 383.24 1.07 1.07
I20-2-1-5 364.89 370.22 364.89 373.59 343.70 6.17 6.17
I20-2-1-6 344.51 344.51 344.51 344.51 344.51 0.00 0.00
I20-2-1-7 379.50 407.70 426.47 479.74 354.59 7.03 20.27
I20-2-1-8 363.34 368.28 366.19 376.44 351.37 3.41 4.22
I20-2-1-9 476.32 476.32 476.32 494.04 476.32 0.00 0.00
Avg 6.51 3.17
O20-2-1-0 240.46 240.46 240.46 240.46 240.46 0.00 0.00
O20-2-1-1 261.02 261.02 278.50 278.56 260.84 0.07 6.77
O20-2-1-2 250.62 250.62 251.75 251.75 250.62 0.00 0.45
O20-2-1-3 254.79 254.79 254.79 254.79 254.79 0.00 0.00
O20-2-1-4 273.98 274.99 275.45 275.56 273.79 0.07 0.61
O20-2-1-5 269.61 269.61 269.61 269.61 269.61 0.00 0.00
O20-2-1-6 260.87 260.92 260.87 261.21 260.31 0.22 0.22
O20-2-1-7 245.95 246.37 246.97 246.97 245.95 0.00 0.41
O20-2-1-8 265.74 265.74 240.28 244.44 240.28 10.60 0.00
O20-2-1-9 247.82 247.97 230.15 235.51 229.92 7.79 0.10
Avg 1.87 0.86
A20-2-1-0 367.97 367.97 367.91 379.79 362.31 1.56 1.55
A20-2-1-1 444.8 444.80 444.80 444.80 444.80 0.00 0.00
A20-2-1-2 364.77 375.31 364.77 404.68 329.67 10.65 10.65
A20-2-1-3 412.44 439.21 423.93 456.66 363.62 13.43 16.59
A20-2-1-4 415.4 415.40 343.77 397.64 343.77 20.84 0.00
A20-2-1-5 295.37 297.82 299.91 305.22 287.74 2.65 4.23
A20-2-1-6 340.74 340.74 338.23 338.74 338.23 0.74 0.00
A20-2-1-7 298.51 304.03 301.26 304.94 290.21 2.86 3.81
A20-2-1-8 314.20 314.20 314.20 314.20 314.20 0.00 0.00
A20-2-1-9 400.40 400.40 323.60 361.33 323.60 23.73 0.00
Avg 7.65 3.68
Table 15.  Meta-heuristics results for instances with 40 requests
Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I40-2-1-0 733.03 769.61 741.58 773.84 706.64 3.73 4.94
I40-2-1-1 617.81 617.81 610.54 675.38 600.90 2.81 1.60
I40-2-1-2 756.99 806.65 755.90 772.53 729.24 3.81 3.66
I40-2-1-3 651.55 681.20 718.16 718.16 651.55 0.00 10.22
I40-2-1-4 699.59 731.00 720.42 720.42 699.59 0.00 2.98
I40-2-1-5 718.38 761.48 672.90 771.28 647.36 10.97 3.95
I40-2-1-6 605.91 639.66 627.27 700.22 590.24 4.35 6.27
I40-2-1-7 653.35 653.35 612.68 686.02 612.68 6.64 0.00
I40-2-1-8 601.37 635.83 582.26 645.55 573.59 4.84 1.51
I40-2-1-9 612.71 654.01 610.28 677.78 598.44 2.38 1.98
Avg 3.95 3.71
O40-2-1-0 573.13 607.63 530.77 613.94 494.73 15.85 7.28
O40-2-1-1 451.96 479.67 476.94 535.79 434.04 4.13 9.88
O40-2-1-2 465.61 486.61 452.72 499.94 445.80 4.44 1.55
O40-2-1-3 523.35 523.35 523.35 523.35 523.35 0.00 0.00
O40-2-1-4 549.35 549.35 549.35 549.35 549.35 0.00 0.00
O40-2-1-5 577.85 601.43 603.35 666.88 573.11 0.83 5.28
O40-2-1-6 492.06 525.27 492.06 492.06 489.14 0.60 0.60
O40-2-1-7 545.21 550.93 545.21 545.21 528.80 3.10 3.10
O40-2-1-8 431.92 455.46 430.07 473.46 427.55 1.02 0.59
O40-2-1-9 579.27 602.79 601.79 668.05 578.85 0.07 3.96
Avg 3.00 3.23
A40-2-1-0 636.15 636.28 551.33 631.55 550.20 15.62 0.21
A40-2-1-1 606.64 644.56 616.86 622.47 597.17 1.59 3.30
A40-2-1-2 587.75 587.75 582.03 583.37 582.03 0.98 0.00
A40-2-1-3 506.85 506.85 508.34 559.68 505.21 0.32 0.62
A40-2-1-4 573.67 573.78 568.42 570.30 567.77 1.04 0.11
A40-2-1-5 683.98 697.73 617.34 703.95 617.34 10.79 0.00
A40-2-1-6 587.71 660.17 569.77 572.96 537.91 9.26 5.92
A40-2-1-7 615.47 645.69 605.92 703.23 542.06 13.54 11.78
A40-2-1-8 624.30 670.44 624.30 702.84 600.61 3.94 3.94
A40-2-1-9 697.84 724.57 697.60 816.89 632.33 10.36 10.32
Avg 6.75 3.62
Table Options

Download as excel

Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I40-2-1-0 733.03 769.61 741.58 773.84 706.64 3.73 4.94
I40-2-1-1 617.81 617.81 610.54 675.38 600.90 2.81 1.60
I40-2-1-2 756.99 806.65 755.90 772.53 729.24 3.81 3.66
I40-2-1-3 651.55 681.20 718.16 718.16 651.55 0.00 10.22
I40-2-1-4 699.59 731.00 720.42 720.42 699.59 0.00 2.98
I40-2-1-5 718.38 761.48 672.90 771.28 647.36 10.97 3.95
I40-2-1-6 605.91 639.66 627.27 700.22 590.24 4.35 6.27
I40-2-1-7 653.35 653.35 612.68 686.02 612.68 6.64 0.00
I40-2-1-8 601.37 635.83 582.26 645.55 573.59 4.84 1.51
I40-2-1-9 612.71 654.01 610.28 677.78 598.44 2.38 1.98
Avg 3.95 3.71
O40-2-1-0 573.13 607.63 530.77 613.94 494.73 15.85 7.28
O40-2-1-1 451.96 479.67 476.94 535.79 434.04 4.13 9.88
O40-2-1-2 465.61 486.61 452.72 499.94 445.80 4.44 1.55
O40-2-1-3 523.35 523.35 523.35 523.35 523.35 0.00 0.00
O40-2-1-4 549.35 549.35 549.35 549.35 549.35 0.00 0.00
O40-2-1-5 577.85 601.43 603.35 666.88 573.11 0.83 5.28
O40-2-1-6 492.06 525.27 492.06 492.06 489.14 0.60 0.60
O40-2-1-7 545.21 550.93 545.21 545.21 528.80 3.10 3.10
O40-2-1-8 431.92 455.46 430.07 473.46 427.55 1.02 0.59
O40-2-1-9 579.27 602.79 601.79 668.05 578.85 0.07 3.96
Avg 3.00 3.23
A40-2-1-0 636.15 636.28 551.33 631.55 550.20 15.62 0.21
A40-2-1-1 606.64 644.56 616.86 622.47 597.17 1.59 3.30
A40-2-1-2 587.75 587.75 582.03 583.37 582.03 0.98 0.00
A40-2-1-3 506.85 506.85 508.34 559.68 505.21 0.32 0.62
A40-2-1-4 573.67 573.78 568.42 570.30 567.77 1.04 0.11
A40-2-1-5 683.98 697.73 617.34 703.95 617.34 10.79 0.00
A40-2-1-6 587.71 660.17 569.77 572.96 537.91 9.26 5.92
A40-2-1-7 615.47 645.69 605.92 703.23 542.06 13.54 11.78
A40-2-1-8 624.30 670.44 624.30 702.84 600.61 3.94 3.94
A40-2-1-9 697.84 724.57 697.60 816.89 632.33 10.36 10.32
Avg 6.75 3.62
Table 16.  Meta-heuristics results for instances with 60 requestss
Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I60-2-1-0 971.76 930.24 954.90 1040.17 911.77 6.58 4.73
I60-2-1-1 997.55 990.98 997.55 1070.57 987.76 0.99 0.99
I60-2-1-2 893.43 879.02 897.08 1033.44 877.23 1.85 2.26
I60-2-1-3 907.53 902.23 901.81 1008.95 882.44 2.84 2.20
I60-2-1-4 979.14 967.49 975.61 1121.17 896.87 9.17 8.78
I60-2-1-5 1004.53 997.95 1004.53 1065.50 996.95 0.76 0.76
I60-2-1-6 1061.43 1051.96 1056.81 1093.90 1043.88 1.68 1.24
I60-2-1-7 1005.16 981.49 950.37 1110.89 944.32 6.44 0.64
I60-2-1-8 882.39 854.26 854.36 965.17 818.94 7.75 4.33
I60-2-1-9 890.19 877.62 870.52 1028.26 865.24 2.88 0.61
Avg 4.09 2.65
O60-2-1-0 713.15 746.03 703.50 758.65 652.35 9.32 3.73
O60-2-1-1 820.25 872.50 782.50 820.53 746.22 9.92 0.55
O60-2-1-2 782.26 799.70 761.74 868.31 732.49 6.79 0.15
O60-2-1-3 847.18 875.98 820.05 853.67 787.76 7.54 0.52
O60-2-1-4 776.48 845.20 771.15 817.65 727.32 6.76 0.64
O60-2-1-5 820.66 851.19 763.93 844.07 752.74 9.02 0.40
O60-2-1-6 708.48 714.50 680.46 680.46 680.46 4.12 0.00
O60-2-1-7 816.27 830.39 781.70 811.56 752.96 8.41 1.16
O60-2-1-8 723.94 759.78 715.02 806.47 695.58 4.08 0.00
O60-2-1-9 783.28 871.56 747.26 771.70 723.61 8.25 0.18
Avg 7.42 0.73
A60-2-1-0 858.31 858.31 836.63 929.83 836.54 2.60 0.01
A60-2-1-1 956.96 1024.04 952.71 1049.60 911.33 5.01 4.54
A60-2-1-2 719.41 741.14 776.51 778.37 703.79 2.22 10.33
A60-2-1-3 849.45 928.96 802.22 912.04 781.73 8.66 2.62
A60-2-1-4 857.32 880.81 841.54 899.44 793.69 8.02 6.03
A60-2-1-5 808.57 830.08 761.17 803.11 740.28 9.22 2.82
A60-2-1-6 803.29 862.81 803.29 871.89 754.71 6.44 6.44
A60-2-1-7 853.23 853.23 802.72 905.31 780.28 9.35 2.88
A60-2-1-8 780.61 815.35 772.43 843.73 751.38 3.89 2.80
A60-2-1-9 763.12 795.25 762.09 825.88 705.99 8.09 7.95
Avg 6.35 4.64
Table Options

Download as excel

Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I60-2-1-0 971.76 930.24 954.90 1040.17 911.77 6.58 4.73
I60-2-1-1 997.55 990.98 997.55 1070.57 987.76 0.99 0.99
I60-2-1-2 893.43 879.02 897.08 1033.44 877.23 1.85 2.26
I60-2-1-3 907.53 902.23 901.81 1008.95 882.44 2.84 2.20
I60-2-1-4 979.14 967.49 975.61 1121.17 896.87 9.17 8.78
I60-2-1-5 1004.53 997.95 1004.53 1065.50 996.95 0.76 0.76
I60-2-1-6 1061.43 1051.96 1056.81 1093.90 1043.88 1.68 1.24
I60-2-1-7 1005.16 981.49 950.37 1110.89 944.32 6.44 0.64
I60-2-1-8 882.39 854.26 854.36 965.17 818.94 7.75 4.33
I60-2-1-9 890.19 877.62 870.52 1028.26 865.24 2.88 0.61
Avg 4.09 2.65
O60-2-1-0 713.15 746.03 703.50 758.65 652.35 9.32 3.73
O60-2-1-1 820.25 872.50 782.50 820.53 746.22 9.92 0.55
O60-2-1-2 782.26 799.70 761.74 868.31 732.49 6.79 0.15
O60-2-1-3 847.18 875.98 820.05 853.67 787.76 7.54 0.52
O60-2-1-4 776.48 845.20 771.15 817.65 727.32 6.76 0.64
O60-2-1-5 820.66 851.19 763.93 844.07 752.74 9.02 0.40
O60-2-1-6 708.48 714.50 680.46 680.46 680.46 4.12 0.00
O60-2-1-7 816.27 830.39 781.70 811.56 752.96 8.41 1.16
O60-2-1-8 723.94 759.78 715.02 806.47 695.58 4.08 0.00
O60-2-1-9 783.28 871.56 747.26 771.70 723.61 8.25 0.18
Avg 7.42 0.73
A60-2-1-0 858.31 858.31 836.63 929.83 836.54 2.60 0.01
A60-2-1-1 956.96 1024.04 952.71 1049.60 911.33 5.01 4.54
A60-2-1-2 719.41 741.14 776.51 778.37 703.79 2.22 10.33
A60-2-1-3 849.45 928.96 802.22 912.04 781.73 8.66 2.62
A60-2-1-4 857.32 880.81 841.54 899.44 793.69 8.02 6.03
A60-2-1-5 808.57 830.08 761.17 803.11 740.28 9.22 2.82
A60-2-1-6 803.29 862.81 803.29 871.89 754.71 6.44 6.44
A60-2-1-7 853.23 853.23 802.72 905.31 780.28 9.35 2.88
A60-2-1-8 780.61 815.35 772.43 843.73 751.38 3.89 2.80
A60-2-1-9 763.12 795.25 762.09 825.88 705.99 8.09 7.95
Avg 6.35 4.64
Table 17.  Meta-heuristics results for instances with 100 requests
Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I100-2-1-0 1638.35 1704.61 1609.09 1890.61 1500.16 9.21 7.26
I100-2-1-1 1475.76 1550.51 1462.03 1720.88 1399.61 5.44 4.46
I100-2-1-2 1549.56 1714.37 1519.43 1792.65 1481.37 4.60 2.57
I100-2-1-3 1541.71 1630.81 1516.8 1799.58 1406.15 9.64 7.87
I100-2-1-4 1586.41 1607.53 1501.97 1774.75 1471.77 7.79 2.05
I100-2-1-5 1547.53 1591.87 1476.42 1763.20 1465.71 5.58 0.73
I100-2-1-6 1594.07 1622.95 1501.05 1791.06 1482.92 7.50 1.22
I100-2-1-7 1568.12 1653.99 1508.18 1741.59 1439.77 8.91 4.75
I100-2-1-8 1340.87 1424.62 1358.42 1513.15 1277.58 4.95 6.33
I100-2-1-9 1393.89 1430.99 1346.03 1604.42 1286.29 8.37 4.64
Avg 7.20 4.19
O100-2-1-0 1279.18 1347.70 1252.87 1352.97 1215.92 5.20 3.04
O100-2-1-1 1169.86 1255.83 1149.36 1236.94 1113.13 5.10 3.25
O100-2-1-2 1123.63 1191.98 1098.08 1156.11 1066.12 5.39 3.00
O100-2-1-3 1272.18 1320.34 1209.93 1297.75 1166.47 9.06 3.73
O100-2-1-4 1278.7 1376.42 1206.94 1273.12 1146.62 11.52 5.26
O100-2-1-5 1282.2 1310.21 1264.78 1444.76 1223.53 4.80 3.37
O100-2-1-6 1112.92 1195.06 1099.75 1266.59 1062.43 4.75 3.51
O100-2-1-7 1271.97 1338.24 1231.68 1310.19 1224.31 3.89 0.60
O100-2-1-8 1071.1 1141.54 1000.51 1190.17 971.56 10.25 2.98
O100-2-1-9 1163.25 1211.45 1197.58 1339.77 1098.25 5.92 9.04
Avg 6.59 3.78
A100-2-1-0 1280.19 1361.66 1265.52 1359.89 1212.68 5.57 4.36
A100-2-1-1 1362.77 1431.84 1362.04 1541.04 1271.73 7.16 7.10
A100-2-1-2 1183.91 1240.90 1159.67 1326.68 1129.63 4.81 2.66
A100-2-1-3 1214.65 1288.61 1198.17 1355.01 1162.85 2.73 3.04
A100-2-1-4 1236.76 1325.19 1243.54 1400.64 1190.23 3.91 4.48
A100-2-1-5 1177.71 1241.31 1144.83 1228.66 1093.48 7.70 4.70
A100-2-1-6 1270.56 1328.54 1256.54 1336.74 1208.76 5.11 3.95
A100-2-1-7 1227.98 1308.64 1221.57 1316.30 1174.24 4.58 4.03
A100-2-1-8 1210.54 1298.73 1192.27 1288.85 1154.51 3.99 3.27
A100-2-1-9 1271.11 1320.95 1253.95 1419.94 1217.18 4.43 3.02
Avg 5.00 4.06
Table Options

Download as excel

Instance GRASP ILS GRASP-ILS
Zmin Zavg Zmin Zavg Zmin ImpGRASP-ILS, GRASP ImpGRASP-ILS, ILS
I100-2-1-0 1638.35 1704.61 1609.09 1890.61 1500.16 9.21 7.26
I100-2-1-1 1475.76 1550.51 1462.03 1720.88 1399.61 5.44 4.46
I100-2-1-2 1549.56 1714.37 1519.43 1792.65 1481.37 4.60 2.57
I100-2-1-3 1541.71 1630.81 1516.8 1799.58 1406.15 9.64 7.87
I100-2-1-4 1586.41 1607.53 1501.97 1774.75 1471.77 7.79 2.05
I100-2-1-5 1547.53 1591.87 1476.42 1763.20 1465.71 5.58 0.73
I100-2-1-6 1594.07 1622.95 1501.05 1791.06 1482.92 7.50 1.22
I100-2-1-7 1568.12 1653.99 1508.18 1741.59 1439.77 8.91 4.75
I100-2-1-8 1340.87 1424.62 1358.42 1513.15 1277.58 4.95 6.33
I100-2-1-9 1393.89 1430.99 1346.03 1604.42 1286.29 8.37 4.64
Avg 7.20 4.19
O100-2-1-0 1279.18 1347.70 1252.87 1352.97 1215.92 5.20 3.04
O100-2-1-1 1169.86 1255.83 1149.36 1236.94 1113.13 5.10 3.25
O100-2-1-2 1123.63 1191.98 1098.08 1156.11 1066.12 5.39 3.00
O100-2-1-3 1272.18 1320.34 1209.93 1297.75 1166.47 9.06 3.73
O100-2-1-4 1278.7 1376.42 1206.94 1273.12 1146.62 11.52 5.26
O100-2-1-5 1282.2 1310.21 1264.78 1444.76 1223.53 4.80 3.37
O100-2-1-6 1112.92 1195.06 1099.75 1266.59 1062.43 4.75 3.51
O100-2-1-7 1271.97 1338.24 1231.68 1310.19 1224.31 3.89 0.60
O100-2-1-8 1071.1 1141.54 1000.51 1190.17 971.56 10.25 2.98
O100-2-1-9 1163.25 1211.45 1197.58 1339.77 1098.25 5.92 9.04
Avg 6.59 3.78
A100-2-1-0 1280.19 1361.66 1265.52 1359.89 1212.68 5.57 4.36
A100-2-1-1 1362.77 1431.84 1362.04 1541.04 1271.73 7.16 7.10
A100-2-1-2 1183.91 1240.90 1159.67 1326.68 1129.63 4.81 2.66
A100-2-1-3 1214.65 1288.61 1198.17 1355.01 1162.85 2.73 3.04
A100-2-1-4 1236.76 1325.19 1243.54 1400.64 1190.23 3.91 4.48
A100-2-1-5 1177.71 1241.31 1144.83 1228.66 1093.48 7.70 4.70
A100-2-1-6 1270.56 1328.54 1256.54 1336.74 1208.76 5.11 3.95
A100-2-1-7 1227.98 1308.64 1221.57 1316.30 1174.24 4.58 4.03
A100-2-1-8 1210.54 1298.73 1192.27 1288.85 1154.51 3.99 3.27
A100-2-1-9 1271.11 1320.95 1253.95 1419.94 1217.18 4.43 3.02
Avg 5.00 4.06
Table 18.  Cost savings for instances with 20 requests
Instance Non-collaboration Collaboration
Cost NV Cost NV $\phi$
I20-2-1-0 528.74 5 459.26 3 13.14
I20-2-1-1 477.54 4 366.66 2 23.22
I20-2-1-2 612.48 4 478.19 3 21.93
I20-2-1-3 481.75 4 360.24 2 25.22
I20-2-1-4 491.83 4 383.24 2 22.08
I20-2-1-5 427.16 4 343.7 2 19.54
I20-2-1-6 453.01 5 344.51 2 23.95
I20-2-1-7 476.59 4 354.59 2 25.60
I20-2-1-8 484.62 4 351.37 2 27.50
I20-2-1-9 622.55 5 476.32 3 23.49
Avg 4.3 2.3 22.57
O20-2-1-0 283.63 4 240.46 2 15.22
O20-2-1-1 299.27 4 260.84 2 12.84
O20-2-1-2 336.31 4 250.62 2 25.48
O20-2-1-3 316.26 4 254.79 2 19.44
O20-2-1-4 329.42 5 273.79 2 16.89
O20-2-1-5 323.26 4 269.61 2 16.60
O20-2-1-6 293.28 4 260.31 2 11.24
O20-2-1-7 348.76 4 245.95 2 29.48
O20-2-1-8 296.46 4 240.28 2 18.95
O20-2-1-9 263.93 4 229.92 2 12.89
Avg 4.1 2 17.90
A20-2-1-0 403.54 4 362.31 2 10.22
A20-2-1-1 494.62 4 444.8 3 10.07
A20-2-1-2 383.46 5 329.67 2 14.03
A20-2-1-3 410.31 5 363.62 2 11.38
A20-2-1-4 386.48 4 343.77 2 11.05
A20-2-1-5 302.36 4 287.74 2 4.83
A20-2-1-6 371.57 4 338.23 2 8.97
A20-2-1-7 333.01 4 290.21 2 12.85
A20-2-1-8 358.15 4 314.2 2 12.27
A20-2-1-9 367.36 4 323.6 2 11.91
Avg 4.2 10.76
Table Options

Download as excel

Instance Non-collaboration Collaboration
Cost NV Cost NV $\phi$
I20-2-1-0 528.74 5 459.26 3 13.14
I20-2-1-1 477.54 4 366.66 2 23.22
I20-2-1-2 612.48 4 478.19 3 21.93
I20-2-1-3 481.75 4 360.24 2 25.22
I20-2-1-4 491.83 4 383.24 2 22.08
I20-2-1-5 427.16 4 343.7 2 19.54
I20-2-1-6 453.01 5 344.51 2 23.95
I20-2-1-7 476.59 4 354.59 2 25.60
I20-2-1-8 484.62 4 351.37 2 27.50
I20-2-1-9 622.55 5 476.32 3 23.49
Avg 4.3 2.3 22.57
O20-2-1-0 283.63 4 240.46 2 15.22
O20-2-1-1 299.27 4 260.84 2 12.84
O20-2-1-2 336.31 4 250.62 2 25.48
O20-2-1-3 316.26 4 254.79 2 19.44
O20-2-1-4 329.42 5 273.79 2 16.89
O20-2-1-5 323.26 4 269.61 2 16.60
O20-2-1-6 293.28 4 260.31 2 11.24
O20-2-1-7 348.76 4 245.95 2 29.48
O20-2-1-8 296.46 4 240.28 2 18.95
O20-2-1-9 263.93 4 229.92 2 12.89
Avg 4.1 2 17.90
A20-2-1-0 403.54 4 362.31 2 10.22
A20-2-1-1 494.62 4 444.8 3 10.07
A20-2-1-2 383.46 5 329.67 2 14.03
A20-2-1-3 410.31 5 363.62 2 11.38
A20-2-1-4 386.48 4 343.77 2 11.05
A20-2-1-5 302.36 4 287.74 2 4.83
A20-2-1-6 371.57 4 338.23 2 8.97
A20-2-1-7 333.01 4 290.21 2 12.85
A20-2-1-8 358.15 4 314.2 2 12.27
A20-2-1-9 367.36 4 323.6 2 11.91
Avg 4.2 10.76
Table 19.  Cost savings for instances with 40 requests
Instance Non- collaboration Collaboration
Cost NV Cost NV $\phi$
I40-2-1-0 1021.39 8 706.64 6 30.82
I40-2-1-1 861.87 8 600.90 6 30.28
I40-2-1-2 1006.32 8 729.24 6 27.53
I40-2-1-3 943.17 8 651.55 6 30.92
I40-2-1-4 1062.08 8 699.59 6 34.13
I40-2-1-5 930.23 8 647.36 6 30.41
I40-2-1-6 874.73 8 590.24 6 32.52
I40-2-1-7 910.38 8 612.68 6 32.70
I40-2-1-8 841.23 8 573.59 6 31.82
I40-2-1-9 843.80 8 598.44 6 29.08
Avg 8 6 31.02
O40-2-1-0 650.32 7 494.73 3 23.93
O40-2-1-1 574.51 7 434.04 3 24.45
O40-2-1-2 578.02 7 445.80 3 22.87
O40-2-1-3 692.40 8 523.35 4 24.42
O40-2-1-4 749.51 7 549.35 4 26.71
O40-2-1-5 750.72 8 573.11 4 23.66
O40-2-1-6 636.65 7 492.06 4 22.71
O40-2-1-7 734.12 7 528.80 3 27.97
O40-2-1-8 553.40 7 427.55 3 22.74
O40-2-1-9 746.28 8 578.85 4 22.43
Avg 7.3 3.5 24.19
A40-2-1-0 686.52 8 550.2 4 19.86
A40-2-1-1 730.78 7 597.17 4 18.28
A40-2-1-2 708.31 8 582.03 4 17.83
A40-2-1-3 662.45 8 505.21 4 23.74
A40-2-1-4 667.54 8 567.77 4 14.95
A40-2-1-5 714.79 7 617.34 4 13.63
A40-2-1-6 610.43 7 537.91 3 11.88
A40-2-1-7 639.30 7 542.06 4 15.21
A40-2-1-8 695.09 7 600.61 4 13.59
A40-2-1-9 739.69 8 632.33 4 14.51
Avg 7.5 3.9 16.35
Table Options

Download as excel

Instance Non- collaboration Collaboration
Cost NV Cost NV $\phi$
I40-2-1-0 1021.39 8 706.64 6 30.82
I40-2-1-1 861.87 8 600.90 6 30.28
I40-2-1-2 1006.32 8 729.24 6 27.53
I40-2-1-3 943.17 8 651.55 6 30.92
I40-2-1-4 1062.08 8 699.59 6 34.13
I40-2-1-5 930.23 8 647.36 6 30.41
I40-2-1-6 874.73 8 590.24 6 32.52
I40-2-1-7 910.38 8 612.68 6 32.70
I40-2-1-8 841.23 8 573.59 6 31.82
I40-2-1-9 843.80 8 598.44 6 29.08
Avg 8 6 31.02
O40-2-1-0 650.32 7 494.73 3 23.93
O40-2-1-1 574.51 7 434.04 3 24.45
O40-2-1-2 578.02 7 445.80 3 22.87
O40-2-1-3 692.40 8 523.35 4 24.42
O40-2-1-4 749.51 7 549.35 4 26.71
O40-2-1-5 750.72 8 573.11 4 23.66
O40-2-1-6 636.65 7 492.06 4 22.71
O40-2-1-7 734.12 7 528.80 3 27.97
O40-2-1-8 553.40 7 427.55 3 22.74
O40-2-1-9 746.28 8 578.85 4 22.43
Avg 7.3 3.5 24.19
A40-2-1-0 686.52 8 550.2 4 19.86
A40-2-1-1 730.78 7 597.17 4 18.28
A40-2-1-2 708.31 8 582.03 4 17.83
A40-2-1-3 662.45 8 505.21 4 23.74
A40-2-1-4 667.54 8 567.77 4 14.95
A40-2-1-5 714.79 7 617.34 4 13.63
A40-2-1-6 610.43 7 537.91 3 11.88
A40-2-1-7 639.30 7 542.06 4 15.21
A40-2-1-8 695.09 7 600.61 4 13.59
A40-2-1-9 739.69 8 632.33 4 14.51
Avg 7.5 3.9 16.35
Table 20.  Cost savings for instances with 60 requests
Instance Non- collaboration Collaboration
Cost NV Cost NV $\phi$
I60-2-1-0 1405.67 11 911.77 6 35.14
I60-2-1-1 1466.10 10 987.76 7 32.63
I60-2-1-2 1326.57 12 877.23 6 33.87
I60-2-1-3 1381.98 12 882.44 6 36.15
I60-2-1-4 1341.28 11 896.87 5 33.13
I60-2-1-5 1438.62 11 996.95 7 30.70
I60-2-1-6 1575.24 13 1043.88 7 33.73
I60-2-1-7 1384.43 10 944.32 6 31.79
I60-2-1-8 1245.97 10 818.94 5 34.27
I60-2-1-9 1266.52 10 865.24 8 31.68
Avg 11 6.3 33.31
O60-2-1-0 920.63 8 652.35 5 29.14
O60-2-1-1 1049.04 11 742.55 4 29.22
O60-2-1-2 1092.15 11 732.49 5 32.93
O60-2-1-3 1083.86 11 787.76 5 27.32
O60-2-1-4 1031.74 11 727.32 5 29.51
O60-2-1-5 981.97 10 752.74 5 23.34
O60-2-1-6 956.39 9 680.46 5 28.85
O60-2-1-7 1052.40 11 752.96 5 28.45
O60-2-1-8 977.50 9 695.58 5 28.84
O60-2-1-9 959.39 10 723.61 5 24.58
Avg 10.1 4.9 4.9 28.22
A60-2-1-0 1133.63 11 836.54 6 26.21
A60-2-1-1 1187.66 10 911.33 6 23.27
A60-2-1-2 956.53 10 703.79 5 26.42
A60-2-1-3 969.58 10 781.73 5 19.37
A60-2-1-4 1074.74 10 793.69 5 26.15
A60-2-1-5 984.88 9 740.28 5 24.84
A60-2-1-6 999.87 10 754.71 5 24.52
A60-2-1-7 1061.10 11 780.28 5 26.46
A60-2-1-8 962.43 11 751.38 5 21.93
A60-2-1-9 941.98 9 705.99 5 25.05
Avg 10.1 5.2 5.2 24.42
Table Options

Download as excel

Instance Non- collaboration Collaboration
Cost NV Cost NV $\phi$
I60-2-1-0 1405.67 11 911.77 6 35.14
I60-2-1-1 1466.10 10 987.76 7 32.63
I60-2-1-2 1326.57 12 877.23 6 33.87
I60-2-1-3 1381.98 12 882.44 6 36.15
I60-2-1-4 1341.28 11 896.87 5 33.13
I60-2-1-5 1438.62 11 996.95 7 30.70
I60-2-1-6 1575.24 13 1043.88 7 33.73
I60-2-1-7 1384.43 10 944.32 6 31.79
I60-2-1-8 1245.97 10 818.94 5 34.27
I60-2-1-9 1266.52 10 865.24 8 31.68
Avg 11 6.3 33.31
O60-2-1-0 920.63 8 652.35 5 29.14
O60-2-1-1 1049.04 11 742.55 4 29.22
O60-2-1-2 1092.15 11 732.49 5 32.93
O60-2-1-3 1083.86 11 787.76 5 27.32
O60-2-1-4 1031.74 11 727.32 5 29.51
O60-2-1-5 981.97 10 752.74 5 23.34
O60-2-1-6 956.39 9 680.46 5 28.85
O60-2-1-7 1052.40 11 752.96 5 28.45
O60-2-1-8 977.50 9 695.58 5 28.84
O60-2-1-9 959.39 10 723.61 5 24.58
Avg 10.1 4.9 4.9 28.22
A60-2-1-0 1133.63 11 836.54 6 26.21
A60-2-1-1 1187.66 10 911.33 6 23.27
A60-2-1-2 956.53 10 703.79 5 26.42
A60-2-1-3 969.58 10 781.73 5 19.37
A60-2-1-4 1074.74 10 793.69 5 26.15
A60-2-1-5 984.88 9 740.28 5 24.84
A60-2-1-6 999.87 10 754.71 5 24.52
A60-2-1-7 1061.10 11 780.28 5 26.46
A60-2-1-8 962.43 11 751.38 5 21.93
A60-2-1-9 941.98 9 705.99 5 25.05
Avg 10.1 5.2 5.2 24.42
Table 21.  Cost savings for instances with 100 requests
Instance Non- collaboration Collaboration
Cost NV Cost NV $\phi$
I100-2-1-0 2741.02 20 1500.16 10 45.27
I100-2-1-1 2308.06 17 1399.61 10 39.36
I100-2-1-2 2634.95 19 1481.37 10 43.78
I100-2-1-3 2517.73 18 1406.15 10 44.15
I100-2-1-4 2275.46 17 1471.77 9 35.32
I100-2-1-5 2393.39 17 1465.71 10 38.76
I100-2-1-6 2635.37 19 1482.92 10 43.73
I100-2-1-7 2628.76 19 1439.77 10 45.23
I100-2-1-8 1910.26 15 1277.58 9 33.12
I100-2-1-9 2337.01 17 1286.29 10 44.96
Avg 17.8 9.8 41.37
O100-2-1-0 1791.81 15 1215.92 9 32.14
O100-2-1-1 1692.20 14 1113.13 8 34.22
O100-2-1-2 1690.38 14 1066.12 8 36.93
O100-2-1-3 1803.45 15 1166.47 9 35.32
O100-2-1-4 1641.55 14 1146.62 9 30.15
O100-2-1-5 1924.70 15 1223.53 9 36.43
O100-2-1-6 1606.09 14 1062.43 8 33.85
O100-2-1-7 1786.01 14 1224.31 9 31.45
O100-2-1-8 1538.25 13 971.56 7 36.84
O100-2-1-9 1582.04 13 1098.25 8 30.58
Avg 14.1 8.4 33.79
A100-2-1-0 1760.57 14 1212.68 9 31.12
A100-2-1-1 1809.52 15 1271.73 9 29.72
A100-2-1-2 1717.81 14 1129.63 8 34.24
A100-2-1-3 1497.94 10 1162.85 8 22.37
A100-2-1-4 1611.69 14 1190.23 9 26.15
A100-2-1-5 1613.52 14 1093.48 8 32.23
A100-2-1-6 1895.50 15 1208.76 9 36.23
A100-2-1-7 1764.98 14 1174.24 8 33.47
A100-2-1-8 1764.23 14 1154.51 9 34.56
A100-2-1-9 1727.48 14 1217.18 10 29.54
Avg 13.8 8.7 30.96
Table Options

Download as excel

Instance Non- collaboration Collaboration
Cost NV Cost NV $\phi$
I100-2-1-0 2741.02 20 1500.16 10 45.27
I100-2-1-1 2308.06 17 1399.61 10 39.36
I100-2-1-2 2634.95 19 1481.37 10 43.78
I100-2-1-3 2517.73 18 1406.15 10 44.15
I100-2-1-4 2275.46 17 1471.77 9 35.32
I100-2-1-5 2393.39 17 1465.71 10 38.76
I100-2-1-6 2635.37 19 1482.92 10 43.73
I100-2-1-7 2628.76 19 1439.77 10 45.23
I100-2-1-8 1910.26 15 1277.58 9 33.12
I100-2-1-9 2337.01 17 1286.29 10 44.96
Avg 17.8 9.8 41.37
O100-2-1-0 1791.81 15 1215.92 9 32.14
O100-2-1-1 1692.20 14 1113.13 8 34.22
O100-2-1-2 1690.38 14 1066.12 8 36.93
O100-2-1-3 1803.45 15 1166.47 9 35.32
O100-2-1-4 1641.55 14 1146.62 9 30.15
O100-2-1-5 1924.70 15 1223.53 9 36.43
O100-2-1-6 1606.09 14 1062.43 8 33.85
O100-2-1-7 1786.01 14 1224.31 9 31.45
O100-2-1-8 1538.25 13 971.56 7 36.84
O100-2-1-9 1582.04 13 1098.25 8 30.58
Avg 14.1 8.4 33.79
A100-2-1-0 1760.57 14 1212.68 9 31.12
A100-2-1-1 1809.52 15 1271.73 9 29.72
A100-2-1-2 1717.81 14 1129.63 8 34.24
A100-2-1-3 1497.94 10 1162.85 8 22.37
A100-2-1-4 1611.69 14 1190.23 9 26.15
A100-2-1-5 1613.52 14 1093.48 8 32.23
A100-2-1-6 1895.50 15 1208.76 9 36.23
A100-2-1-7 1764.98 14 1174.24 8 33.47
A100-2-1-8 1764.23 14 1154.51 9 34.56
A100-2-1-9 1727.48 14 1217.18 10 29.54
Avg 13.8 8.7 30.96
Table 4.  Notations of performance indicators and their description
Notations Description
UB The best cost obtained by CPLEX solver in a preset running time.
LB The lower bound obtained by CPLEX solver in a preset running time
Ini The cost of the best initial solution obtained by GRASP-ILS
Zmin The best cost of 10 runs for each meta-heuristic
Zavg The average cost of 10 runs for each meta-heuristic
Dev The standard deviation of the costs obtained in ten runs by each meta-heuristic.
$Imp_{Ini}$ The improvement of best cost over Ini.
For CPLEX solver $Imp_{Ini}$ is calculated by ${{(UB - Ini)} / {UB}}*100\%$
For meta-heuristics, $Imp_{Ini}$ is calculated by$ {{({z_{min}} - Ini)} /{{z_{min}}}}*100\%$
$Gap_{LB}$ The percentage gap between the best cost and LB.
For CPLEX solver, $Gap_{LB}$ is calculated by $Gap_{LB} = {{(UB - Ini)} /{UB}}*100\%$
For meta-heuristics, $Gap_{LB}$ is calculated by$ {{({z_{min}} - LB)} /{{z_{min}}}}*100\%$
$Imp_{Cplex}$ The improvement of the best cost obtained by meta-heuristics over the best cost
obtained by CPLEX solver.$Imp_{Cplex}$ is calculated as:${{(UB - {z_{min}})} /{UB}}*100\%$
$Imp_{GRASP-ILS,GRASP}$ The improvement of over. It is calculated as:
${{({Z_{min,GRASP}} - {z_{min,GRASP - ILS}})} / {{z_{min,GRASP - ILS}}}}*100\%$
$Imp_{GRASP-ILS,ILS}$ The improvement of over. It is calculated as:
${{({Z_{min,ILS}} - {z_{min,GRASP - ILS}})} / {{z_{min,GRASP - ILS}}}}*100\%$
NV The average total number of vehicles used in the transportation
$Cost_{N}$ The total transportation cost of the shippers without collaboration obtained by CPLEX solver.
$Cost_{C}$ The total transportation cost of the shippers with collaboration, which is the best objective value of CPLEX solver and GRASP-ILS.
$\phi$ The cost savings in percentage achieved by the collaboration among the shippers. is defined as: ${{({Cost_N} - {Cost_C})} /{{Cost_N}}}*100\%$
$CPU_{avg}$ The average execution time in seconds for meta-heuristics
Table Options

Download as excel

Notations Description
UB The best cost obtained by CPLEX solver in a preset running time.
LB The lower bound obtained by CPLEX solver in a preset running time
Ini The cost of the best initial solution obtained by GRASP-ILS
Zmin The best cost of 10 runs for each meta-heuristic
Zavg The average cost of 10 runs for each meta-heuristic
Dev The standard deviation of the costs obtained in ten runs by each meta-heuristic.
$Imp_{Ini}$ The improvement of best cost over Ini.
For CPLEX solver $Imp_{Ini}$ is calculated by ${{(UB - Ini)} / {UB}}*100\%$
For meta-heuristics, $Imp_{Ini}$ is calculated by$ {{({z_{min}} - Ini)} /{{z_{min}}}}*100\%$
$Gap_{LB}$ The percentage gap between the best cost and LB.
For CPLEX solver, $Gap_{LB}$ is calculated by $Gap_{LB} = {{(UB - Ini)} /{UB}}*100\%$
For meta-heuristics, $Gap_{LB}$ is calculated by$ {{({z_{min}} - LB)} /{{z_{min}}}}*100\%$
$Imp_{Cplex}$ The improvement of the best cost obtained by meta-heuristics over the best cost
obtained by CPLEX solver.$Imp_{Cplex}$ is calculated as:${{(UB - {z_{min}})} /{UB}}*100\%$
$Imp_{GRASP-ILS,GRASP}$ The improvement of over. It is calculated as:
${{({Z_{min,GRASP}} - {z_{min,GRASP - ILS}})} / {{z_{min,GRASP - ILS}}}}*100\%$
$Imp_{GRASP-ILS,ILS}$ The improvement of over. It is calculated as:
${{({Z_{min,ILS}} - {z_{min,GRASP - ILS}})} / {{z_{min,GRASP - ILS}}}}*100\%$
NV The average total number of vehicles used in the transportation
$Cost_{N}$ The total transportation cost of the shippers without collaboration obtained by CPLEX solver.
$Cost_{C}$ The total transportation cost of the shippers with collaboration, which is the best objective value of CPLEX solver and GRASP-ILS.
$\phi$ The cost savings in percentage achieved by the collaboration among the shippers. is defined as: ${{({Cost_N} - {Cost_C})} /{{Cost_N}}}*100\%$
$CPU_{avg}$ The average execution time in seconds for meta-heuristics

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (284)
  • HTML views (1160)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences