Introduction

The solution approaches to attacking VRPs fall into three major categories and the book is also structured correspondingly.

Exact algorithms

Exact algorithms are of particular interest if we want optimal solutions for our problems at hand. Unfortunately, VRPs are computationall intractable in nature unless the problem in small in scale or possess certain special problem structure. In this section, we will cover several mathematical modeling approaches towards the Traveling Salesman Problem (TSP) and the Capacitate VRP (CVRP).

More importantly, we will look into one powerful technique, column generation, that not noly see great success in solving VRPs, but many other optimization problems in general. Column generation is my personal favorite technique in solving VRP in that it is a very flexible framework that in itself can find good solutions, but can also be combined with other algorithms to jointly come up with even better solutions.

Heuristic and metaheuristics

We will mostly look at some constructive heuristics for TSP and VRP. In addition, we will examine how to implement various metaheuristics to solve these problems.

Large neighborhood search (LNS) is a popular searching algorithm for VRPs. It’s powering several industry-level routing optimization engines I am aware of. Several other routing engines also utilize Guided Local Search (GLS).

Open source routing solvers

The two open source VRP solvers we will check are the Google OR-Tools routing solver and Timefold. Google OR-Tools offers a routing engine that provides routing optimization capabilities out of the box. Once getting used to its modeling syntax, it provides a jump start to solving many VRPs.

Similarly, Timefold is a great open source solver for planning and scheduling optimization problems.