Figure 1.
The main steps of the TS-heuristics and SA-heuristics
-
Previous Article
Three-dimensional computer simulation of twill woven fabric by using polynomial mathematical model
- DCDS-S Home
- This Issue
-
Next Article
Efficient systolic multiplications in composite fields for cryptographic systems
August & September
2019, 12(4&5): 1147-1166.
doi: 10.3934/dcdss.2019079
The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads
School of Business Administration, Jiangxi University of Finance and Economics, Nanchang 30013, China |
- Abstract
- Full Text(HTML)
- Figure(1) / Table(7)
- Related Papers
Under a Creative Commons license
This paper addresses a new variant of the location routing problem (LRP), namely the heterogeneous fleet LRP with simultaneous pickup and delivery and overloads (HFLRPSPDO) which has not been previously tackled in literatures. In this problem, the heterogeneous fleet is comprised of vehicles with different capacities, and the vehicle overloads up to a specified upper bound is allowed. This paper proposes a polynomial-size mixed integer linear programming formulation for the problem in which a penalty function, allowing capacity violations of vehicles, is integrated into objective function. Furthermore, two heuristic algorithms, respectively based on tabu search and simulated annealing, are proposed to solve HFLRPSPDO. Computational results on simulated instances show the effectiveness of the proposed problem formulation and the efficiency of the proposed heuristic algorithms.
Keywords:
Heterogeneous fleet,
location-routing problem,
simultaneous pickup and delivery,
overloads.
Mathematics Subject Classification:
68U99.
Citation:
Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete and Continuous Dynamical Systems - S,
2019, 12
(4&5)
: 1147-1166.
doi: 10.3934/dcdss.2019079
![]()
References:
| [1] |
D. Ambrosinoa,
Distribution network design: New problems and related models, European Journal of Operational Research, 165 (2005), 610-624.
doi: 10.1016/j.ejor.2003.04.009. |
| [2] |
R. T. Berger, C. R. Coullard and M. S. Daskin,
Location-routing problems with distance constraints, Transportation Science, 41 (2007), 29-43.
|
| [3] |
T. W. Chien,
Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems, Decision Sciences, 24 (1993), 995-1021.
|
| [4] |
C. H. Chu and J. Hopscotch,
Further discussion for transit system of chicago, Journal of Discrete Mathematical Sciences & Cryptography, 20 (2017), 717-724.
doi: 10.1080/09720529.2016.1197600. |
| [5] |
G. Clarke and J. W. Wright,
Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964), 568-581.
|
| [6] |
J. Dethloff,
Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR-Spektrum, 23 (2001), 79-96.
doi: 10.1007/PL00013346. |
| [7] |
J. Geunes and B. M. Chang,
Operations Research Models for Supply Chain Management and Design, vol. 76, Springer US, 1994. |
| [8] |
B. Golden, A. Assad, L. Levy and F. Gheysens,
The fleet size and mix vehicle routing problem, Computers & Operations Research, 11 (1984), 49-66.
|
| [9] |
G. Ioannou, M. Kritikos and G. Prastacos,
A greedy look-ahead heuristic for the vehicle routing problem with time windows, Journal of the Operational Research Society, 52 (2001), 523-537.
|
| [10] |
H. Kamankesh and V. G. Agelidis,
A sufficient stochastic framework for optimal operation of micro-grids considering high penetration of renewable energy sources and electric vehicles, Journal of Intelligent & Fuzzy Systems, 32 (2017), 373-387.
|
| [11] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz,
A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery, European Journal of Operational Research, 211 (2011), 318-332.
doi: 10.1016/j.ejor.2011.01.003. |
| [12] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz,
The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach, Omega, 40 (2012), 465-477.
|
| [13] |
M. N. Kritikos and G. Ioannou,
The heterogeneous fleet vehicle routing problem with overloads and time windows, International Journal of Production Economics, 144 (2013), 68-75.
|
| [14] |
G. Laporte, Y. Nobert and D. Arpin,
An exact algorithm for solving a capacitated location-routing problem, Annals of Operations Research, 6 (1986), 293-310.
|
| [15] |
G. Laporte, Y. Nobert and S. Taillefer,
Solving a family of multi-depot vehicle routing and location-routing problems, Transportation Science, 22 (1988), 161-172.
doi: 10.1287/trsc.22.3.161. |
| [16] |
C. K. Y. Lin, C. K. Chow and A. Chen,
A location-routing-loading problem for bill delivery services, Computers & Industrial Engineering, 43 (2002), 5-25.
|
| [17] |
C. K. Y. Lin and R. C. W. Kwok,
Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data, European Journal of Operational Research, 175 (2006), 1833-1849.
|
| [18] |
M. Lundy and A. Mees,
Convergence of an annealing algorithm, Mathematical Programming, 34 (1986), 111-124.
doi: 10.1007/BF01582166. |
| [19] |
H. Min,
Consolidation terminal location-allocation and consolidated routing problems, Journal of Business Logistics, 17 (1996), 235-263.
|
| [20] |
H. Min, V. Jayaraman and R. Srivastava,
Combined Location-Routing Problems: A Synthesis and Future Research Directions, vol. 108, Springer Berlin Heidelberg, 1998. |
| [21] |
G. Nagy and S. Salhi,
Location-routing: Issues, models and methods, European Journal of Operational Research, 177 (2007), 649-672.
doi: 10.1016/j.ejor.2006.04.004. |
| [22] |
G. Nagy and S. Salhi, Nested heuristic methods for the location-routing problem, 47 (1996), 1166-1174. |
| [23] |
C. Prodhon,, in http://prodhonc.free.fr/homepage, 2016. |
| [24] |
S. Salhi and M. Fraser,
An integrated heuristic approach for the combined location vehicle fleet mix problem, Studies in Locational Analysis, 8 (1996), 3-21.
|
| [25] |
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.
|
| [26] |
M. Schwardt and J. Dethloff,
Solving a continuous location-routing problem by use of a self-organizing map, International Journal of Physical Distribution & Logistics Management, 35 (2005), 390-408.
|
| [27] |
R. Srivastava,
Alternate solution procedures for the location-routing problem, Omega, 21 (1993), 497-506.
|
| [28] |
D. Tuzun and L. I. Burke,
A two-phase tabu search approach to the location routing problem, European Journal of Operational Research, 116 (1999), 87-99.
|
| [29] |
T. H. Wu, C. Low and J. W. Bai,
Heuristic solutions to multi-depot location-routing problems, Computers & Operations Research, 29 (2002), 1393-1415.
|
| [30] |
X. Zhang, Z. B. Zhang, H. Broersma and X. Wen,
On the complexity of edge-colored subgraph partitioning problems in network optimization, Discrete Mathematics & Theoretical Computer Science Dmtcs, 17 (2016), 227-244.
|
show all references
References:
| [1] |
D. Ambrosinoa,
Distribution network design: New problems and related models, European Journal of Operational Research, 165 (2005), 610-624.
doi: 10.1016/j.ejor.2003.04.009. |
| [2] |
R. T. Berger, C. R. Coullard and M. S. Daskin,
Location-routing problems with distance constraints, Transportation Science, 41 (2007), 29-43.
|
| [3] |
T. W. Chien,
Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems, Decision Sciences, 24 (1993), 995-1021.
|
| [4] |
C. H. Chu and J. Hopscotch,
Further discussion for transit system of chicago, Journal of Discrete Mathematical Sciences & Cryptography, 20 (2017), 717-724.
doi: 10.1080/09720529.2016.1197600. |
| [5] |
G. Clarke and J. W. Wright,
Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964), 568-581.
|
| [6] |
J. Dethloff,
Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR-Spektrum, 23 (2001), 79-96.
doi: 10.1007/PL00013346. |
| [7] |
J. Geunes and B. M. Chang,
Operations Research Models for Supply Chain Management and Design, vol. 76, Springer US, 1994. |
| [8] |
B. Golden, A. Assad, L. Levy and F. Gheysens,
The fleet size and mix vehicle routing problem, Computers & Operations Research, 11 (1984), 49-66.
|
| [9] |
G. Ioannou, M. Kritikos and G. Prastacos,
A greedy look-ahead heuristic for the vehicle routing problem with time windows, Journal of the Operational Research Society, 52 (2001), 523-537.
|
| [10] |
H. Kamankesh and V. G. Agelidis,
A sufficient stochastic framework for optimal operation of micro-grids considering high penetration of renewable energy sources and electric vehicles, Journal of Intelligent & Fuzzy Systems, 32 (2017), 373-387.
|
| [11] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz,
A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery, European Journal of Operational Research, 211 (2011), 318-332.
doi: 10.1016/j.ejor.2011.01.003. |
| [12] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz,
The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach, Omega, 40 (2012), 465-477.
|
| [13] |
M. N. Kritikos and G. Ioannou,
The heterogeneous fleet vehicle routing problem with overloads and time windows, International Journal of Production Economics, 144 (2013), 68-75.
|
| [14] |
G. Laporte, Y. Nobert and D. Arpin,
An exact algorithm for solving a capacitated location-routing problem, Annals of Operations Research, 6 (1986), 293-310.
|
| [15] |
G. Laporte, Y. Nobert and S. Taillefer,
Solving a family of multi-depot vehicle routing and location-routing problems, Transportation Science, 22 (1988), 161-172.
doi: 10.1287/trsc.22.3.161. |
| [16] |
C. K. Y. Lin, C. K. Chow and A. Chen,
A location-routing-loading problem for bill delivery services, Computers & Industrial Engineering, 43 (2002), 5-25.
|
| [17] |
C. K. Y. Lin and R. C. W. Kwok,
Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data, European Journal of Operational Research, 175 (2006), 1833-1849.
|
| [18] |
M. Lundy and A. Mees,
Convergence of an annealing algorithm, Mathematical Programming, 34 (1986), 111-124.
doi: 10.1007/BF01582166. |
| [19] |
H. Min,
Consolidation terminal location-allocation and consolidated routing problems, Journal of Business Logistics, 17 (1996), 235-263.
|
| [20] |
H. Min, V. Jayaraman and R. Srivastava,
Combined Location-Routing Problems: A Synthesis and Future Research Directions, vol. 108, Springer Berlin Heidelberg, 1998. |
| [21] |
G. Nagy and S. Salhi,
Location-routing: Issues, models and methods, European Journal of Operational Research, 177 (2007), 649-672.
doi: 10.1016/j.ejor.2006.04.004. |
| [22] |
G. Nagy and S. Salhi, Nested heuristic methods for the location-routing problem, 47 (1996), 1166-1174. |
| [23] |
C. Prodhon,, in http://prodhonc.free.fr/homepage, 2016. |
| [24] |
S. Salhi and M. Fraser,
An integrated heuristic approach for the combined location vehicle fleet mix problem, Studies in Locational Analysis, 8 (1996), 3-21.
|
| [25] |
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.
|
| [26] |
M. Schwardt and J. Dethloff,
Solving a continuous location-routing problem by use of a self-organizing map, International Journal of Physical Distribution & Logistics Management, 35 (2005), 390-408.
|
| [27] |
R. Srivastava,
Alternate solution procedures for the location-routing problem, Omega, 21 (1993), 497-506.
|
| [28] |
D. Tuzun and L. I. Burke,
A two-phase tabu search approach to the location routing problem, European Journal of Operational Research, 116 (1999), 87-99.
|
| [29] |
T. H. Wu, C. Low and J. W. Bai,
Heuristic solutions to multi-depot location-routing problems, Computers & Operations Research, 29 (2002), 1393-1415.
|
| [30] |
X. Zhang, Z. B. Zhang, H. Broersma and X. Wen,
On the complexity of edge-colored subgraph partitioning problems in network optimization, Discrete Mathematics & Theoretical Computer Science Dmtcs, 17 (2016), 227-244.
|
Table 1.
Problem cost parameters for simulated instances
| Parameter | Value | |
| Depot | Capacity ( |
Uniformly distributed over the interval [200,400] |
| Fixed cost ( |
3000 unit per depot | |
| Vehicle | Type | Type A, B, C for customers. |
| Fixed cost ( |
Cost (100,150,200) for type (A, B, C), respectively. | |
| Capacity ( |
Cost (100,200,300) for type (A, B, C), respectively | |
| Distance cost ratio | Unit cost distance (1, 1.5, 2) for type (A, B, C), respectively |
| Parameter | Value | |
| Depot | Capacity ( |
Uniformly distributed over the interval [200,400] |
| Fixed cost ( |
3000 unit per depot | |
| Vehicle | Type | Type A, B, C for customers. |
| Fixed cost ( |
Cost (100,150,200) for type (A, B, C), respectively. | |
| Capacity ( |
Cost (100,200,300) for type (A, B, C), respectively | |
| Distance cost ratio | Unit cost distance (1, 1.5, 2) for type (A, B, C), respectively |
Table 2.
Parameter settings of TS-heuristics and SA-heuristics
| TS-heuristics | SA -heuristics | |||
| Parameter | Value | Parameter | Value | |
| max-add | 5 | initial temperature (location and routing phases) | 50 | |
| max-swap | 8 | cooling rate (location phase) | 0.95 | |
| max-route | 6 | cooling rate (routing phase) | 0.9 | |
| tabu duration (location phase) |
8 | final temperature (location and routing phase) | 0.15 | |
| tabu duration (routing phase) |
10 | no-improvement number of cycles (location and routing phases) | 10 | |
| TS-heuristics | SA -heuristics | |||
| Parameter | Value | Parameter | Value | |
| max-add | 5 | initial temperature (location and routing phases) | 50 | |
| max-swap | 8 | cooling rate (location phase) | 0.95 | |
| max-route | 6 | cooling rate (routing phase) | 0.9 | |
| tabu duration (location phase) |
8 | final temperature (location and routing phase) | 0.15 | |
| tabu duration (routing phase) |
10 | no-improvement number of cycles (location and routing phases) | 10 | |
Table 3.
Computational results for the formulations on small-size test problems
| Original formulation | Strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 45.82 | 86.29 | 10 | 5.04 | 48.02 | 10 | |
| 20 | 3 | 36.02 | 1973.64 | 8 | 1.47 | 2074.65 | 9 | |
| 20 | 4 | 51.80 | 2391.82 | 6 | 0.85 | 2619.46 | 7 | |
| 30 | 4 | 26.39 | 3729.65 | 5 | 13.23 | 3482.73 | 6 | |
| 40 | 4 | 38.74 | 5183.59 | 5 | 15.78 | 5827.84 | 5 | |
| 30 | 5 | 33.90 | 4734.64 | 4 | 21.92 | 5418.38 | 5 | |
| 40 | 5 | 46.29 | 5374.68 | 2 | 3.63 | 6016.73 | 3 | |
| 50 | 5 | 34.62 | 6739.52 | 2 | 8.51 | 6473.63 | 3 | |
| 40 | 6 | 29.43 | 7200.00 | 0 | 2.58 | 7200.00 | 0 | |
| 50 | 6 | 37.58 | 7200.00 | 0 | 16.28 | 7200.00 | 0 | |
| Average | 38.06 | 5279.52 | 8.93 | 4636.14 | ||||
| Original formulation | Strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 45.82 | 86.29 | 10 | 5.04 | 48.02 | 10 | |
| 20 | 3 | 36.02 | 1973.64 | 8 | 1.47 | 2074.65 | 9 | |
| 20 | 4 | 51.80 | 2391.82 | 6 | 0.85 | 2619.46 | 7 | |
| 30 | 4 | 26.39 | 3729.65 | 5 | 13.23 | 3482.73 | 6 | |
| 40 | 4 | 38.74 | 5183.59 | 5 | 15.78 | 5827.84 | 5 | |
| 30 | 5 | 33.90 | 4734.64 | 4 | 21.92 | 5418.38 | 5 | |
| 40 | 5 | 46.29 | 5374.68 | 2 | 3.63 | 6016.73 | 3 | |
| 50 | 5 | 34.62 | 6739.52 | 2 | 8.51 | 6473.63 | 3 | |
| 40 | 6 | 29.43 | 7200.00 | 0 | 2.58 | 7200.00 | 0 | |
| 50 | 6 | 37.58 | 7200.00 | 0 | 16.28 | 7200.00 | 0 | |
| Average | 38.06 | 5279.52 | 8.93 | 4636.14 | ||||
Table 4.
Computational results for relaxations of the formulations
| LP of original formulation | LP of strong formulation | SLP of strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | ||||
| 15 | 3 | 45.82 | 0.03 | 18.63 | 0.02 | 4.75 | 0.43 | ||
| 20 | 3 | 36.02 | 1.84 | 1.76 | 1.59 | 2.04 | 15.71 | ||
| 20 | 4 | 51.80 | 2.53 | 1.09 | 2.37 | 1.84 | 1.68 | ||
| 30 | 4 | 26.39 | 6.85 | 16.39 | 5.89 | 4.73 | 184.93 | ||
| 40 | 4 | 38.74 | 6.52 | 2.54 | 7.41 | 5.91 | 347.55 | ||
| 30 | 5 | 33.90 | 12.48 | 11.64 | 11.91 | 2.43 | 194.69 | ||
| 40 | 5 | 46.29 | 11.53 | 10.83 | 10.53 | 3.74 | 842.68 | ||
| 50 | 5 | 34.62 | 14.83 | 18.46 | 13.96 | 6.47 | 1043.79 | ||
| 40 | 6 | 29.43 | 17.35 | 13.58 | 15.37 | 10.25 | 357.73 | ||
| 50 | 6 | 37.58 | 28.59 | 17.36 | 22.54 | 12.54 | 1074.51 | ||
| Average | 38.06 | 10.26 | 11.23 | 13.13 | 5.47 | 406.37 | |||
| LP of original formulation | LP of strong formulation | SLP of strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | ||||
| 15 | 3 | 45.82 | 0.03 | 18.63 | 0.02 | 4.75 | 0.43 | ||
| 20 | 3 | 36.02 | 1.84 | 1.76 | 1.59 | 2.04 | 15.71 | ||
| 20 | 4 | 51.80 | 2.53 | 1.09 | 2.37 | 1.84 | 1.68 | ||
| 30 | 4 | 26.39 | 6.85 | 16.39 | 5.89 | 4.73 | 184.93 | ||
| 40 | 4 | 38.74 | 6.52 | 2.54 | 7.41 | 5.91 | 347.55 | ||
| 30 | 5 | 33.90 | 12.48 | 11.64 | 11.91 | 2.43 | 194.69 | ||
| 40 | 5 | 46.29 | 11.53 | 10.83 | 10.53 | 3.74 | 842.68 | ||
| 50 | 5 | 34.62 | 14.83 | 18.46 | 13.96 | 6.47 | 1043.79 | ||
| 40 | 6 | 29.43 | 17.35 | 13.58 | 15.37 | 10.25 | 357.73 | ||
| 50 | 6 | 37.58 | 28.59 | 17.36 | 22.54 | 12.54 | 1074.51 | ||
| Average | 38.06 | 10.26 | 11.23 | 13.13 | 5.47 | 406.37 | |||
Table 5.
Perform comparison of HFLRPSPDO on the effect of capacity violation
| Cost without violation | Cost with violation | Improvement on cost (%) | CPU times (sec) |
Capacity violation (%) | ||
| 15 | 3 | 29222 | 24731 | 15.37 | 86.29 | 6.82 |
| 20 | 3 | 32626 | 29742 | 8.84 | 1973.64 | 7.38 |
| 20 | 4 | 30325 | 27387 | 9.69 | 2391.82 | 9.65 |
| 30 | 4 | 51172 | 48373 | 5.47 | 3729.65 | 4.27 |
| 40 | 4 | 66101 | 61382 | 7.14 | 5183.59 | 6.49 |
| 30 | 5 | 51798 | 46183 | 10.84 | 4734.64 | 3.85 |
| 40 | 5 | 62976 | 53284 | 15.39 | 5374.68 | 6.58 |
| 50 | 5 | 64828 | 59337 | 8.47 | 6739.52 | 9.83 |
| 40 | 6 | 59014 | 55833 | 5.39 | 7200.00 | 5.48 |
| 50 | 6 | 64188 | 57821 | 9.92 | 7200.00 | 6.29 |
| Average | 51225 | 46407 | 9.65 | 6.66 | ||
| Cost without violation | Cost with violation | Improvement on cost (%) | CPU times (sec) |
Capacity violation (%) | ||
| 15 | 3 | 29222 | 24731 | 15.37 | 86.29 | 6.82 |
| 20 | 3 | 32626 | 29742 | 8.84 | 1973.64 | 7.38 |
| 20 | 4 | 30325 | 27387 | 9.69 | 2391.82 | 9.65 |
| 30 | 4 | 51172 | 48373 | 5.47 | 3729.65 | 4.27 |
| 40 | 4 | 66101 | 61382 | 7.14 | 5183.59 | 6.49 |
| 30 | 5 | 51798 | 46183 | 10.84 | 4734.64 | 3.85 |
| 40 | 5 | 62976 | 53284 | 15.39 | 5374.68 | 6.58 |
| 50 | 5 | 64828 | 59337 | 8.47 | 6739.52 | 9.83 |
| 40 | 6 | 59014 | 55833 | 5.39 | 7200.00 | 5.48 |
| 50 | 6 | 64188 | 57821 | 9.92 | 7200.00 | 6.29 |
| Average | 51225 | 46407 | 9.65 | 6.66 | ||
Table 6.
Computational results of the TS and SA on small-size problems
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 0.00 | 24731 | 38.13 | 0.00 | 24731 | 40.57 | |
| 20 | 3 | 0.00 | 29742 | 63.59 | 0.00 | 29742 | 54.13 | |
| 20 | 4 | 0.01 | 27387 | 73.82 | 0.02 | 27390 | 80.53 | |
| 30 | 4 | 0.23 | 48373 | 102.43 | 0.28 | 48397 | 138.62 | |
| 40 | 4 | 0.91 | 61382 | 162.57 | 0.73 | 61273 | 147.76 | |
| 30 | 5 | 0.35 | 46183 | 90.37 | 0.34 | 46178 | 128.54 | |
| 40 | 5 | 0.97 | 53284 | 194.63 | 1.14 | 53307 | 251.72 | |
| 50 | 5 | 1.24 | 59337 | 288.79 | 1.45 | 59460 | 300.05 | |
| 40 | 6 | 0.99 | 55833 | 239.40 | 1.06 | 55872 | 207.24 | |
| 50 | 6 | 1.93 | 57821 | 247.56 | 1.82 | 57759 | 277.42 | |
| Average | 0.66 | 46407 | 150.13 | 0.75 | 46411 | 162.66 | ||
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 0.00 | 24731 | 38.13 | 0.00 | 24731 | 40.57 | |
| 20 | 3 | 0.00 | 29742 | 63.59 | 0.00 | 29742 | 54.13 | |
| 20 | 4 | 0.01 | 27387 | 73.82 | 0.02 | 27390 | 80.53 | |
| 30 | 4 | 0.23 | 48373 | 102.43 | 0.28 | 48397 | 138.62 | |
| 40 | 4 | 0.91 | 61382 | 162.57 | 0.73 | 61273 | 147.76 | |
| 30 | 5 | 0.35 | 46183 | 90.37 | 0.34 | 46178 | 128.54 | |
| 40 | 5 | 0.97 | 53284 | 194.63 | 1.14 | 53307 | 251.72 | |
| 50 | 5 | 1.24 | 59337 | 288.79 | 1.45 | 59460 | 300.05 | |
| 40 | 6 | 0.99 | 55833 | 239.40 | 1.06 | 55872 | 207.24 | |
| 50 | 6 | 1.93 | 57821 | 247.56 | 1.82 | 57759 | 277.42 | |
| Average | 0.66 | 46407 | 150.13 | 0.75 | 46411 | 162.66 | ||
Table 7.
Computational results of the TS and SA on larger-size problems
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 50 | 8 | 2.41 | 54823 | 234.65 | 2.08 | 54711 | 208.40 | |
| 80 | 8 | 1.73 | 113897 | 383.59 | 2.36 | 114602 | 361.47 | |
| 100 | 8 | 0.96 | 137254 | 437.42 | 1.53 | 138029 | 472.43 | |
| 80 | 9 | 1.24 | 100286 | 369.38 | 2.37 | 101405 | 390.22 | |
| 100 | 9 | 0.72 | 130287 | 482.36 | 1.24 | 130960 | 538.52 | |
| 120 | 9 | 0.92 | 157239 | 501.36 | 0.83 | 157099 | 409.25 | |
| 150 | 9 | 1.09 | 186275 | 472.17 | 0.95 | 186117 | 463.47 | |
| 80 | 10 | 3.73 | 983673 | 302.54 | 2.54 | 982388 | 378.49 | |
| 100 | 10 | 2.27 | 125362 | 261.52 | 2.36 | 125472 | 330.52 | |
| 120 | 10 | 1.34 | 139927 | 289.55 | 2.03 | 140080 | 375.38 | |
| 150 | 10 | 1.46 | 173845 | 573.82 | 3.41 | 174186 | 593.54 | |
| 200 | 10 | 2.03 | 237419 | 479.53 | 3.56 | 238279 | 636.39 | |
| Average | 1.66 | 211690 | 398.99 | 2.11 | 211944 | 429.84 | ||
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 50 | 8 | 2.41 | 54823 | 234.65 | 2.08 | 54711 | 208.40 | |
| 80 | 8 | 1.73 | 113897 | 383.59 | 2.36 | 114602 | 361.47 | |
| 100 | 8 | 0.96 | 137254 | 437.42 | 1.53 | 138029 | 472.43 | |
| 80 | 9 | 1.24 | 100286 | 369.38 | 2.37 | 101405 | 390.22 | |
| 100 | 9 | 0.72 | 130287 | 482.36 | 1.24 | 130960 | 538.52 | |
| 120 | 9 | 0.92 | 157239 | 501.36 | 0.83 | 157099 | 409.25 | |
| 150 | 9 | 1.09 | 186275 | 472.17 | 0.95 | 186117 | 463.47 | |
| 80 | 10 | 3.73 | 983673 | 302.54 | 2.54 | 982388 | 378.49 | |
| 100 | 10 | 2.27 | 125362 | 261.52 | 2.36 | 125472 | 330.52 | |
| 120 | 10 | 1.34 | 139927 | 289.55 | 2.03 | 140080 | 375.38 | |
| 150 | 10 | 1.46 | 173845 | 573.82 | 3.41 | 174186 | 593.54 | |
| 200 | 10 | 2.03 | 237419 | 479.53 | 3.56 | 238279 | 636.39 | |
| Average | 1.66 | 211690 | 398.99 | 2.11 | 211944 | 429.84 | ||
| [1] |
Bariş Keçeci, Fulya Altıparmak, İmdat Kara. A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012 |
| [2] |
Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial and Management Optimization, 2022, 18 (2) : 897-932. doi: 10.3934/jimo.2021002 |
| [3] |
Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial and Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87 |
| [4] |
Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial and Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 |
| [5] |
Melis Alpaslan Takan, Refail Kasimbeyli. Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2073-2095. doi: 10.3934/jimo.2020059 |
| [6] |
Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 |
| [7] |
Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045 |
| [8] |
Linet Ozdamar, Dilek Tuzun Aksu, Elifcan Yasa, Biket Ergunes. Disaster relief routing in limited capacity road networks with heterogeneous flows. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1367-1380. doi: 10.3934/jimo.2018011 |
| [9] |
Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1949-1977. doi: 10.3934/jimo.2021051 |
| [10] |
Nurhadi Siswanto, Stefanus Eko Wiratno, Ahmad Rusdiansyah, Ruhul Sarker. Maritime inventory routing problem with multiple time windows. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091 |
| [11] |
Jesse Collingwood, Robert D. Foley, David R. McDonald. Networks with cascading overloads. Journal of Industrial and Management Optimization, 2012, 8 (4) : 877-894. doi: 10.3934/jimo.2012.8.877 |
| [12] |
Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058 |
| [13] |
Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240 |
| [14] |
Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1065-1084. doi: 10.3934/jimo.2016062 |
| [15] |
Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119 |
| [16] |
Gbeminiyi John Oyewole, Olufemi Adetunji. Solving the facility location and fixed charge solid transportation problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1557-1575. doi: 10.3934/jimo.2020034 |
| [17] |
Feliz Minhós, T. Gyulov, A. I. Santos. Existence and location result for a fourth order boundary value problem. Conference Publications, 2005, 2005 (Special) : 662-671. doi: 10.3934/proc.2005.2005.662 |
| [18] |
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 |
| [19] |
Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1247-1259. doi: 10.3934/jimo.2021017 |
| [20] |
Samia Challal, Abdeslem Lyaghfouri. The heterogeneous dam problem with leaky boundary condition. Communications on Pure and Applied Analysis, 2011, 10 (1) : 93-125. doi: 10.3934/cpaa.2011.10.93 |
2021 Impact Factor: 1.865
Tools
Metrics
Other articles
by authors
[Back to Top]