American Institute of Mathematical Sciences

Advanced
  • 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

Bariş Keçeci 1,, , Fulya Altıparmak 1,2, and  İmdat Kara 1,2,

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.

Keywords: Vehicle routing problem, simultaneous pickup-delivery, heterogeneous fixed fleet, mathematical model, simulated annealing algorithm.
Mathematics Subject Classification: Primary: 90B06, 90C11, 90C59; Secondary: 90C27.
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. 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.  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. 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.  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. 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.  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'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.  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. 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.  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. 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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Figure 1.  Relationship between the HVRPSPD and its variants
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Representation of the HVRPSPD solution with 10 customers and three routes
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Inter-route neighborhood structures
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Intra-route neighborhood structures
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Pseudo code of the LS
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Pseudo code of SA-LS
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  The convergence of SA-LS with different initial temperature values
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  The convergence of SA-LS with different final temperature values
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  The convergence of SA-LS with different cooling rate values
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  Pseudo code of the NN
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  Pseudo code of the PCWS
Figure Options

Download full-size image

Download as PowerPoint slide

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.
Table Options

Download as excel

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].
Table Options

Download as excel

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
Table Options

Download as excel

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).
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

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]

Copyright © 2021 American Institute of Mathematical Sciences