Efficient Local Search Limitation Strategies for Vehicle Routing Problems
In this paper we examine five different strategies for limiting the local search neighborhoods in the context of vehicle routing problems. The vehicle routing problem deals with the assignment of a set of transportation orders to a fleet of vehicles, and
- PDF / 467,495 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 59 Downloads / 185 Views
Graduate School of Information Sciences, Japan Advanced Institute of Science and Technology, Japan [email protected] Agora Innoroad Laboratory, Agora Center, P.O.Box 35, FI-40014 University of Jyv¨ askyl¨ a, Finland [email protected]
Abstract. In this paper we examine five different strategies for limiting the local search neighborhoods in the context of vehicle routing problems. The vehicle routing problem deals with the assignment of a set of transportation orders to a fleet of vehicles, and the sequencing of stops for each vehicle to minimize transportation costs. The examined strategies are applied to three standard neighborhoods and implemented in a recently suggested powerful memetic algorithm. Experimental results on 26 well-known benchmark problems indicate significant speedups of almost 80% without worsening the solution quality. On the contrary, in 12 cases new best solutions were obtained.
1
Introduction
In this paper we focus on the Capacitated Vehicle Routing Problem (CVRP). It can be defined as follows. Let G = (V, E) be a complete undirected graph consisting of n + 1 nodes, and a set of edges E with non-negative weights and with associated travel times. Let one of the nodes be designated as the depot. With each node i, apart from the depot, is associated a demand qi that can be a delivery from or a pickup to the depot. The problem is to minimize the total travel distance of a routing plan such that the total demand of any route does not exceed a vehicle capacity Q (the capacity constraint), the duration of any route does not exceed an upper limit L (the route duration limit), each route must start and end at the depot, and each customer must be served by exactly once by one vehicle. Note that the above described VRP with the route duration limit is often separated from CVRP and called distance-constrained VRP (DVRP). In this paper, the DVRP is not considered. The VRP is a NP-hard problem which makes it difficult to solve it to optimality. In practice, heuristic or metaheuristic solution methods are often the only option. For more details, see e.g. Laporte and Semet [10], Gendreau et al. [5], and Cordeau et al. [4]. In broad terms, the actual search in almost all known heuristic and metaheuristic solution methods is based on various local search procedures and often J. van Hemert and C. Cotta (Eds.): EvoCOP 2008, LNCS 4972, pp. 48–60, 2008. c Springer-Verlag Berlin Heidelberg 2008
Efficient Local Search Limitation Strategies for Vehicle Routing Problems
49
the local search is clearly the most time consuming part of the algorithms. Because of this, it is crucial that strategies for efficient implementation and for speeding up the local searches are developed and tested. An obvious approach is to forbid moves that apparently seem to degenerate the current solution. The main contribution of this paper is to examine five different approaches that are used to rule out non-improving local search moves and to demonstrate that significant speedups can be gained without worsening the solution quality. The five l
Data Loading...
