Target problem
The class of problems to find the optimal delivery routing plans for vehicles (trucks),
starting from a depot, visiting several points for pickup and/or delivery, and returning to the original depot,
is called the vehicle routing problems (VRP).
For this class of problems, several objectives are applied for different situations,
such as minimization of the number of trucks, the minimization of the total time for operations,
and the minimization of the total distance traveled.
Also, in practice VRPs involve many constraints such as:
- Maximum capacities and operating times of trucks
- Limited periods of time when truck can visit points (time windows)
- The set of depots that can serve each point (when there are multiple depots)
- The set of vehicles that can handle each load
- The extra costs for overtime work by drivers
- Rest times for drivers (e.g., one hour around noon)
- Milk runs (routes planned around a basic route)
- Transshipments of loads at depots (cross-docking)
- Pickups and deliveries of loads within the same route
- Extra costs for driving in urban areas
- ...
The most common objective in practice is "minimization of the number of trucks".
In order to find good near-optimal solutions for this problem by using a local search,
starting from an initial solution, solutions with smaller costs are iteratively searched for.
During the search, in order to decrease the number of trucks,
sometimes bad solutions (with longer routes) need to be accepted and passed through.
Therefore, an important design point of local search algorithms is how to pass through bad solutions.
For example, in the figure below, Solution C is the most desirable.
When local search only moves one load at a time, Solution B needs to be visited after starting from Solution A.
But, Solution B is not accepted because the route length of Solution B is longer than that of Solution A,
and therefore Solution C is never reached.
The Vehicle Routing Planner (VRP)
IBM Tokyo Research Laboratory has been researching
vehicle routing problems with various constraints
and has provided key algorithmic components for an IBM software product called
Vehicle Routing Planner (VRP).
IBM VRP is equipped with a local search with the following neighborhood operations.
As described above, this local search itself can be easily trapped by bad local optimal solutions:
Neighborhood operations of local search in IBM VRP
IBM VRP is equipped with an algorithm to escape out of bad local optimal solutions
and to find better solutions (in most cases, with a smaller number of trucks).
These types of algorithms, in general called meta-heuristics, include tabu search,
simulated annealing, and genetic algorithms.
The following figure illustrates an original meta-heuristic developed at IBM Tokyo Research Laboratory for VRP.
In this meta-heuristic, a route is randomly selected and its cost is augmented, and then the local search is applied.
This process is repeated until no better solutions are found.
A good point of this meta-heuristic is that it only has a few tuning parameters
and is able to find good solutions easily for various types of instances.
IBM VRP runs on a geographical information system,
and calculates traveling distance and time between points
by using a digital road map.
IBM Vehicle Routing Planner
Reference
- N. Park, H. Okano, and H. Imai, "A Path-Exchange-Type Local Search Algorithm for Vehicle Routing and its Efficient Search Strategy", Journal of ORSJ, 43, pp.197-208, 2000.
- H. Okano. "Delivery route optimization and its applications, with examples from logistics in banks". Research Report RT0309, IBM Tokyo Research Laboratory, 1999.
- H. Okano. "Extension of a traveling salesman heuristic for vehicle routing". Research Report RT0225, IBM Tokyo Research Laboratory, 1997.
|
|
