1 Introduction

The capacitated arc routing problem (CARP) introduced by Golden and Wong (1981) is an arc routing counterpart to the well-known vehicle routing problem. The CARP is defined on an undirected connected graph with edge costs and non-negative edge demands, where edges with positive-demands are called required edges or tasks. A fleet of homogeneous vehicles are based at a single depot. Any edge can be traversed any number of times by vehicles with each required edge being serviced only once. The objective is to find a set of vehicle routes of the least total cost of traversed edges, such that each route starts and ends at the depot while the total demand of each route does not exceed vehicle capacity.

The CARP is NP-hard in that it can be reduced to the NP-hard rural postman problem (RPP) (Lenstra and Rinnooy Kan 1976). During the 1980s and early 1990s, heuristics used to be the mainstream approach to solve the CARP and many heuristics were introduced, such as augment-merge (Golden and Wong 1981), path-scanning (Golden et al. 1983) and route-first, cluster-second (Ulusoy 1985), etc. In the recent decade, some meta-heuristics have been proposed, such as tabu search (Hertz et al. 2000; Brandão and Eglese 2008), variable neighborhood descent (Hertz and Mittaz 2001), guided local search (Beullens et al. 2003), memetic algorithms (Lacomme et al. 2001, 2004; Tang et al. 2009) and ant colony optimization (Santos et al. 2010), etc. A recent review can be found in Liu et al. (2008) and Corberán and Prins (2010).

Applications of the CARP include collection or delivery, street sweeping and snow removal, etc. However, the CARP has its limitation in modeling most real-life applications such as salt spreader routing problem and waste collection. Eglese (1994) and Li and Eglese (1996) study the salt spreader routing problem and propose that there can be multiple depot locations, different capacities of gritters (vehicles) and other constraints in this real-life problem. In municipal solid waste collection, large companies or public sectors usually have more than one depot and they have a fleet of vehicles characterized by different capacities and operating costs to collect or transport waste. Therefore, in this paper we consider two major extensions of the basic CARP, namely heterogeneous vehicles and multiple depots. The resulting new problem can be called the multi-depot heterogeneous fleet CARP (MDHCARP).

The heterogeneous fleet CARP (HCARP) has two versions, one is the heterogeneous fixed fleet CARP with a limited number of vehicles, and the other is the fleet size and mix CARP (FSMCARP) with unlimited ones. The FSMCARP is first introduced by Ulusoy (1985) who proposes the route-first, cluster-second method. Therein, a RPP is solved to form a giant tour, and then the giant tour is partitioned into feasible vehicle routes subject to the constraints by solving the shortest path problem on a transformed new graph. This idea is embedded in our genetic local search (GLS) algorithm. The multi-depot CARP (MDCARP) is studied firstly by Amberg et al. (2000). In their research, this problem is defined on an undirected graph with M depots. A fixed number of vehicles with heterogeneous capacity, but without fixed costs and variable costs, are stationed in each depot. Recently, Kansou and Yassine (2010) and Xing et al. (2010) have studied the MDCARP by using different meta-heuristics.

In this paper, we systematically study the NP-hard MDHCARP for the first time, and propose an effective genetic local search (GLS) algorithm for the problem. It has been shown that metaheuristics combining genetic algorithm (GA) with local search (LS) are powerful for the CARP and its variants (Lacomme et al. 2004; Mei et al. 2011; Tang et al. 2009), because it has the potential to exploit the global search advantage of GA and local search advantage of problem-specific LS. The remainder of this paper is organized as follows: Sect. 2 gives a formal and detailed description of the MDHCARP. The general framework and key components of the proposed GLS are introduced in Sect. 3. Computational experiments on real-life applications and new generated data are presented in Sect. 4, and finally, Sect. 5 summarizes some concluding remarks.

2 Problem definition and notations

The MDHCARP can be described as follows. Given a mixed graph \( G = (V,E \cup A) \) with a set V of n nodes, an undirected edge set E, a directed arc set A. \( E \cup A \) is the set of links (edges and arcs), c ij  = c ji (≥0) is the cost (length) of a link \( (i,j) \in E \cup A \), and \( E_{R} \subseteq E \) and \( A_{R} \subseteq A \) are the sets of t required edges and arcs, respectively. Let \( D \subseteq V \) be the set of M depots. A heterogeneous (different types) fleet of vehicles indexed in a set K is stationed at multiple depots. The number of vehicles of each type k in depot m is fixed (limited) and equals n mk and the total number of vehicles of each type k is n k . A fixed cost λ mk , a variable cost per unit distance μ mk and capacity Q mk is associated to each vehicle of type k in depot m. The MDHCARP is to determine a set of routes in such a way that: (1) the number of vehicles used of each type k is not more than n k , and even each type k from depot m is not more than n mk ; (2) each vehicle route starts and ends at the same depot; (3) each required link (task) is served exactly once; (4) the total demand of each route served by vehicle k from depot m does not exceed Q mk , and its total duration does not exceed a preset value L mk ; (5) the total routing cost is minimized.

To describe the tasks clearly, each required arc is identified by a task number instead of one pair of nodes. Each arc \( u \in A \) has a tail (start node) a(u), a head (end node) b(u) and a traversing (deadheading) cost tc(u). Each required link (task) \( u \in (E_{R} \cup A_{R} ) \) has a demand d(u), a serving cost sc(u); and if u is an edge task, it has an inverse mark inv(u). Task inv(u) and u have the same traversing cost, demand and serving cost. Note that each edge task \( u \in E_{R} \) can be served in either direction, i.e., only one of task u and inv(u) is served. Table 1 summarizes the notations adopted by the paper.

Table 1 List of notations about the MDHCARP
Full size table

3 The genetic local search algorithm

The genetic local search (GLS) algorithm is a combination of a population-based global search genetic algorithm (GA) and an individual-based local search. Our GLS has several main characters: (a) in chromosome encoding for the CARP with complex multi-depot and heterogeneous constraints, the GLS uses a simple permutation (sequence) of t tasks, without cluster and route delimiters (excluding depots); (b) a multi-depot heterogeneous partition (MDH-Partition) procedure is proposed to convert the indirect chromosomes encoding into solutions; (c) in population replacement, one chromosome P r is selected in the parent population using one new replacement method described in Sect. 3.5.

The proposed GLS includes two phases, i.e., a main phase and a restart phase. Initially, each chromosome represents a potential MDHCARP solution through an encoding mechanism. Next, an initial population is generated, and the chromosomes of the population are evaluated by the MDH-Partition procedure of Sect. 3.1.1 and sorted according to a fitness function.

Then, a typical iteration of the main phase proceeds as follows. Selection, crossover and local search operators are implemented to generate an offspring. The offspring is added into the parent population by applying a replacement operator. The new population is then kept sorted again and these operators are repeated until the stopping criterion of the main phase is reached. Finally, the restart phase keeps some best chromosomes of the main phase and generates other new chromosomes to form another initial population, and then the typical iteration is repeated until the termination condition of the restart phase is met. Table 2 shows the basic steps of the GLS. Several main components are described in detail in Sect. 3.1–3.5.

Table 2 General framework of the GLS
Full size table

3.1 Chromosome structure and evaluation

As the MDHCARP belongs to the class of multi-depot routing problems, it is a natural idea to use depots as cluster delimiters, and even as route delimiters for each cluster in encoding corresponding to GAs proposed in the published multi-depot routing problem literature (Ho et al. 2008; Lau et al. 2010; Ombuki-Berman and Hanshar 2009; Kansou and Yassine 2010).

Nevertheless, inspired by Lacomme et al. (2004) and Prins (2009), our chromosome T is a simple permutation (sequence) of t tasks, without cluster and route delimiters (excluding depots). Implicit shortest paths (deadheading paths) are between consecutive tasks. It can be viewed as a RPP or a giant tour traversed by one vehicle without capacity constraints from one depot. This kind of chromosome representation is adopted because: (1) the encoding is simple, and classical GA operators for the travelling salesman problem can be reused; (2) a chromosome can be converted into a feasible MDHCARP solution by the MDH-Partition procedure described in Sect. 3.1.1; (3) the indirect encoding is so flexible that it is suitable for extended problems including new constraints and objectives.

3.1.1 MDH-partition

Under the above chromosome structure, an MDHCARP solution can be obtained by decoding the chromosome using the MDH-Partition procedure. The fitness of each chromosome is evaluated based on the total cost of this corresponding solution.

Given a chromosome \( T = (c_{1} ,c_{2} , \ldots ,c_{t} ) \) where t corresponds to the number of tasks, the MDH-Partition procedure works on an auxiliary directed acyclic graph G a  = (X, Y, Z), where X is a set of t + 1 vertex index from a dummy node 0 to t. Y is a set of arcs where one arc \( (i,j) \in Y \) means that a trip serving tasks subsequence \( (c_{i + 1} ,c_{i + 2} , \ldots ,c_{j} ) \) is feasible in terms of capacity and duration, i.e., load(i + 1, j) ≤ Q mk and length(i + 1, j, m) ≤ L mk where load(i + 1, j) is the load of the trip, length(i + 1, j, m) is the length of this trip served by the vehicle from depot m. Z is the set of the weight of arcs where one weight \( z_{ij}^{mk} \) corresponds to the total cost of vehicle type k from depot m to serve tasks subsequence \( (c_{i + 1} ,c_{i + 2} , \ldots ,c_{j} ) \).

In each depot m, vehicles have k m different types, with a number n mk of vehicles for each type k. Vehicles (even the same size) from different depots will generate different costs, leading to \( z_{ij}^{mk} \) instead of z ij in the CARP. The optimal partitioning of chromosome T corresponds to a shortest path from node 0 to node t in G a , with no more than n mk arcs for vehicle type k from depot m. Thus, this problem is a resource-constrained shortest path problem (RCSPP), which is an NP-hard problem but can be solved in pseudo-polynomial time based on dynamic programming.

In our dynamic programming approach, a set of labels is associated with each node i of the auxiliary graph G a , and each label \( L(v_{11} , \ldots ,v_{{1k_{1} }} , \ldots ,v_{M1} , \ldots ,v_{{Mk_{M} }} ,z) \) represents different paths from the origin 0 to node i with specific consumption of vehicle resources and cost. To be specific, \( v:(v_{11} , \ldots ,v_{{1k_{1} }} , \ldots ,v_{M1} , \ldots ,v_{{Mk_{M} }} ) \) is the consumption combination of all types of vehicles, where v mk indicates the number of vehicle type k used from depot m (1 ≤ m ≤ M, 1 ≤ k ≤ k m , 1 ≤ v mk  ≤ n mk ); and z the corresponding cost of the path associated with the label. The number of possible vehicle consumption combinations is \( \omega = \prod\limits_{m = 1,k = 1}^{{M,k_{M} }} {(n_{mk} + 1)} \), where null consumptions are considered.

To use a simpler notation, let k 1 + k 2 + … + k M equal \( \xi \) which is the total number of vehicle types across all depots. Note that when we define label \( L(v_{11} , \ldots ,v_{{1k_{1} }} , \ldots ,v_{M1} , \ldots ,v_{{Mk_{M} }} ,z) \) and compute \( \xi \), even if vehicle types from different depots are the same, they are still regarded as different because vehicles of the same type and from different depots generate different costs when used; and the number of them may also be different. Then, each kind of possible vehicle consumption combination \( v:(v_{11} , \ldots ,v_{{1k_{1} }} , \ldots ,v_{M1} , \ldots ,v_{{Mk_{M} }} ) \) with two-dimensional suffixes corresponds to a vector \( \hbar :(\hbar_{1} ,\hbar_{2} , \ldots ,\hbar_{\xi } ) \) with one-dimensional suffix and can be further converted into a scalar q ∈ [0, ω − 1]. Thus, we can represent L q i as the qth label in node i for the path ending at node i, i.e., tasks subsequence \( (c_{1} ,c_{2} , \ldots ,c_{i} ) \), and then, \( L_{i}^{q} .v \) as the partial fleet used, \( L_{i}^{q} .v_{mk} \) as vehicle consumptions of type k from depot m, and \( L_{i}^{q} .z \) as the corresponding cost. Given the label \( L_{i}^{q} \) and the arc \( (i,j) \in Y \) (a trip c i+1 to c j ), then

$$ load(i + 1,j) = \sum\limits_{l = i + 1}^{j} {d(c_{l} )} $$
(1)
$$ length(i + 1,j,m) = tc(m,c_{i} ) + \sum\limits_{x = i + 1}^{j} {[sc(c_{x} ) + tc(c_{x - 1} ,c_{x} )} ] + tc(c_{j} ,m) $$
(2)

In Eq. (1), d(c l ) is the demand of task c l , and in Eq. (2), the length includes the traversing cost tc from depot m to task c i , from c i to c i+1 until c j and from c j to the depot m, and the serving cost sc of any task from c i+1 to c j . If the vehicle of type k from depot m is available and load(i + 1, j) ≤ Q mk and length(i + 1, j, m) ≤ L mk , one label \( L_{j}^{r} \) for node j is generated by using recursive equations:

$$ L_{j}^{r} .v_{mk} = L_{i}^{q} .v_{mk} + 1,{ 0} \le i < j \le t, \, 1 \le m \le M $$
(3)
$$ L_{j}^{r} .z = L_{i}^{q} .z + z_{ij}^{mk} ,{ 0} \le i < j \le t, \, 1 \le m \le M $$
(4)

In Eq. (4), \( z_{ij}^{mk} = \lambda_{mk} + \mu_{mk} \cdot length(i + 1,j,m) \). The time complexity of the MDH-Partition procedure is \( O(t^{2} \omega \xi ) \). Since a large number of labels increase the computing time, a dominance rule can be adopted.

In addition, largest capacity check is also useful, which means that if the vehicle with the largest capacity cannot satisfy the condition load(i + 1, j) ≤ Q mk , all of other size of vehicles cannot have enough capacity to serve tasks subsequence \( (c_{i + 1} ,c_{i + 2} , \ldots ,c_{j} ) \). Note that since the number of vehicles of each type is fixed, when the total capacity of vehicles is slightly larger than the total demand, a chromosome may not be able to be converted into a solution by MDH-Partition procedure. In that case, we can add additional vehicles in the process of MDH-Partition without affecting the final solution.

3.1.2 An illustrative example

Consider one example of 4 edge tasks with their respective demands being 8, 14, 8, 9, and two types of vehicles and two depots. A single vehicle with a capacity of 30 (type 1) is stationed in depot 1, and a single vehicle with a capacity of 25 (type 2) is in depot 2. The detailed vehicle information is shown in Table 3. Figure 1a shows the chromosome tour T = (c 1, c 2, c 3, c 4) with demands in brackets. Thin dotted lines represent shortest paths between any two nodes, and the numbers under t = 4 tasks are the serving costs.

Table 3 Vehicle information
Full size table
Fig. 1
figure 1

Example of MDH-Partition. a Chromosome tour with 4 edge tasks. b Auxiliary graph G a , labels and shortest path. c Resulting trips

Full size image

The MDH-Partition procedure builds an auxiliary graph G a with t + 1 nodes indexed from 0 to t, as shown in Fig. 1b. The initial label of node 0 is \( L_{0}^{0} \) with \( L_{0}^{0} .v = \left( {0,0} \right) \) and \( L_{0}^{0} .z = 0 \), i.e., no vehicles are used and no costs are generated. Arcs from node 0 to node 1 represent the trips that serve task c 1 . To be specific, if task c 1 is served by the vehicle of type 1 from depot 1, it leads to the label \( L_{1}^{1} \) with cost \( L_{1}^{1} .z \) = 50 + 1.5 × 36 = 104, and if served by the vehicle of type 2 from depot 2, it leads to the label \( L_{1}^{2} \)with cost \( L_{1}^{2} .z \) =40 + 1 × 26 = 66. But actually in our MDH-Partition procedure, neither of these two labels is generated. The reason is that if task c 1 is served by the vehicle of type 1 (type 2), the remaining capacity is only 25 (30) which is not enough to serve the remaining three tasks with a total demand of 31. Therefore, subsequent labels that arise from \( L_{1}^{1} \) and \( L_{1}^{2} \) are not all generated. In addition, the vehicle of type 1 cannot cover the total demands of four tasks. According to the largest capacity check technique of Sect. 3.1.1, neither can the small size vehicle of type 2, so neither of labels \( L_{4}^{1} \) and \( L_{4}^{2} \) is generated.

A shortest path from node 0 to node t in G a (bold) indicates the optimal partitioning of T: two trips and a label \( L_{4}^{3} \) obtained from label \( L_{2}^{1} \), with vehicles consumption\( L_{4}^{3} .v = \left( { 1, 1} \right) \) and total cost \( L_{4}^{3} .z = 1 9 3 \). The resulting MDHCARP solution is trip (0, c 1 , c 2 , 0) with a cost of 113 served by vehicle 1 from depot 1 and trip (0, c 3 , c 4 , 0) with a cost of 80 served by vehicle 2 from depot 2, as shown in Fig. 1c.

3.2 Initial population

The population P is composed of ps chromosomes. The initial population consists of two good (low-cost) chromosomes and ps-2 random chromosomes. To be specific, two good chromosomes P 1 and P 2 are constructed by using matching-based algorithm (MBA) and modified path-scanning (MPS), both with local search. Note that when chromosomes are randomly generated, identical chromosomes (clones) may result in a premature convergence, and should therefore be avoided. Since exact detection for identical chromosomes is time consuming, we adopt a simpler and faster diversity condition, i.e., two chromosomes do not have the same cost. To meet this condition, we try try_max times to generate each random chromosome and decrease the number of chromosomes in the population if try_max times all fail.

All the above methods generate ps permutations of tasks (giant RPP tours) which are then converted into ps solutions by MDH-Partition procedure. Then each solution is concatenated into one chromosome, and all chromosomes are stored using an array in increasing cost order.

3.2.1 Matching-based algorithm

We recommend matching-based algorithm (MBA) to generate a very good chromosome, because this algorithm proposed by Frederickson (1979) for RPP has a worst-case bound of 3/2, which is similar to the travelling salesman problem heuristic of Christofides (1976).

The MBA works on the original undirected graph, and can be described as follows.

  1. 1.

    Construct a minimum cost spanning tree to connect several components of the original graph, and denote the new graph as G1.

  2. 2.

    Determine a minimum cost perfect matching (Edmonds and Johnson 1973) of the odd degree vertices of G1, denote the new graph as G2.

  3. 3.

    Find an Euler tour of G2 using the end-pairing algorithm (Edmonds and Johnson 1973), and the Euler tour is exactly the RPP tour.

  4. 4.

    Transform the representation of the RPP tour from nodes sequence into tasks sequence with an implicit shortest path between any two consecutive tasks, using pre-marked task numbers for each task.

3.2.2 Modified path-scanning

The original path-scanning algorithm is introduced by Golden et al. (1983) for the capacitated Chinese postman problem. This heuristic builds trip routes based on a greedy idea subject to vehicle capacity Q. In constructing each route, the sequence of tasks is extended by joining the task that looks most promising until Q or maximum trip length L or maximum time duration is exhausted. For a sequence ending at task f, the task closest to f is chosen as the next task. If multiple tasks satisfy this condition, five rules are employed to determine the next task g, not yet served: (1) maximize the distance from g to depot; (2) minimize the distance from g to depot; (3) maximize the ratio of demand/service cost of g, i.e., \( d(g)/sc(g) \); (4) minimize the ratio of demand/service cost of g, i.e., \( d(g)/sc(g) \); (5) use rule 1 if the vehicle is no more than half-full, or else use rule 2.

In our version, due to the coexistence of multi-depot and heterogeneous fleet with different capacities, a giant RPP tour is constructed by using modified path-scanning (MPS), in which there is only one depot (the first depot) and only one vehicle where Q equals the total demand of overall tasks. Note that, MPS starts from the first depot, and chooses different next tasks to serve by implementing five different rules, until all tasks are chosen. Therefore, MPS will generate five different tours. Each of them is followed by the MDH-Partition procedure of Sect. 3.1.1, respectively. Then, five MDHCARP solutions are extracted, and only the best solution is kept.

3.3 Selection and crossover

The proposed GLS selects two parents P1 and P2 randomly from the sorted population. When the two parents are selected, order crossover (OX) (Davis 1985) and linear order crossover (LOX) (Falkenauer and Bouffouix 1991) are randomly selected to implement. Note that the OX and LOX generate two child chromosomes which are both kept in the original OX and LOX, but only one child randomly chosen is preserved in our OX and LOX. Fig. 2 gives one sample of OX with two parents P1 and P2 and two crossover points i = 4, j = 7, where ten tasks are undirected, i.e., inv(1) = 11, inv(2) = 12, and so on. Therefore, when child C1 is filled using P2(j + 1) to P2(i − 1), task 2 in P2 should be excluded because its opposite arc 12 is the same task that has been included in C1.

Fig. 2
figure 2

Example of OX crossover

Full size image

3.4 Local search

A local search (LS) is adopted with a fixed probability p m in our GLS to produce a better offspring after each crossover. The LS works on a MDHCARP solution obtained by implementing the MDH-Partition procedure on the child C, because if it operates directly on the chromosome C without route delimiters, a large amount of time will be spent to evaluate each move of it. Let tasks i and j be served after tasks f and g in their respective routes and all move types are described below.

  • M1: move task f after task g.

  • M2: move two consecutive tasks (f, i) after task g.

  • M3: swap task f and g.

  • M4: swap task f and (g, j).

  • M5: swap task (f, i) and (g, j).

  • M6: 2-opt moves.

The LS scans each pair of tasks (f, g) in \( o(t^{2} ) \), and each iteration of the LS implements M1–M6 and stops when it finds the first improving move, and then the solution is updated and the next iteration is continued until all pairs of tasks are scanned; however, the whole M1–M6 process for each pair of tasks is repeated as long as the solutions can be further improved.

There are several points to be noted in the LS. First, each type of move is implemented in the same route or in two different routes which may or may not be from the same depot. Second, in M1–M5, if a task f is moved to another position, it can appear in either as f or inv (f). Third, in M1 and M2, g can be the start depot of its route. Fourth, in 2-opt, if the move operates on two routes from different depots, we must reconnect the first or last task of the two routes to the two depots after 2-opt, to guarantee that a route starts and ends at the same depot (as shown in Fig. 3).

Fig. 3
figure 3

Example of 2-opt move: a original two routes R1 and R2 from depot m1 and m2, respectively; b the shortest paths linking f to i and g to j are replaced by the shortest paths from f to j and from g to i; c and d new routes are reconnected to depot m1 and m2 in two ways

Full size image

At last, some routes are removed if they become empty. The final solution of LS is converted into a chromosome by concatenating these routes and excluding route delimiters (depots). Then, the chromosome is converted into a solution by the optimal MDH-Partition which sometimes can bring a better solution for the same chromosome.

3.5 Replacement and termination

We propose a new replacement method, i.e., two chromosomes are selected from a subpopulation and the worse one P r is replaced by the child C if C is not identical to any other chromosomes of the parent population. We test several kinds of subpopulation choices, such as the latter 1/2, the latter 2/3 and the whole of the parent population where chromosomes are stored in increasing cost order, and preliminary experiments show that the latter 2/3 is superior. After replacement, the ps chromosomes are stored in increasing cost order again.

As mentioned before, the proposed GLS includes two phases, i.e., a main phase and a restart phase. The main phase stops after a maximum number of iterations (ni). After that, the restart procedure is implemented for nr times, where two best chromosomes are kept, and others are replaced by new randomly generated chromosomes. Then, the main phase is repeated but with a higher local search probability p r . That is to say, the total number of iterations is (1 + nr) × ni.

4 Computational experiments

4.1 Test problems

The MDHCARP is a new problem and there are no benchmark instances. In this paper, we first test the real-life instances dealing with problems of route planning for winter gritting in the areas of Königstein and Wennigsen, Germany, which are from Amberg et al. (2000) and can be viewed as simplified MDHCARPs since no fixed costs and variable costs of vehicles are considered, and then generate new general MDHCARP data from CARP instances. To evaluate our GLS, especially for generated instances, we extend the memetic algorithm (Lacomme et al. 2004) to solve the MDHCARP for comparison. In the extended memetic algorithm (EMA), depots are used as cluster delimiters but not as route delimiters in chromosome encoding, as in Kansou and Yassine (2010). To be specific, a chromosome S consists of M sub-chromosome S m where M corresponds to the number of depots. Each S m is a sequence of tasks associated to depot m, without route delimiters. Then a chromosome is converted into a feasible MDHCARP solution by a heterogeneous partition (H-Partition) to each S m of S. The H-Partition for the single depot HCARP is a special case of the MDH-Partition.

4.1.1 Simplified MDHCARP cases

The data of three real-life instances are shown in Table 4 and the corresponding sketch maps of the first two instances are shown in Fig. 4a and b. In Table 4, the first column stands for the instance name; |V|, |E| and t indicate the number of nodes, the number of edges, and the number of tasks, respectively; T D represents the total demand; M is the number of depots; m is the depot node; Q mk is vehicle capacity of each type k in depot m; n mk and CT mk are the corresponding number of vehicle and time capacity, and fixed costλ mk and variable cost μ mk of each vehicle are not given. In Fig. 4, dashed lines are non-required edges which can be traversed but do not have to be served, solid lines represent required edges, and blue solid lines are parallel tasks.

Table 4 Three simplified MDHCARP cases
Full size table
Fig. 4
figure 4

Graphs about Königstein problem (a) and Wennigsen problem (b)

Full size image

The first instance is a relatively large size problem in the area of Königstein. Six vehicles are stationed in the same depot (node 8) but have different time and vehicle capacities. In this sense, it is a single-depot HCARP. The graph has 65 nodes and 93 required edges with total demand 202 (Amberg et al. (2000) state 94 required edges by mistake). The time capacity CT mk is the maximum time duration of vehicle of type k from depot m and can be converted into the maximum trip length L mk , since the average speed of vehicles is given as 30 km/h. Special conditions are that the vehicle with capacity Q = 650 must pass a load station node 65 and one edge (15, 16) is a narrow street and must be served by a small vehicle with Q = 150 or Q = 250.

The second instance concerns the area of Wennigsen. Six vehicles are stationed in two depot nodes 1 and 15. They have different vehicle capacities but no time capacities. The graph has 48 nodes and 55 required edges with a total demand of 229.4.

The third instance (Wennigsen-modified) arises from the Wennigsen problem, and the only difference between them is that the third instance eliminates four of the required edges, i.e., (17, 13), (13, 18), (15, 17) and (18, 19), and thus has 51 required edges. Therefore, the total demand is decreased to 214.5.

4.1.2 New MDHCARP instances

Some general MDHCARP data are generated by adding depots and vehicle types in three sets of standard CARP instances (gdb, val and egl files) which can be downloaded from http://www.uv.es/~belengue/carp.html. The gdb set is 23 small size instances with 7–27 nodes and 11–55 edges; the val set includes 34 medium size instances with 24–50 nodes and 34–97 edges and the egl set contains 24 large size instances with 77–140 nodes and 98–190 edges. In the gdb and val sets, all the edges are required edges (tasks), and the egl set has 51–190 required edges and some non-required edges.

The general MDHCARP instances are generated from three benchmark sets of CARP problems: gdb, val and egl, so named mdh-gdb, mdh-val and mdh-egl, respectively, which are available upon request from the authors. For each instance, we change the original depot number from one depot into 2–5 depots, and replace the original homogeneous fleet with a heterogeneous fleet of 3–5 different vehicle types stationed at depots, according to the problem size. For the vehicles of each instance, their respective capacities Q mk are in arithmetic progression, and their respective number n mk is set to guarantee that the total capacity equals the original capacity; their fixed costs λ mk are equivalent to their respective capacities; their unit variable cost μ mk is 1.0, 1.2, …, 1.8. Table 5 gives the example of mdh-egl-s1-C generated from egl-s1-C.

Table 5 An example of general MDHCARP instances
Full size table

4.2 Parameter settings

The GLS and EMA are implemented in C and executed on an Intel (R) Pentium (R) Dual 1.8 GHz PC under Windows XP.

Preliminary experiments were required to determine the best parameter settings. In these experiments, the following combinations of factors are tested: (1) population size ps tested at two levels, 30 and 50; (2) maximum value of try_max to generate each random non-clone chromosome tested at two levels, 10 and 20; (3) local search probability p m in the main phase tested at four levels, 0, 0.15, 0.3 and 0.5; (4) local search probability p r in the restart phase tested at three levels, 0.25, 0.5 and 0.75; (5) maximum iteration number of the main phase ni tested at two levels, 5,000 and 10,000; (6) maximum value of restarts nr tested at two levels, 10 and 20. Preliminary tests were done on the 34 instances of mdh-val generated problems.

The parameters based on the experimental results are set as follows: the population size ps is 30, the maximum value of try_max to generate each random non-clone chromosome is 10, the local search probability p m and p r in the main phase and restart phase are 0.5 and 0.75, respectively, the maximum iteration number of the main phase ni is 5,000, and the maximum number of restarts nr is 10.

4.3 Results on the simplified MDHCARP

For the Königstein problem, the comparison between the GLS and EMA and four strategies of Amberg et al. (2000) is shown in Table 6 (Boldface indicates the new best solution). Note that, in Amberg et al. (2000), each solution corresponds to the total length of additional edges (deadheading length); therefore, the total travelling length equals the solution plus the total length of required edges. Take the Königstein problem for instance, the best solution is 79.5, and the total travelling length should be 79.5 plus 202. Amberg et al. (2000) gives four strategies using Simulated Annealing and Tabu Search, i.e., SA t, STS s, CSM c 1 c 2 c 3 and REM r where SA, STS, CSM and REM are names of strategies, and t, s, c 1 c 2 c 3 and r are their respective parameters. In Table 6, we only show the best result of each strategy instead of giving all of them. Note that in Amberg et al. (2000), the CPU time is the average time of the last improvement instead of the total computing time.

Table 6 Comparison between the GLS and EMA and four published metastrateties for Königstein problem
Full size table

In Table 6, the third and fourth columns are the best and average solutions of the EMA and GLS over 10 runs, respectively, the fifth column is the average computing time in seconds. From Table 6, we can find that even the average solutions of the GLS and EMA outperform all meta-strategies of Amberg et al. (2000), and the GLS is the best algorithm which has a better average solution and gets the new best solution in less time than EMA. The new best solution is 273.5 with an improvement of 2.84 % and the computing time is acceptable. The corresponding routes are given in detail in Königstein of Appendix.

For the Wennigsen problem, the comparison between the GLS and EMA and four strategies of Amberg et al. (2000) is shown in Table 7 (Boldface indicates the new best solution). From Table 7, we can find that the new best solution with cost 325.8 is obtained easily with an improvement of 1.81 % and likewise the GLS converges faster than the EMA. The corresponding routes are given in Wennigsen of Appendix.

Table 7 Comparison between the GLS and EMA and four published metastrateties for Wennigsen problem
Full size table

For the Wennigsen-modified problem, the computing time and the number of iterations are not given in Amberg et al. (2000) whose best solution is 329.2 (104.7 plus 214.5). The GLS and EMA both can improve the result by 3.34 % after 0.70 and 0.92 s, respectively, and the corresponding routes of the new best solutions with cost 318.2, are shown in Wennigsen-modified of Appendix.

GLS and EMA outperform the metaheuristics of Amberg et al. (2000) in that GLS and EMA combine genetic algorithm (GA) with local search (LS), and they have the potential to exploit the global search advantage of GA and local search advantage of problem-specific LS.

4.4 Results on the general MDHCARP

The results of the general MDHCARP instances (mdh-gdb, mdh-val and mdh-egl) are presented in Tables 8, 9, 10. For each instance, two good initial solutions generated by heuristics MBA and MPS, and improved by LS, respectively, are given in columns 2–5, and the average solutions, the best solutions, and the average computing times in seconds over 10 runs for EMA and GLS are shown in columns 6–8 and columns 9–11, respectively. In Tables 8, 9, 10, if the best solution of the GLS (GLSbs) is superior to that of the EMA (EMAbs) then it is shown in bold.

Table 8 Results of the mdh-gdb set
Full size table
Table 9 Results of the mdh-val set
Full size table
Table 10 Results of the mdh-egl set
Full size table

The average solution quality of the algorithms is summarized in Table 11. For each file, the first row shows the average results and the second row reports the average deviations (in  %) above the best-known solutions (BKS) which are our best solutions obtained from the GLSbs. Main conclusions can be drawn from the results as follows.

Table 11 Average solution quality of the algorithms
Full size table
  1. 1.

    The solutions of the GLS and the EMA are much better than two good initial solutions of the simple heuristics. For example, the average deviations of the initial solutions obtained from MBA + LS from the best solution GLSbs are 1.26, 5.30 and 9.12 % on mdh-gab, mdh-val and mdh-egl files, respectively.

  2. 2.

    The local search is effective. To be specific, MBA + LS improves MBA by 11.3, 4.5 and 7.9 % on three files, respectively. MPS + LS improves MPS by 3.6, 4.6 and 8.8 % on three files, respectively.

  3. 3.

    The GLS outperforms the EMA both in the results and in the computing time. To be specific, the average solutions of the GLS (GLSas) over all instances are better than those of the EMA (EMAas); for small size instances of the mdh-gdb set, the EMAbs obtains the same best solutions as the GLSbs, but requires additional computing time; while for medium and large size instances, the average deviations of the EMAbs from the GLSbs are 0.17 and 0.42 %, respectively. It can be found that the GLS obtains new best solutions on 20 out of 34 mdh-val instances, and 17 out of 24 mdh-egl instances, which is better than the EMA. Compared with EMAas and EMAbs, GLSas and GLSbs save on average 0.2 and 0.4 % on two files. GLS outperforms EMA in that in GLS, the chromosome T is a permutation (sequence) of t tasks, without cluster and route delimiters (excluding depots) and an optimal possible MDHCARP solution can be extracted from a chromosome by the MDH-Partition procedure, while in EMA, a chromosome is a sequence S of M (the number of depots) sub-chromosome S m where each S m is a sequence of tasks associated to depot m. A feasible MDHCARP solution by a heterogeneous partition (H-Partition) to each S m of S is a local optimal solution, and therefore worse than an optimal MDHCARP solution extracted from a chromosome T by the MDH-Partition procedure.

  4. 4.

    The computing times of the GLS and the EMA are both reasonable, even for large size problems.

5 Conclusions

This paper introduces the MDHCARP, a problem that despite its many real-life applications, has not received much attention in previous research on the CARP. The MDHCARP is to determine the least cost routes for a given heterogeneous fleet of vehicles to serve a set of required edges and arcs (tasks). The vehicles located at multi-depot are with different capacities, fixed costs and variable costs.

Due to its theoretical complexity, we propose the GLS and EMA for the MDHCARP, which extend the classic memetic algorithm (hybrid genetic algorithm) to both multi-depot and heterogeneous fleet constraints. The simplified MDHCARPs from real-world cases are tested and new better solutions are found by the GLS and EMA in reasonable computation times. A large number of general MDHCARP instances generated from CARP instances are also tested and the results show that the GLS outperforms the EMA.

Note that our GLS is also effective for the multi-depot fleet size and mix CARP, where the number of available vehicles of each type is unlimited. The main modification is that the chromosome evaluation corresponds to the shortest path problem instead of the resource-constrained shortest path problem.

Our work is a foundation for future research on complicated constraints on the CARP. We plan to extend in several ways. First, an efficient lower bound can be provided to evaluate our GLS. Second, more complex and practical constraints can be involved, such as time windows and periodic demands for tasks. Due to the flexibility of the GLS, we intend to extend it to tackle these additional attributes. Finally, we also plan to propose some new operators to improve the performance of the GLS, as well as other more efficient hybrid metaheuristics combining population search and local search.