Orienteering Problems - Models and Algorithms for VehicleRouting Problems with Profits

When logistic or e-commerce companies distribute all kinds of products to their customers, they want to minimize their distribution costs. This is typically obtained by solving so called `vehicle routing problems', where the objective is to minimize the total cost, distance, or time required to visit all customers.This tutorial introduces readers to routing problems with profits. In these routing problems, each customer is modeled with a certain profit and not all customers need to be visited. Since the orienteering problem (OP) is by far the most studied problem in this category of routing problems, the OP is the main focus of this book and the other problems are presented as variants of the OP, focusing on the similarities and differences between these variants. The goal of the OP is to determine the best subset of customers to visit, and in which order, so that the total profit is maximized and a given time budget is not exceeded.This book clearly explains and illustrates, to both academics and practitioners, the available definitions and mathematical models for these routing problems with profits and introduces research opportunities for academic researchers. This book shows the readers that many practical problems can be modeled more appropriately as a routing problem with profits instead of as a regular routing problem. In addition, the book presents different scientific rigorous solution techniques for these OP variants. Solution techniques and mathematical models are accompanied by easy to understand examples and figures.Plenty of examples facilitate the understanding of these routing problems. Several benchmark instances including their latest best known results are also included, to explain the complexity of solving these problems. Links to online benchmark instances, solvers, and detailed solutions are provided as well. In order to better understand the problems and their relevance, this tutorial also discusses a variety of applications from different fields, such as logistics, tourism, and crowdsourcing. This book discusses the OP, the team OP, the (team) OP with time windows, the profitable tour problem, and the prize-collecting traveling salesperson problem in detail. Other variants (with capacity constraints, time dependency, stochasticity, etc.) are discussed more briefly. We further limit this book to so called `node routing problems', where customers have a given location, and we do not consider the `arc routing problems' with profits, where driving through an entire street is considered as a single customer. Obviously, we include references for readers who are interested in arc routing problems with profits, node routing variants or many other solution approaches we could not discuss in this book.The book mainly aims for graduate students (Master, MBA, or PhD) in engineering, economics or applied mathematics, and obviously operations research. It is also suitable for advanced undergraduate students with some background in operations research. Moreover, practitioners and planning engineers in logistic companies will be inspired by understanding these alternative routing problems and the presented solution techniques.

ISBN:978-3-030-29745-9

Jaar van publicatie:2019