Metaheuristic Approaches for Vehicle Routing Problems

Routing And Vehicle Routing Problems

Routing problems are often presented as graphical networks. The use of networks to describe these problems has the advantage of allowing the decision maker to visualize the problem under consideration. As an example, refer to Figure 1 (see Figure 1 in the Appendix). The Figure 1 (see Figure 1 in the Appendix) consists of five circles called nodes. Four of the nodes (node 2 through 5) represent pickup and/or delivery points, and a fifth (node 1) represents a depot node, from which the vehicle’s trip originates and ends. The depot node is the home base, from which the vehicle originates and ends.

Figure 1.

Routing network example

The depot node is the home base for the vehicle or product. Connecting these nodes are line segments referred to as arcs. Arcs describe the distance required to travel from one node to another. The numbers along the arcs in Figure 1 (see Figure 1 in the Appendix) are distances in kilometres. Directed arcs represent the direction of travel in routing problems. The small network in Figure 1 can be viewed as a route for a single vehicle. The route for the vehicle, also called a tour, is 1-2-3-4-5-1. The total distance for tour is 51 kilometres.

The tour described in Figure 1 (see Figure 1 in the Appendix) is a solution to a simple routing problem where the objective is to find the route that minimizes cost or any other criterion that may be appropriate. The minimum-cost solution, however, is subject to the tour being feasible. Feasibility depends on the type of problem, but, in general, implies that:

• 1.

  A tour must include all nodes;

• 2.

  A node must be visited only once;

• 3.

  A tour must begin and at a depot.