A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities
Smart logistics is an indispensable building block in smart cities development that requires solving the challenge of efficiently serving the demands of geographically distributed customers by a fleet of vehicles. It consists of a very well-known NP-hard complex optimization problem, which is known...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/13/10/1923 |
| _version_ | 1797513068640468992 |
|---|---|
| author | Mohammad Sajid Jagendra Singh Raza Abbas Haidri Mukesh Prasad Vijayakumar Varadarajan Ketan Kotecha Deepak Garg |
| author_facet | Mohammad Sajid Jagendra Singh Raza Abbas Haidri Mukesh Prasad Vijayakumar Varadarajan Ketan Kotecha Deepak Garg |
| author_sort | Mohammad Sajid |
| collection | DOAJ |
| description | Smart logistics is an indispensable building block in smart cities development that requires solving the challenge of efficiently serving the demands of geographically distributed customers by a fleet of vehicles. It consists of a very well-known NP-hard complex optimization problem, which is known as the capacitated vehicle routing problem (CVRP). The CVRP has widespread real-life applications such as delivery in smart logistics, the pharmaceutical distribution of vacancies, disaster relief efforts, and others. In this work, a novel giant tour best cost crossover (GTBCX) operator is proposed which works stochastically to search for the optimal solutions of the CVRP. An NSGA-II-based routing algorithm employing GTBCX is also proposed to solve the CVRP to minimize the total distance traveled as well as to minimize the longest route length. The simulated study is performed on 88 benchmark CVRP instances to validate the success of our proposed GTBCX operator against the nearest neighbor crossover (NNX) and edge assembly crossover (EAX) operators. The rigorous simulation study shows that the GTBCX is a powerful operator and helps to find results that are superior in terms of the overall distance traveled, length of the longest route, quality, and number of Pareto solutions. This work employs a multi-objective optimization algorithm to solve the capacitated vehicle routing problem (CVRP), where the CVRP is represented in the form of a two-dimensional graph. To compute the values’ objective functions, the distance between two nodes in the graph is considered symmetric. This indicates that the genetic algorithm complex optimization algorithm is employed to solve CVRP, which is a symmetry distance-based graph. |
| first_indexed | 2024-03-10T06:10:29Z |
| format | Article |
| id | doaj.art-7b86bd93e73c401aa1376efe9af15621 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T06:10:29Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-7b86bd93e73c401aa1376efe9af156212023-11-22T20:11:07ZengMDPI AGSymmetry2073-89942021-10-011310192310.3390/sym13101923A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart CitiesMohammad Sajid0Jagendra Singh1Raza Abbas Haidri2Mukesh Prasad3Vijayakumar Varadarajan4Ketan Kotecha5Deepak Garg6Department of Computer Science, Aligarh Muslim University, Aligarh 202002, IndiaSchool of Engineering and Applied Science, Bennett University, Greater Noida 203206, IndiaDepartment of Computer Science and Information Technology, Khwaja Moinuddin Chishti Language University, Luckhnow 226013, IndiaSchool of Computer Science, Faculty of Engineering, University of Technology Sydney, Sydney, NSW 2007, AustraliaSchool of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, AustraliaSymbiosis Centre for Applied Artificial Intelligence, Faculty of Engineering, Symbiosis International University, Pune 412115, IndiaSchool of Engineering and Applied Science, Bennett University, Greater Noida 203206, IndiaSmart logistics is an indispensable building block in smart cities development that requires solving the challenge of efficiently serving the demands of geographically distributed customers by a fleet of vehicles. It consists of a very well-known NP-hard complex optimization problem, which is known as the capacitated vehicle routing problem (CVRP). The CVRP has widespread real-life applications such as delivery in smart logistics, the pharmaceutical distribution of vacancies, disaster relief efforts, and others. In this work, a novel giant tour best cost crossover (GTBCX) operator is proposed which works stochastically to search for the optimal solutions of the CVRP. An NSGA-II-based routing algorithm employing GTBCX is also proposed to solve the CVRP to minimize the total distance traveled as well as to minimize the longest route length. The simulated study is performed on 88 benchmark CVRP instances to validate the success of our proposed GTBCX operator against the nearest neighbor crossover (NNX) and edge assembly crossover (EAX) operators. The rigorous simulation study shows that the GTBCX is a powerful operator and helps to find results that are superior in terms of the overall distance traveled, length of the longest route, quality, and number of Pareto solutions. This work employs a multi-objective optimization algorithm to solve the capacitated vehicle routing problem (CVRP), where the CVRP is represented in the form of a two-dimensional graph. To compute the values’ objective functions, the distance between two nodes in the graph is considered symmetric. This indicates that the genetic algorithm complex optimization algorithm is employed to solve CVRP, which is a symmetry distance-based graph.https://www.mdpi.com/2073-8994/13/10/1923smart logisticscapacitated vehicle routing problemPareto optimalitynon-dominated sorting |
| spellingShingle | Mohammad Sajid Jagendra Singh Raza Abbas Haidri Mukesh Prasad Vijayakumar Varadarajan Ketan Kotecha Deepak Garg A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities Symmetry smart logistics capacitated vehicle routing problem Pareto optimality non-dominated sorting |
| title | A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities |
| title_full | A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities |
| title_fullStr | A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities |
| title_full_unstemmed | A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities |
| title_short | A Novel Algorithm for Capacitated Vehicle Routing Problem for Smart Cities |
| title_sort | novel algorithm for capacitated vehicle routing problem for smart cities |
| topic | smart logistics capacitated vehicle routing problem Pareto optimality non-dominated sorting |
| url | https://www.mdpi.com/2073-8994/13/10/1923 |
| work_keys_str_mv | AT mohammadsajid anovelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT jagendrasingh anovelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT razaabbashaidri anovelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT mukeshprasad anovelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT vijayakumarvaradarajan anovelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT ketankotecha anovelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT deepakgarg anovelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT mohammadsajid novelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT jagendrasingh novelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT razaabbashaidri novelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT mukeshprasad novelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT vijayakumarvaradarajan novelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT ketankotecha novelalgorithmforcapacitatedvehicleroutingproblemforsmartcities AT deepakgarg novelalgorithmforcapacitatedvehicleroutingproblemforsmartcities |