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:
- 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.
- (1+1) EA: A standard evolutionary algorithm using bit-wise mutation, which allows for multiple simultaneous changes to the solution string with low probability.
- 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_swapand 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