• 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
doi: 10.3934/jimo.2020012

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

* Corresponding author: Bariş Keçeci

Received  November 2018 Revised  July 2019 Published  January 2020

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.

Citation: 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 & Management Optimization, doi: 10.3934/jimo.2020012
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.  Google Scholar

[2]

S. AllahyariM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

R. BaldacciP. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

G. CallejaA. CorominasA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

M. Dell'AmicoG. 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.  Google Scholar

[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.  Google Scholar

[20]

M. GendreauG. LaporteC. 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.  Google Scholar

[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.  Google Scholar

[22]

F. P. GoksalI. 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.  Google Scholar

[23]

B. GoldenA. AssadL. 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.  Google Scholar

[24]

A. HoffH. AnderssonM. ChristiansenG. 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.  Google Scholar

[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.  Google Scholar

[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. JuanJ. FaulinJ. Caceres-CruzB. 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.  Google Scholar

[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.  Google Scholar

[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çeciF. 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.  Google Scholar

[33]

S. KirkpatrickC. D. GelattJr . and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.  doi: 10.1126/science.220.4598.671.  Google Scholar

[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.  Google Scholar

[35]

T. W. LiaoP.-C. ChangR. 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.  Google Scholar

[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. LiuW. 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.  Google Scholar

[38]

M. A. MasmoudiM. HosnyK. 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.  Google Scholar

[39]

N. MetropolisA. W. RosenbluthM. N. RosenbluthA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. ParaskevopoulosP. P. RepoussisC. D. TarantilisG. 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.  Google Scholar

[45]

P. H. V. PennaA. 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.  Google Scholar

[46]

O. PolatC. B. KalayciO. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[53]

L. SimeonovaN. WassanS. 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.  Google Scholar

[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.  Google Scholar

[55]

A. SubramanianL. M. d. A. DrummondC. BentesL. 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. SubramanianP. H. V. PennaE. 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.  Google Scholar

[57]

A. SubramanianE. UchoaA. 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.  Google Scholar

[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.  Google Scholar

[59]

E.-G. Talbi, A taxonomy of hybrid metaheuristics, Journal of heuristics, 8 (2002), 541-564.   Google Scholar

[60]

C. BlumJ. PuchingerG. 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.  Google Scholar

[61]

C. D. TarantilisC. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[67]

Y. ZhangM. Y. QiW.-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.  Google Scholar

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.  Google Scholar

[2]

S. AllahyariM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

R. BaldacciP. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

G. CallejaA. CorominasA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

M. Dell'AmicoG. 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.  Google Scholar

[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.  Google Scholar

[20]

M. GendreauG. LaporteC. 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.  Google Scholar

[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.  Google Scholar

[22]

F. P. GoksalI. 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.  Google Scholar

[23]

B. GoldenA. AssadL. 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.  Google Scholar

[24]

A. HoffH. AnderssonM. ChristiansenG. 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.  Google Scholar

[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.  Google Scholar

[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. JuanJ. FaulinJ. Caceres-CruzB. 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.  Google Scholar

[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.  Google Scholar

[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çeciF. 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.  Google Scholar

[33]

S. KirkpatrickC. D. GelattJr . and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.  doi: 10.1126/science.220.4598.671.  Google Scholar

[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.  Google Scholar

[35]

T. W. LiaoP.-C. ChangR. 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.  Google Scholar

[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. LiuW. 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.  Google Scholar

[38]

M. A. MasmoudiM. HosnyK. 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.  Google Scholar

[39]

N. MetropolisA. W. RosenbluthM. N. RosenbluthA. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. ParaskevopoulosP. P. RepoussisC. D. TarantilisG. 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.  Google Scholar

[45]

P. H. V. PennaA. 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.  Google Scholar

[46]

O. PolatC. B. KalayciO. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[53]

L. SimeonovaN. WassanS. 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.  Google Scholar

[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.  Google Scholar

[55]

A. SubramanianL. M. d. A. DrummondC. BentesL. 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. SubramanianP. H. V. PennaE. 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.  Google Scholar

[57]

A. SubramanianE. UchoaA. 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.  Google Scholar

[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.  Google Scholar

[59]

E.-G. Talbi, A taxonomy of hybrid metaheuristics, Journal of heuristics, 8 (2002), 541-564.   Google Scholar

[60]

C. BlumJ. PuchingerG. 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.  Google Scholar

[61]

C. D. TarantilisC. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[67]

Y. ZhangM. Y. QiW.-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.  Google Scholar

Figure 1.  Relationship between the HVRPSPD and its variants
Figure 2.  Representation of the HVRPSPD solution with 10 customers and three routes
Figure 3.  Inter-route neighborhood structures
Figure 4.  Intra-route neighborhood structures
Figure 5.  Pseudo code of the LS
Figure 6.  Pseudo code of SA-LS
Figure 7.  The convergence of SA-LS with different initial temperature values
Figure 8.  The convergence of SA-LS with different final temperature values
Figure 9.  The convergence of SA-LS with different cooling rate values
Figure 10.  Pseudo code of the NN
Figure 11.  Pseudo code of the PCWS
Table 1.  Characteristics of the test problems
Problems n # of instances
Small and medium-size 20 4x($ 8^a $+$ 18^b $)
25 4x($ 8^a $+$ 18^b $)
30 4x($ 8^a $+$ 18^b $)
35 4x($ 8^a $+$ 18^b $)
40 4x($ 8^a $+$ 18^b $)
Large-size 50 4x$ 4^a $
75 4x$ 2^a $
100 4x($ 2^a $+$ 18^b $)
aTaillard's [58] test problems, bLiu and Shen's [36] test problems.
Problems n # of instances
Small and medium-size 20 4x($ 8^a $+$ 18^b $)
25 4x($ 8^a $+$ 18^b $)
30 4x($ 8^a $+$ 18^b $)
35 4x($ 8^a $+$ 18^b $)
40 4x($ 8^a $+$ 18^b $)
Large-size 50 4x$ 4^a $
75 4x$ 2^a $
100 4x($ 2^a $+$ 18^b $)
aTaillard's [58] test problems, bLiu and Shen's [36] test problems.
Table 2.  Computational results of SA-LS on small and medium-size test problems
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].
Table 3.  Comparison of SA-LS with NN and CWS on large-size test problems
n Type $ \text{Dev%}_{NN} $ $ \text{Dev%}_{CWT} $ $ \text{Dev%}_{MIPLB} $ 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 $ \text{Dev%}_{NN} $ $ \text{Dev%}_{CWT} $ $ \text{Dev%}_{MIPLB} $ 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
Table 4.  Comparison of SA-LS with HVRP test instances
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).
Table 5.  Comparison of SA-LS with VRPSPD test instances
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
Table 6.  Comparison of SA-LS on set 1 test instances
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
Table 7.  Comparison of SA-LS on set 2 test instances
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]

Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1147-1166. doi: 10.3934/dcdss.2019079

[2]

Melis Alpaslan Takan, Refail Kasimbeyli. Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020059

[3]

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 & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435

[4]

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

[5]

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, 2019  doi: 10.3934/jimo.2019134

[6]

T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53

[7]

Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200

[8]

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 & Management Optimization, 2020  doi: 10.3934/jimo.2020045

[9]

Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026

[10]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

[11]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

[12]

Yukang He, Zhengwen He, Nengmin Wang. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020077

[13]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[14]

Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701

[15]

Linet Ozdamar, Dilek Tuzun Aksu, Elifcan Yasa, Biket Ergunes. Disaster relief routing in limited capacity road networks with heterogeneous flows. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1367-1380. doi: 10.3934/jimo.2018011

[16]

Nurhadi Siswanto, Stefanus Eko Wiratno, Ahmad Rusdiansyah, Ruhul Sarker. Maritime inventory routing problem with multiple time windows. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091

[17]

Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial & Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87

[18]

Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1065-1084. doi: 10.3934/jimo.2016062

[19]

Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119

[20]

Alexander V. Budyansky, Kurt Frischmuth, Vyacheslav G. Tsybulin. Cosymmetry approach and mathematical modeling of species coexistence in a heterogeneous habitat. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 547-561. doi: 10.3934/dcdsb.2018196

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]