TY - JOUR
T1 - Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem
AU - Yu, Vincent F.
AU - Redi, A. A.N.Perwira
AU - Yang, Chao Lung
AU - Ruskartina, Eki
AU - Santosa, Budi
N1 - Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2017/3/1
Y1 - 2017/3/1
N2 - This paper presents the symbiotic organisms search (SOS) heuristic for solving the capacitated vehicle routing problem (CVRP), which is a well-known discrete optimization problem. The objective of CVRP is to decide the routes for a set of vehicles to serve a set of demand points while minimizing the total routing cost. SOS is a simple and powerful metaheuristic that simulates the symbiotic interaction strategies adopted by an organism for surviving in an ecosystem. As SOS is originally developed for solving continuous optimization problems, we therefore apply two solution representations, SR-1 and SR-2, to transform SOS into an applicable solution approach for CVRP and then apply a local search strategy to improve the solution quality of SOS. The original SOS uses three interaction strategies, mutualism, commensalism, and parasitism, to improve a candidate solution. In this improved version, we propose two new interaction strategies, namely competition and amensalism. We develop six versions of SOS for solving CVRP. The first version, SOSCanonical, utilizes a commonly used continuous to discrete solution representation transformation procedure. The second version is an improvement of canonical SOS with a local search strategy, denoted as SOSBasic. The third and fourth versions use SR-1 and SR-2 with a local search strategy, denoted as SOSSR-1 and SOSSR-2. The fifth and sixth versions, denoted as ISOSSR-1 and ISOSSR-2, improve the implementation of SOSSR-1 and SOSSR-2 by adding the newly proposed competition and amensalism interaction strategies. The performances of SOSCanonical, SOSBasic, SOSSR-1, and SOSSR-2 are evaluated on two sets of benchmark problems. First, the results of the four versions of SOS are compared, showing that the preferable result was obtained from SOSSR-1 and SOSSR-2. The performances of SOSSR-1, SOSSR-2, ISOSSR-1, and ISOSSR-2 are then compared, presenting that ISOSSR-1 and ISOSSR-2 offer a better performance. Next, the ISOSSR-1 and ISOSSR-2 results are compared to the best-known solutions. The results show that ISOSSR-1 and ISOSSR-2 produce good VRP solutions under a reasonable computational time, indicating that each of them is a good alternative algorithm for solving the capacitated vehicle routing problem.
AB - This paper presents the symbiotic organisms search (SOS) heuristic for solving the capacitated vehicle routing problem (CVRP), which is a well-known discrete optimization problem. The objective of CVRP is to decide the routes for a set of vehicles to serve a set of demand points while minimizing the total routing cost. SOS is a simple and powerful metaheuristic that simulates the symbiotic interaction strategies adopted by an organism for surviving in an ecosystem. As SOS is originally developed for solving continuous optimization problems, we therefore apply two solution representations, SR-1 and SR-2, to transform SOS into an applicable solution approach for CVRP and then apply a local search strategy to improve the solution quality of SOS. The original SOS uses three interaction strategies, mutualism, commensalism, and parasitism, to improve a candidate solution. In this improved version, we propose two new interaction strategies, namely competition and amensalism. We develop six versions of SOS for solving CVRP. The first version, SOSCanonical, utilizes a commonly used continuous to discrete solution representation transformation procedure. The second version is an improvement of canonical SOS with a local search strategy, denoted as SOSBasic. The third and fourth versions use SR-1 and SR-2 with a local search strategy, denoted as SOSSR-1 and SOSSR-2. The fifth and sixth versions, denoted as ISOSSR-1 and ISOSSR-2, improve the implementation of SOSSR-1 and SOSSR-2 by adding the newly proposed competition and amensalism interaction strategies. The performances of SOSCanonical, SOSBasic, SOSSR-1, and SOSSR-2 are evaluated on two sets of benchmark problems. First, the results of the four versions of SOS are compared, showing that the preferable result was obtained from SOSSR-1 and SOSSR-2. The performances of SOSSR-1, SOSSR-2, ISOSSR-1, and ISOSSR-2 are then compared, presenting that ISOSSR-1 and ISOSSR-2 offer a better performance. Next, the ISOSSR-1 and ISOSSR-2 results are compared to the best-known solutions. The results show that ISOSSR-1 and ISOSSR-2 produce good VRP solutions under a reasonable computational time, indicating that each of them is a good alternative algorithm for solving the capacitated vehicle routing problem.
KW - Capacitated vehicle routing problem
KW - Metaheuristics
KW - Solution representation
KW - Symbiotic organisms search
UR - http://www.scopus.com/inward/record.url?scp=85005810492&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2016.10.006
DO - 10.1016/j.asoc.2016.10.006
M3 - Article
AN - SCOPUS:85005810492
SN - 1568-4946
VL - 52
SP - 657
EP - 672
JO - Applied Soft Computing Journal
JF - Applied Soft Computing Journal
ER -