
-
Previous Article
On limiting characteristics for a non-stationary two-processor heterogeneous system with catastrophes, server failures and repairs
- JIMO Home
- This Issue
-
Next Article
Optimal production and emission reduction policies for a remanufacturing firm considering deferred payment strategy
A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery
1. | Deparment of Industrial Engineering, School of Engineering, Başkent University, Baǧlıca Kampüsü Fatih Sultan Mahallesi, Eskişehir Yolu 18.km, Etimesgut, Ankara, TR 06790, Türkiye |
2. | Deparment of Industrial Engineering, School of Engineering, Gazi University, Eti Mahallesi, Yükseliş Sokak, No:5, Maltepe, Ankara, TR 06570, Türkiye |
This study considers a variant of the vehicle routing problem (VRP) called the heterogeneous VRP with simultaneous pickup and delivery (HVRPSPD). The HVRPSPD may broadly be defined as identifying the minimum cost routes and vehicle types. To solve the HVRPSPD, first, we propose a polynomial-size mixed integer programming formulation. Because the HVRPSPD is an NP-hard problem, it is difficult to determine the optimal solution in a reasonable time for moderate and large-size problem instances. Hence, we develop a hybrid metaheuristic approach based on the simulated annealing and local search algorithms called SA-LS. We conduct a computational study in three stages. First, the performance of the mathematical model and SA-LS are investigated on small and medium-size HVRPSPD instances. Second, we compare SA-LS with the constructive heuristics, nearest neighborhood and Clarke-Wright savings algorithms, adapted for the HVRPSPD. Finally, the performance of SA-LS is evaluated on the instances of the heterogeneous VRP (HVRP), which is a special case of the HVRPSPD. Computational results demonstrate that the mathematical model can solve small-size instances optimally up to 35 nodes; SA-LS provides good quality solutions for medium and large-size problems. Moreover, SA-LS is superior to simple constructive heuristics and can be a preferable solution method to solve HVRP and VRPSPD instances successfully.
References:
[1] |
T. J. Ai and V. Kachitvichyanukul,
A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 36 (2009), 1693-1702.
doi: 10.1016/j.cor.2008.04.003. |
[2] |
S. Allahyari, M. Salari and D. Vigo,
A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem, European Journal of Operational Research, 242 (2015), 756-768.
doi: 10.1016/j.ejor.2014.10.048. |
[3] |
J.-F. Arvis, D. Saslavsky, L. Ojala, B. Shepherd, C. Busch, A. Raj and T. Naula, Connecting to Compete 2016: Trade Logistics in the Global Economy-The Logistics Performance Index and Its Indicators, World Bank, 2016.
doi: 10.1596/24598. |
[4] |
M. Avci and S. Topaloglu,
An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries, Computers & Industrial Engineering, 83 (2015), 15-29.
doi: 10.1016/j.cie.2015.02.002. |
[5] |
M. Avci and S. Topaloglu,
A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery, Expert Systems with Applications, 53 (2016), 160-171.
doi: 10.1016/j.eswa.2016.01.038. |
[6] |
R. Baldacci, M. Battarra and D. Vigo, Routing a heterogeneous fleet of vehicles, The Vehicle Routing Problem: Latest Advances and New Challenges, Oper. Res./Comput. Sci. Interfaces Ser., Springer, New York, 43 2008, 3–27.
doi: 10.1007/978-0-387-77778-8_1. |
[7] |
R. Baldacci, P. Toth and D. Vigo,
Exact algorithms for routing problems under vehicle capacity constraints, Annals of Operations Research, 175 (2010), 213-245.
doi: 10.1007/s10479-009-0650-0. |
[8] |
J. E. Beasley,
Route first-Cluster second methods for vehicle routing, Omega, 11 (1983), 403-408.
doi: 10.1016/0305-0483(83)90033-6. |
[9] |
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 |
[10] |
J. Brandão, A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem, European journal of operational research, 195 (2009), 716-728. Google Scholar |
[11] |
J. Brandão,
A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem, Comput. Oper. Res., 38 (2011), 140-151.
doi: 10.1016/j.cor.2010.04.008. |
[12] |
G. Calleja, A. Corominas, A. García-Villoria and R. Pastor,
Hybrid metaheuristics for the Accessibility Windows Assembly Line Balancing Problem Level 2 (AWALBP-L2), European Journal of Operational Research, 250 (2016), 760-772.
doi: 10.1016/j.ejor.2015.10.025. |
[13] |
S. Çetín and C. Gencer, Heterojen araç filolu zaman pencereli eş zamanlı daǧıtım-toplamalı araç rotalama problemleri: Matematiksel model, Uluslararası Mühendislik Araştırma ve Geliştirme Dergisi, 3 (2011), 19–27. Google Scholar |
[14] |
E. Choi and D.-W. Tcha,
A column generation approach to the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 34 (2007), 2080-2095.
doi: 10.1016/j.cor.2005.08.002. |
[15] |
A. K. Coşar and B. Demir, Domestic road infrastructure and international trade: Evidence from turkey, Journal of Development Economics, 118 (2016), 232-244. Google Scholar |
[16] |
G. B. Dantzig and J. H. Ramser,
The truck dispatching problem, Management Science, 6 (1959/60), 80-91.
doi: 10.1287/mnsc.6.1.80. |
[17] |
M. Dell'Amico, G. Righini and M. Salani, A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection, Transportation science, 40 (2006), 235-247. Google Scholar |
[18] |
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. |
[19] |
Y. Gajpal and P. Abad,
Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery, Journal of the Operational Research Society, 61 (2010), 1498-1509.
doi: 10.1057/jors.2009.83. |
[20] |
M. Gendreau, G. Laporte, C. Musaraganyi and É. D. Taillard,
A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 26 (1999), 1153-1173.
doi: 10.1016/S0305-0548(98)00100-2. |
[21] |
F. Gheysens, B. Golden and A. Assad, A new heuristic for determining fleet size and composition, Netflow at Pisa, Math. Programming Stud., 1986, 233–236.
doi: 10.1007/bfb0121103. |
[22] |
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.
doi: 10.1016/j.cie.2012.01.005. |
[23] |
B. Golden, A. Assad, L. Levy and F. Gheysens,
The fleet size and mix vehicle routing problem, Computers & Operations Research, 11 (1984), 49-66.
doi: 10.1016/0305-0548(84)90007-8. |
[24] |
A. Hoff, H. Andersson, M. Christiansen, G. Hasle and A. Løkketangen,
Industrial aspects and literature survey: Fleet composition and routing, Comput. Oper. Res., 37 (2010), 2041-2061.
doi: 10.1016/j.cor.2010.03.015. |
[25] |
S. Irnich and G. Desaulniers, Shortest path problems with resource constraints, Column Generation, Springer, (2005), 33–65.
doi: 10.1007/0-387-25486-2_2. |
[26] |
S. Irnich, M. Schneider and D. Vigo, Chapter 9: Four variants of the vehicle routing problem, Vehicle Routing: Problems, Methods, and Applications, Second Edition, SIAM, (2014), 241–271. Google Scholar |
[27] |
A. A. Juan, J. Faulin, J. Caceres-Cruz, B. B. Barrios and E. Martinez,
A successive approximations method for the heterogeneous vehicle routing problem: Analysing different fleet configurations, Eur. J. Ind. Eng, 8 (2014), 762-788.
doi: 10.1504/EJIE.2014.066934. |
[28] |
I. Kara and T. Derya,
Polynomial size formulations for the distance and capacity constrained vehicle routing problem, AIP Conference Proceedings, 1389 (2011), 1713-1718.
doi: 10.1063/1.3636940. |
[29] |
I. Karaoglan, Location Routing Problem with Simultaneous Pickup and Delivery in Distribution Network Design, PhD thesis, Gazi University, Institue of Science, Ankara, Turkey, 2009. Google Scholar |
[30] |
B. Keçeci, F. Altıparmak and I. Kara, The heterogeneous vehicle routing problem with simultaneous pickup and delivery: A hybrid heuristic approach based on simulated annealing, CIE44 & IMSS'14 Proceedings, (2014). Google Scholar |
[31] |
B. Keçeci, F. Altiparmak and I. Kara, Heterogeneous vehicle routing problem with simultaneous pickup and delivery: Mathematical formulations and a heuristic algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 30 (2015), 185-195. Google Scholar |
[32] |
B. Kececi, F. Altiparmak and I. Kara, A hybrid constructive mat-heuristic algorithm for the heterogeneous vehicle routing problem with simultaneous pick-up and delivery, Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Comput. Sci., Springer, Cham, 9595 (2016), 1–17.
doi: 10.1007/978-3-319-30698-8_1. |
[33] |
S. Kirkpatrick, C. D. Gelatt, Jr . and M. P. Vecchi,
Optimization by simulated annealing, Science, 220 (1983), 671-680.
doi: 10.1126/science.220.4598.671. |
[34] |
Ç. Koç, T. Bektaş, O. Jabali and G. Laporte,
Thirty years of heterogeneous vehicle routing, European Journal of Operational Research, 249 (2016), 1-21.
doi: 10.1016/j.ejor.2015.07.020. |
[35] |
T. W. Liao, P.-C. Chang, R. J. Kuo and C.-J. Liao,
A comparison of five hybrid metaheuristic algorithms for unrelated parallel-machine scheduling and inbound trucks sequencing in multi-door cross docking systems, Applied Soft Computing, 21 (2014), 180-193.
doi: 10.1016/j.asoc.2014.02.026. |
[36] |
F.-H. Liu and S.-Y. Shen, The fleet size and mix vehicle routing problem with time windows, Journal of the Operational Research society, 50 (1999), 721-732. Google Scholar |
[37] |
S. G. Liu, W. L. Huang and H. M. Ma,
An effective genetic algorithm for the fleet size and mix vehicle routing problems, Transportation Research Part E: Logistics and Transportation Review, 45 (2009), 434-445.
doi: 10.1016/j.tre.2008.10.003. |
[38] |
M. A. Masmoudi, M. Hosny, K. Braekers and A. Dammak,
Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem, Transportation Research Part E: Logistics and Transportation Review, 96 (2016), 60-80.
doi: 10.1016/j.tre.2016.10.002. |
[39] |
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller,
Equation of state calculations by fast computing machines, The Journal of Chemical Physics, 21 (1953), 1087-1092.
doi: 10.2172/4390578. |
[40] |
H. Min,
The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research Part A: General, 23 (1989), 377-386.
doi: 10.1016/0191-2607(89)90085-X. |
[41] |
F. Alfredo Tang Montané and R. D. Galvão,
A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Comput. Oper. Res., 33 (2006), 595-619.
doi: 10.1016/j.cor.2004.07.009. |
[42] |
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.
doi: 10.1016/j.ejor.2002.11.003. |
[43] |
I. H. Osman and S. Salhi, Local search strategies for the vehicle fleet mix problem, Modern Heuristic Search Methods, 131–153. Google Scholar |
[44] |
D. C. Paraskevopoulos, P. P. Repoussis, C. D. Tarantilis, G. Ioannou and G. P. Prastacos,
A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows, Journal of Heuristics, 14 (2008), 425-455.
doi: 10.1007/s10732-007-9045-z. |
[45] |
P. H. V. Penna, A. Subramanian and L. S. Ochi,
An iterated local search heuristic for the heterogeneous fleet vehicle routing problem, Journal of Heuristics, 19 (2013), 201-232.
doi: 10.1007/s10732-011-9186-y. |
[46] |
O. Polat, C. B. Kalayci, O. Kulak and H.-O. Günther,
A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit, European Journal of Operational Research, 242 (2015), 369-382.
doi: 10.1016/j.ejor.2014.10.010. |
[47] |
C. Prins,
A simple and effective evolutionary algorithm for the vehicle routing problem, Comput. Oper. Res., 31 (2004), 1985-2002.
doi: 10.1016/S0305-0548(03)00158-8. |
[48] |
C. Prins,
Two memetic algorithms for heterogeneous fleet vehicle routing problems, Engineering Applications of Artificial Intelligence, 22 (2009), 916-928.
doi: 10.1016/j.engappai.2008.10.006. |
[49] |
J. Renaud and F. F. Boctor,
A sweep-based algorithm for the fleet size and mix vehicle routing problem, European Journal of Operational Research, 140 (2002), 618-628.
doi: 10.1016/S0377-2217(01)00237-5. |
[50] |
S. Ropke and D. Pisinger,
An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation science, 40 (2006), 455-472.
doi: 10.1287/trsc.1050.0135. |
[51] |
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 |
[52] |
S. Salhi and G. K. Rand,
Incorporating vehicle routing into the vehicle fleet composition problem, European Journal of Operational Research, 66 (1993), 313-330.
doi: 10.1016/0377-2217(93)90220-H. |
[53] |
L. Simeonova, N. Wassan, S. Salhi and G. Nagy,
The heterogeneous fleet vehicle routing problem with light loads and overtime: Formulation and population variable neighbourhood search with adaptive memory, Expert Systems with Applications, 114 (2018), 183-195.
doi: 10.1016/j.eswa.2018.07.034. |
[54] |
M. M. Solomon,
Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35 (1987), 254-265.
doi: 10.1287/opre.35.2.254. |
[55] |
A. Subramanian, L. M. d. A. Drummond, C. Bentes, L. S. Ochi and R. Farias, A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 37 (2010), 1899-1911. Google Scholar |
[56] |
A. Subramanian, P. H. V. Penna, E. Uchoa and L. S. Ochi,
A hybrid algorithm for the heterogeneous fleet vehicle routing problem, European Journal of Operational Research, 221 (2012), 285-295.
doi: 10.1016/j.ejor.2012.03.016. |
[57] |
A. Subramanian, E. Uchoa, A. A. Pessoa and L. S. Ochi,
Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery, Optimization Letters, 7 (2013), 1569-1581.
doi: 10.1007/s11590-012-0570-9. |
[58] |
É. D. Taillard,
A heuristic column generation method for the heterogeneous fleet VRP, RAIRO-Operations Research, 33 (1999), 1-14.
doi: 10.1051/ro:1999101. |
[59] |
E.-G. Talbi, A taxonomy of hybrid metaheuristics, Journal of heuristics, 8 (2002), 541-564. Google Scholar |
[60] |
C. Blum, J. Puchinger, G. Raidl and A. Roli,
Hybrid metaheuristics, Hybrid Optimization, Springer Optim. Appl., Springer, New York, 45 (2011), 305-335.
doi: 10.1007/978-1-4419-1644-0_9. |
[61] |
C. D. Tarantilis, C. T. Kiranoudis and V. S. Vassiliadis,
A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem, European Journal of Operational Research, 152 (2004), 148-158.
doi: 10.1016/S0377-2217(02)00669-0. |
[62] |
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.
doi: 10.1109/ICCIE.2010.5668433. |
[63] |
P. Toth and D. Vigo, The Vvehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, 9. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002.
doi: 10.1137/1.9780898718515. |
[64] |
X. F. Wang,
The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads, Discrete Contin. Dyn. Syst. Ser. S, 12 (2019), 1147-1166.
|
[65] |
N. A. Wassan and I. H. Osman,
Tabu search variants for the mix fleet vehicle routing problem, Journal of the Operational Research Society, 53 (2002), 768-782.
doi: 10.1057/palgrave.jors.2601344. |
[66] |
C. Waters,
Expanding the scope of linear programming solutions for vehicle scheduling problems, Omega, 16 (1988), 577-583.
doi: 10.1016/0305-0483(88)90031-X. |
[67] |
Y. Zhang, M. Y. Qi, W.-H. Lin and L. X. Miao,
A metaheuristic approach to the reliable location routing problem under disruptions, Transportation Research Part E: Logistics and Transportation Review, 83 (2015), 90-110.
doi: 10.1016/j.tre.2015.09.001. |
show all references
References:
[1] |
T. J. Ai and V. Kachitvichyanukul,
A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 36 (2009), 1693-1702.
doi: 10.1016/j.cor.2008.04.003. |
[2] |
S. Allahyari, M. Salari and D. Vigo,
A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem, European Journal of Operational Research, 242 (2015), 756-768.
doi: 10.1016/j.ejor.2014.10.048. |
[3] |
J.-F. Arvis, D. Saslavsky, L. Ojala, B. Shepherd, C. Busch, A. Raj and T. Naula, Connecting to Compete 2016: Trade Logistics in the Global Economy-The Logistics Performance Index and Its Indicators, World Bank, 2016.
doi: 10.1596/24598. |
[4] |
M. Avci and S. Topaloglu,
An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries, Computers & Industrial Engineering, 83 (2015), 15-29.
doi: 10.1016/j.cie.2015.02.002. |
[5] |
M. Avci and S. Topaloglu,
A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery, Expert Systems with Applications, 53 (2016), 160-171.
doi: 10.1016/j.eswa.2016.01.038. |
[6] |
R. Baldacci, M. Battarra and D. Vigo, Routing a heterogeneous fleet of vehicles, The Vehicle Routing Problem: Latest Advances and New Challenges, Oper. Res./Comput. Sci. Interfaces Ser., Springer, New York, 43 2008, 3–27.
doi: 10.1007/978-0-387-77778-8_1. |
[7] |
R. Baldacci, P. Toth and D. Vigo,
Exact algorithms for routing problems under vehicle capacity constraints, Annals of Operations Research, 175 (2010), 213-245.
doi: 10.1007/s10479-009-0650-0. |
[8] |
J. E. Beasley,
Route first-Cluster second methods for vehicle routing, Omega, 11 (1983), 403-408.
doi: 10.1016/0305-0483(83)90033-6. |
[9] |
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 |
[10] |
J. Brandão, A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem, European journal of operational research, 195 (2009), 716-728. Google Scholar |
[11] |
J. Brandão,
A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem, Comput. Oper. Res., 38 (2011), 140-151.
doi: 10.1016/j.cor.2010.04.008. |
[12] |
G. Calleja, A. Corominas, A. García-Villoria and R. Pastor,
Hybrid metaheuristics for the Accessibility Windows Assembly Line Balancing Problem Level 2 (AWALBP-L2), European Journal of Operational Research, 250 (2016), 760-772.
doi: 10.1016/j.ejor.2015.10.025. |
[13] |
S. Çetín and C. Gencer, Heterojen araç filolu zaman pencereli eş zamanlı daǧıtım-toplamalı araç rotalama problemleri: Matematiksel model, Uluslararası Mühendislik Araştırma ve Geliştirme Dergisi, 3 (2011), 19–27. Google Scholar |
[14] |
E. Choi and D.-W. Tcha,
A column generation approach to the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 34 (2007), 2080-2095.
doi: 10.1016/j.cor.2005.08.002. |
[15] |
A. K. Coşar and B. Demir, Domestic road infrastructure and international trade: Evidence from turkey, Journal of Development Economics, 118 (2016), 232-244. Google Scholar |
[16] |
G. B. Dantzig and J. H. Ramser,
The truck dispatching problem, Management Science, 6 (1959/60), 80-91.
doi: 10.1287/mnsc.6.1.80. |
[17] |
M. Dell'Amico, G. Righini and M. Salani, A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection, Transportation science, 40 (2006), 235-247. Google Scholar |
[18] |
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. |
[19] |
Y. Gajpal and P. Abad,
Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery, Journal of the Operational Research Society, 61 (2010), 1498-1509.
doi: 10.1057/jors.2009.83. |
[20] |
M. Gendreau, G. Laporte, C. Musaraganyi and É. D. Taillard,
A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 26 (1999), 1153-1173.
doi: 10.1016/S0305-0548(98)00100-2. |
[21] |
F. Gheysens, B. Golden and A. Assad, A new heuristic for determining fleet size and composition, Netflow at Pisa, Math. Programming Stud., 1986, 233–236.
doi: 10.1007/bfb0121103. |
[22] |
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.
doi: 10.1016/j.cie.2012.01.005. |
[23] |
B. Golden, A. Assad, L. Levy and F. Gheysens,
The fleet size and mix vehicle routing problem, Computers & Operations Research, 11 (1984), 49-66.
doi: 10.1016/0305-0548(84)90007-8. |
[24] |
A. Hoff, H. Andersson, M. Christiansen, G. Hasle and A. Løkketangen,
Industrial aspects and literature survey: Fleet composition and routing, Comput. Oper. Res., 37 (2010), 2041-2061.
doi: 10.1016/j.cor.2010.03.015. |
[25] |
S. Irnich and G. Desaulniers, Shortest path problems with resource constraints, Column Generation, Springer, (2005), 33–65.
doi: 10.1007/0-387-25486-2_2. |
[26] |
S. Irnich, M. Schneider and D. Vigo, Chapter 9: Four variants of the vehicle routing problem, Vehicle Routing: Problems, Methods, and Applications, Second Edition, SIAM, (2014), 241–271. Google Scholar |
[27] |
A. A. Juan, J. Faulin, J. Caceres-Cruz, B. B. Barrios and E. Martinez,
A successive approximations method for the heterogeneous vehicle routing problem: Analysing different fleet configurations, Eur. J. Ind. Eng, 8 (2014), 762-788.
doi: 10.1504/EJIE.2014.066934. |
[28] |
I. Kara and T. Derya,
Polynomial size formulations for the distance and capacity constrained vehicle routing problem, AIP Conference Proceedings, 1389 (2011), 1713-1718.
doi: 10.1063/1.3636940. |
[29] |
I. Karaoglan, Location Routing Problem with Simultaneous Pickup and Delivery in Distribution Network Design, PhD thesis, Gazi University, Institue of Science, Ankara, Turkey, 2009. Google Scholar |
[30] |
B. Keçeci, F. Altıparmak and I. Kara, The heterogeneous vehicle routing problem with simultaneous pickup and delivery: A hybrid heuristic approach based on simulated annealing, CIE44 & IMSS'14 Proceedings, (2014). Google Scholar |
[31] |
B. Keçeci, F. Altiparmak and I. Kara, Heterogeneous vehicle routing problem with simultaneous pickup and delivery: Mathematical formulations and a heuristic algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 30 (2015), 185-195. Google Scholar |
[32] |
B. Kececi, F. Altiparmak and I. Kara, A hybrid constructive mat-heuristic algorithm for the heterogeneous vehicle routing problem with simultaneous pick-up and delivery, Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Comput. Sci., Springer, Cham, 9595 (2016), 1–17.
doi: 10.1007/978-3-319-30698-8_1. |
[33] |
S. Kirkpatrick, C. D. Gelatt, Jr . and M. P. Vecchi,
Optimization by simulated annealing, Science, 220 (1983), 671-680.
doi: 10.1126/science.220.4598.671. |
[34] |
Ç. Koç, T. Bektaş, O. Jabali and G. Laporte,
Thirty years of heterogeneous vehicle routing, European Journal of Operational Research, 249 (2016), 1-21.
doi: 10.1016/j.ejor.2015.07.020. |
[35] |
T. W. Liao, P.-C. Chang, R. J. Kuo and C.-J. Liao,
A comparison of five hybrid metaheuristic algorithms for unrelated parallel-machine scheduling and inbound trucks sequencing in multi-door cross docking systems, Applied Soft Computing, 21 (2014), 180-193.
doi: 10.1016/j.asoc.2014.02.026. |
[36] |
F.-H. Liu and S.-Y. Shen, The fleet size and mix vehicle routing problem with time windows, Journal of the Operational Research society, 50 (1999), 721-732. Google Scholar |
[37] |
S. G. Liu, W. L. Huang and H. M. Ma,
An effective genetic algorithm for the fleet size and mix vehicle routing problems, Transportation Research Part E: Logistics and Transportation Review, 45 (2009), 434-445.
doi: 10.1016/j.tre.2008.10.003. |
[38] |
M. A. Masmoudi, M. Hosny, K. Braekers and A. Dammak,
Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem, Transportation Research Part E: Logistics and Transportation Review, 96 (2016), 60-80.
doi: 10.1016/j.tre.2016.10.002. |
[39] |
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller,
Equation of state calculations by fast computing machines, The Journal of Chemical Physics, 21 (1953), 1087-1092.
doi: 10.2172/4390578. |
[40] |
H. Min,
The multiple vehicle routing problem with simultaneous delivery and pick-up points, Transportation Research Part A: General, 23 (1989), 377-386.
doi: 10.1016/0191-2607(89)90085-X. |
[41] |
F. Alfredo Tang Montané and R. D. Galvão,
A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Comput. Oper. Res., 33 (2006), 595-619.
doi: 10.1016/j.cor.2004.07.009. |
[42] |
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.
doi: 10.1016/j.ejor.2002.11.003. |
[43] |
I. H. Osman and S. Salhi, Local search strategies for the vehicle fleet mix problem, Modern Heuristic Search Methods, 131–153. Google Scholar |
[44] |
D. C. Paraskevopoulos, P. P. Repoussis, C. D. Tarantilis, G. Ioannou and G. P. Prastacos,
A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows, Journal of Heuristics, 14 (2008), 425-455.
doi: 10.1007/s10732-007-9045-z. |
[45] |
P. H. V. Penna, A. Subramanian and L. S. Ochi,
An iterated local search heuristic for the heterogeneous fleet vehicle routing problem, Journal of Heuristics, 19 (2013), 201-232.
doi: 10.1007/s10732-011-9186-y. |
[46] |
O. Polat, C. B. Kalayci, O. Kulak and H.-O. Günther,
A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit, European Journal of Operational Research, 242 (2015), 369-382.
doi: 10.1016/j.ejor.2014.10.010. |
[47] |
C. Prins,
A simple and effective evolutionary algorithm for the vehicle routing problem, Comput. Oper. Res., 31 (2004), 1985-2002.
doi: 10.1016/S0305-0548(03)00158-8. |
[48] |
C. Prins,
Two memetic algorithms for heterogeneous fleet vehicle routing problems, Engineering Applications of Artificial Intelligence, 22 (2009), 916-928.
doi: 10.1016/j.engappai.2008.10.006. |
[49] |
J. Renaud and F. F. Boctor,
A sweep-based algorithm for the fleet size and mix vehicle routing problem, European Journal of Operational Research, 140 (2002), 618-628.
doi: 10.1016/S0377-2217(01)00237-5. |
[50] |
S. Ropke and D. Pisinger,
An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation science, 40 (2006), 455-472.
doi: 10.1287/trsc.1050.0135. |
[51] |
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 |
[52] |
S. Salhi and G. K. Rand,
Incorporating vehicle routing into the vehicle fleet composition problem, European Journal of Operational Research, 66 (1993), 313-330.
doi: 10.1016/0377-2217(93)90220-H. |
[53] |
L. Simeonova, N. Wassan, S. Salhi and G. Nagy,
The heterogeneous fleet vehicle routing problem with light loads and overtime: Formulation and population variable neighbourhood search with adaptive memory, Expert Systems with Applications, 114 (2018), 183-195.
doi: 10.1016/j.eswa.2018.07.034. |
[54] |
M. M. Solomon,
Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35 (1987), 254-265.
doi: 10.1287/opre.35.2.254. |
[55] |
A. Subramanian, L. M. d. A. Drummond, C. Bentes, L. S. Ochi and R. Farias, A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 37 (2010), 1899-1911. Google Scholar |
[56] |
A. Subramanian, P. H. V. Penna, E. Uchoa and L. S. Ochi,
A hybrid algorithm for the heterogeneous fleet vehicle routing problem, European Journal of Operational Research, 221 (2012), 285-295.
doi: 10.1016/j.ejor.2012.03.016. |
[57] |
A. Subramanian, E. Uchoa, A. A. Pessoa and L. S. Ochi,
Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery, Optimization Letters, 7 (2013), 1569-1581.
doi: 10.1007/s11590-012-0570-9. |
[58] |
É. D. Taillard,
A heuristic column generation method for the heterogeneous fleet VRP, RAIRO-Operations Research, 33 (1999), 1-14.
doi: 10.1051/ro:1999101. |
[59] |
E.-G. Talbi, A taxonomy of hybrid metaheuristics, Journal of heuristics, 8 (2002), 541-564. Google Scholar |
[60] |
C. Blum, J. Puchinger, G. Raidl and A. Roli,
Hybrid metaheuristics, Hybrid Optimization, Springer Optim. Appl., Springer, New York, 45 (2011), 305-335.
doi: 10.1007/978-1-4419-1644-0_9. |
[61] |
C. D. Tarantilis, C. T. Kiranoudis and V. S. Vassiliadis,
A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem, European Journal of Operational Research, 152 (2004), 148-158.
doi: 10.1016/S0377-2217(02)00669-0. |
[62] |
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.
doi: 10.1109/ICCIE.2010.5668433. |
[63] |
P. Toth and D. Vigo, The Vvehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, 9. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002.
doi: 10.1137/1.9780898718515. |
[64] |
X. F. Wang,
The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads, Discrete Contin. Dyn. Syst. Ser. S, 12 (2019), 1147-1166.
|
[65] |
N. A. Wassan and I. H. Osman,
Tabu search variants for the mix fleet vehicle routing problem, Journal of the Operational Research Society, 53 (2002), 768-782.
doi: 10.1057/palgrave.jors.2601344. |
[66] |
C. Waters,
Expanding the scope of linear programming solutions for vehicle scheduling problems, Omega, 16 (1988), 577-583.
doi: 10.1016/0305-0483(88)90031-X. |
[67] |
Y. Zhang, M. Y. Qi, W.-H. Lin and L. X. Miao,
A metaheuristic approach to the reliable location routing problem under disruptions, Transportation Research Part E: Logistics and Transportation Review, 83 (2015), 90-110.
doi: 10.1016/j.tre.2015.09.001. |











n | Type | SA-LS | MIP Formulation | MatH-LS* | |||||||
Gap% | Imp% | #OpSol | CPU (s) | Gap% | #OpSol | CPU (s) | Gap% | #OpSol | CPU (s) | ||
20 | X | 4.50 | 5.50 | 6 | 1.90 | 1.90 | 20 | 306.01 | 5.38 | 8 | 16.53 |
Y | 4.40 | 5.30 | 7 | 2.00 | 1.51 | 20 | 321.93 | 5.49 | 7 | 13.6 | |
W | 4.00 | 7.10 | 7 | 1.90 | 0.49 | 23 | 290.63 | 4.38 | 12 | 13.24 | |
Z | 6.30 | 3.30 | 3 | 1.80 | 3.75 | 13 | 295.44 | 5.23 | 11 | 12.33 | |
(Total)Average | 4.80 | 5.30 | (23) | 1.90 | 1.91 | (76) | 303.50 | 5.12 | (38) | 13.93 | |
25 | X | 5.10 | 3.80 | 3 | 3.50 | 2.39 | 13 | 1174.24 | 9.35 | 5 | 18.48 |
Y | 5.00 | 3.50 | 2 | 2.70 | 2.38 | 15 | 1362.22 | 8.87 | 7 | 17.52 | |
W | 6.10 | 3.80 | 3 | 3.00 | 2.65 | 14 | 644.11 | 7.21 | 7 | 16.74 | |
Z | 8.10 | 3.20 | 1 | 3.00 | 2.78 | 13 | 580.30 | 9.69 | 7 | 15.25 | |
(Total)Average | 6.08 | 3.58 | (9) | 3.05 | 2.55 | (55) | 940.22 | 8.78 | (26) | 17 | |
30 | X | 8.75 | 4.30 | 2 | 5.30 | 5.91 | 7 | 2133.27 | 13.06 | 1 | 21.95 |
Y | 11, 20 | 2.80 | 4 | 4.10 | 7.08 | 5 | 2154.08 | 12.95 | 2 | 28.12 | |
W | 6.55 | 6.30 | 0 | 5.90 | 6.26 | 4 | 1672.95 | 11.11 | 5 | 22.58 | |
Z | 6.18 | 4.90 | 3 | 5.20 | 4.39 | 9 | 1694.82 | 11.56 | 4 | 18.93 | |
(Total)Average | 8.17 | 4.58 | (9) | 5.13 | 5.91 | (25) | 1913.78 | 12.17 | (12) | 22.89 | |
35 | X | 8.32 | 11, 70 | 0 | 7.90 | 10, 76 | 0 | 3984.36 | 26.08 | 1 | 32.78 |
Y | 9.29 | 5.72 | 0 | 7.50 | 9.00 | 1 | 3724.80 | 16.14 | 0 | 31.31 | |
W | 7.97 | 3.99 | 1 | 7.40 | 9.90 | 4 | 3741.48 | 14.92 | 0 | 25.42 | |
Z | 9.88 | 3.67 | 1 | 8.20 | 9.59 | 6 | 3242.11 | 13.69 | 1 | 26.26 | |
(Total)Average | 8.87 | 6.27 | (2) | 7.75 | 9.81 | (11) | 3673.19 | 17.71 | (2) | 28.94 | |
40 | X | 16.60 | 5.44 | 0 | 11, 70 | 20.54 | 0 | 5833.66 | 27.66 | 0 | 41.16 |
Y | 18, 10 | 8.10 | 0 | 11, 60 | 19, 06 | 0 | 6216.06 | 19.28 | 0 | 46.15 | |
W | 9.08 | 4.93 | 0 | 11, 30 | 13.82 | 1 | 5685.47 | 15.68 | 0 | 28.66 | |
Z | 8.36 | 6.66 | 2 | 11, 50 | 10, 68 | 6 | 4810.54 | 11.87 | 0 | 28.79 | |
(Total)Average | 13, 04 | 6.28 | (2) | 11, 53 | 16, 02 | (7) | 5636.43 | 18.62 | (0) | 36.19 | |
Overall(Total) | 8.19 | 5.20 | (45) | 5.87 | 7.24 | (174) | 2493.42 | 12.48 | (78) | 23.79 | |
*MatH-LS is the algorithm proposed by Kececi et al. [32]. |
n | Type | SA-LS | MIP Formulation | MatH-LS* | |||||||
Gap% | Imp% | #OpSol | CPU (s) | Gap% | #OpSol | CPU (s) | Gap% | #OpSol | CPU (s) | ||
20 | X | 4.50 | 5.50 | 6 | 1.90 | 1.90 | 20 | 306.01 | 5.38 | 8 | 16.53 |
Y | 4.40 | 5.30 | 7 | 2.00 | 1.51 | 20 | 321.93 | 5.49 | 7 | 13.6 | |
W | 4.00 | 7.10 | 7 | 1.90 | 0.49 | 23 | 290.63 | 4.38 | 12 | 13.24 | |
Z | 6.30 | 3.30 | 3 | 1.80 | 3.75 | 13 | 295.44 | 5.23 | 11 | 12.33 | |
(Total)Average | 4.80 | 5.30 | (23) | 1.90 | 1.91 | (76) | 303.50 | 5.12 | (38) | 13.93 | |
25 | X | 5.10 | 3.80 | 3 | 3.50 | 2.39 | 13 | 1174.24 | 9.35 | 5 | 18.48 |
Y | 5.00 | 3.50 | 2 | 2.70 | 2.38 | 15 | 1362.22 | 8.87 | 7 | 17.52 | |
W | 6.10 | 3.80 | 3 | 3.00 | 2.65 | 14 | 644.11 | 7.21 | 7 | 16.74 | |
Z | 8.10 | 3.20 | 1 | 3.00 | 2.78 | 13 | 580.30 | 9.69 | 7 | 15.25 | |
(Total)Average | 6.08 | 3.58 | (9) | 3.05 | 2.55 | (55) | 940.22 | 8.78 | (26) | 17 | |
30 | X | 8.75 | 4.30 | 2 | 5.30 | 5.91 | 7 | 2133.27 | 13.06 | 1 | 21.95 |
Y | 11, 20 | 2.80 | 4 | 4.10 | 7.08 | 5 | 2154.08 | 12.95 | 2 | 28.12 | |
W | 6.55 | 6.30 | 0 | 5.90 | 6.26 | 4 | 1672.95 | 11.11 | 5 | 22.58 | |
Z | 6.18 | 4.90 | 3 | 5.20 | 4.39 | 9 | 1694.82 | 11.56 | 4 | 18.93 | |
(Total)Average | 8.17 | 4.58 | (9) | 5.13 | 5.91 | (25) | 1913.78 | 12.17 | (12) | 22.89 | |
35 | X | 8.32 | 11, 70 | 0 | 7.90 | 10, 76 | 0 | 3984.36 | 26.08 | 1 | 32.78 |
Y | 9.29 | 5.72 | 0 | 7.50 | 9.00 | 1 | 3724.80 | 16.14 | 0 | 31.31 | |
W | 7.97 | 3.99 | 1 | 7.40 | 9.90 | 4 | 3741.48 | 14.92 | 0 | 25.42 | |
Z | 9.88 | 3.67 | 1 | 8.20 | 9.59 | 6 | 3242.11 | 13.69 | 1 | 26.26 | |
(Total)Average | 8.87 | 6.27 | (2) | 7.75 | 9.81 | (11) | 3673.19 | 17.71 | (2) | 28.94 | |
40 | X | 16.60 | 5.44 | 0 | 11, 70 | 20.54 | 0 | 5833.66 | 27.66 | 0 | 41.16 |
Y | 18, 10 | 8.10 | 0 | 11, 60 | 19, 06 | 0 | 6216.06 | 19.28 | 0 | 46.15 | |
W | 9.08 | 4.93 | 0 | 11, 30 | 13.82 | 1 | 5685.47 | 15.68 | 0 | 28.66 | |
Z | 8.36 | 6.66 | 2 | 11, 50 | 10, 68 | 6 | 4810.54 | 11.87 | 0 | 28.79 | |
(Total)Average | 13, 04 | 6.28 | (2) | 11, 53 | 16, 02 | (7) | 5636.43 | 18.62 | (0) | 36.19 | |
Overall(Total) | 8.19 | 5.20 | (45) | 5.87 | 7.24 | (174) | 2493.42 | 12.48 | (78) | 23.79 | |
*MatH-LS is the algorithm proposed by Kececi et al. [32]. |
n | Type | CPU(s) | |||
50 | X | -36.69 | -14.23 | 6.71 | 19.62 |
Y | -35.79 | -18.23 | 5.57 | 20.75 | |
W | -42.96 | -7.83 | 8.79 | 23.65 | |
Z | -42.43 | -9.62 | 9.26 | 24.42 | |
Average | -39.47 | -12.48 | 7.58 | 22.11 | |
75 | X | -58.39 | -16.50 | 11.96 | 72.23 |
Y | -56.69 | -18.08 | 11.79 | 58.14 | |
W | -59.49 | -18.32 | 15.11 | 82.00 | |
Z | -59.14 | -12.37 | 17.55 | 57.12 | |
Average | -58.43 | -16.32 | 14.10 | 67.37 | |
100 | X | -60.04 | -20.91 | 15.65 | 210.87 |
Y | -60.46 | -20.23 | 16.17 | 220.00 | |
W | -63.42 | -16.71 | 12.20 | 223.16 | |
Z | -63.30 | -16.32 | 14.95 | 221.59 | |
Average | -61.81 | -18.54 | 14.74 | 218.90 |
n | Type | CPU(s) | |||
50 | X | -36.69 | -14.23 | 6.71 | 19.62 |
Y | -35.79 | -18.23 | 5.57 | 20.75 | |
W | -42.96 | -7.83 | 8.79 | 23.65 | |
Z | -42.43 | -9.62 | 9.26 | 24.42 | |
Average | -39.47 | -12.48 | 7.58 | 22.11 | |
75 | X | -58.39 | -16.50 | 11.96 | 72.23 |
Y | -56.69 | -18.08 | 11.79 | 58.14 | |
W | -59.49 | -18.32 | 15.11 | 82.00 | |
Z | -59.14 | -12.37 | 17.55 | 57.12 | |
Average | -58.43 | -16.32 | 14.10 | 67.37 | |
100 | X | -60.04 | -20.91 | 15.65 | 210.87 |
Y | -60.46 | -20.23 | 16.17 | 220.00 | |
W | -63.42 | -16.71 | 12.20 | 223.16 | |
Z | -63.30 | -16.32 | 14.95 | 221.59 | |
Average | -61.81 | -18.54 | 14.74 | 218.90 |
Inst. | n | Salhi and Rand[52] | MRPERT Osman and Salhi[43] | TSVFM Osman and Salhi[43] | Taillard[58] | Gendreau et al.[20] | Wassan and Osman[65] | Renaud and Boctor[49] | Choi and Tcha[14] | Brandao[10] | Prins[48] | Liu et al.[37] | Penna et al.[45] | Subramanian et al. [56] | Simeonova et al. [53] | SA-LS | Dev% | CPU (s) |
G_3 | 20 | 1003 | 971.95 | 971.24 | 961.03 | 961.03 | 961.03 | 963.61 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 0.00 | 0.46 |
G_4 | 20 | 6447 | 6447.80 | 6445.10 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 0.00 | 0.87 |
G_5 | 20 | 1015 | 1015.13 | 1009.15 | 1008.59 | 1007.05 | 1007.05 | 1007.96 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 0.00 | 0.47 |
G_6 | 20 | 6516 | 6516.56 | 6516.56 | 6516.47 | 6516.47 | 6516.47 | 6537.74 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 0.00 | 0.86 |
G_13 | 50 | 2493 | 2462.01 | 2471.07 | 2413.78 | 2408.41 | 2422.10 | 2406.43 | 2406.36 | 2406.36 | 2406.36 | 2406.36 | 2408.41 | 2406.36 | 2406.36 | 2412, 36 | 0.25 | 5.21 |
G_14 | 50 | 9153 | 9141.69 | 9125.65 | 9119.03 | 9119.03 | 9119.86 | 9122.01 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9121, 71 | 0.03 | 11.86 |
G_15 | 50 | 2623 | 2600.31 | 2606.72 | 2586.37 | 2586.37 | 2586.37 | 2618.03 | 2586.37 | 2586.84 | 2586.37 | 2586.37 | 2586.37 | 2586.37 | 2586.37 | 2588, 77 | 0.09 | 7.02 |
G_16 | 50 | 2765 | 2745.04 | 2745.01 | 2741.50 | 2741.50 | 2730.08 | 2761.96 | 2720.43 | 2728.14 | 2729.08 | 2724.22 | 2724.22 | 2720.43 | 2720.43 | 2779, 72 | 2.18 | 6.97 |
G_17 | 75 | 1767 | 1766.81 | 1762.05 | 1747.24 | 1749.50 | 1755.10 | 1757.21 | 1744.83 | 1736.09 | 1746.09 | 1734.53 | 1734.53 | 1734.53 | 1734.53 | 1770, 09 | 2.05 | 31.30 |
G_18 | 75 | 2439 | 2439.40 | 2412.56 | 2373.63 | 2381.43 | 2385.52 | 2413.39 | 2371.49 | 2376.89 | 2369.65 | 2369.65 | 2371.48 | 2369.65 | 2369.65 | 2434, 78 | 2.75 | 16.43 |
G_19 | 100 | 8751 | 8704.20 | 8685.71 | 8661.81 | 8675.16 | 8659.74 | 8687.31 | 8664.29 | 8667.26 | 8665.12 | 8662.94 | 8662.86 | 8661.81 | 8667.26 | 9173, 19 | 5.93 | 60.70 |
G_20 | 100 | 4187 | 4166.03 | 4188.73 | 4047.55 | 4086.76 | 4061.64 | 4094.54 | 4039.49 | 4048.09 | 4044.78 | 4038.46 | 4037.9 | 4032.81 | 4038.45 | 4153, 74 | 3.00 | 56.60 |
Avg. | 1.36 | 16.56 | ||||||||||||||||
MRPERT: Modified version of procedure RPERT proposed by Salhi and Rand [52], TSVFM: Tabu search for the vehicle fleet mix problem (VFM). |
Inst. | n | Salhi and Rand[52] | MRPERT Osman and Salhi[43] | TSVFM Osman and Salhi[43] | Taillard[58] | Gendreau et al.[20] | Wassan and Osman[65] | Renaud and Boctor[49] | Choi and Tcha[14] | Brandao[10] | Prins[48] | Liu et al.[37] | Penna et al.[45] | Subramanian et al. [56] | Simeonova et al. [53] | SA-LS | Dev% | CPU (s) |
G_3 | 20 | 1003 | 971.95 | 971.24 | 961.03 | 961.03 | 961.03 | 963.61 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 961.03 | 0.00 | 0.46 |
G_4 | 20 | 6447 | 6447.80 | 6445.10 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 6437.33 | 0.00 | 0.87 |
G_5 | 20 | 1015 | 1015.13 | 1009.15 | 1008.59 | 1007.05 | 1007.05 | 1007.96 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 1007.05 | 0.00 | 0.47 |
G_6 | 20 | 6516 | 6516.56 | 6516.56 | 6516.47 | 6516.47 | 6516.47 | 6537.74 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 6516.47 | 0.00 | 0.86 |
G_13 | 50 | 2493 | 2462.01 | 2471.07 | 2413.78 | 2408.41 | 2422.10 | 2406.43 | 2406.36 | 2406.36 | 2406.36 | 2406.36 | 2408.41 | 2406.36 | 2406.36 | 2412, 36 | 0.25 | 5.21 |
G_14 | 50 | 9153 | 9141.69 | 9125.65 | 9119.03 | 9119.03 | 9119.86 | 9122.01 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9119.03 | 9121, 71 | 0.03 | 11.86 |
G_15 | 50 | 2623 | 2600.31 | 2606.72 | 2586.37 | 2586.37 | 2586.37 | 2618.03 | 2586.37 | 2586.84 | 2586.37 | 2586.37 | 2586.37 | 2586.37 | 2586.37 | 2588, 77 | 0.09 | 7.02 |
G_16 | 50 | 2765 | 2745.04 | 2745.01 | 2741.50 | 2741.50 | 2730.08 | 2761.96 | 2720.43 | 2728.14 | 2729.08 | 2724.22 | 2724.22 | 2720.43 | 2720.43 | 2779, 72 | 2.18 | 6.97 |
G_17 | 75 | 1767 | 1766.81 | 1762.05 | 1747.24 | 1749.50 | 1755.10 | 1757.21 | 1744.83 | 1736.09 | 1746.09 | 1734.53 | 1734.53 | 1734.53 | 1734.53 | 1770, 09 | 2.05 | 31.30 |
G_18 | 75 | 2439 | 2439.40 | 2412.56 | 2373.63 | 2381.43 | 2385.52 | 2413.39 | 2371.49 | 2376.89 | 2369.65 | 2369.65 | 2371.48 | 2369.65 | 2369.65 | 2434, 78 | 2.75 | 16.43 |
G_19 | 100 | 8751 | 8704.20 | 8685.71 | 8661.81 | 8675.16 | 8659.74 | 8687.31 | 8664.29 | 8667.26 | 8665.12 | 8662.94 | 8662.86 | 8661.81 | 8667.26 | 9173, 19 | 5.93 | 60.70 |
G_20 | 100 | 4187 | 4166.03 | 4188.73 | 4047.55 | 4086.76 | 4061.64 | 4094.54 | 4039.49 | 4048.09 | 4044.78 | 4038.46 | 4037.9 | 4032.81 | 4038.45 | 4153, 74 | 3.00 | 56.60 |
Avg. | 1.36 | 16.56 | ||||||||||||||||
MRPERT: Modified version of procedure RPERT proposed by Salhi and Rand [52], TSVFM: Tabu search for the vehicle fleet mix problem (VFM). |
Instance | n | Q | Salhi and Nagy [51] | Goksal et al. [22] | SA-LS | ||||
Min | Avg | Max | Dev% | CPU (s) | |||||
CMT1X | 50 | 160 | 601 | 466.77 | 487 | 494.4 | 503 | 4.33 | 2.65 |
CMT1Y | 50 | 160 | 603 | 466.77 | 467 | 473.0 | 486 | 0.05 | 2.48 |
CMT2X | 75 | 140 | 873 | 668.77 | 698 | 709.0 | 726 | 4.37 | 4.58 |
CMT2Y | 75 | 140 | 924 | 663.25 | 672 | 683.6 | 699 | 1.32 | 5.32 |
CMT3X | 100 | 200 | 923 | 721.27 | 731 | 740.8 | 753 | 1.35 | 19.00 |
CMT3Y | 100 | 200 | 923 | 721.27 | 714 | 721.6 | 739 | -1.01 | 21.66 |
CMT4X | 150 | 200 | 1178 | 852.46 | 884 | 891.0 | 899 | 3.70 | 50.35 |
CMT4Y | 150 | 200 | 1178 | 852.46 | 849 | 853.2 | 857 | -0.41 | 50.06 |
CMT5X | 199 | 200 | 1509 | 1029.25 | 1115 | 1134.0 | 1151 | 8.33 | 86.07 |
CMT5Y | 199 | 200 | 1477 | 1029.25 | 1021 | 1042.8 | 1060 | -0.80 | 90.89 |
CMT11X | 120 | 200 | 1500 | 833.92 | 916 | 937.2 | 978 | 9.84 | 34.47 |
CMT11Y | 120 | 200 | 1500 | 830.39 | 785 | 803.0 | 835 | -5.47 | 38.87 |
CMT12X | 100 | 200 | 820 | 644.7 | 674 | 700.0 | 725 | 4.54 | 14.87 |
CMT12Y | 100 | 200 | 873 | 659.52 | 632 | 655.0 | 671 | -4.17 | 15.02 |
Overall Avg. | 1063.00 | 745.72 | 760.36 | 774.19 | 791.57 | 1.86 | 31.16 |
Instance | n | Q | Salhi and Nagy [51] | Goksal et al. [22] | SA-LS | ||||
Min | Avg | Max | Dev% | CPU (s) | |||||
CMT1X | 50 | 160 | 601 | 466.77 | 487 | 494.4 | 503 | 4.33 | 2.65 |
CMT1Y | 50 | 160 | 603 | 466.77 | 467 | 473.0 | 486 | 0.05 | 2.48 |
CMT2X | 75 | 140 | 873 | 668.77 | 698 | 709.0 | 726 | 4.37 | 4.58 |
CMT2Y | 75 | 140 | 924 | 663.25 | 672 | 683.6 | 699 | 1.32 | 5.32 |
CMT3X | 100 | 200 | 923 | 721.27 | 731 | 740.8 | 753 | 1.35 | 19.00 |
CMT3Y | 100 | 200 | 923 | 721.27 | 714 | 721.6 | 739 | -1.01 | 21.66 |
CMT4X | 150 | 200 | 1178 | 852.46 | 884 | 891.0 | 899 | 3.70 | 50.35 |
CMT4Y | 150 | 200 | 1178 | 852.46 | 849 | 853.2 | 857 | -0.41 | 50.06 |
CMT5X | 199 | 200 | 1509 | 1029.25 | 1115 | 1134.0 | 1151 | 8.33 | 86.07 |
CMT5Y | 199 | 200 | 1477 | 1029.25 | 1021 | 1042.8 | 1060 | -0.80 | 90.89 |
CMT11X | 120 | 200 | 1500 | 833.92 | 916 | 937.2 | 978 | 9.84 | 34.47 |
CMT11Y | 120 | 200 | 1500 | 830.39 | 785 | 803.0 | 835 | -5.47 | 38.87 |
CMT12X | 100 | 200 | 820 | 644.7 | 674 | 700.0 | 725 | 4.54 | 14.87 |
CMT12Y | 100 | 200 | 873 | 659.52 | 632 | 655.0 | 671 | -4.17 | 15.02 |
Overall Avg. | 1063.00 | 745.72 | 760.36 | 774.19 | 791.57 | 1.86 | 31.16 |
Intance | n | B | Avci and Topaloglu [5] | SA-LS | ||||||
Min | Avg | CPU (s) | Min | Avg | Max | Dev% | CPU (s) | |||
1 | 10 | 2 | 620.2 | 620.2 | 17.2 | 607.7 | 618.3 | 626.1 | -2.02 | 0.0 |
2 | 10 | 2 | 588.5 | 588.5 | 14.7 | 585.6 | 587.5 | 590.7 | -0.49 | 0.0 |
3 | 15 | 3 | 445.1 | 445.1 | 22.7 | 415.3 | 433.1 | 445.5 | -6.71 | 0.1 |
4 | 15 | 4 | 437.1 | 437.1 | 24.5 | 417.1 | 435.3 | 441.5 | -4.57 | 0.1 |
5 | 20 | 3 | 494 | 498.9 | 27.1 | 480.3 | 493.3 | 503.4 | -2.77 | 0.2 |
6 | 20 | 4 | 542.7 | 551.9 | 26.7 | 539.4 | 561.8 | 578.1 | -0.60 | 0.2 |
7 | 35 | 3 | 1108.2 | 1123.4 | 56.6 | 1126.6 | 1140.2 | 1158.3 | 1.66 | 1.0 |
8 | 35 | 3 | 1586.5 | 1601.2 | 54.7 | 1614.5 | 1673.8 | 1711.6 | 1.76 | 0.7 |
9 | 50 | 3 | 964.4 | 990.2 | 91.4 | 943.9 | 948.3 | 960.5 | -2.12 | 2.3 |
10 | 50 | 2 | 1197.7 | 1228.6 | 95.8 | 1177.7 | 1192.2 | 1206.3 | -1.67 | 2.0 |
11 | 75 | 3 | 1642.2 | 1673.9 | 143.8 | 1538.4 | 1572.9 | 1609.8 | -6.32 | 7.4 |
12 | 75 | 2 | 973.1 | 1002.5 | 164.9 | 969.5 | 982.1 | 1007.3 | -0.37 | 6.9 |
13 | 100 | 2 | 1299.5 | 1353.5 | 288.5 | 1262.3 | 1279.7 | 1311.0 | -2.86 | 22.7 |
14 | 100 | 2 | 1658.2 | 1678.2 | 310.3 | 1525.6 | 1545.0 | 1580.0 | -8.00 | 19.2 |
Overall Avg. | 968, 4 | 985, 2 | 95.6 | 943.1 | 961.7 | 980.7 | -2.51 | 4.5 |
Intance | n | B | Avci and Topaloglu [5] | SA-LS | ||||||
Min | Avg | CPU (s) | Min | Avg | Max | Dev% | CPU (s) | |||
1 | 10 | 2 | 620.2 | 620.2 | 17.2 | 607.7 | 618.3 | 626.1 | -2.02 | 0.0 |
2 | 10 | 2 | 588.5 | 588.5 | 14.7 | 585.6 | 587.5 | 590.7 | -0.49 | 0.0 |
3 | 15 | 3 | 445.1 | 445.1 | 22.7 | 415.3 | 433.1 | 445.5 | -6.71 | 0.1 |
4 | 15 | 4 | 437.1 | 437.1 | 24.5 | 417.1 | 435.3 | 441.5 | -4.57 | 0.1 |
5 | 20 | 3 | 494 | 498.9 | 27.1 | 480.3 | 493.3 | 503.4 | -2.77 | 0.2 |
6 | 20 | 4 | 542.7 | 551.9 | 26.7 | 539.4 | 561.8 | 578.1 | -0.60 | 0.2 |
7 | 35 | 3 | 1108.2 | 1123.4 | 56.6 | 1126.6 | 1140.2 | 1158.3 | 1.66 | 1.0 |
8 | 35 | 3 | 1586.5 | 1601.2 | 54.7 | 1614.5 | 1673.8 | 1711.6 | 1.76 | 0.7 |
9 | 50 | 3 | 964.4 | 990.2 | 91.4 | 943.9 | 948.3 | 960.5 | -2.12 | 2.3 |
10 | 50 | 2 | 1197.7 | 1228.6 | 95.8 | 1177.7 | 1192.2 | 1206.3 | -1.67 | 2.0 |
11 | 75 | 3 | 1642.2 | 1673.9 | 143.8 | 1538.4 | 1572.9 | 1609.8 | -6.32 | 7.4 |
12 | 75 | 2 | 973.1 | 1002.5 | 164.9 | 969.5 | 982.1 | 1007.3 | -0.37 | 6.9 |
13 | 100 | 2 | 1299.5 | 1353.5 | 288.5 | 1262.3 | 1279.7 | 1311.0 | -2.86 | 22.7 |
14 | 100 | 2 | 1658.2 | 1678.2 | 310.3 | 1525.6 | 1545.0 | 1580.0 | -8.00 | 19.2 |
Overall Avg. | 968, 4 | 985, 2 | 95.6 | 943.1 | 961.7 | 980.7 | -2.51 | 4.5 |
Intance | n | B | Avci and Topaloglu [5] | SA-LS | ||||||
Min | Avg | CPU (s) | Min | Avg | Max | Dev% | CPU (s) | |||
1 | 150 | 3 | 1499.4 | 1624.5 | 592.5 | 1468.4 | 1493.1 | 1520.3 | -2.07 | 157.8 |
2 | 150 | 3 | 2144.8 | 2152.5 | 548.9 | 2105.9 | 2168.6 | 2241.4 | -1.81 | 118.1 |
3 | 200 | 3 | 3673.1 | 3688.8 | 831.6 | 3188.5 | 3302.3 | 3335.5 | -13.19 | 116.0 |
4 | 200 | 2 | 2485.3 | 2682.5 | 919.4 | 2169.6 | 2181.8 | 2207.9 | -12.70 | 313.8 |
5 | 250 | 3 | 2639.6 | 2810.0 | 1448.1 | 2373.7 | 2428.6 | 2541.9 | -10.08 | 483.9 |
6 | 250 | 2 | 2549.8 | 2605.6 | 1521.3 | 2192.4 | 2219.6 | 2272.0 | -14.02 | 311.8 |
7 | 300 | 3 | 3205.0 | 3431.1 | 2440.4 | 2502.0 | 2523.7 | 2549.2 | -21.94 | 775.7 |
8 | 300 | 2 | 3252.8 | 3364.6 | 2518.2 | 2459.7 | 2533.5 | 2573.6 | -24.38 | 908.8 |
9 | 350 | 3 | 3457.9 | 3637.0 | 3770.1 | 3270.1 | 3380.9 | 3434.2 | -5.43 | 2385.5 |
10 | 350 | 2 | 3760.9 | 3897.5 | 3988.7 | 2262.0 | 2332.3 | 2409.0 | -39.85 | 1766.4 |
11 | 400 | 2 | 5809.5 | 6018.9 | 5662.4 | 3188.3 | 3236.3 | 3276.6 | -45.12 | 4466.4 |
12 | 400 | 2 | 4045.9 | 4447.0 | 5791.5 | 2871.9 | 2964.2 | 3048.6 | -29.02 | 3306.5 |
13 | 500 | 2 | 11008.8 | 12062.5 | 7200.0 | 7889.3 | 7948.0 | 8056.6 | -28.34 | 7789.4 |
14 | 550 | 2 | 12762.0 | 13046.3 | 7200.0 | 8987.9 | 9041.7 | 9089.8 | -29.57 | 7620.6 |
Overall Avg. | 4449.6 | 4676.3 | 3173.8 | 3352.1 | 3411.1 | 3468.3 | -19.82 | 2180.0 |
Intance | n | B | Avci and Topaloglu [5] | SA-LS | ||||||
Min | Avg | CPU (s) | Min | Avg | Max | Dev% | CPU (s) | |||
1 | 150 | 3 | 1499.4 | 1624.5 | 592.5 | 1468.4 | 1493.1 | 1520.3 | -2.07 | 157.8 |
2 | 150 | 3 | 2144.8 | 2152.5 | 548.9 | 2105.9 | 2168.6 | 2241.4 | -1.81 | 118.1 |
3 | 200 | 3 | 3673.1 | 3688.8 | 831.6 | 3188.5 | 3302.3 | 3335.5 | -13.19 | 116.0 |
4 | 200 | 2 | 2485.3 | 2682.5 | 919.4 | 2169.6 | 2181.8 | 2207.9 | -12.70 | 313.8 |
5 | 250 | 3 | 2639.6 | 2810.0 | 1448.1 | 2373.7 | 2428.6 | 2541.9 | -10.08 | 483.9 |
6 | 250 | 2 | 2549.8 | 2605.6 | 1521.3 | 2192.4 | 2219.6 | 2272.0 | -14.02 | 311.8 |
7 | 300 | 3 | 3205.0 | 3431.1 | 2440.4 | 2502.0 | 2523.7 | 2549.2 | -21.94 | 775.7 |
8 | 300 | 2 | 3252.8 | 3364.6 | 2518.2 | 2459.7 | 2533.5 | 2573.6 | -24.38 | 908.8 |
9 | 350 | 3 | 3457.9 | 3637.0 | 3770.1 | 3270.1 | 3380.9 | 3434.2 | -5.43 | 2385.5 |
10 | 350 | 2 | 3760.9 | 3897.5 | 3988.7 | 2262.0 | 2332.3 | 2409.0 | -39.85 | 1766.4 |
11 | 400 | 2 | 5809.5 | 6018.9 | 5662.4 | 3188.3 | 3236.3 | 3276.6 | -45.12 | 4466.4 |
12 | 400 | 2 | 4045.9 | 4447.0 | 5791.5 | 2871.9 | 2964.2 | 3048.6 | -29.02 | 3306.5 |
13 | 500 | 2 | 11008.8 | 12062.5 | 7200.0 | 7889.3 | 7948.0 | 8056.6 | -28.34 | 7789.4 |
14 | 550 | 2 | 12762.0 | 13046.3 | 7200.0 | 8987.9 | 9041.7 | 9089.8 | -29.57 | 7620.6 |
Overall Avg. | 4449.6 | 4676.3 | 3173.8 | 3352.1 | 3411.1 | 3468.3 | -19.82 | 2180.0 |
[1] |
Ö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 & Management Optimization, 2020 doi: 10.3934/jimo.2021002 |
[2] |
Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134 |
[3] |
Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 |
[4] |
M. Dambrine, B. Puig, G. Vallet. A mathematical model for marine dinoflagellates blooms. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 615-633. doi: 10.3934/dcdss.2020424 |
[5] |
Yuxin Zhang. The spatially heterogeneous diffusive rabies model and its shadow system. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020357 |
[6] |
Philippe Laurençot, Christoph Walker. Variational solutions to an evolution model for MEMS with heterogeneous dielectric properties. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 677-694. doi: 10.3934/dcdss.2020360 |
[7] |
Xin Zhang, Jie Xiong, Shuaiqi Zhang. Optimal reinsurance-investment and dividends problem with fixed transaction costs. Journal of Industrial & Management Optimization, 2021, 17 (2) : 981-999. doi: 10.3934/jimo.2020008 |
[8] |
Jakub Kantner, Michal Beneš. Mathematical model of signal propagation in excitable media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 935-951. doi: 10.3934/dcdss.2020382 |
[9] |
Björn Augner, Dieter Bothe. The fast-sorption and fast-surface-reaction limit of a heterogeneous catalysis model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 533-574. doi: 10.3934/dcdss.2020406 |
[10] |
Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219 |
[11] |
Martin Kalousek, Joshua Kortum, Anja Schlömerkemper. Mathematical analysis of weak and strong solutions to an evolutionary model for magnetoviscoelasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 17-39. doi: 10.3934/dcdss.2020331 |
[12] |
Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 |
[13] |
Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 |
[14] |
Weihong Guo, Yifei Lou, Jing Qin, Ming Yan. IPI special issue on "mathematical/statistical approaches in data science" in the Inverse Problem and Imaging. Inverse Problems & Imaging, 2021, 15 (1) : I-I. doi: 10.3934/ipi.2021007 |
[15] |
Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099 |
[16] |
Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020401 |
[17] |
Fabian Ziltener. Note on coisotropic Floer homology and leafwise fixed points. Electronic Research Archive, , () : -. doi: 10.3934/era.2021001 |
[18] |
Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020168 |
[19] |
Guangbin CAI, Yang Zhao, Wanzhen Quan, Xiusheng Zhang. Design of LPV fault-tolerant controller for hypersonic vehicle based on state observer. Journal of Industrial & Management Optimization, 2021, 17 (1) : 447-465. doi: 10.3934/jimo.2019120 |
[20] |
Philippe G. Ciarlet, Liliana Gratie, Cristinel Mardare. Intrinsic methods in elasticity: a mathematical survey. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 133-164. doi: 10.3934/dcds.2009.23.133 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]