459784 Travelling Traders’ Exchange Problem: Stochastic Simulation and Sensitivity Analysis

Monday, November 14, 2016
Grand Ballroom B (Hilton San Francisco Union Square)
Chunbing Huang1, Patrick Piccione2, Federica Cattani2 and Federico Galvanin1, (1)Department of Chemical Engineering, University College London, London, United Kingdom, (2)Jealott’s Hill International Research Centre, Process Studies Group, Technology & Engineering, Syngenta, Bracknell, Berkshire, United Kingdom

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 Li, money exchange direction Di and money transfer coefficient kia and kip.

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.



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


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.


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.


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.


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


D. T. Gillespie, "Approximate accelerated stochastic simulation of chemically reacting systems," The Journal of Chemical Physics, vol. 115, no. 4, p. 1716, 2001.


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.



Extended Abstract: File Not Uploaded