| Main Resources Benchmarks Projects Bibliography |
One of the best known routing problems is the Traveling Salesman Problem (TSP). In TSP a number of cities have to be visited by a salesman who must return to the same city where he started. In solving the problem one tries to construct the route so that the total distance traveled is minimized. In the m-TSP problem, the m-salesman has to cover the given cities and each city must be visited by exactly one salesman. Every salesman starts from the same city, called depot, and must return at the end of his journey to this city again. The Vehicle Routing Problem (VRP) is the m-TSP, where a demand is associated with each city or customer and each vehicle has a certain capacity. Moreover, in VRP also the number of vehicles, m, is often considered as a minimization criterion in addition to total traveled distance.
A typical VRP can be described as the problem of designing least cost routes from one depot to a set of geographically scattered points (cities, stores, warehouses, schools, customers etc). The routes must be designed in such a way that each point is visited only once by exactly one vehicle, all routes start and end at the depot, and the total demands of all points on one particular route cannot exceed the capacity of the vehicle.
Intrinsically, the VRP is a spatial problem. During the last few decades, however, temporal aspects of routing problems have become increasingly important. Specific examples of problems with time windows include bank deliveries, postal deliveries, industrial refuse collection, school-bus routing and situations where the customer must provide access, verification, or payment upon delivery of the product or service. In these problems customers can be served only during certain hours of the day, such as office hours or the hours before the opening of a shop. For example, a warehouse may only accept deliveries between 9:00 AM and 4:00 PM. Therefore, much attention has been given to the Vehicle Routing Problem with Time Windows (VRPTW). The time windows can be hard or soft. In the hard time window case, if a vehicle arrives too early at a customer, it is permitted to wait until the customer is ready to begin service. However, a vehicle is not permitted to arrive at a customer after the latest time to begin service. In contrast, in the soft time window case, the time windows can be violated at a cost.
In Arc Routing Problems (ARPs), the aim is to determine a least cost traversal of all edges or arcs of a graph, subject to some side constraints. Compared to more common node routing problems, customers are here modelled as arcs or edges. Such problems arise naturally in several applications related to garbage collection, mail delivery, snow clearing, meter reading, school bus routing, police patrols etc.
In contrast to the VRP, in the pickup and delivery problems each transportation request specifies both the locations where the load is to be picked up and the locations where it is to be delivered. Each load has to be transported by one vehicle from its set of origins to its set of destinations without any transshipment at other locations.
The real-world planning situation requires quite often a weekly schedule in addition to the daily planning, for instance for fuel, oil and industrial gas distribution, and for garbage collection and beer and soft drink distribution. The related VRP is called the Period Vehicle Routing Problem (PVRP). It can be defined as the problem of finding routes for all days of a given T-day period. These types of problems are also called allocation/routing problems. The allocation part consist of the assignment of customers to days of the period, while the routing part governs for the daily planning.
Recently the business practice called Vendor Managed Inventory replenishment (VMI) has been adopted by many companies. VMI refers to the situation in which a vendor monitors the inventory levels at its customers and decides when and how much inventory to replenish at each customer. Practical applications of VMI include logistics in the petrochemical and industrial gas industry. The task of developing such a distribution strategy is called Inventory Routing Problem (IRP). The IRP is concerned with the repeated distribution of a single product from a single facility, to a set of customers over a given planning horizon. Each customer consumes the product at a given rate and has a known capacity to maintain a local inventory of the product.
Although often assumed in theory, a trucking firm’s vehicle fleet is rarely homogenous. The differences in equipment, carrying capacity and the fact that vehicles might differ in age, causes them to have a different cost structure. In contrast to traditional VRP, in Fleet Size and Mix Vehicle Routing Problem (FSMVRP) the vehicles are assumed to have heterogenous capacities and acquisition costs. The objective is to minimize both routing costs and vehicle costs.
Most of the existing VRP research has been focused on problems of a deterministic and static nature, although a substantial number of dynamic and stochastic models have been formulated and studied. The increasing role of on-line freight marketplaces, increases in customer service expectations and the availability of real-time information on traffic network conditions have all led to a dramatic rise in the number of freight and fleet management systems that are operating under explicit dynamic conditions. In dynamic and stochastic routing models decisions must be made before all information needed is known. The stochastic nature of these problems takes many forms. The timing, location and level of demand may vary. The availability of resources may vary as well due to service times, dock times and operations in other zones, regions or areas of operation. There are two main classes of models. The first class of models deals with a priori optimization in which a solution is generated for stochastic problems prior to the receipt of information regarding the realization of its random elements. The general approach is to generate an a priori solution that has the least cost in the expected sense. The second set of applications involves making decisions and observing outcomes on a continuous, rolling horizon basis.
Numerous other variants of the VRP include the Time Dependent VRP (TDVRP), Multi Depot VRP (MDVRP) and Split deliveries. The TDVRP is a VRP for which the travel time between two nodes depends on the distance between the points and the time of the day. The time-dependency accounts for variations in travel speed caused by congestion etc. In the MDVRP vehicles operate from one of several depots, and each vehicle must start and end at the same depot. Sometimes the demand of a stop may be fulfilled by more than one vehicle. This can occur for instance when the demand required by a customer is larger than the capacity of a vehicle, or when it is less costly to service a customer more than once.
In these page we'll present information about research groups working on routing problems, well-known benchmark problems and best-known results for them, electronically available papers and ongoing research projects under the TOP programme.
Created July 18 2001 by amr
Last updated March 20 2002 by olb