Analysis of Baseline Evolutionary Algorithms for the Packing While Travelling Problem

Vahid Roostapour, Mojgan Pourhassan, Frank Neumann

Abstract

This paper presents a rigorous theoretical and experimental analysis of baseline evolutionary algorithms (EAs) applied to the Packing While Travelling (PWT) problem. PWT is a non-linear variant of the classic knapsack problem where item weight impacts travel costs and duration. We analyze the performance of Random Local Search with swaps (RLS_swap), the (1+1) EA, and the Global Simple Evolutionary Multi-objective Optimizer (GSEMO). Our results demonstrate that these algorithms can find optimal solutions in polynomial time ($O(n^3)$) for specific problem classes, bridging a significant gap in evolutionary computation theory which has historically focused on linear objectives.

Introduction

In the field of combinatorial optimization, linear problems like the standard Knapsack Problem are well-understood. However, real-world engineering and logistics often involve non-linear dependencies. The Packing While Travelling (PWT) problem is a prime example of such complexity. It models a scenario where a vehicle travels between cities to collect items; while more items increase potential profit, they also increase the vehicle's weight, thereby reducing velocity and increasing time-based "renting costs."

This study aims to determine if simple, baseline evolutionary algorithms—the fundamental building blocks of more complex AI solvers—can efficiently navigate this non-linear landscape to find optimal solutions.

The Packing While Travelling Problem

The PWT problem introduces a non-linear objective function. Imagine a vehicle moving between cities with a set of potential items $n$. Each item has a profit $p_i$ and a weight $w_i$. The total benefit $B(x)$ is calculated as:

$$B(x) = P(x) - R \cdot T(x)$$

Where $P(x)$ is the total profit of collected items, $R$ is the renting rate, and $T(x)$ is the total travel time. Because travel time $T(x)$ is a function of the vehicle's velocity—which decreases as weight increases—adding a high-profit item might actually decrease the total benefit if the resulting slowdown is too severe. This creates a complex optimization landscape where local optima are common.

Methodology

The researchers evaluated three primary algorithmic frameworks:

  1. RLS_swap: A variant of Random Local Search. While standard RLS flips a single bit (adding or removing one item), this version includes a "swap" operator that can replace one item with another in a single step, allowing it to exchange heavy, low-profit items for lighter, high-profit ones.
  2. (1+1) EA: A standard evolutionary algorithm using bit-wise mutation, which allows for multiple simultaneous changes to the solution string with low probability.
  3. GSEMO (Global Simple Evolutionary Multi-objective Optimizer): A multi-objective algorithm that maintains a population of solutions (a Pareto front) by treating total weight and total benefit as separate objectives.

Experimental Setup

Theoretical analysis was conducted on generalized instances with $n$ items and a two-city model. For experimental validation, the authors used 30 random instances with $n=300$ items for convergence tests and scaled instances from $n=100$ to $n=10,000$ to analyze runtime scaling. Parameters such as renting rate ($R$), distances ($d$), and velocity ($v$) were fixed to simulate realistic transport constraints.

Key Insights

The Threshold Effect

A pivotal discovery in this research is the "weight threshold." The authors proved that for every item, there exists a unique weight threshold. If the current cargo weight is below this threshold, adding the item improves the objective; if it is above, the item becomes a liability. This insight allows the non-linear PWT to be mapped onto a more manageable mathematical structure for runtime analysis.

The Necessity of Swapping

The analysis revealed that standard local search (single-bit flips) frequently becomes trapped in local optima. The RLS_swap modification is essential because it provides the necessary "jump" to bypass these traps. Similarly, multi-objective algorithms like GSEMO perform well because their population-based approach acts as a buffer; even if one solution is stuck, other individuals in the population can continue to progress toward the global optimum.

Results and Performance

  • Theoretical Runtimes: The authors mathematically proved that RLS_swap and GSEMO find the optimal solution in $O(n^3)$ expected time for instances where weights and profits are correlated (i.e., lighter items are generally more profitable).
  • Uniform Weights: For instances where all items have the same weight, the (1+1) EA finds the optimum in $O(n^2 \log(\max\{n, p_{max}\}))$ time.
  • Empirical Scaling: Experimental results showed that in practice, these algorithms often outperform their theoretical worst-case bounds. Runtimes on random instances scaled closer to $O(n^2)$ or $O(n \log n)$.
  • Convergence Characteristics: While the (1+1) EA and RLS converge rapidly in the early stages of the search, multi-objective algorithms like GSEMO demonstrate superior performance when refining solutions very close to the optimal front.

Conclusion and Future Work

This paper provides the first formal runtime analysis for evolutionary algorithms on the non-linear Packing While Travelling problem. By demonstrating that baseline EAs can solve specific classes of PWT in polynomial time, the authors provide a theoretical foundation for using heuristic solvers on non-linear transport problems.

Future research will focus on expanding these proofs beyond the two-city model to multi-city paths and investigating algorithmic performance on uncorrelated item distributions, where the problem is known to be NP-hard.

Summary updated

Abstract

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.
BibTeX
@inproceedings{roostapour2019analysis,
  author = {Vahid Roostapour and Mojgan Pourhassan and Frank Neumann},
  title = {{Analysis of Baseline Evolutionary Algorithms for the Packing While Travelling Problem}},
  booktitle = {FOGA},
  year = {2019},
  doi = {10.1145/3299904.3340313},
}
Figure