research-article

A New Hybrid Bat Algorithm Optimizing the Capacitated Vehicle Routing Problem

Authors:

Simon Kussman,

Yannick Godat,

Thomas Hanne,

Rolf DornbergerAuthors Info & Claims

ICCMB '20: Proceedings of the 2020 the 3rd International Conference on Computers in Management and Business

Pages 107 - 111

https://doi.org/10.1145/3383845.3383880

Published: 05 April 2020 Publication History

Get Access

Abstract

The Capacitated Vehicle Routing Problem (CVRP), an extension of the Traveling Salesman Problem with two added constraints, a local depot and a capacity constraint for each vehicle, is solved by a Hybrid Bat Algorithm (HBA). This paper investigates how the standard Bat Algorithm must be extended to become a HBA being able to solve the CVRP. The Hybrid Bat Algorithm is tested and compared to three other optimization algorithms for the CVRP, the Clarke & Wright Savings Algorithm, the Holmes and Parker Algorithm, and the Fisher and Jaikumar Method. It is discussed how the HBA is able to deliver decent solutions of the CVRP.

References

[1]

G. B. Dantzig, J. H. Ramser (1959). The truck dispatching problem. Management Science, 6(1), 8091.

Google Scholar

[2]

X.-S. Yang (2010), A New Metaheuristic Bat-Inspired Algorithm, in: Nature Inspired Cooperative Strategies for Optimization (NISCO 2010) (Eds. J. R. Gonzalez et al.), Studies in Computational Intelligence, Springer Berlin, 284, Springer, 65--74.

Crossref

Google Scholar

[3]

G. Clarke, J. W. Wright (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568581.

Google Scholar

[4]

T. J. Ai, V. Kachitvichyanukul, "Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem," Computers and Industrial Engineering, vol. 56, no. 1, pp. 380--387, 2009.

Digital Library

Google Scholar

[5]

W. Y. Szeto, Y. Wu, and S. C. Ho, "An artificial bee colony algorithm for the capacitated vehicle routing problem," European Journal of Operational Research, vol. 215, no. 1, pp. 126--135, 2011.

Crossref

Google Scholar

[6]

J. Faulin, A. Juan, F. Lera and S. Grasman, "Solving the Capacitated Vehicle Routing Problem with Environmental Criteria Based on Real Estimations in Road Transportation: A Case Study", Procedia Social and Behavioral Sciences 20 (2011) pp. 323--334.

Crossref

Google Scholar

[7]

Z. Borcinovà, "Two models of the capacitated vehicle routing problem" Croatian Operational Research Review (CRORR 8) 2017, pp. 463--469.

Crossref

Google Scholar

[8]

Y. Zhou, J. Xie and H. Zheng, "A Hybrid Bat Algorithm with Path Relinking for Capacitated Vehicle Routing Problem", Mathematical Problems in Engineering Volume 2013, Article ID 392789.

Google Scholar

[9]

M. A. H. Akhand, Z. J. Peya, T. Sultana and Al-Mahmud, "Solving Capacitated Vehicle Routing Problem with Route Optimization using Swarm Intelligence, IEEE Int. Conf. EICT 2015, pp. 112--117, 2015.

Google Scholar

[10]

M. Islam, S. Ghosh and M. Rahman, "Solving Capacitated Vehicle Routing Problem by Using Heuristic Approaches: A Case Study", Global Engineering, Science and Technology Conf. BIAM Foundation, Dhaka, 2015.

Google Scholar

[11]

T. Caric, A. Galic, J. Fosin, et al. "A Modelling and Optimization Framework for Real-World Vehicle Routing Problems," Vehicle Routing Problem, In-The, 2008.

Google Scholar

Cited By

View all

Stamadianos TTaxidou AMarinaki MMarinakis Y(2024)Swarm intelligence and nature inspired algorithms for solving vehicle routing problems: a surveyOperational Research10.1007/s12351-024-00862-524:3Online publication date: 23-Aug-2024
https://doi.org/10.1007/s12351-024-00862-5
Liu LGu RHuo JZhou Y(2023)Origin-Oriented Shuffled Frog Leaping Vehicle Routing Multiobjective Optimization AlgorithmJournal of Database Management10.4018/JDM.32154934:3(1-24)Online publication date: 28-Apr-2023
https://dl.acm.org/doi/10.4018/JDM.321549

Index Terms

A New Hybrid Bat Algorithm Optimizing the Capacitated Vehicle Routing Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial optimization

Recommendations

A new hybrid matheuristic of GRASP and VNS based on constructive heuristics, set-covering and set-partitioning formulations applied to the capacitated vehicle routing problem
Abstract
This paper develops a hybrid matheuristic in two stages to solve Capacitated Vehicle Routing Problem (CVRP) by applying Greedy Randomized Adaptive Search Procedure (GRASP), mathematical models and Variable Neighborhood Search (VNS). ...
Highlights
- We develop a new hybrid matheuristic of GRASP, VNS, SCP and SPP to solve CVRP.
- ...
Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem

We aim at developing a new hybrid large neighbourhood search algorithm for CVRP.Our algorithm incorporates solution construction heuristic of ACO into LNS.The proposed hybrid LNS-ACO algorithm is tested on a set of CVRP instances.Computational results ...
A new Hybrid Electromagnetism-like Algorithm for capacitated vehicle routing problems

Vehicle routing problems have been extensively analyzed within the last few decades, since they play a central role in optimization of distribution networks. This paper presents a new Hybrid Electromagnetism-like Algorithm for solving capacitated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCMB '20: Proceedings of the 2020 the 3rd International Conference on Computers in Management and Business

January 2020

303 pages

ISBN:9781450376778

DOI:10.1145/3383845

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

Univ. of Manchester: University of Manchester
The Hong Kong Polytechnic: The Hong Kong Polytechnic University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 April 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICCMB 2020

ICCMB 2020: 2020 The 3rd International Conference on Computers in Management and Business

January 31 - February 2, 2020

Tokyo, Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
129
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Stamadianos TTaxidou AMarinaki MMarinakis Y(2024)Swarm intelligence and nature inspired algorithms for solving vehicle routing problems: a surveyOperational Research10.1007/s12351-024-00862-524:3Online publication date: 23-Aug-2024
https://doi.org/10.1007/s12351-024-00862-5
Liu LGu RHuo JZhou Y(2023)Origin-Oriented Shuffled Frog Leaping Vehicle Routing Multiobjective Optimization AlgorithmJournal of Database Management10.4018/JDM.32154934:3(1-24)Online publication date: 28-Apr-2023
https://dl.acm.org/doi/10.4018/JDM.321549

View Options

Login options

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

Cited By

Index Terms

Recommendations

A new hybrid matheuristic of GRASP and VNS based on constructive heuristics, set-covering and set-partitioning formulations applied to the capacitated vehicle routing problem

Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem

A new Hybrid Electromagnetism-like Algorithm for capacitated vehicle routing problems