Abstract
This paper introduces four different types of Generalized Travelling Salesman Problem (GTSP) which are actually dynamic variants of the well-known logistics problems. For all of these defined types, new cities are added to/deleted from the city domain during the travelling of the salesman. This city addition and deletion during the solution phase of the problem, differentiates the proposed types from the classical GTSP. Since these variants of GTSP are relatively complicated compared to classical forms, an agent-based strategy is proposed in this paper to handle complexity and dynamism. In this respect, proposed agent-based strategy employs a general manager and numerous region agents to control and coordinate the dynamism in their regions and in the central level. Region agents create solutions just for their regions and thereby complexity of obtaining a central solution for each change containing is avoided. Findings of the proposed agent-based strategy confirm that adaptation ability of agent-based strategy against the dynamism is significantly better than classical central solution approach. In this respect, this paper is expected to be novel in two respects. First, those four types of GTSP defined in this paper, are different from the classical GTSP since they have dynamic city domain. Second, the proposed novel agent-based solution strategy is capable to create solutions in a timely manner.
Keywords
Introduction and problem statement
Generalized traveling salesman problem (GTSP) is a variation of traveling salesman problem (TSP) where a tour doesn’t require visiting of all nodes. The objective function for a classical GTSP is finding the tour that passes through exactly one node of each cluster/region which minimizes the total tour length. Papers considering GTSP have differences in terms of the scales used. Some studies suppose symmetry or the triangle inequality; others don’t [1]. Some studies necessitate the subsets to form a firm division of the node set; others let them to overlap. Most of the studies permit the tour to visit more than one node per cluster, but some call for exactly one node per cluster to be visited [1].
GTSP is known to be more complex than TSP [2] due to its additional constraints. Complexity of the GTSP considerably increases when the number of clusters increases. A lot of consideration was paid to solve those complex GTSPs [3]. Particularly, heuristics are employed as favorable approaches in order to obtain good (but not inevitably exact) solutions for larger GTSP instances [4].
Although it is possible to see dynamic versions of TSP [5–9]in the literature, until recently, to our best knowledge, dynamic versions of GTSP have been only discussed only in [10, 11]. Since we intended to focus on the dynamic variants of GTSP in this paper, we introduce four novel types of dynamic GTSP. In these novel types of GTSP, new cities are allowed to be added to city domain and/or can be deleted from the domain during the solution process; thereby new cities/regions can appear or disappear in the routing plan. These dynamic events (new city arrivals and disappearance of existing cities) created randomly by the time. The other classical assumptions of GTSP have been kept as they are for those newly introduced types. A salesman with a vehicle starts transporting the deliveries from their pick-up locations to their delivery regions/clusters (region and clusters have exactly the same meaning though this paper). Consequently, this salesman visits certain number of regions at given geographical coordinates and at the end of tour he/she returns to the initial region having the home city. Any added/removed order requires a new route for the vehicle. On each route, the vehicle moves from one client to another, just spending time in traveling among clients at their locations. The vehicle(s) travel according to the Euclidean metric and their velocity is assumed to beconstant.
The dynamism considered in those proposed types, makes GTSP much more complex than the classical types defined before. This paper intends to shed light on whether agent-based systems can be adopted to solve dynamic GTSPs in a balance in terms of the acceptability and being timely. Agent systems, due to their properties of autonomy, reactivity and pro-activeness [12] are able to handle dynamism in the systems. In this respect, using agent-based approaches may help us to save considerable amount of time and memory by the cooperative behaviors of agents and communication ability of them. This time reduction is expected if the problem can be divided into a set of sub-problems. Instead of dealing with a huge problem; agents can be assigned to solve the problem under their responsibility (in our paper; it is the search of regional tour alternatives by region agents). The “time concept” mentioned here requires a clarification. If there is unlimited time, better solutions can be obtained for any GTSP. Unfortunately this is not the fact in real life. The real need is to obtain “timely solution”, which is acceptable. The time required to find a very good solution may have no meaning if the case loses its validity. Since, we can always wait longer for a solution in static optimization; in dynamic-optimization, intervene between performance and time complexity is determined by the problem difficulty and the relation between the rate of change and the obtainable computing resources [13].
Unfortunately, general algorithms may be inefficient to achieve good solutions even for the dynamic versions of TSP [6]. Although it is desirable to find an optimum solution after each change, it is unobtainable mostly in a quick way. In fact, if you want to get better solutions, the efficiency will be lower, and conversely, if you require quick solutions, their quality will reduce that is to say the two goals (solution quality and time response) are in conflict. Since we can’t get an optimum solution at every instant, we can solve the problem in discrete time steps, finding good solutions in a time step as short as possible [6].
Thus, we propose a solution strategy covering intelligent agents, where region agents are capable to inform each other about cities under their control (communication of agents) and evaluate routing alternatives for the cities in their regions. The proposed strategy also includes modification of existing solution on the hand, without remodeling and resolving the problem.
The rest of this paper is structured as follows; in Section 2, problem types and initial setups for them are introduced; Section 3 presents the test study and its structure. Section 4 provides agent-based simulation results, and finally in Section 5 conclusions are drawn.
GTSP Types and initial setups
In this section, we provide a comprehensive explanation of the most significant aspects of dynamic GTSP, and describe main features of those four new variants of dynamic GTSP. The GTSP is a generalization of TSP, and it is one of the intractable combinatorial optimization problems. In the GTSP, we are given n cities which are grouped into mutually disjoint districts (clusters) and non-negative distances between the cities in different districts.
The GTSP was introduced in relation with record balancing problems arising in computer design and with the routing of clients through agencies providing various services [14]. However, in real life, some assumptions of classical GTSP have ended up with the failure of reflecting physical complexity and dynamism. Keeping the number of cities constant has been unrealistic, since customer orders may vary in dynamic markets. Consequently, “a solution provided for a specific state defined for a time” loses its superiority immediately after these unexpected changes. In this respect, these proposed dynamic variants of GTSP may not be modeled with the conventional research methods since much time and memory spaces are required to setup novel models and solve them repeatedly.
Aside from centralized Artificial Intelligence (AI) approaches [e.g., genetic algorithms (GAs), artificial neural networks, fuzzy logic, and expert systems], agent technology is emerging as a solution for distributed AI that has attracted a wide attention [15]. Therefore, this paper focuses on a novel agent-based solution strategy to provide promising solutions to the defined variants of GTSP. It is remarkable to state here that, promising solutions mentioned here do not equally mean the optimal solutions, it is rather the feasible solutions obtained in affordable time and in an acceptable level.
Within the scope of this paper, a continuous agent-based simulation approach has been used to simulate defined GTSPs. In the defined system; regional agents (RA) are created by the general manager agent (GMA) for each of the regions in the problem domain. Consequently, each RA attempts to find an initial solution for its own region by making use of a meta-heuristic optimization algorithm which is known as Great Deluge Algorithm. Those RAs are also authorized to modify their existing solution alternatives if any change occurs in their region. RAs deliver their bids to the GMA to produce the final decision about the routes.
Consequently, results obtained via the proposed agent-based strategy have also been compared with the solutions provided by the solo implementation of Great Deluge Algorithm. For comparison purposes, findings have been checked periodically. We compare the solutions before having an exact solution since the purpose of this study is to check quality differences of solutions under time limitations.
As a conclusion, it has been understood that, agent-based strategy is much more adaptable to continuous change and it outperforms the Heuristic solution.
Problem variants
GTSP variants introduced in this paper are as summarized in Table 1. GTSPs that are within content of this paper are all dynamic optimization problems where a city may be added to/removed from the list of cities. In problem Type 1 and problem Type 2; exactly one city from each region/cluster is visited where the objective is to minimize the total cost of tours.
In problem Type 3 and problem Type 4, Dynamic GTSP and Dynamic TSP are considered together. As illustrated in Fig. 1, objective function of these two types is to minimize the total cost that is generated by the grand tour (cost of visiting exactly one city from each region-Cost A in Fig. 1) plus the costs of the local tours (where a vehicle in the regions visits all of cities within the region: Cost B, Cost C, Cost D in Fig. 1).
The difference of Type 1 from Type 2 and similarly Type 3 from Type 4 is only the region determination strategy that is considered. In Type 1 and Type 3, regions are known and are given. In most of studies on GTSPs, data already acknowledges the solver about the cities that are covered by a region. Awkwardly, the rationality behind the given regions remains as mystery.
On the other hand, in real life; logistics companies construct region offices/branches based on a prior feasibility analysis. Solving a problem with the given regions may avoid managers to reconsider their region determination (known also as branching) strategies. In this regard, we differentiated Type 1 from Type 2 and similarly Type 3 from Type 4 according to region determination strategies.
City and region creation
City and region creation is performed based on some principles regarding to problem types defined in this paper. These principles are important in order to facilitate a better understanding of the solution strategies. One is about naming and creating cities and regions. In all of the introduced problem variants, initial number of cities is determined by the user. Cities are then created randomly in a user-defined environment (that has 1000 unit of width and 1000 unit of length maximum). Creation sequence of cities is used as the city id (the fifth randomly created city is named as City 5). For the problem types where regions are predetermined (Type 1, Type 3), regions are also named consecutively according to the row and column that they are located. If a city is in kth row and jth column then the cluster/region of that city is [(j–1)* number of rows)+k] as illustrated in Fig. 2.
If regions are not given as in problem Type 2 and Type 4, then the region having the city 1 is named as region 1 and then new regions are named consecutively based on closeness to center of Region 1. In this regard, there is no constant home region and any region can be home region that is selected by the central agent with respect to the cost advantages.
Agent creation
The proposed solution strategy utilizes three types of agents as illustrated in Fig. 3. Since a collection of agents exists that are directly interacting [16], the proposed system is a Multi-agent system. All these three type of agents are capable of messaging and this functionality facilitates information transfer between agents in the system [17].
The first agent type in the proposed system is General Manager Agent (GMA) that is responsible from the final routing decisions. It also decides creation/destruction of new regional agents (RAs) based on the change in city domain. RAs are the second type of agents, which are accountable from the cities located in their regions. Specific to Type 3 and Type 4 GTSPs (where all cities in a region is visited), RAs are also responsible to produce the routing alternatives for their regions by using Great Deluge Algorithm. Since each RA search for local solution alternatives simultaneously, considerable amount of time and memory is saved.
GMA is the only agent that can initialize an auction with the creation of cities. Initially, GMA informs all RAs and asks for their bids. RAs evaluate the possible alternatives for their regions and provide bids for the open auctions.
The third type of the defined agents is vehicle agent, which is responsible from the delivery and transportation of loads. This vehicle agent is informed about the planned route by the GMA. All tasks of those agents are defined using the state charts of AnyLogic.
Region determination strategies
In GTSP, regions describe a part of physical environment where cities with similar coordinates are gathered. Therefore each region in the problem domain should have a region ID. There exist two strategies for region determination. One is the predetermined regions. In this type of region determination (problem Type 1 and problem Type 3), user defines a unit area for a unit region. Subsequently, environment is divided into regions by that unit of area. For instance; if environment is 1000×1000 units and a region is defined, as 10×10 then, 100 regions is created. Thereby, it gets easier to determine a city’s region just by checking its coordinates, corresponding rows and columns as discussed in “City and Region Generation section”.
In the second option, intelligent region determination policies are applied (problem Type 2 and problem Type 4). In those intelligent region determination policies, average distance (AD) has been used as the base measure. A city to be clustered is checked whether its distance to the region center is less or more then AD.
For calculation of AD, maximum and minimum values of X and Y should be found for the created cities as illustrated in Fig. 4. Difference between “maximum of X coordinate values” and “minimum of X coordinate values” determines the horizontal range of cities. Similarly, the difference between “maximum of Y coordinate values” and “minimum of Y coordinate values” determine the vertical range of cities.
Subsequently, AD is calculated upon the option selected by the user. Provided options are Euclidian AD and circle diameter AD. Euclidian distance is calculated using Equation (1).
If circular-diameter option is selected, following procedure is applied. If those cities were homogenously distributed in the defined environment, there would be n circles with radios r where total area of them should be equal to A = nπr2 as illustrated in Fig. 5. “Ideal r value” is competed using Equation (2).
After AD is calculated according to the user preference, one of the following intelligent region determination options is used:
Equal Distance Option: In this region determination option, City 1 is selected as the center of Region 1. A city having the distance at most “AD much” to the City 1 is clustered in the same region (Region 1). After determination of all cities in region 1, the nearest city to City 1 (which has not been clustered yet) is found and accepted as the center of the second region. This policy is continued until all cities have been clustered.
Modified Equal Distance Option: In this option, equal distance option is performed first. The distance between the first city of Region 1 and the first city of Region 2 is calculated and named as “Modified Equal Distance (MED)”. In this procedure cities having distance less than AD is clustered like “equal distance option”. If there is only one city in region then the cities having less distance then MED is clustered at the same region (excluding the Region 1 and Region 2). After determination of all cities in a region, the nearest city to center city (which has not been clustered yet) is found and accepted as the center of the next region.
There can be extreme cases for Modified Equal Distance Option. If some cities are accepted to a cluster due to having less distance then MED, next region’s center city may be closer to previous region as illustrated in Fig. 6. In that case, that city is added to next region.
A sample case indicating the determined regions via the use of “modified distance option” is as presented in Fig. 7.
Due to their distinctiveness, ABMs have been lately using heuristic procedures to solve problems whose domains are scattered, complex and heterogeneous [18]. In this respect, Great Deluge Algorithm (GDA) was adapted to solve the defined GTSP variants in this paper. GDA was proposed by Dueck in 1993 [19]. It is an easy to apply algorithm which is used for optimization purposes. Since it requires only one algorithm specific parameter to arrange, it is very agreeable for solving optimization problems [20]. GDA conditionally accepts worse candidate solutions during its run [21] and due to high similarity it is accepted as a variant of simulated annealing algorithm. GDA is employed for the searches of the difficult problems, where it can be too difficult to obtain exact and optimal solutions such as TSP problems. The quality of the computational results obtained so far by GDA for TSP showed that GDA behave equally well as many frontier algorithms [22].
An adapted variant of GDA is employed in this work as presented in Fig. 8 [20]. The GDA algorithm is started with the generation of a random solution represented by s. Subsequently, initial cost of the solution (cost of visiting cities in the route-total distance) is computed for s and it is called as the badness of the solution. As cost/badness f(s) value increases, undesirability of the solution increases. One other parameter of the GDA is tolerance (B) which is equalized to an arbitrary cost value or to the initial cost at the start-up.
The worse solutions are also acceptable to avoid to get stuck in local optima. If fitness value of a solution is less than or equal to upper limit B (level), then the candidate solution is also accepted. If the newly generated solution s* is undesirable when compared to tolerance/upper limit (B), a different neighbor of S is chosen and the process is restarted. Neighbor selection is performed as described in section 3.2. If neighbors of s yields insignificant improvements beyond tolerance (B), then the search is stopped and s* is taken as the best solution.
In this paper, regional agents also use GDA to find the best possible route alternative for the regions that are under their responsibility. General Manager Agent also uses GDA to find the best possible grand tour alternative. In all of these implementations, application is quite straightforward and they follow exactly same pseudo code.
Random initial solution
A random floating number is produced such as 3.5. First part of this number (it is 3 in the given example) indicates the region to be selected. According to the number of cities in that region (assumed as 4 for the given example) a random city is selected by multiplying the floating part with the number of cities in that cluster/region (0.5*4 = 2 then City 2 is selected).
Neighborhood creation
There are two strategies to generate neighborhood solutions. One is swapping of cities where two randomly selected cities are interchanged. In this strategy, two random numbers are generated to determine the order of the cities to be changed. In the second strategy, a random number is generated and a city is selected. Subsequently, all the cities that are following the selected city is taken from its location in the sequence and added to home city. Beside those two neighborhood generation strategies, user interface also presents an option to change of cities without changing the order of clusters/regions. There is also an option to avoid having same solutions in the solution set defined for GDA. There are two options for stopping the iterations. One is defining the consecutive number of non-improving solutions and the other is maximum number of iterations.
Agent competition
The problem types and the implemented agent strategies are as illustrated in Fig. 9. In problem Type 1 and Type 2, if home region is determined but home city is not determined yet; then the first city of the region (having the smallest ID) is considered as the first candidate home city. General-manager agent asks all other region agents to offer their bids to be connected to current home city. Regional agents check all cities in their region to be connected to the candidate home city and they deliver their minimum bids (the bests that they have) to General Manager Agent (GMA). The region agent (RA) that is giving the best bid (suggesting the minimum cost to be connected) becomes winner agent. Suggested city of the winner agent is assigned as the city to be visited after the first candidate home city. Similarly, all unassigned remaining RAs provide their bids to be added to the subsequent city (winner of the previous competition). This procedure is repeated until a complete tour is obtained. GMA keeps the best alternative for the state where the first city in the home region is candidate of being home-city. Figure 10 represents the corresponding flow of agent competition and presents a demo of the flow. In the presented figure (Fig. 10), home region is 3. RA 3 informs the GMA about the home city of home region (which is C2). Consequently, GMA asks for the bids of other RAs to be connected to C2. Subsequently the second city in the home region is assumed as the second candidate of being home city and the same procedure is applied. After all those applied, at final step, GMA have different tour arrangement alternatives where each is the best solution of different home city alternatives. In this respect, GMA selects the alternative with minimum cost. Solution duration of the problem is less when compared to conventional methods since RAs evaluate their alternatives simultaneously and this helps us to save time.
In problem Type 3 and Type 4, there are two different touring types under consideration. The first is the grand tour where exactly one city is visited from each region. The second is the regional tour where each city of the region is visited once and home city is visited at the end. Each RA consider different regional tour alternatives using GDA and keep the best tours each starting with different cities of that region to report the GMA. If home region is determined but home city is not determined yet; then the first city of the region (having the smallest ID) is considered as the first candidate home city. Then, GMA asks all other region agents to offer their bids to be connected to candidate home city. Different from problem Type 1 and problem Type 2, each RA produce their alternative bids, including both total cost of their regional tours and the grand tours. However, RAs only deliver the alternative that has the smallest cost. The procedure is followed until several full-length tour alternatives (number of iterations as a termination condition can be selected by the solver via interface) are determined. Finally, the GM selects the alternative with the least Total Cost.
Changes and actions
New city arrivals
In the case of a new city arrival, for dynamic GTSP “regions are predefined (problem Type 1)”, then region of the city is found as described in region determination section. If that city is the unique city in its region, then that city is added to visit plan and a region agent is created for that cluster. If that city is not the unique city for that region which has not been visited yet, then possibility of planning that new city to be visited is calculated. If total cost for the tour decreases then, new city is added as planned city, otherwise no change is required for the visit plan.
If a new city appears in the case where, grand tours and regional tours are both considered and regions are predefined (problem Type 3), then region of the city is found. If that city is the unique city in its region, then that city is added to visit plan and a region agent is created for that cluster.
If that city is not the unique city for that unvisited region, then firstly; home city of that region is kept constant and possibility of adding it behind the other cities is calculated. The minimum total cost found among those possible additions are saved as COST A. Subsequently, possibility of assigning that new city as a home city (if existing home-city has not been visited yet) is searched. For that purpose, Great Deluge Algorithm (GDA) is asked to determine the regional tour cost if that new city becomes the home city for that region. This possibility also changes the grand tour cost. New total cost is saved as COST B. COST A and COST B are compared and the smaller one is selected as the new visit plan.
If regions are not known for the new coming city (problem types 3 and 4), all RAs are informed about it (coordinates of it is transmitted). All RAs check whether they can consider this new city in their region or not. This decision is taken upon two measures: average total distance of cities to region center (ATDC), and their standard deviation of distances of cities in that region (SDD). If new city’s distance to a region agent is less than ATDC+SDD, then that city can be accepted for that region. Since having less deviation, from the average is preferable, if there are several regions that are able to accept that city to their region, then new city is added to the region where deviation is the least. If the city is added to one of the existing clusters then exactly same procedure is applied as described for problem Type 3 andType 1.
City deletion
In case of city deletion/disappearance, following procedures are applied with respect to the selected problem type.
If a city is already visited, deletion of that city will have no influence in the system. If a vehicle is routed to a certain city and if that city is deleted from the city domain before arrival, the already passed distance through that deleted city is also included in the total cost.
For the all problem types, it is first checked if the deleted city is planned in the grand tour or not. If deleted city is a part of grand tour and if there is at least two cities remaining after deletion, RA delivers the second best alternative (having the same city order) in its list to be considered by GMA. If the deleted city is unique city in its region, then it is deleted and corresponding RA is destroyed (even if the region determination strategy is “intelligent clustering”, no auction is performed for the merger of regions). If the deleted city is not in the visit plan of the grand tour, then the city is deleted only from the regional tour in Type 3 and Type 4.
Settings and comparisons for simulation model
There are several input settings that are required to be fixed before implementing GDA. After several trials, it has been found that, GDA performs better where tolerance (B) = 0.001 and neighborhood size as 30 in the defined GTSPs. Total numbers of 1000 iterations or 800 non-improving iterations have been considered as the terminating criteria.
New events in the defined system are creation of cities and deletion of cities from the city domain. In the proposed system these defined events set to happen in each 0.002 hours. Such events are created periodically with time intervals distributed exponentially with the parameter rate.
For comparison purposes, findings of the proposed agent-based strategy are compared with the solutions obtained via unaccompanied implementation of GDA. Those comparisons are performed when the total number of cities becomes zero (0) in mode 5. GDA that has exactly the same parameters with the proposed agent-based strategy is used for solving defined problems and calculated costs are saved. Since solutions obtained via GDA, are only valid for certain states, we called them as “the solutions at a moment” through this section. Thereby solutions obtained with continuous agent-based system are compared with the solutions at a moment.
It is remarkable to state here that, “frozen solutions” are the results obtained for hypothetic cases where change is not considered for a moment and the model is rebuilt and solved from the beginning as it is like a new problem. Undesirably, rebuilding a model may consume too much time due to parameter setting. Furthermore, in case of GTSP; terminating the delivery process until a good solution is found has no practical value since it may create irrepressible problems like the loose of waiting customers. There is also one more crucial difference between the hypothetic case and the continuous agent-based modeling. In the frozen solutions; all information is assumed to be known (having the perfect information), on the other hand; in real continuous systems, number of cities are dynamic and that change is not known formerly.
In this respect, comparisons given in the next sections should be read as follows. Heuristic based approaches are normally expected to produce promising results compared to agent-based negotiation strategies, while they may require unaffordable amount of resources. However, if the cost of parameter setting is waived/omitted (other costs remaining as they are) agent-based negotiation strategies even produce better results. The results are presented in figures and tables in the subsequent sections, as averages of 100 runs of algorithms.
Findings for problem Type 1 and Type 2
In both Type 1 and Type 2 problems, our objective is to find the better alternatives that are shortening total distance of a tour. Table 2 represents the results for comparison purposes where initial number of cities (n) is 20. Since number of cities increase and decrease during the visits, numbers of cities are sometimes the same. This is the reason why number of cities is the same sometimes at the given tables. Tables 2–4 demonstrates the other results obtained for problem Type 1.
To test the significance of the difference between the proposed agent-based solution strategies and the Frozen GDA results, Paired-T test is performed and the results are as given in Table 5. We preferred to use paired T test since it calculates the difference within each before-and-after pair of measurements, determines the mean of these changes, and reports whether this mean of the differences is statistically significant or not. The normality of differences has also been checked and no violation detected for the normality assumption.
Since the p-value for the experiment is almost equal to zero (0.0042), we can conclude that there is a statistically significant difference among the results of these strategies. Since the average of the total cost of the proposed Agent-Based strategy is lower than the Frozen GDA, we can conclude that the proposed Agent-Based approach has a better performance compared to the Frozen GDA strategy.
Tables 6–8 demonstrates the other results obtained for problem type 2.
To test the significance of the difference between proposed agent-based solution strategies with the Frozen GDA results for Type 2 problems, Paired-T test is performed and the findings are as described in Table 9. Since the p-value for the experiment is almost equal to zero (0.0001), we can conclude that there is a statistically significant differentiation among the results of these strategies. Since the average of the total cost of the proposed Agent-Based strategy is lower than the Frozen GDA, we can conclude that the proposed Agent-Based strategy has a better performance compared to the Frozen GDA strategy.
Findings of problem Type 3 and Type 4
In these defined types, the target is finding suitable cities from each region to complete the grand tour and the local tours to be visited through the visit of each city of each region by another vehicle to minimize the total cost. Problems have high dynamism due to random addition and deletion of cities. Tables 10–12 demonstrates the other results obtained for problem type 3.
To test the significance of the difference between proposed agent-based solution strategies and the Frozen GDA for Type 3 problems, Paired-T test is performed and the findings are as described in Table 13. Since the p-value for the experiment is 0.5721, we can conclude that there is not a statistically significant difference among the results of these strategies. Since the average of the total cost of the proposed Agent-Based strategy is lower than the Frozen GDA, we can still conclude that the proposed Agent-Based strategy has a better performance compared to the Frozen GDA strategy.
Tables 14–16 demonstrates the other results obtained for problem type 4.
To test the significance of the difference between proposed agent-based solution strategy and the Frozen GDA for Type 4 problems, Paired-T test is performed and the findings are as described in Table 17. Since the p-value for the experiment is almost equal to zero (0.0156), we can conclude that there is statistically significant difference among the results of these strategies. Since the average of the total cost of the proposed Agent-Based strategy is lower than the Frozen GDA, we can conclude that the proposed Agent-Based strategy has a better performance compared to the Frozen GDA strategy.
Conclusions
In this study, four different variants of dynamic GTSPs are introduced to show whether agent-based systems can be adopted to solve dynamic GTSPs in easier way or not. We compare the solutions obtained by the conventional central/aggregate solution approach, with the solutions obtained by a distributed agent-based approach both employing Great Deluge Algorithm. Since the focus of this study is to show how the quality of solutions may be better (in the case where there is limited time avoiding us to wait for the best possible result) if agents are assigned to solve smaller sized sub-problems, we used GDA for both of the cases. Other comparisons can be extended by implementing other heuristics in the future studies. Since the defined GTSP variants are complex and distributed, use of agent-based strategy allowed us to employ local and parallel search strategies. Thereby this actually helped us to save time. Generally “frozen results” is expected to be better since the problems are handled from the beginning and different combinations are searched repeatedly.
As Barbati et al. [18], state; because agent-based procedures are distributed and they don’t have an overall view of the state of the system, they may fail to find a truthfully good solution. However construction of a qualified communication scheme between the agents can overcome this handicap. On the other hand, a heuristic like GDA may lose its capability to produce good results when parameters are kept constant as performed in this study. Total number of iterations terminating the search of a heuristic for a 50 city problem may not be adequate to search a 100 city problem. This is also an evidence of the certain advantage of ABM through negotiation. Providentially, in the proposed agent-based strategy, parameter setting have no considerable effect after the obtaining the first solution since other solutions are obtained via negotiation of agents. This feature can be accepted as the superiority of obtaining agent-based solutions to highly dynamic types of GTSP. As Angelelli et al. [23] states, absence of information on future events generates the need for algorithms able to take rapid decisions on the basis of present information possibly making some estimate on future. As it is demonstrated through all of the given results, increasing the number cities make the results better for the proposed agent-based strategy (Fig. 11). Since agent-based techniques support the division of the overall problem into a number of smaller “local” problems, large-sized problems can be handled well when the problem presents characteristics of modularity [18].
Similarly, in the problem types where specific region determination strategies are used (Type 2 and Type 4), power of the proposed agent strategy increases remarkably since agents are capable of intelligent merger or deletion.
This paper presents the power of agent-based modeling once more for modeling and solving the complex and dynamic systems. The paper also presents the first application of the multi-agent based approach to modeling and solving of dynamic GTSP successfully. This power of agent-based models can be explained with their capability to capture the collective behavior of all agents in a complex system. The significant advantages, which came out of the proposed agent-based strategy, can be summarized as follows: The proposed strategy adapts to the changes (in number of cities) much rapidly than a conventional heuristic (GDA). The requirement for parameter setting of heuristics can be reduced with this strategy. Complexity of the problem can be reduced. As the population of the cities increase in the problem domain, the power of the strategy becomes much more apparent.
Footnotes
Acknowledgments
The authors would like to acknowledge the financial support provided by Scientific Research Projects Governing Unit of Dokuz Eylül University (Project No: 2011238).