More Web Proxy on the site http://driver.im/

research-article

A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows

Authors:

Hongwei LiuAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 316, Issue C

Pages 266 - 292

https://doi.org/10.1016/j.ins.2015.04.001

Published: 20 September 2015 Publication History

Abstract

This paper proposes a novel hybrid shuffled frog leaping algorithm (HSFLA) for vehicle routing problem with time windows (VRPTW). The diversity control strategy is developed to construct the memeplexes of the HSFLA and avoid ending the search prematurely. The modified clone selection procedure is presented to improve the quality of the solutions and bring more diversity to the population. Improved and extended extremal optimization (EO) with alternative move operators is also introduced to the exploitation of the algorithm. Furthermore, the adaptive soft time windows penalty measure is proposed to allow the existence of infeasible solutions in the evolution process. Our approach is estimated and compared with other state-of-the-art heuristics using Solomon and Cordeau VRPTW test sets. The experimental results show that the presented algorithm is very effective for handling VRPTW.

References

[1]

M.A. Ahandani, A diversified shuffled frog leaping: an application for parameter identification, Appl. Math. Comput., 239 (2014) 1-16.

[2]

M.A. Ahandani, H. Alavi-Rad, Opposition-based learning in shuffled frog leaping: an application for parameter identification, Inform. Sci., 291 (2015) 19-42.

Digital Library

[3]

D. Barbucha, A cooperative population learning algorithm for vehicle routing problem with time windows, Neurocomputing (2014).

[4]

A.K. Beheshti, S.R. Hejazi, A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window, Inform. Sci. 316 (2015) 598-615.

Digital Library

[5]

K.K. Bhattacharjee, S.P. Sarmah, Shuffled frog leaping algorithm and its application to 0/1 knapsack problem, Appl. Soft Comput., 19 (2014) 252-263.

[6]

S. Boettcher, A.G. Percus, Extremal optimization: methods derived from co-evolution, in: Proceedings of the Genetic and Evolutionary Computation Conference, New York, USA, 1999, pp. 101-106.

[7]

S. Boettcher, Extremal optimization for the Sherrington-Kirkpatrick spin glass, Eur. Phys. J. B, 46 (2005) 501-505.

[8]

O. Braysy, M. Gendreau, Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transport. Sci., 39 (2005) 104-118.

Digital Library

[9]

O. Braysy, M. Gendreau, Vehicle routing problem with time windows, part II: metaheuristics, Transport. Sci., 39 (2005) 19-39.

[10]

F.M. Burnet, The Clonal Selection Theory of Acquired Immunity, Cambridge University Press, 1959.

[11]

D. Cattaruzza, N. Absi, D. Feillet, D. Vigo, An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows, Comput. Oper. Res., 51 (2014) 257-267.

Digital Library

[12]

A. Chabrier, Vehicle routing problem with elementary shortest path based column generation, Comput. Oper. Res., 33 (2006) 2972-2990.

Digital Library

[13]

M.R. Chen, Y.Z. Lu, A novel elitist multi-objective optimization algorithm: multiobjective extremal optimization, Eur. J. Oper. Res., 188 (2008) 637-651.

[14]

J.F. Cordeau, G. Desaulniers, J. Desrosiers, M.M. Solomon, F. Soumis, VRP with time windows, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, vol. 9, Philadelphia, PA, 2002, pp. 157-93.

[15]

J.F. Cordeau, G. Laporte, A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows, J. Oper. Res. Soc., 52 (2001) 928-936.

[16]

J.F. Cordeau, G. Laporte, A. Mercier, An improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows, J. Oper. Res. Soc., 55 (2004) 542-546.

[17]

J.F. Cordeau, M. Maischberger, A parallel iterated tabu search heuristic for vehicle routing problems, Comput. Oper. Res., 39 (2012) 2033-2050.

Digital Library

[18]

W.P. Ding, Z.J. Guan, Q. Shi, J.D. Wang, A more efficient attribute self-adaptive co-evolutionary reduction algorithm by combining quantum elitist frogs and cloud model operators, Inform. Sci., 293 (2015) 214-234.

[19]

R. Dondo, J. Cerdá, A hybrid local improvement algorithm for large scale multi-depot vehicle routing problems with time windows, Comput. Chem. Eng., 33 (2009) 513-530.

[20]

Q. Duan, S. Sorooshian, V.K. Gupta, Effective and efficient global optimization for conceptual rainfall-runoff models, Water Resour. Res., 28 (1992) 1031-1051.

[21]

J.F. Ehmke, A.M. Campbell, T.L. Urban, Ensuring service levels in routing problems with time windows and stochastic travel times, Eur. J. Oper. Res. (2014).

[22]

E. Elbeltagi, T. Hegazy, D. Griersonb, A modified shuffled frog-leaping optimization algorithm: applications to project management, Struct. Infrastruct. Eng., 3 (2007) 53-60.

[23]

M. Eusuff, K. Lansey, Optimization of water distribution network design using the shuffled frog leaping algorithm, J. Water Resour. Plann. Manage., 129 (2003) 10-25.

[24]

C. Fang, L. Wang, An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem, Comput. Oper. Res., 39 (2012) 890-901.

Digital Library

[25]

P. Francis, K. Smilowitz, M. Tzur, The period vehicle routing problem and its extensions, in: The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, 2008, pp. 73-102.

[26]

H. Gehring, J. Homberger, A parallel two-phase metaheuristic for routing problems with time windows, Asia-Pacific J. Oper. Res., 18 (2001) 35-47.

[27]

M. Gendreau, C.D. Tarantilis, Solving Large-scale Vehicle Routing Problems with Time Windows: The State-of-the-art, Technical Report 2010-04, CIRRELT, Montreal, QC, Canada, 2010.

[28]

K. Ghoseiri, S.F. Ghannadpour, Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Appl. Soft Comput., 10 (2010) 1096-1107.

Digital Library

[29]

B. Golden, S. Raghavan, E. Wasil, The vehicle routing problem, latest advances and new challenges, in: Operations Research/Computer Science Interfaces Series, vol. 43, Springer, Berlin, 2008.

[30]

B. Golden, S. Raghavan, E. Wasil, The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, New York, 2008.

[31]

M. Hollander, D. Wolfe, Nonparametric Statistical Methods, Wiley-Interscience, New York, 1999.

[32]

L.X. Hong, An improved LNS algorithm for real-time vehicle routing problem with time windows, Comput. Oper. Res., 39 (2012) 151-163.

Digital Library

[33]

Y.Y. Hong, W.J. Liao, Optimal passive filter planning considering probabilistic parameters using cumulant and adaptive dynamic clone selection algorithm, Electr. Power Energy Syst., 45 (2013) 159-166.

[34]

S. Irnich, D. Villeneuve, The shortest path problem with resource constraints and k-cycle elimination, INFORMS J. Comput., 18 (2006) 391-406.

Digital Library

[35]

M. Jadidoleslam, A. Ebrahimi, Reliability constrained generation expansion planning by a modified shuffled frog leaping algorithm, Electr. Power Energy Syst., 64 (2015) 743-751.

[36]

M. Jepsen, S. Spoorendonk, B. Petersen, D. Pisinger, A Non-robust Branch-and- cut-and-price Algorithm for the Vehicle Routing Problem with Time Windows, Technical Report No. 06/03 ISSN: 0107-8283, Department of Computer Science, University of Copenhagen, 2006.

[37]

M. Jepsen, S. Spoorendonk, B. Petersen, D. Pisinger, Subset-row inequalities applied to the vehicle-routing problem with time windows, INFORMS J. Oper. Res., 56 (2008) 479-511.

[38]

B. Kallehauge, J. Larsenb, O.B.G. Madsena, Lagrangian duality applied to the vehicle routing problem with time windows, Comput. Oper. Res., 33 (2006) 1464-1487.

Digital Library

[39]

Z. Li, J. Cao, X. Zhao, W. Liu, Swarm intelligence for atmospheric compensation in free space optical communication-modified shuffled frog leaping algorithm, Opt. Laser Technol., 66 (2015) 89-97.

[40]

X. Li, J.P. Luo, M.R. Chen, N. Wang, An improved shuffled frog-leaping algorithm with extremal optimization for continuous optimization, Inform. Sci., 192 (2012) 143-151.

Digital Library

[41]

A. Lim, F. Wang, Multi-depot vehicle routing problem: a one-stage approach, IEEE Trans. Autom. Sci. Eng., 2 (2005) 397-402.

[42]

R.C. Liu, L.C. Jiao, X.R. Zhang, Y.Y. Li, Gene transposon based clone selection algorithm for automatic clustering, Inform. Sci., 204 (2012) 1-22.

Digital Library

[43]

J.P. Luo, M.R. Chen, Improved shuffled frog leaping algorithm and its multi-phase model for multi-depot vehicle routing problem, Expert Syst. Appl., 41 (2014) 2535-2545.

[44]

J.P. Luo, M.R. Chen, Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW, Comput. Ind. Eng., 72 (2014) 84-97.

[45]

M. Mavrovouniotis, S.X. Yang, Ant algorithms with immigrants schemes for the dynamic vehicle routing problem, Inform. Sci., 294 (2015) 456-477.

Digital Library

[46]

Y. Nagata, O. Brasy, W. Dullaert, A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Comput. Oper. Res., 37 (2010) 724-737.

Digital Library

[47]

I.S. Nieto, F.J. López, P.N. Herazo, Desarrollo y Codificación de un Modelo Matemático para la Optimización de un Problema de Ruteo de Vehículos con Múltiples Depósitos, in: Tenth LACCEI Latin American and Caribbean Conference (LACCEI'2012), Megaprojects: Building Infrastructure by Fostering Engineering Collaboration, Efficient and Effective Integration and Innovative Planning, Panama City, Panama, 2012.

[48]

T. Niknam, E. Azad-Farsani, M. Nayeripour, An efficient multi-objective modified shuffled frog leaping algorithm for distribution feeder reconfiguration problem, Eur. Trans. Electr. Power, 21 (2011) 721-739.

[49]

T. Niknam, M.R. Narimani, M. Jabbari, A.R. Malekpour, A modified shuffle frog leaping algorithm for multi-objective optimal power flow, Energy, 36 (2011) 6420-6432.

[50]

D. Pisinger, S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007) 2403-2435.

Digital Library

[51]

M. Polacek, S. Benkner, K.F. Doerner, R.F. Hartl, A cooperative and adaptive variable neighborhood search for the multi depot vehicle routing problem with time windows, BuRBusiness Res., 1 (2008) 207-218.

[52]

V. Pureza, R. Morabito, M. Reimann, Vehicle routing with multiple deliverymen: modeling and heuristic approaches for the VRPTW, Eur. J. Oper. Res., 218 (2012) 636-647.

[53]

A. Rahimi-Vahed, A.H. Mirzaei, A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem, Comput. Ind. Eng., 53 (2007) 642-666.

Digital Library

[54]

A.S. Reddy, K. Vaisakh, Shuffled differential evolution for economic dispatch with valve point loading effects, Electr. Power Syst. Res., 96 (2013) 237-245.

[55]

S. Rostami, D. O'Reilly, A. Shenfield, N. Bowring, A novel preference articulation operator for the evolutionary multi-objective optimisation of classifiers in concealed weapons detection, Inform. Sci., 295 (2015) 494-520.

Digital Library

[56]

P. Roy, P. Roy, A. Chakrabarti, Modified shuffled frog leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect, Appl. Soft Comput., 13 (2013) 4244-4252.

[57]

S. Safaei Arshi, A. Zolfaghari, S.M. Mirvakili, A multi-objective shuffled frog leaping algorithm for in-core fuel management optimization, Comput. Phys. Commun., 185 (2014) 2622-2628.

[58]

S. Samanta, M.K. Jha, Multi depot probabilistic vehicle routing problems with a time window: theory, solution and application, Int. J. Oper. Res. Inform. Syst., 2 (2011) 40-64.

[59]

G.G. Samuel, C.C.A. Rajan, Hybrid: particle swarm optimization-genetic algorithm and particle swarm optimization-shuffled frog leaping algorithm for long-term generator maintenance scheduling, Electr. Power Energy Syst., 65 (2015) 432-442.

[60]

P. Shaw, Using constraint programming and local search methods to solve VRPs, in: CP-98, Fourth International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, vol. 1520, 1998, pp. 17-31.

Digital Library

[61]

M.M. Solomon, J. Desrosiers, Time window constrained routing and scheduling problems, Transport. Sci., 22 (1988) 1-13.

Digital Library

[62]

E.G. Talbi, A taxonomy of hybrid metaheuristics, J. Heurist., 8 (2002) 541-564.

Digital Library

[63]

D. Taş, O. Jabali, T.V. Woensel, A vehicle routing problem with flexible time windows, Comput. Oper. Res., 52 (2014) 39-54.

Digital Library

[64]

S.R. Thangiah, A hybrid genetic algorithms, simulated annealing and tabu search heuristic for vehicle routing problems with time windows, in: Complex Structures, vol. III, CRC Press, 1999, pp. 347-381.

[65]

C.J. Ting, C.H. Chen, Combination of multiple ant colony system and simulated annealing for the multi depot vehicle routing problem with time windows, Transport. Res. Rec.: J. Transport. Res. Board, 2089 (2009) 85-92.

[66]

B. Tripathy, S. Dashb, S.K. Padhy, Multiprocessor scheduling and neural network training methods using shuffled frog-leaping algorithm, Comput. Ind. Eng., 80 (2015) 154-158.

Digital Library

[67]

Z. Ursani, D. Essam, D. Cornforth, R. Stocker, Localized genetic algorithm for vehicle routing problem with time windows, Appl. Soft Comput., 11 (2011) 5375-5390.

[68]

T. Vidal, T.G. Crainic, M. Gendreau, C. Prins, A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Comput. Oper. Res., 40 (2013) 475-489.

Digital Library

[69]

L. Wang, C. Fang, An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem Original, Inform. Sci., 181 (2011) 4804-4822.

Digital Library

[70]

Z. Wang, J. Zhang, X. Wang, A modified variable neighborhood search algorithm for the multi depot vehicle routing problem with time windows, Chin. J. Manage. Sci., 19 (2011) 99-109.

[71]

J. Wy, B. Kim, S. Kim, The rollon-rolloff waste collection vehicle routing problem with time windows, Eur. J. Oper. Res., 224 (2013) 466-476.

[72]

J.Y. Potvin, T. Kervahut, B.L. Garcia, J.M. Rousseau, The vehicle routing problem with timewindows, PartI: Tabu search, INFORMS J. Comput., 8 (1996) 158-164.

Digital Library

[73]

C. Yammani, S. Maheswarapu, S. Matam, Multiobjective optimization for optimal placement and size of DG using shuffled frog leaping algorithm, Energy Proc., 14 (2012) 990-995.

[74]

M.H.F. Zarandi, A. Hemmati, S. Davari, The multi-depot capacitated location-routing problem with fuzzy travel times, Expert Syst. Appl., 38 (2011) 10075-10084.

[75]

X. Zhang, Y. Zhang, Y. Shi, L. Zhao, C. Zou, Power control algorithm in cognitive radio system based on modified shuffled frog leaping algorithm, Int. J. Electron. Commun., 66 (2012) 448-454.

[76]

G.Y. Zhu, W.B. Zhang, An improved shuffled frog-leaping algorithm to optimize component pick-and-place sequencing optimization problem, Expert Syst. Appl., 41 (2014) 6818-6829.

Digital Library

Cited By

Selvakumar KSelvabharathi DPalanisamy RThamizh Thentral T(2023)CO2 Emission-Constrained Short-Term Unit Commitment Problem Using Shuffled Frog Leaping AlgorithmJournal of Electrical and Computer Engineering10.1155/2023/23366892023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/2336689
Cubukcu BYuzgec U(2023)Meliorated Crab Mating Optimization Algorithms for Capacitated Vehicle Routing ProblemSN Computer Science10.1007/s42979-023-02385-w5:1Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1007/s42979-023-02385-w
Elshaer RAwad H(2022)A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variantsComputers and Industrial Engineering10.1016/j.cie.2019.106242140:COnline publication date: 21-Apr-2022
https://dl.acm.org/doi/10.1016/j.cie.2019.106242
Show More Cited By

A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows

Recommendations

Evolutionary hyperheuristic for capacitated vehicle routing problem
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

In this paper a novel constructive hyperheuristic for CVRP is proposed. This hyperheuristic, called HyperPOEMS, is based on an evolutionary-based iterative local search algorithm. Its inherent characteristics make it capable of autonomously searching a ...
A Modified Shuffled Frog Leaping Algorithm with Genetic Mutation for Combinatorial Optimization
Computational Collective Intelligence. Technologies and Applications
Abstract
In this work, we propose modified versions of shuffled frog leaping algorithm (SFLA) to solve multiple knapsack problems (MKP). The proposed algorithm includes two important operations: repair operator and genetic mutation with a small ...
A mnemonic shuffled frog leaping algorithm with cooperation and mutation

Shuffled frog leaping algorithm (SFLA) has shown its good performance in many optimization problems. This paper proposes a Mnemonic Shuffled Frog Leaping Algorithm with Cooperation and Mutation (MSFLACM), which is inspired by the competition and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 316, Issue C

September 2015

616 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 20 September 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Selvakumar KSelvabharathi DPalanisamy RThamizh Thentral T(2023)CO2 Emission-Constrained Short-Term Unit Commitment Problem Using Shuffled Frog Leaping AlgorithmJournal of Electrical and Computer Engineering10.1155/2023/23366892023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/2336689
Cubukcu BYuzgec U(2023)Meliorated Crab Mating Optimization Algorithms for Capacitated Vehicle Routing ProblemSN Computer Science10.1007/s42979-023-02385-w5:1Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1007/s42979-023-02385-w
Elshaer RAwad H(2022)A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variantsComputers and Industrial Engineering10.1016/j.cie.2019.106242140:COnline publication date: 21-Apr-2022
https://dl.acm.org/doi/10.1016/j.cie.2019.106242
Zhou ZChen RGao JXing H(2022)A multi-objective optimization approach to package delivery by the crowd of occupied taxisKnowledge and Information Systems10.1007/s10115-022-01722-464:10(2713-2736)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10115-022-01722-4
Tang DZhao JYang JLiu ZCai Y(2021)An Evolutionary Frog Leaping Algorithm for Global Optimization Problems and ApplicationsComputational Intelligence and Neuroscience10.1155/2021/89281822021Online publication date: 14-Dec-2021
https://dl.acm.org/doi/10.1155/2021/8928182
Tang DLiu ZYang JZhao J(2019)Memetic frog leaping algorithm for global optimizationSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3662-323:21(11077-11105)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1007/s00500-018-3662-3
Yahyaoui HKrichen SDekdouk A(2018)A Decision Model Based on a GRASP Genetic Algorithm for Solving the Vehicle Routing ProblemInternational Journal of Applied Metaheuristic Computing10.4018/IJAMC.20180401049:2(72-90)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.4018/IJAMC.2018040104
Cao ZLiu KHu B(2018)An Improved MOEA/D for Order Scheduling Problem in Automated Warehouse2018 IEEE 14th International Conference on Automation Science and Engineering (CASE)10.1109/COASE.2018.8560504(797-802)Online publication date: 20-Aug-2018
https://dl.acm.org/doi/10.1109/COASE.2018.8560504
Zhu SWang YShang SZhao GWang J(2017)Probabilistic routing using multimodal dataNeurocomputing10.1016/j.neucom.2016.08.138253:C(49-55)Online publication date: 30-Aug-2017
https://dl.acm.org/doi/10.1016/j.neucom.2016.08.138
Ting CLiao XHuang YLiaw R(2017)Multi-vehicle selective pickup and delivery using metaheuristic algorithmsInformation Sciences: an International Journal10.1016/j.ins.2017.04.001406:C(146-169)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.ins.2017.04.001
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents