Article Preview
Top1. Introduction
The complexity of the processes and operations of real-world applications are massively increasing where interacting components must be handled at the same time. Various examples of such applications currently exist. For instance, supply-chain management is one application that consists of several dependent components, such as procurement, production and delivery. These must be considered simultaneously to minimize organization costs like inventory and transportation costs, as well as maximizing organization benefit and utilization of resources (Melo, Nickel, & Saldanha-da-Gama, 2009; Stolk, Mann, Mohais, & Michalewicz, 2013). Another example is garbage collection, in which there are complex interactions between related components such as route timing constraints, and which includes collection of garbage and recycling. This problem is an example of the well-known complex problem called the capacitated arc routing problem with service profit (UCARPP), where a profit and demand are associated with edges and a vehicle must find a route that satisfy the constraints of vehicle capacity and the duration of the routes (Archetti, Feillet, Hertz, & Speranza, 2010).
The complexity of such problems likely arises because of the interdependence amongst their components, which are usually considered as sub-problems. For example, in supply-chain management reducing a certain cost does not guarantee a maximized benefit to the organization. Therefore, it is meaningless to solve each sub-problem individually, as an optimal solution of one component does not ensure an overall optimal solution. Several challenges arise when trying to solve and deal with such problems, most importantly designing an appropriate algorithm for this purpose. Thus, a novel benchmark problem called the Traveling Thief Problem (TTP) was defined by (Bonyadi, Michalewicz, & Barone, 2013) to investigate the interdependence between multi-component problems. To simulate real-world multi-components problems, the TTP consists of two interrelated well-known benchmark problems, which are the Traveling Salesman Problem (TSP) and the Knapsack Problem (0-1). These two sub-problems were combined in a way that an optimal solution for one sub-problem does not certainly lead to an optimal solution for the main problem (TTP). More specifically, the shortest salesman route does not necessarily lead to an optimal TTP solution, and neither does packing the most profitable items.
Several algorithms and approaches were introduced to solve the TTP. These approaches mainly focus on hill-climber search methods, heuristics, and evolutionary approaches. More details about such approaches are highlighted in the following section. To the best of our knowledge, very limited efforts have been carried out to employ swarm intelligence approaches for solving the TTP. In this paper we propose a modified Artificial Bees Colony approach (ABC) for solving the TTP. ABC is one of the recent swarm intelligence techniques that simulate the behavior of honey bees foraging. It is known for its robustness and simplicity, and it was successfully adopted in various optimization problems (Karaboga, Gorkemli, Ozturk, & Karaboga, 2014). ABC was modified here to solve the problem in an interdependent manner where several evolutionary operators, such as 2-opt mutation and insertion crossover, were adopted together with various packing heuristics. The quality of the produced candidate solutions (i.e., objective value) is calculated based on combining the TSP tour and its corresponding packing plan. The performance of this proposed approach was compared to state-of-the-art approaches and the results are discussed.
The remainder of the article is proposed as follows. Section 2 sheds light on the state-of-the-art approaches that were adopted to solve the TTP. The TTP is described in Section 3, whereas the proposed approach is described in Section 4. A detailed explanation of the problem representation is provided in Section 5, which also includes a section that demonstrates how the proposed approach was applied to TTP instances. The experimental setup is explained in section 6 and the experimental results are discussed in Section 7. Finally, the paper is concluded in section 8 and future work directions are outlined.