Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution
Vehicle routing problem (VRP) is one of the many difficult issues that have no perfect solutions yet. Many researchers over the last few decades have established numerous researches and used many methods with different techniques to handle it. But, for all research, finding the lowest cost is very c...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier B.V.
2017
|
| Subjects: | |
| Online Access: | http://eprints.uthm.edu.my/3898/1/AJ%202017%20%28527%29.pdf |
| _version_ | 1825637164407324672 |
|---|---|
| author | Mohammed, Mazin Abed Abd Ghani, Mohd Khanapi Hamed, Raed Ibraheem A. Mostafa, Salama Ahmed Ibrahim, Dheyaa Jameel, Humam Khaled Alallah, Ahmed Hamed |
| author_facet | Mohammed, Mazin Abed Abd Ghani, Mohd Khanapi Hamed, Raed Ibraheem A. Mostafa, Salama Ahmed Ibrahim, Dheyaa Jameel, Humam Khaled Alallah, Ahmed Hamed |
| author_sort | Mohammed, Mazin Abed |
| collection | UTHM |
| description | Vehicle routing problem (VRP) is one of the many difficult issues that have no perfect solutions yet. Many researchers over the last few decades have established numerous researches and used many methods with different techniques to handle it. But, for all research, finding the lowest cost is very complex. However, they have managed to come up with approximate solutions that differ in efficiencies depending on the search space. Problem: In this study the problem is as follows: have a number of vehicles which are used for transporting applications to instance place. Each vehicle starts from a main location at different times every day. The vehicle picks up applications from start locations to the instance place in many different routes and return back to the start location in at specific times every day, starting from early morning until the end of official working hours, on the following conditions: (1) Every location will be visited once in each route, and (2) The capacity of each vehicle is enough for all applications included in each route. Objectives: Our paper attempt to find an optimal route result for VRP by using K-Nearest Neighbor Algorithm (KNNA). To achieve an optimal solution for VRP with the accompanying targets: (1) To reduce the distance and the time for all paths this leads to speedy the transportation of customers to their locations, (2) To implement the capacitated vehicle routing problem (CVRP) model for optimizing the solutions. Approach: The approach has been presented based on two phases: firstly, the algorithms have been adapted to solve the research problem, where its procedure is different than the common algorithm. The structure of the algorithm is designed so that the program does not require a large database to store the population, which speeds up the implementation of the program execution to obtain the solution; secondly, the algorithm has proven its success in solving the problem and finds a shortest route. For the purpose of testing the algorithm’s capability and reliability, it was applied to solve the same problem online validated and it achieved success in finding a shorter route. Finding: The findings outcome from this study have shown that: (1) A universal listed of dynamic KNNACVRP; (2) Identified and built up an assessment measure for KNNACVRP; (3) Highlight the strategies, based KNNA operations, for choosing the most ideal way (4) KNNA finds a shorter route for VRP paths. The extent of lessening the distance for each route is generally short, but the savings in the distance becomes more noteworthy while figuring the aggregate distances traveled by all transports day by day or month to month. This applies likewise to the time calculate that has been decreased marginally in view of the rate of reduction in the distances of the paths. |
| first_indexed | 2024-03-05T21:47:04Z |
| format | Article |
| id | uthm.eprints-3898 |
| institution | Universiti Tun Hussein Onn Malaysia |
| language | English |
| last_indexed | 2024-03-05T21:47:04Z |
| publishDate | 2017 |
| publisher | Elsevier B.V. |
| record_format | dspace |
| spelling | uthm.eprints-38982021-11-22T06:38:45Z http://eprints.uthm.edu.my/3898/ Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution Mohammed, Mazin Abed Abd Ghani, Mohd Khanapi Hamed, Raed Ibraheem A. Mostafa, Salama Ahmed Ibrahim, Dheyaa Jameel, Humam Khaled Alallah, Ahmed Hamed QA299.6-433 Analysis Vehicle routing problem (VRP) is one of the many difficult issues that have no perfect solutions yet. Many researchers over the last few decades have established numerous researches and used many methods with different techniques to handle it. But, for all research, finding the lowest cost is very complex. However, they have managed to come up with approximate solutions that differ in efficiencies depending on the search space. Problem: In this study the problem is as follows: have a number of vehicles which are used for transporting applications to instance place. Each vehicle starts from a main location at different times every day. The vehicle picks up applications from start locations to the instance place in many different routes and return back to the start location in at specific times every day, starting from early morning until the end of official working hours, on the following conditions: (1) Every location will be visited once in each route, and (2) The capacity of each vehicle is enough for all applications included in each route. Objectives: Our paper attempt to find an optimal route result for VRP by using K-Nearest Neighbor Algorithm (KNNA). To achieve an optimal solution for VRP with the accompanying targets: (1) To reduce the distance and the time for all paths this leads to speedy the transportation of customers to their locations, (2) To implement the capacitated vehicle routing problem (CVRP) model for optimizing the solutions. Approach: The approach has been presented based on two phases: firstly, the algorithms have been adapted to solve the research problem, where its procedure is different than the common algorithm. The structure of the algorithm is designed so that the program does not require a large database to store the population, which speeds up the implementation of the program execution to obtain the solution; secondly, the algorithm has proven its success in solving the problem and finds a shortest route. For the purpose of testing the algorithm’s capability and reliability, it was applied to solve the same problem online validated and it achieved success in finding a shorter route. Finding: The findings outcome from this study have shown that: (1) A universal listed of dynamic KNNACVRP; (2) Identified and built up an assessment measure for KNNACVRP; (3) Highlight the strategies, based KNNA operations, for choosing the most ideal way (4) KNNA finds a shorter route for VRP paths. The extent of lessening the distance for each route is generally short, but the savings in the distance becomes more noteworthy while figuring the aggregate distances traveled by all transports day by day or month to month. This applies likewise to the time calculate that has been decreased marginally in view of the rate of reduction in the distances of the paths. Elsevier B.V. 2017 Article PeerReviewed text en http://eprints.uthm.edu.my/3898/1/AJ%202017%20%28527%29.pdf Mohammed, Mazin Abed and Abd Ghani, Mohd Khanapi and Hamed, Raed Ibraheem and A. Mostafa, Salama and Ahmed Ibrahim, Dheyaa and Jameel, Humam Khaled and Alallah, Ahmed Hamed (2017) Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution. Journal of Computational Science, 21 (NIL). pp. 232-240. ISSN 1877-7503 http://dx.doi.org/10.1016/j.jocs.2017.04.012 |
| spellingShingle | QA299.6-433 Analysis Mohammed, Mazin Abed Abd Ghani, Mohd Khanapi Hamed, Raed Ibraheem A. Mostafa, Salama Ahmed Ibrahim, Dheyaa Jameel, Humam Khaled Alallah, Ahmed Hamed Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution |
| title | Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution |
| title_full | Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution |
| title_fullStr | Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution |
| title_full_unstemmed | Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution |
| title_short | Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution |
| title_sort | solving vehicle routing problem by using improved k nearest neighbor algorithm for best solution |
| topic | QA299.6-433 Analysis |
| url | http://eprints.uthm.edu.my/3898/1/AJ%202017%20%28527%29.pdf |
| work_keys_str_mv | AT mohammedmazinabed solvingvehicleroutingproblembyusingimprovedknearestneighboralgorithmforbestsolution AT abdghanimohdkhanapi solvingvehicleroutingproblembyusingimprovedknearestneighboralgorithmforbestsolution AT hamedraedibraheem solvingvehicleroutingproblembyusingimprovedknearestneighboralgorithmforbestsolution AT amostafasalama solvingvehicleroutingproblembyusingimprovedknearestneighboralgorithmforbestsolution AT ahmedibrahimdheyaa solvingvehicleroutingproblembyusingimprovedknearestneighboralgorithmforbestsolution AT jameelhumamkhaled solvingvehicleroutingproblembyusingimprovedknearestneighboralgorithmforbestsolution AT alallahahmedhamed solvingvehicleroutingproblembyusingimprovedknearestneighboralgorithmforbestsolution |