Probabilistic travelling salesman off the beaten track: the impact of clustering, construction, and correlation

Abstract

Same-day parcel deliveries, grocery order collection in warehouses and food delivery by bicycles are but a few recent examples that illustrate the increased complexity of the routing problems our society is facing nowadays. The increasingly complex nature of routing problems is in part caused by a tremendous growth of stochastic involvement. Travel times between customers are usually uncertain, their demands may change, and their presence at the time of delivery is often unknown. Accounting for such uncertainties plays an important role in the design of efficient routes. The body of literature dedicated to the performance of solution methods in such stochastic settings is therefore growing rapidly. However, only few studies approach the uncertainty retained by routing problems from the opposite perspective.

By revisiting one of the earliest accounts in the field of stochastic routing, the probabilistic travelling salesman problem, this thesis investigates the impact of uncertainty in customer presence ‘off the beaten track’: How the problem characteristics of a fundamental stochastic routing problem poses challenges to the empirical performance of solution methods. The probabilistic travelling salesman problem is concerned with finding the shortest route along a set of customers in a graph, while their presence is stochastic. That is, each customer in the graph only requires a visit with a certain probability. Therefore, the subset of customers that eventually requires a visit is unknown. Since it is well-known that the optimal solution of this problem may differ from its deterministic counterpart, the travelling salesman problem, many problem-specific solution methods have been developed to cope with the stochastic nature of the probabilistic travelling salesman problem. But only little empirical research has focused on the opposite perspective: How problem characteristics affect the performance of solution methods.

Starting from scratch, a first study reviews and compares solution methods for the probabilistic travelling salesman problem. It provides a comprehensive overview of the most important probabilistic methodological adaptations of exact methods, construction heuristics, improvement heuristics and metaheuristics, and discusses their strategies, key features and performance. An in-depth analysis evaluates the construction phase of a selection of several solution methods under different circumstances. The application of sufficiently explorative heuristics in the improvement phase of deterministic routing problems has led to the commonly held belief that advantages accrued by construction heuristics vanish in the final solution. Consequently, the construction phase also remained largely unexplored in the probabilistic travelling salesman problem. I put the hypothesis to the test that initial solutions found by construction heuristics contribute to the quality of final solutions for the probabilistic travelling salesman problem. Empirical research reveals that the spatial configuration of customers in the problem is an essential determinant in the extent of the contribution. Specifically, the presence of clustering of customers across the plane is one of the main drivers of the relative performance of construction heuristics.

Building on this insight, a follow-up study proposes a new hyperheuristic framework that generates new construction heuristics tailored to any given problem setting. This hyperheuristic framework, named GENS-H, is the first reported application of hyperheuristics in the stochastic routing domain that explicitly takes problem characteristics into account. GENS-H relies on the Generic Savings procedure, a solution approach that unifies a class of construction heuristics, namely savings-based procedures, into a single generalised and parameterised framework. GENS embeds existing savings procedures as special instances, but is also capable of producing numerous new procedures on demand by plugging in different parameter configurations. Notwithstanding its potential, the goal of an included GENS-H benchmark study is not predominantly to outperform state-of-the-art methods, but rather to demonstrate the added value of pursuing an approach where problem characteristics — and specifically, the clustering of customers — are taken into consideration. Extensive numerical tests support this premise.

The notion that spatial proximity in the form of customer clustering plays a quintessential role in the characterisation of a problem promotes the idea that dependency through other, potentially also nonspatial, interactions between customers could be an overlooked trait in models for stochastic routing. That is, the assumption made by the probabilistic travelling salesman problem that customers are independent can be regarded as an oversimplification. Drawing on concepts in computational sociology and financial mathematics, the last study of this thesis proposes a generalised version of the probabilistic travelling salesman problem that incorporates a hands-on way to model dependencies between customers who are seemingly related. This new stochastic combinatorial optimisation problem, the correlated probabilistic travelling salesman problem, ventures into an unexplored territory of stochastic routing where the probabilistic requirements to interact with customers are not isolated endeavours any more. More specifically, the correlated probabilistic travelling salesman problem integrates a heterogeneous set-up that allows one to specify correlations between the stochastic requirements of visiting a group or cluster of customers, with the ability to reduce to the original probabilistic travelling salesman problem in case dependence is absent. This implementation has many practical applications in solving real-world routing problems where, for example, similar behaviour in customer presence can be observed among different customer segments. This study also demonstrates that good solutions for the deterministic version of the travelling salesman problem and the probabilistic travelling salesman problem do not necessarily coincide with good solutions for the correlated adaptation. As such, the development of new, customised, solution methods for the correlated probabilistic travelling salesman is needed.