The Vehicle Routing Problem (VRP) is a classic operations research problem concerned with finding the optimal routing of a fleet of k vehicles seeking to reach n nodes. Each vehicle must begin its route at a shared source node and return to said source node at the end of its path. Optimality can be defined in a few ways but generally includes minimizing some quantity such as distance or time. For example, we might want to minimize the distance travelled across all vehicles in an effort to minimize fuel usage. Or, we may want to minimize the time until the last vehicle returns to the source thereby setting a cap on the amount of time to serve all n nodes.
Another way of thinking about this problem is as a generalization of the classic Travelling Salesman Problem (TSP). The TSP involves a wandering salesman seeking to sell his goods to customers in n far off cities. The salesman wants to minimize the amount of time to reach each of these cities and return to his starting place. Generalizing to the VRP from the TSP, instead of one salesperson, we now have k salespeople who agree that each destination will be serviced by one member of the sales team before the salespeople return home to the source. Notice that the VRP must have a fixed source unlike the TSP since the TSP’s solution generates a single cycle in the network and thus the starting point does not affect optimality. In contrast, the starting point of the VRP defines the distinct cycles each vehicle or salesperson must complete. Secondly, the VRP contains an assignment problem buried into it. To find the optimal solution, we have to find the optimal assignment of nodes to vehicles along with the optimal path for each vehicle to its assigned node.
An important shared trait of the TSP and the VRP is that neither of them can be solved simple, efficient algorithms. Just like many combinatorial optimization problems, they fall into the class of NP-Hard problems. The feasible set of solutions (or in this case routing choices) is enormous and grows exponentially with the problem size. For a given VRP with n destinations and k vehicles, there are \(k^{n-1}\) valid assignments of destinations to vehicles plus the sum of within common assignment permutations of destinations. Clearly, enumerating over the entire space is not remotely feasible for larger problems. Finally, one of the other challenges of combinatorial optimization problems is that the cost function typically contains a large number of local optima that an approach such as hill-climbing will be unable to overcome. These challenges motivate the use of simulated annealing.
Simulated annealing presents a very plausible approach to the VRP given its ability to maneuver between peaks and valleys in the cost function to avoid getting caught in a local optima. The random proposals aspect is absolutely necessary for this movement to happen. Then, as the peaks become sharper, we should expect to find the optimal routing.
In more formal terms, the Vehicle Routing Problem can be formulated as follows. If our objective is to minimize the total distance travelled by the vehicles, the problem becomes:
\[ \begin{aligned} \min &\sum_{i=1}^k \sum_{j=2}^{n_k} d(x_{i(j-1)},x_{ij}) \\ \text{subject to} & \sum_{i=1}^k n_k = n + 2k - 1 \\ & x_{i1} = x_{in_k} = x_1 \qquad \forall i \in 1,2,\dots,k \end{aligned} \]
where the variables are defined as follows:
The functions computing the distance and cost of a given routing are available in Appendix A1.
As specified above, the problem operates over a graph with \(n\) nodes and a designated source node. For the purposes of examining the performance of simulated annealing on the VRP, we can generate sample networks by plotting \(n\) uniformly generated nodes in the unit square. We will leave the option to set a specified starting node to illustrate the impact of different source nodes on the solutions. Below are a set of four sample networks. One of them is completely random, the other three have their source nodes set at \((0,0)\), \((0.5,0)\), and \((0.5,0.5)\). The code to generate these plots can be found in Appendix A3.