In the following notebooks, we learn to solve the traveling salesman problem (TSP) and vehicle routing problem (VRP) using different algorithms.
Travelling Salesman Problem - MTZ Formulation: This notebook gives an overview of solving the traveling salesman problem using the Miller-Tucker-Zemlin (MTZ) formulation. We will be back to using
PuLP
.Travelling Salesman Problem - Benchmarking the MTZ model: The solution time for MTZ models of different problem sizes increases drastically. So, in this notebook, we learn to benchmark the performance of the MTZ model for varying problem sizes.
Travelling Salesman Problem - Nearest Neighbour Heuristic: Using the nearest neighbor method learned in class, we learn to solve the traveling salesperson problem.
Travelling Salesman Problem - Genetic Algorithm: We solve the travelling salesperson problem using a genetic algorithm (GA).
Travelling Salesman Problem - Solution Comparison: We compare different methods of solving the traveling salesperson problem.
Multiple Travelling Salesman Problem: In this notebook, we explore the traveling salesperson problem with multiple salespeople.
Capacitated Vehicle Routing Problem: We solve the capacitated vehicle routing problem to improve on the solution of the multiple traveling salesperson problem.
Sweep Method: To solve the vehicle routing problem quickly, perhaps even at the cost of not having the best solution, we apply the sweep method, as learned in class.
Savings Method: We solve the vehicle routing problem, and we apply the savings method, as learned in class.
Vehicle Routing Problem - Genetic Algorithm: We again apply the genetic algorithm, but this time to solve the vehicle routing problem.
We encourage you to have a look at the notebooks and understand the differences between the various algorithms to solve the traveling salesperson problem and the vehicle routing problem.