# (245e) Travelling Traders’ Exchange Problem: Stochastic Simulation and Sensitivity Analysis

- Conference: AIChE Annual Meeting
- Year: 2016
- Proceeding: 2016 AIChE Annual Meeting
- Group: Computing and Systems Technology Division
- Session:
- Time: Monday, November 14, 2016 - 3:45pm-5:45pm

In the traveling

salesman problem (TSP) [1], given a list of cities and the distances between

each pair of cities, the problem is to find the shortest possible route that

visits each city exactly once and returns to the city of origin. The TSP problem

is here recast and revisited as a travelling traders’ exchange problem (TTEP),

in order to analyse a population of *N* traders when the traders can move

in space and interact with each other. The following assumptions are introduced

for describing the TTEP:

*N*traders travel

across a country over time (i.e. the problem is dynamic); 2. The traders initially start with a

certain amount of money

*M*; 3. During a trading season lasting

τ the traders are free to move over a territory (i.e. the problem is

space-dependent); 4. Each time they meet they exchange

money 5. The total amount of money is conserved.

The TTEP is a

fundamental problem arising in a number of relevant applications including

epidemiology [2], chemistry [3] and physics [4]. In all these studies, computational methods based on

stochastic simulations [5] are frequently employed for the study and

characterisation of these systems in which uncertainty exists. This method is

widely employed when it is difficult to describe and analyse the system in a

deterministic way. In

particular, Bansal

et al. [2] studied a stochastic simulation of a compartmental model in

epidemiology; stochastic modelling was also discussed for thermal conductivity

in harmonic lattices [4]. Stochastic simulation approaches with various

extensions and modifications for chemical reaction processes are presented by a

number of researchers [3] [6] [7]. Within a stochastic simulation model, some

variables are randomly changing in time while the entire system evolves

dynamically and presents a highly time-dependent outcome. The objective of this paper is to

develop a stochastic simulation model for describing the TTEP to get insights

in the emergent properties and evolution over time of the distribution of

traders’ accounts.

The TTEP stochastic simulation model

developed here is a model within a bounded region (i.e. city or country), in

which a number of travelling traders, each with an initially assigned amount of

money, stochastically migrate. Both the migration of the traders and the potential

money exchange will influence the amount of money every trader has in time. A

sketch of a 1-D TTEP model is given in Figure 1a. The definitions of (*i*)

initial allocation of amount of money to each trader and (*ii*)

interaction mechanism of any two traders who collide are assumed during the

construction of the stochastic simulation model. In the model, these influences

and definitions are presented mathematically by a number of parameters

including money exchange location *L _{i}*, money exchange

direction

*D*and money transfer coefficient

_{i}*k*and

_{i}^{a}*k*.

_{i}^{p}In the TTEP model, complexity is

added sequentially for describing the mechanisms at different levels of detail

and the computational results are related to the underlying assumptions 1-5 so

as to provide expectations and compare various scenarios. Instead of studying the individual

stochastic trajectories of each trader and his money, the time evolution of the

probability distribution of the amount of money the traders hold in this

stochastic system is of significant interest (Figure 1b). The probability

distribution is described by a set of distribution parameters whose values and

precision depends on the analysis of probability density function (PDF) and derivation

of stochastic differential equations (SDEs). Results show how the impact of

several parameters on the system can be mathematically described; a sensitivity

analysis on each distribution parameter is carried out to evaluate the impact

of the exchange mechanism on the outcomes.

Future work aims

at extending and modifying the stochastic model so that an inverse estimate of

the model parameters, based on optimisation techniques, can be carried out to

relate model output and input. It is also of great interest to relate the

parameters describing the exchange on a trader-by-trader basis to the emergent

properties of the entire distribution by analytical techniques.

[1] |
D. L. Applegate, R. E. Bixby, V. Chvátal and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2011. |

[2] |
S. Bansal, B. T. Grenfell and L. A. Meyers, "When individual behaviour matters: homogeneous and network models in epidemiology," |

[3] |
M. A. Gibson and J. Bruck, "Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels," |

[4] |
G. Basile, C. Bernardin, M. Jara, T. Komorowski and S. Olla, "Thermal Conductivity in Harmonic Lattices with Random Collisions," in |

[5] |
B. Nelson, Foundations and Methods of Stochastic Simulation, New York: Springer US, 2013. |

[6] |
D. T. Gillespie, "Approximate accelerated stochastic simulation of chemically reacting systems," |

[7] |
E. L. Haseltine and J. B. Rawlings, "Approximate simulation of coupled fast and slow reactions for stochastic chemical kinetics," |

** **