The first stage is to describe the problem in natural language. Routing can be defined as the process of assigning visits to vehicles, while taking into account constraints such as capacity or time windows, to produce a routing plan with the least possible cost.

The complexity of routing problems varies greatly. The Vehicle Routing Problem (VRP) requires a set of vehicles to visit a set of customers from one or more depots. To solve a VRP you have to solve two intertwined problems. An assignment problem--whether or not to assign a particular visit to a given vehicle--is added to the geometry problem, where each vehicle has to visit a given set of customers as expeditiously as possible. A second type of routing problem, the Pickup and Delivery Problem (PDP), extends the VRP by allowing pickups and deliveries within the same route.

Each class of routing problem--whether VRP, PDP, and so on--itself comes in many guises. For example, the VRP may be modified by introducing multiple depots or alternative delivery sites; by requiring vehicles to make multiple round trips or tours; or by coupling the vehicle with a technician.

A problem may include different kinds of side constraints--such as capacity, time windows, precedence, technician skill levels, and so on--or specific constraints that depend on the business area of the application. Constraints may be added to allow for work breaks, such as lunch and coffee breaks or overnight stops, to minimize the number of vehicles, or to introduce costs for late deliveries or technical service.

There also exists wide variation in the size of routing problems. The size may vary from a few dozen activities to thousands of visits. The methods that work well for small problems may not be applicable to bigger problems, due to the increased complexity.

Besides the diversity in the possible data of routing problems, different environments may require different performance from the algorithms solving the problems. For example, in some applications the construction of a routing plan must be performed in seconds while in other applications computation times of a few days are allowed. Similarly, any feasible solution is sufficient for many applications, whereas others require near-optimal solutions.

In each lesson in this manual, you will describe the routing problem before modeling and solving it. Though the Describe stage of the process may seem trivial in certain simple problems, you will find that taking the time to fully describe a more complex, real-world problem is vital for creating a successful program. You will be able to code your program more quickly and effectively if you take the time to describe the model before writing your application.