  The performance of base-line Evolutionary Algorithms (EAs) on combinatorial
problems has been studied rigorously. From the theoretical viewpoint, the
literature extensively investigates the linear problems, while the theoretical
analysis of the non-linear problems is still far behind. In this paper,
variations of the Packing While Travelling (PWT) -- also known as the
non-linear knapsack problem -- are studied as an attempt to analyse the
behaviour of EAs on non-linear problems from theoretical perspective. We
investigate PWT for two cities and $n$ items with correlated weights and
profits, using single-objective and multi-objective algorithms. Our results
show that RLS\_swap, which differs from the classical RLS by having the ability
to swap two bits in one iteration, finds the optimal solution in $O(n^3)$
expected time. We also study an enhanced version of GSEMO, which a specific
selection operator to deal with exponential population size, and prove that it
finds the Pareto front in the same asymptotic expected time. In the case of
uniform weights, (1+1)~EA is able to find the optimal solution in expected time
$O(n^2\log{(\max\{n,p_{\max}\})})$, where $p_{\max}$ is the largest profit of
the given items. We also perform an experimental analysis to complement our
theoretical investigations and provide additional insights into the runtime
behavior.
