Genetic and artificial bee colony algorithms for scheduling of multi-skilled manpower in combined manpower-vehicle routing problem

Abstract

This paper investigates a scheduling combined manpower-vehicle routing problem with a central depot in and a set of multi-skilled manpower for serving to customers. Teams are in different range of competencies that it will affect the service time duration. Vehicles are in different moving speeds and costs and not all the vehicles are capable to move toward all the customers’ sites. The objective is to minimize the total cost of servicing, routing, and lateness penalties. This paper presents a mixed integer programming model and two meta-heuristic approaches of genetic algorithm (GA) and artificial bee colony algorithm (ABC) are developed to solve the generated problems. Furthermore, Taguchi experimental design method is applied to set the proper values of parameters. The available results show the higher performance of proposed GA compared with ABC, in quality of solutions.

Keywords:

• Vehicle routing problem
• manpower
• competency of working team
• genetic Algorithm
• artificial bee colony algorithm

1. Introduction

The vehicle routing problem (VRP) was introduced by Dantzig and Ramser in 1959 (Dantzig & Ramser, 1959). It is a fundamental planning problem in the field of transportation, distribution, and logistics. This combinatorial optimization problem consists in seeking routes for a set of vehicles, to perform a set of tasks in a network. The VRP can be defined as finding optimal routes for a fleet of vehicles to serve some geographically scattered customers in order to minimize the total operation cost, with each route starting and ending at the depot. Collection of household waste, gasoline delivery trucks, goods distribution, snow plough, and mail delivery are the most used applications of the VRP. The VRP plays a vital role in distribution and logistics. In the traditional VRP, the vehicles are the servers for the customer locations and a customer requires only one task (or visit) by one vehicle. Problems associated with determining optimal routes for vehicles from one or several depots to a set of locations/customers, subject to various constraints, such as vehicle capacity, route length, time windows, etc. are known as VRPs. These problems have a significant economic importance due to the many practical applications in the field of distribution, collection, logistics, etc. In the combined manpower-vehicle routing problem (CMVRP) that is presented in this paper, a central depot is considered in which a set of vehicles and a set of multi-skilled teams originate from it to move toward each customer’s site for servicing tasks. The problem is different from traditional VRP in which the tasks are not done by vehicles but by the teams. Although it is hard to find literature in this problem, it arises in areas like allocation of technicians to service jobs, in hospitals where teams of doctors and nurses are needed for different surgeries, and in the problems of home care sector.

In the previous studies, Lim, Rodrigues, and Song (2004) proposed a manpower allocation model with time windows in which each customer is served by multiple servicemen. However, in their model the servicemen are assumed to be all the same that can move by them and they did not consider vehicles for the movements. Li, Lim, and Rodrigues (2005) extended the model of Lim et al. (2004) by introducing job-teaming constraints while a job is satisfied if the required composite team can be brought together at the job’s location. Hollis, Forbes, and Douglas (2006) are the first to consider a problem with multiple depots, where vehicles and teams may be stationed and interchanged. They describe a simultaneous vehicle and crew routing and scheduling application for urban letter mail distribution at Australia Post, and presented a path-based mixed integer programming model and solved it by heuristic column generation. Zäpfel and Bögl (2008) consider an application of local letter mail distribution for Pickup and delivery routes. Schedules are planned for both teams and vehicles, taking into account European Union social legislation. The problem is solved heuristically, by decomposing it into a generalized VRP with time windows and a ‘personnel assignment problem’. Laurent and Hao (2008) consider the problem of simultaneously scheduling vehicles and teams for a limousine rental company. The required transports are pickup-and-delivery trips with given time windows. The authors use a two-stage solution approach which aims to find a feasible crew and vehicle schedule by assigning a team-limousine pair to each trip. Dohn, Kolind, and Clausen (2009) studied the scheduling problem of ground handling tasks in some European airports. The problem requires manpower allocation with the consideration of time windows, job-teaming constraints, and a limited number of teams in order to maximize the total number of assigned tasks. Kim, Koo, and Park (2010) presented a combined vehicle routing and staff scheduling problem where a certain number of tasks has to be performed in a fixed sequence by a set of teams. The teams should be moved by a set of vehicles and the objective is to find an efficient schedule for the teams. They developed a mixed integer programming model for the problem that could not be solved optimally due to out of memory errors. Hence, they developed a dispatching-based heuristic algorithm to find feasible solutions for the generated problems. Ho and Leung (2010) studied a manpower scheduling problem with job time windows and job-skills constraints. They considered an airline servicing operations before the flights take-off. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign them to the jobs, to service as many flights as possible.

Drexl, Rieck, and Berning (2011) study a simultaneous vehicle and crew routing and scheduling problem arising in long-distance road transport. In their study, they abandon the assumption of fixed assignment of teams to vehicles and allow for vehicle/driver changes at some relay stations. Although their work did not contain a mathematical model, they developed a solution heuristic based on two-stage decomposition for the problem.

In home care sector, Rasmussen, Justesen, Dohn, and Larsen (2012) studied a crew scheduling problem with Preference-based visit clustering and temporal dependencies. A home caring staff has to be assigned to a number of visits to patients’ homes, such that the overall service level is maximized. In their model, the challenge lies within assigning visits to crews, in the existence of soft preference constraints, and temporal dependencies between the start times of visits. Pureza, Morabito, and Reimann (2012) considered a vehicle routing with multiple deliverymen for which, besides routing and scheduling decisions, a number of extra deliverymen can be assigned to each route in order to reduce service times. They presented a model based on the assumptions that each vehicle performs only one route, the deliverymen skills are not different, and the number of the deliverymen that are dedicated to each route affects the related service times. Goel and Meisel (2013) investigated a combined routing and scheduling problem for the maintenance of electricity networks. Each maintenance job therefore consists of multiple tasks which must be performed at different locations in the network. The goal is to assign each task to a worker and to determine a schedule such that the downtimes of power lines and the travel effort of workers are minimized. To solve the problem, they combine a Large Neighborhood Search meta-heuristic with mathematical programming techniques.

Talarico, Meisel, and Sorensen (2015) considered a routing problem for ambulances in a disaster response scenario, in which a large number of injured people require medical aid at the same time. Each ambulance carries medical personnel that can provide first aid to slightly injured people in the field. Seriously injured individuals are accompanied by the medical staff on their way to the hospital where skilled doctors are available. The authors presented two mathematical formulations for their problem of minimizing the latest service completion time and proposed a Large Neighborhood Search meta-heuristic. For a comprehensive and relevant review of the literature, the readers may refer to the taxonomy provided by Lahyani, Khemakhem, and Semet (2015).

This paper addresses a problem integrating vehicle routing and crew scheduling. In this problem, a number of geographically scattered customers demand a specific task with a predefined due date. A number of multi-skilled teams, located at depot, are ready to do the tasks. Each task should be serviced by exactly one team. However, the teams are in different range of competencies which affects the service time. Furthermore, a fleet of vehicles are used to move the teams. The vehicles are in different range of moving speed and not all the vehicles are capable to move toward all the customers. Hence, there is no fixed assignment of a vehicle to a team. Indeed, after visiting a customer, the corresponding vehicle may either continue the route with the companion team or return to the depot to exchange the companion team and then, leave the depot to visit another customer. The objective is to find an efficient schedule for the teams and vehicles movement in order to minimize the total cost of servicing, routing, and lateness penalties. To our knowledge, there is no study related to CMVRP with crew scheduling that considered exchanging teams in depot.

The remainder of the paper is organized as follows. Section 2 presents the problem definition and model formulation. The solution methodologies of proposed Genetic Algorithm (GA) and Artificial Bee Colony Algorithm (ABC) are described in Section 3. The parameter tuning and experimental design is conducted in Section 4. Section 5 provides comparisons between the Cplex software and the meta-heuristic algorithms and discusses the superiority of the proposed GA. Finally, conclusions and future frameworks are drawn in Section 6.

2. Problem definition and modeling

This paper investigates the vehicle routing and crew scheduling problem. There are a number of customers locating in known points. The travel distance between two points is calculated using the Euclidean distance. Each customer demands a specific task and in a predefined due date which is serviced by only one team. The teams are multi-skilled and can perform some, but not all the tasks of customers. The available teams to perform a task are in different competencies, that it will affect the servicing time. The vehicles are in the charge of moving and exchanging the teams in the depot. The vehicles are different from one another in their moving speed and the capability to move toward each customer’s site, which is known in literature as a site-dependent problem. There is no fixed assignment of a vehicle to a team, but teams and vehicles should be synchronized.

After completing one task of a customer by a team, the vehicle in a tour may exchange the companion team with another appropriate team in the depot to perform the next customer’s tasks. If the services to the customers are done after the due date, some penalties of lateness are considered for the problem. The goal is to service all the customers with appropriate teams, in order to minimize all the costs of routing, servicing, and the costs of penalties for lateness. Basic notations are introduced as follows:

Indices

i, j, h Index of nodes i, j, h = 0,1,2,…,N,

k Index of vehicles k = 1,2,…,V,

m Index of teams m = 1,2,…,R.

Parameters

D(i,j): Distance between nodes i, j(i ≠ j),

CV (k): Cost of vehicle k incurred for performing a route,

V (k): Movement speed of vehicle k,

ST(j): Standard duration of the task of customer j,

CT (m): Cost of team m to perform a task,

A (m, i): Matrix of competency of team m to perform the task of customer i,

G (k, i): Matrix of capability of vehicle k to visit the customer i,

D D (i): Due date of servicing for the customer i,

W (i): Penalty of lateness of servicing for the customer i,

M: A big number.

Decision variables

T(i): Finishing time of servicing to customer i,

L(i): Tardiness time of servicing to customer i,

S(i): variable for elimination of sub tour.

Mathematical model

(1)

s.t.(2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14)

The objective function is to minimize total costs of servicing by the teams, routing by the vehicles, and the penalties of lateness. Restrictions (2(2) ) and (3(3) ) ensure that every vehicle should start its tour from the depot and comeback to it at the end of the tour. Restrictions (4(4) ), (5(5) ) and (6(6) ) state that each customer is visited by exactly one vehicle and one team, and the same vehicle and team will leave the visited customer. Restrictions (7(7) ) are subtour elimination constraint set. Constraints (8(8) ) and (9(9) ) show the time connection between two consequent customers in a tour of a vehicle. Constraints (10(10) ) and (11(11) ) are the compatibility constraints for the teams and vehicles to visit the customers. They guarantee that the inappropriate vehicles and teams are not sending to each customer. Equations (12(12) ) and (13(13) ) are to know which teams go over the traveling distance and to define lateness for the customer. Constraints (14(14) ) provide limits on the decision variables.

The number of variables and constraints in the model are presented in Tables 1 and 2, respectively, based on the variable indices.

Table 1. The number of variables in the model.

Variable name	Variable count
	(N + 1)·(N + 1)·R·V
	(N + 1)·(N + 1)·R·R·V
T(i)	N
L(i)	N
S(i)	N
Total	[(N + 1)^2·R·(1 + R)·V] + (3·N)

Table 2. The number of constraints in the model.

Equation number	Constraint count
(2)	V
(3)	V
(4)	N
(5)	N
(6)	N·R·V
(7)	N·(N − 1)
(8)	N·(N − 1)·R·V
(9)	N·(N − 1)·R·R·V
(10)	N + 1·(N)·R·R·V
(11)	N + 1·(N)·R·R·V
(12)	N
Total	2·[(N + 1)·N·R·R·V] + [N·(N − 1)·R·V·(1 + R)] + N·(N − 1) + (3·N) + (2·V) + (N·R·V)

3. Solution methodologies

3.1. Genetic algorithm

The basic concept of GA was introduced by Holland (1962), this algorithm is inspired by the natural evolution mechanism, devises a guided random approach to seek the solution space. GAs are stochastic search techniques based on the natural mechanism and genetic rules of the crossover and mutation.

GA starts with a population which consists of population size (PS) of individuals and it is suitable for encoding or representation of the solution to a problem. Each individual has a fitness value that measures the quality of the solution associated with the chromosome. These are the most generation’s numbers in a simple GA in order to evolve current population to the new one for each iteration. There are basic operations which include: Selection, Crossover, Mutation, and Elitisms.

By selecting parents from the population, in a crossover operation, the parents are combined by crossover operator to produce one or more offsprings based on crossover probability (P_c); the mutation operator alters offspring according to the mutation rules to offset convergence effect and guarantees the population diversity based on mutation probability (P_m); and sometimes, in a GA, a number of fitter individuals are copied directly from current to the new population which is called elitisms The proposed GA steps are as follows:

Step 1. Initial of population

In this step, initial feasible population is randomly produced. To represent a solution, a chromosome is included by an array with (N + V − 1) columns and two rows in which N is equal to the number of customers and V is equal to the number of vehicles. The first row represents the customers, while the second row shows the team’s number. To split the tours of vehicles from each other, the sign star (*) is inserted. A typical chromosome of a solution is shown in Figure 1.

Figure 1. A chromosome representation of a solution.

In Figure 1, customers 3 and 2 are in the tour of vehicle 1 which is serviced consequently by the team 1. The customers 6, 7, and 4 are in the tour of second vehicle. Vehicle 2, after visiting customer 6 should exchange the team 3 by the team 2 at the depot and then move to customers 7 and 4 consequently. Also, Vehicle 3 after visiting customer 5 exchanges the team 2 and 1 at the depot and then moves to customer 1 by the team 1.

Step 2. Objective function

After generating the initial population, objective function should be calculated.

Step 3. Selection strategy

The roulette wheel strategy is used for crossover operation and the random selection strategy is employed for mutation operation. Then, after computing fitness values, better solutions have more chances to be selected using the roulette wheel mechanism as a selection approach.

Step 4. Crossover operator

Crossover starts with chromosomes which are selected from the selection mechanism as parents, and mixes them to produce children. Proposed crossover produces offspring by taking the stars position from parent1 and the combination of customers from parent 2, while the teams are copied from the related customer’s number of both parents. The steps of the crossover operator are as follows:

(1)	Select two parents by roulette wheel strategy.
(2)	Copy the stars positions from parent 1 into same positions of the child’s array.
(3)	Insert the sequence of customers from parent 2 into the remaining positions of the offspring’s array.
(4)	Insert the related team number of parents 1 and 2 in alternate order into every other position of second row of the offspring. The proposed crossover operator is shown graphically in Figure 2.

Figure 2. Crossover operator.

Step 5. Mutation operator

The mutation operator changes the structure of some chromosomes in the generation in order to guarantee diversification in solutions. It also helps to prevent from falling into local optimum trap. The steps of the crossover operator are as follows (Figure 3):

(1)	Select a chromosome randomly from the mating pool.
(2)	Pick up a sequence of genes (one route of one vehicle) from the selected chromosome.
(3)	Reverse the sequence of some of the genes and return them back to the same positions.

Figure 3. Mutation operator.

Step 6. Stopping criterion

Stopping criterion is the number of generations and the algorithm will terminate if it meets the given number of generations.

3.2. Artificial bee colony

ABC algorithm was introduced by D. Karboga and it is based on concept of swarm intelligence, which inspired intelligent foraging behavior of honey bee swarm.

ABC is proposed for global optimization problem because it has many advantages such as memory, multi-character, local search, and solution improvement mechanism. Also, it is applied successfully in neural network (Karaboga & Akay, 2007), scheduling problem (Pan, Fatih Tasgetiren, Suganthan, & Chua, 2011), reliability redundancy allocation problem (Yeh & Hsieh, 2011), and function optimization (Kang, Li, & Xu, 2009; Sonmez, 2011).

Three groups of honey bees are in a natural bee swarm namely: employed bees, onlooker, and scouts. Each solution to the problem is called a food source and is represented by n dimension vector. The title ‘Employed bees’ is called to a bee that currently exploiting for a food source. A bee waiting in the hive area for choosing a food source is named as an onlooker and a bee carrying out random search to find a new food source is called a scout. The process of search that is done by the artificial bees is summarized as follows (Pan et al., 2011):

•	A food source in the neighborhood of the food source in their memory is determined by employed bees.
•	The information obtained by employed bees is shared with onlookers within the hive and the onlookers choose one of the food sources.
•	A food source within the neighborhood of food sources chosen by themselves.
•	An employed bee of which the source has been abounded becomes a scout and starts to search a new food source randomly.

ABC is an iterative process similar to other evolutionary algorithms, such as GA, particle swarm optimization, and imperialist competitive algorithm which starts with population of solutions(food sources).Then, the following steps are looped to meet a termination criterion:

Step 1.	The employed bees are sent to the food sources and measure their nectar amounts.
Step 2.	Select the food sources by onlookers after sharing the information of employed bees and determine the nectar amount of the food sources.
Step 3.	Choose the scout bees and send them to possible food sources.

In a robust search, exploration and exploitation must be done together. In ABC algorithm, onlookers and employed bees carry out the exploitation process in the search space and scouts carry out the exploration process.

The main sections of the basic ABC algorithm are described in detail as follows:

3.2.1. Initialization of the parameter

In the basic ABC algorithm, the parameters are the number of food sources (SN) that is equal to the number of the employed bees, the number of trials for releasing a food source (limit), and termination criterion.

The number of employed colony is set to the number of food sources in the population. Therefore, there is only one employed bee for every food source.

3.2.2. Initialization of the population

The initial population of food sources is generated with SN number randomly. Let represent the ith food source in the population of solutions and each ones is produced as follows:(15)

where i = 1, 2, …, SN and j = 1, 2, …, n; r is a uniform random number in the range [0,1]; UB_j and LB_j are the upper and lower bounds for the dimension j, respectively.

3.2.3. Initialization of the bee phase

In this phase, each employed bee determines a new neighborhood source using the food source that is associated with them as follows:(16)

where k = 1, 2, …,SN and j = 1, 2, …, n are randomly generated indexes, but k must be different from i. R is a uniformly distributed number in [−1,1].

3.2.4. Onlooker bee phase

The nectar amount that is taken from all employed bees is calculated and a food source is selected based on its probability value by onlooker bee. The probability is computed by the following expression:(17)

where fit_i is the fitness value for food source i, which is proportional to nectar amount of the food source i. the fitness function is defined as where f_i is the objective function value of solution i.

After each solution is generated and then evaluated by artificial bee, it is compared with the old one. If the new food source has an equal or bigger nectar amount food source, it is replaced with the old one. Otherwise, the old one is retained. In other words, a greedy selection mechanism is applied between these solutions.

3.2.5. Scout bee phase

The corresponding employed bee becomes a scout when a food source cannot improve through a number of trials limit. In this phase, the food source is abounded and scout produces a food source randomly. It assumes that the abandoned source is x_i and j = 1,2,…,n, n is the solution vector, the scout discovers a new food source which will be replaced with x_i.(18)

where j is determined randomly and it must be different from i.

3.2.6. Stopping criterion

There are two basic stopping criterions in this algorithm. One is the maximum number of iterations, and the other is maximum elapsed time. In this study, both the criterions are considered. In other words, the stopping criterion is the maximum number of iterations or maximum elapsed time.

The structure of encoding method in ABC is similar to GA.

The steps of ABC algorithm are described as follows:

Algorithm 2: ABC algorithm

Step 1: Initialize the population of solutions and evaluate them.

Step 2: Generate new solutions for the employed bees and evaluate them.

Step 3: Use the greedy selection process.

Step 4: Calculate the probability for each solution.

Step 5: Produce the new solutions for onlooker bees and evaluate them.

Step 6: Use the greedy selection process.

Step 7: Determine the abandoned solution for the scout.

Step 8: If a termination is not met, go to Step 2; otherwise stop the process of ABC.

4. Experimental design

4.1. Data generation

To evaluate the effectiveness of the proposed algorithm, some test problem instances are generated. The instances must be comprehensive and representative. So, some parameters such as: location of customers (X, Y), The team’s competency, The team’s wages, Travelling cost of vehicles, The moving speed of vehicles, and Penalty of lateness for the teams are determined experimentally and are given in Table 3.

Table 3. Levels of problem parameters.

Factors	Levels
Location of customers (X,Y)	U(0,1000)
The team’s competency	U[0,1]
The team’s wages	U(10,20)
Travelling cost of vehicles	U(2,8)
The moving speed of vehicles	U(10,20)
Penalty of lateness	U(1,3)

4.2. Parameter setting

In this study, Taguchi experimental design is applied for tuning parameters of proposed algorithms. The Parameter Design was developed by Dr. Taguchi in early 1960s and can be applied to process design. Goal of this method is to minimize the effect of noise factors and determine optimal level of important controllable factors based on the concept of robustness. The signal-to-noise (S/N) ratio denotes the amount of variation in the response variable that must be maximized. The formula is:(19)

where E(OF_i) is mean of objective function in round of i . Also, k is number of loop that each meta-heuristic algorithm should be repeated. The level of the parameters of GA and ABC are presented in Tables 4 and 5.

Table 4. Factors and their levels in GA.

Factors	Symbols	Levels
(Population size, Iteration)	A	A(1)-(80,150)
		A(2)-(100,120)
		A(3)-(120,100)
Mutation probability(PM)	B	B(1)-0.05
		B(2)-0.15
		B(3)-0.25
Crossover probability(PC)	D	D(1)-0.6
		D(2)-0.7
		D(3)-0.8

Table 5. Factors and their levels in ABC.

Factors	Symbols	Levels
(Population of food, Iteration)	E	E(1)-(80,150)
		E(2)-(100,120)
		E(3)-(120,100)
Random number	F	F(1)-(-0.5)
Elitism probability(PE)	G	F(2)-(0.25)
		F(3)-(0.75)
		G(1)-0.05
		G(2)-0.1
		G(3)-0.15

The appropriate orthogonal array in GA and ABC is that is shown in Table 6.

Table 6. The orthogonal array .

Trial	A	B	C	D
1	1	1	1	1
2	1	2	3	2
3	1	3	2	3
4	2	1	3	3
5	2	2	2	1
6	2	3	1	2
7	3	1	2	2
8	3	2	1	3
9	3	3	3	1

The experiments on the GA and ABC algorithms were created on the orthogonal array distribution method, and nine different combinations of factors were considered. Each trial is calculated five times and the mean S/N ratio of the objective value for GA and ABC is shown in Figures 4 and 5. As demonstrated in Figure 4, better performance and robustness of the GA is when the parameters are set on the following levels: PC; 0.6, PM; 0.25 and (PS, Iteration1); (120,100). And robust parameters for ABC are on below levels: (Population of food, Iteration); (80,150), Random number; 0.25 and PE; 0.15.

Figure 4. The average S/N ratio plot at each level for GA.

Figure 5. The average S/N ratio plot at each level for ABC.

The goal of analysis of variance (ANOVA) is to inspect the relevant implication of individual parameters based on the objective value. In other words, by means of ANOVA, the parameters that are more effective in problem will be identified. Tables 7 and 8 illustrated ANOVA in GA and ABC algorithms. Results obtained from ANOVA indicate PC in GA and PE in ABC, showing significant impact on the robustness of the algorithms.

Table 7. ANOVA for S/N ratio in GA.

Factor	DF	SS	MS	F	Percent X	Cumulative	p-Value
(Pop, Iteration)	2	181,963	90,981	18.18	4.18	4.18	0.052
PM	2	988,517	494,258	98.77	23.81	27.99	0.010
PC	2	2,939,658	1,469,829	293.71	71.28	99.27	0.03
Error	2	10,009	5004
Total	8	4,120,146

Table 8. ANOVA for S/N ratio in ABC.

Factor	DF	SS	MS	F	Percent X	Cumulative	p-Value
(Food, Iteration)	2	60,309	30,154	1.14	0.7	0.7	0.266
Random number	2	134,142	67,071	2.54	7.52	8.22	0.282
PE	2	888,025	444,012	16.84	77.17	85.39	0.056
Error	2	52,729	26,364
Total	8	1,135,204

5. Computational results

To evaluate the quality of the proposed procedures, mathematical model was encoded in Cplex11 to solve the test problems exactly when it is possible, and the meta-heuristic procedures were encoded in Matlab7. There are 20 combinations for the different values of Number of nodes; Number of vehicles, Number of teams, and the characteristics of each test problem are illustrated in Table 9.

Table 9. The characteristics of the generated test problems.

Name of problem	Number of nodes	Number of vehicles	Number of teams
CMVRP01	6	2	2
CMVRP02	7	2	2
CMVRP03	7	3	3
CMVRP04	8	2	2
CMVRP05	8	3	3
CMVRP06	9	2	2
CMVRP07	9	3	3
CMVRP08	10	2	2
CMVRP09	10	3	3
CMVRP10	11	3	3
CMVRP11	12	3	4
CMVRP12	12	3	3
CMVRP13	20	4	4
CMVRP14	20	6	4
CMVRP15	20	4	6
CMVRP16	23	4	4
CMVRP17	23	4	5
CMVRP18	25	4	4
CMVRP19	25	5	5
CMVRP20	27	5	4

The test problems were run 10 times on an HP 4520s laptop with 4 GB RAM and a 3 GHz processor running in Windows 7. In Table 10, the results of test problem instances are reported under measures of: best solution and computational time for those instances where the exact solutions are available; and under measures of mean solution and computational time of ABC and GA for the large-sized problems.

Table 10. Comparison of results of the model solved by Lingo 9 and GA with ABC

Problem structure	Global solver(Lingo)		GA			ABC
	Best solution	Computational time^a	Best solution	Computational time^a	RPD	Best solution	Computational time^a	RPD
CMVRP01	9595^b	00:00:01	9595	00:00:20	0	9595	00:00:27	0
CMVRP02	12,854^b	00:00:06	12,854	00:00:25	0.001633733	12,854	00:00:31	0
CMVRP03	16,134^b	00:00:31	16,134	00:00:29	0.018160407	16,134	00:00:41	0.018532292
CMVRP04	18,620^b	00:00:18	18,620	00:00:31	0	18,620	00:00:45	0.000429646
CMVRP05	17,772^b	00:01:14	17,772	00:00:39	0	17,772	00:01:02	0
CMVRP06	21,947^b	00:02:44	22,185	00:00:29	0.010844307	22,185	00:00:57	0.0122568
CMVRP07	19,983^b	00:02:12	20,047	00:00:38	0.005104339	20,047	00:00:37	0.007406295
CMVRP08	25,726^b	00:02:58	25,726	00:00:33	0.001360491	25,726	00:00:46	0.006141647
CMVRP09	22,851^b	00:15:01	22,872	00:00:38	0.008533543	22,984	00:00:46	0.015316616
CMVRP10	28,106^b	00:30:09	28,424	00:00:21	0.010848756	28,621	00:00:52	0.026838261
CMVRP11	23,999^b	00:07:09	24,275	00:00:48	0.012708863	24,512	00:01:13	0.030751281
CMVRP12	27,208^b	00:17:27	27,404	00:01:00	0.008343134	27,285	00:01:03	0.028447515
CMVRP13	34,438^c	02:00:00	34,328	00:01:53	0.017245397	34,374	00:03:25	0.022051969
CMVRP14	34,308^c	02:00:00	34,282	00:01:58	0.012309667	34,545	00:02:22	0.020973105
CMVRP15	35,871^c	02:00:00	35,031	00:01:42	0.006708344	35,213	00:02:01	0.011047358
CMVRP16	42,243^c	02:00:00	39,962	00:01:22	0.003903709	41,076	00:02:01	0.054802062
CMVRP17	40,829^c	02:00:00	40,004	00:01:18	0.002874713	40,119	00:02:08	0.030421958
CMVRP18	56,818^c	02:00:00	44,683	00:01:26	0.016652752	44,317	00:03:12	0.038269738
CMVRP19	60,931^c	02:00:00	45,000	00:02:22	0.0034	45,113	00:03:35	0.027155556
CMVRP20	27,208^c	02:00:00	67,887	00:01:47	0.011533872	70,076	00:03:36	0.050775553
Mean					0.007608			0.011704

^a Computational time (Hour: Minute: Second).

^b Global optimum.

^c Local optimum.

The data show that GA and ABC are not so different based on their objective value in small size problems and both of them perform well for this scale. The mean deviation from the best solutions for the first 12 instances for the GA and ABC are 0.006461 and 0.012177. For the instances 13–19, the local optimum solutions of the Cplex11 are available for comparing purposes.

In large-scale problems, Cplex11 cannot obtain optimum solutions even after the implied computational time. Therefore, we emphasize to compare the performance of the proposed algorithm of GA and ABC in large size problem, to determine the better procedure.

The mean deviation of best solutions from the mean for the GA and ABC are 0.0076083 and 0.0208088. For evaluating the proposed algorithms, relative percentage deviation (RPD) is calculated as Equation (20(20) ):(20)

Figure 6 represents and compares the mean RPD of the proposed GA and ABC for the problem instances. It is clear that for the almost of the instances, GA takes much less amount of RPD.

Figure 6. Comparing the RPD for the GA and ABC.

The results of this experiment are shown in Figure 7 and it is clear that GA has better performance than ABC.

Figure 7. Means plot and LSD interval for the algorithms.

For testing these results obtained by the proposed algorithm, the t-test is chosen as a method for statistical testing. Hypothesis testing is as follows:

in which after conducting the statistical tests, the null hypothesis is rejected for all combinations of parameters at 95% significance level. Thus, GA performs better than ABC in almost of the problems.

Figures 8–10 represent the available results of the performance of the proposed GA and ABC for the test problems divided by the number of nodes, vehicles, and teams, respectively.

Figure 8. Average relative percent deviation for different value of number of depots.

Figure 9. Average relative percent deviation for different value of number of vehicles.

Figure 10. Average relative percent deviation for different value of number of teams.

6. Conclusions and future works

This paper considered CMVRP with multi-skill teams. We presented a new mathematical model in order to deal with the simultaneous planning of multi-skilled teams and transporting vehicles. For solving the generated test problems, two meta-heuristic algorithms, namely GA and ABC algorithm, are proposed to achieve best solutions for the problem. To compare their quality in achieving best solutions RPD measure is used and many instances are generated. Also, the parameters of the proposed algorithms are tuned by Taguchi method. Computational results of 20 standard tests problems and 200 instances revealed that GA is statistically performing better than ABC according to RPD measure. For future research, it is worthwhile to seek a dynamic model of the problem where the teams and vehicles are not gathered in a depot, but in scattered places, and the replacements may happen in every node. Also, it is worthwhile to consider ordering relations or priorities between the services of teams to the customers. Hence, the customers may have some preferences for specials teams to receive their services. It is also possible to think of a step forward heuristic for the problem to reach for feasible and optimum solutions.

Disclosure statement

No potential conflict of interest was reported by the authors.