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

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:

1.      The 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_i and money transfer coefficient k_i^aand 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.

References

[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," Journal of the Royal Society Interface, vol. 4, no. 16, pp. 879-891, 2007.
[3]	M. A. Gibson and J. Bruck, "Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels," J. Phys. Chem., vol. 104, no. 9, pp. 1876-1889, 2000.
[4]	G. Basile, C. Bernardin, M. Jara, T. Komorowski and S. Olla, "Thermal Conductivity in Harmonic Lattices with Random Collisions," in Thermal Transport in Low Dimensions: From Statistical Physics to Nanoscale Heat Transfer, Cham, Springer International Publishing, 2016, pp. 215-237.
[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," The Journal of Chemical Physics, vol. 115, no. 4, p. 1716, 2001.
[7]	E. L. Haseltine and J. B. Rawlings, "Approximate simulation of coupled fast and slow reactions for stochastic chemical kinetics," The Journal of Chemical Physics, vol. 117, no. 15, p. 6959, 2002.