Tasks allocation is a fundamental problem in multiagent systems. We formulate the problem as a multiple traveling salesmen problem (MTSP), which is an extension to the well known traveling salesman problem (TSP), both considered to be NP-hard combinatorial optimization problems. We propose a solution in which agents interact in an economic market to win tasks situated in an environment. The agents strive to minimize required costs, defined as either the total distance traveled by all agents or the maximum distance traveled by any agent. Using a set of simple market operations, the agents come up with a solution for task allocation. In this work we examine the processing speed of the market-based solution (MBS), as well as the quality vs. optimal solutions achieved using enumeration for a 3 agents by 8 tasks scenario. We show that the MBS is both quick and close to optimal. We then show that the MBS can be scaled to more complicated problems, by comparing its results with results from genetic algorithm (GA) and clustering. We also show the robustness of the MBS to changes in the scenario, e.g. the addition and removal of tasks or agents.
The previous study for which this one serves as an update concluded that there was good news for those who wished to live in racially integrated communities in Hamilton
County. The news remains good. At the 2010 census, fifty-four suburban Hamilton
County communities and Cincinnati neighborhoods, over one-third of the total,
containing 45% of the total population of the county, were at least modestly racially
integrated (Table 9).2 This continues trends that began as early as 1970 when seven
communities achieved integration that persisted for at least forty years. At the 1980
census, twelve achieved racial integration that lasted for at least thirty years. And at the 1990 census, ten became integrated with that persisting for at least the next twenty years. Together, twenty-nine communities have remained racially integrated for at least twenty years.
At the same time, the dissimilarity index (DI), a standard measure of residential
integration, showed improved black/white integration for both the city of Cincinnati and
Hamilton County as a whole (Table 1). Cincinnati’s DI dropped from 91.2 in 1950, its
highest point, to 64.8 in 2010. Hamilton County’s DI dropped from 82.8 in 1980, the
earliest for which we have data, to 71.3 in 2010. This means that increasing numbers of whites and blacks are living on the same blocks in a number of communities here.
The desirability of these integrated neighborhoods has apparently remained steady over time. Although both the city and the county have lost population, the integrated
neighborhoods have proportionally lost no greater population than the rest. Moreover, in the last decade, conventional wisdom to the contrary, several of the long-term integrated communities experienced increases in the white percentage of their population.
When we looked at socio-economic conditions throughout the county as measured by
seven indicators drawn from the census, we found a range of values for the integrated
communities. Some are clearly in quite good shape and improving and some show signs of decay. On a scale that aggregates five of these indicators, integrated communities on the average fell between the values for the city of Cincinnati as a whole and for suburban Hamilton County. This is particularly good news as the declining economy has certainly hurt the African Americans population more than the rest of the population. Because of this, the integrated communities might be expected to show a greater decline than the rest of the county, and while some of them have been hurt, on the average, they seem to be holding their own in comparison to the rest of the county.
Finally, the city of Cincinnati, which has long seen an increase in black population and a decrease in white population, in the 2000s saw a significant slow-down in the decline of white population and an actual decrease in black population. This suggests that the black/white ratio may stabilize in the city in the near future.