OBJECTIVES / CONSTRAINTS / TYPES OF PROBLEMS

Objectives

The objective in problems of vehicle routing is the minimization of a time/monetary/distance measure, given some relevant parameters.

An example is minimizing the total distance traveled during

• delivery of a week's orders to customers dispersed in a certain geographical region
• served from a central distribution center
• using only one vehicle.

In this example, the distances from the distribution center to the destination points (customers) and distances between destination points are key parameters.

Constraints

Typical constraints in vehicle routing might include

• vehicle capacity
• limit on the total time that a vehicle should spend on route
• assignment of certain number of vehicles to certain customers

etc.

Types of Problems

One possible classification of Vehicle Routing Problems is

• Single Origin-Destination Routing
• Multiple Origin-Destination Routing
• Single Vehicle Origin Round trip Routing
• Vehicle Routing and Scheduling

Single origin-destination routing is also known as shortest path problem, and is optimally solvable by Dijkstra's Algorithm if all the transportation costs are nonnegative. Problems up to around 100,000 nodes are solvable in reasonable times using this algorithm.

Multiple Origin-Destination Routing is modeled as a network flow problem. A very efficient algorithm is the network simplex algorithm, which solves problems up to 100,000 links in a reasonable amount of time.

Single Vehicle Origin Round trip Routing is traveling salesman problem, and solved to optimality using specialized branch and bound algorithms. Problems with over 2000 nodes are computationally very time-consuming but are solved reasonably well using heuristic algorithms.

Vehicle Routing and Scheduling encompasses all vehicle routing problems not part of the preious three classes. This class is many times further divided.

The interest in this topic is steadily increasing, and many research results have been successfully implemented in practical problems. One key consideration in modeling these type of systems, though, is that the big picture should always be kept in the guiding light. Solving the vehicle routing problem with wrong assumptions might lead to inferior policies from a total system point of view.