Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows.
This paper presents a bee colony optimisation (BCO) algorithm to tackle the vehicle routing problem with time window (VRPTW). The VRPTW involves recovering an ideal set of routes for a fleet of vehicles serving a defined number of customers. The BCO algorithm is a population-based algorithm that mim...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2015-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC4488911?pdf=render |
| _version_ | 1818597933967212544 |
|---|---|
| author | Sana Jawarneh Salwani Abdullah |
| author_facet | Sana Jawarneh Salwani Abdullah |
| author_sort | Sana Jawarneh |
| collection | DOAJ |
| description | This paper presents a bee colony optimisation (BCO) algorithm to tackle the vehicle routing problem with time window (VRPTW). The VRPTW involves recovering an ideal set of routes for a fleet of vehicles serving a defined number of customers. The BCO algorithm is a population-based algorithm that mimics the social communication patterns of honeybees in solving problems. The performance of the BCO algorithm is dependent on its parameters, so the online (self-adaptive) parameter tuning strategy is used to improve its effectiveness and robustness. Compared with the basic BCO, the adaptive BCO performs better. Diversification is crucial to the performance of the population-based algorithm, but the initial population in the BCO algorithm is generated using a greedy heuristic, which has insufficient diversification. Therefore the ways in which the sequential insertion heuristic (SIH) for the initial population drives the population toward improved solutions are examined. Experimental comparisons indicate that the proposed adaptive BCO-SIH algorithm works well across all instances and is able to obtain 11 best results in comparison with the best-known results in the literature when tested on Solomon's 56 VRPTW 100 customer instances. Also, a statistical test shows that there is a significant difference between the results. |
| first_indexed | 2024-12-16T11:55:41Z |
| format | Article |
| id | doaj.art-82e2c12b1e564f3e9989f9999bfa7b9b |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-16T11:55:41Z |
| publishDate | 2015-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-82e2c12b1e564f3e9989f9999bfa7b9b2022-12-21T22:32:34ZengPublic Library of Science (PLoS)PLoS ONE1932-62032015-01-01107e013022410.1371/journal.pone.0130224Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows.Sana JawarnehSalwani AbdullahThis paper presents a bee colony optimisation (BCO) algorithm to tackle the vehicle routing problem with time window (VRPTW). The VRPTW involves recovering an ideal set of routes for a fleet of vehicles serving a defined number of customers. The BCO algorithm is a population-based algorithm that mimics the social communication patterns of honeybees in solving problems. The performance of the BCO algorithm is dependent on its parameters, so the online (self-adaptive) parameter tuning strategy is used to improve its effectiveness and robustness. Compared with the basic BCO, the adaptive BCO performs better. Diversification is crucial to the performance of the population-based algorithm, but the initial population in the BCO algorithm is generated using a greedy heuristic, which has insufficient diversification. Therefore the ways in which the sequential insertion heuristic (SIH) for the initial population drives the population toward improved solutions are examined. Experimental comparisons indicate that the proposed adaptive BCO-SIH algorithm works well across all instances and is able to obtain 11 best results in comparison with the best-known results in the literature when tested on Solomon's 56 VRPTW 100 customer instances. Also, a statistical test shows that there is a significant difference between the results.http://europepmc.org/articles/PMC4488911?pdf=render |
| spellingShingle | Sana Jawarneh Salwani Abdullah Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows. PLoS ONE |
| title | Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows. |
| title_full | Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows. |
| title_fullStr | Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows. |
| title_full_unstemmed | Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows. |
| title_short | Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows. |
| title_sort | sequential insertion heuristic with adaptive bee colony optimisation algorithm for vehicle routing problem with time windows |
| url | http://europepmc.org/articles/PMC4488911?pdf=render |
| work_keys_str_mv | AT sanajawarneh sequentialinsertionheuristicwithadaptivebeecolonyoptimisationalgorithmforvehicleroutingproblemwithtimewindows AT salwaniabdullah sequentialinsertionheuristicwithadaptivebeecolonyoptimisationalgorithmforvehicleroutingproblemwithtimewindows |