Crossover Iterated Local Search for SDCARP
- PDF / 1,002,853 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 30 Downloads / 213 Views
Crossover Iterated Local Search for SDCARP An-Yang Liang • Dan Lin
Received: 18 February 2014 / Revised: 29 May 2014 / Accepted: 13 August 2014 / Published online: 12 September 2014 Ó Operations Research Society of China, Periodicals Agency of Shanghai University, and SpringerVerlag Berlin Heidelberg 2014
Abstract This paper introduces a new algorithm based on local search for the capacitated arc routing problem (CARP) and the split-delivery capacitated arc routing problem (SDCARP). We present a intermediate model to transfer CARP to SDCARP and then solve the two problems by an algorithm which combines the iterated local search and the memetic algorithm. We use crossovers to perform fully reproducible initializations in each local search iteration and edge-marking to save computation time. The computational results on 63 instances of standard benchmarks show that the proposed algorithm outperforms most of the existing best-known solutions obtained by other heuristics within a reasonable computing time. Furthermore, compared with the CARP solutions, our algorithm finds three optimums for the SDCARP. Keywords Capacitated arc routing problem Split-delivery Memetic algorithm Iterated local search
1 Introduction The capacitated arc routing problem (CARP) can be stated as follows [13] : Let G be an undirected graph G ¼ ðV; EÞ, where V ¼ fv0 ; v1 ; vn g is a node set and E ¼ f½vi ; vj : vi ; vj 2 V; i\jg is an edge set, each edge of E has a positive cost or length Ce and nonnegative demand or weight De . Node v0 represents a depot node at which a fleet of identical vehicles of capacity WðW > maxfDe ; e 2 EgÞ are based. The number of vehicles is a decision variable. The aim is to find a set of vehicle A.-Y. Liang (&) D. Lin Department of Mathematics School of Science, Tianjin University, Tianjin 300072, China e-mail: [email protected] D. Lin e-mail: [email protected]
123
352
A.-Y. Liang, D. Lin
routes of total minimum cost such that: (1) each route starts and ends at the depot; (2) each positive-demand edge is serviced by exactly one vehicle; (3) the total demand of each route does not exceed the vehicle’s capacity W. Furthermore, each edge e with De [ 0, called a required edge, must be serviced by a vehicle. On the other hand, each edge e with De ¼ 0 may be traversed or not by the set of vehicles. The edge is called traversed edge if a vehicle traverses it without servicing. The CARP meta-heuristic methodologies can be found in the excellent book by Dror [9]. In recent years, the most successful algorithms proposed in literature for CARP were based on different meta-heuristic models including, the tabu search algorithm of Hertz et al. [20], the variable neighborhood descent algorithm of Hertz and Mittaz [19], Polacek et al. [27], the guided local search heuristic of Beullens et al. [6], the memetic algorithm (MA) of Lacomme et al. [21], the evolution algorithm of Handa et al. [17, 18], the deterministic tabu search algorithm of Brandao and Eglese [7], the MA with extended neighborhood search of Ta
Data Loading...
