Solving the VRP

Imagine that you now manage a larger fulfillment center. You still need to deliver packages to a list of customers, but now, you have a fleet of several vehicles at your disposal. What’s the best way to deliver the packages to the customers using these vehicles?

This is an example of the VRP, a generalization of the TSP described in the previous section. The basic VRP consists of the following three components:

• The list of locations that need to be visited
• The number of vehicles
• The location of the depot, which is used as the starting and ending point for each of the vehicles

The problem has numerous variations, such as several depot locations, time-critical deliveries, different types of vehicles (varying capacity, varying fuel consumption), and many more.

The goal of the problem is to minimize the cost, which can also be defined in many different ways. Examples include minimizing the time it takes to deliver all the packages, minimizing...