![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
ABSTRACT
The increasing number of vehicles on the road produces negative effects for health, the environment, quality of life, and the economy, among other areas. To address this problem, an important key is carpooling private vehicles from different homes to a common destination. This paper specifically addresses the long-term carpooling problem, which is an NP-complete problem. The proposed approach is a modified biogeography-based optimization metaheuristic, which is hybridized with a variable neighborhood search. Comparisons with efficient known approaches indicate the effectiveness of the proposed approach for large-scale long-term carpooling problems.
Introduction
Vehicle use has increased, which has caused negative effects such as traffic congestion, air and noise pollution, insufficient parking places, and general degradation of quality of life. As a result, human health, the environment, and the economy are negatively affected. Although public transportation is an adequate response to this problem, it is not a sufficient response. Therefore, carpooling should be established through carpooling incentive policies.
Carpooling exists in two forms, the daily carpooling problem (DCPP) and the long-term carpooling problem (LTCPP). In the DCPP, a set of users or servers is declared each day. Each server picks up its colleagues or clients for the particular day. The problem is to generate for each server a set of clients that fits car capacities and time windows constraints. The DCPP objective is to minimize the total traveled distance. The DCPP is a particular case of the dial-a-ride problem (Ho et al. Citation2018). In the LTCPP, however, the objective is to connect each user to a subgroup called a pool for a long time. In the pool, each user, in turn, acts as a server and picks up the other users or clients of its pool from their homes and carries them to a common destination. The user then performs the inverse route under car capacities and time windows constraints. In the LTCPP, the pools are more stable than in the DCPP, and the objective is to reduce the number of pools and the total traveled distance. The LTCPP is a multi-objective problem; it was proven to be NP-complete (Varrentrapp, Maniezzo, and Stützle Citation2002).
Moreover, the LTCPP was tackled by exact and approximate methods. Baldacci, Maniezzo, and Mingozzi (Citation2004) addressed LTCPP with an exact method. They have exposed two formulations of the LTCPP, one with the clustering approach and one with the partitioning approach of set partitioning. The dual problem of the second formulation, dual set partitioning, was resolved with the column generation method. The benchmark was composed of 35 instances with a maximum size of 250 employees.
Given that the LTCPP is an NP-complete problem, approximate methods are more appropriate to resolve it, especially when the problem is large. Thus, the LTCPP has been addressed using specific heuristics and metaheuristics. The heuristics include the saving functions heuristic (Ferrari et al. Citation2003), the simulation-based algorithm (Correia and Viegas Citation2008), and the multi-matching system (Shangyao, Yan, Chen, and Lin Citation2011). More specifically, the saving functions heuristic is based on a matching preference of two users to be pooled together; this preference corresponds to the saved cost, two users by two. The authors of the simulation-based algorithm adopted a divide and conquer approach. As such, the first stage of the algorithm is based on a k-means clustering algorithm. This clustering is based on minimizing the sum of square distances between the users and the centroid of each corresponding cluster. The second phase is treated by an optimization programme that searches to combine pools in order to obtain the smallest number of groups with high numbers of users. The authors of the multi-matching system treated a different problem, the long-term carpooling many-to-many carpooling problem. In this case, a derived Lagrangian problem is constructed and resolved to produce a lower bound. The upper bound is computed by using a Lagrangian heuristic. The sub-gradient method is used to adjust the Lagrangian multipliers. An iterative process is performed until an acceptable convergent solution is obtained or until a fixed maximum number of iterations is reached. This approach is time consuming, especially for large-scale problems.
A number of metaheuristics were utilized to address the LTCPP. Maniezzo et al. (Citation2004) have examined the LTCPP with two metaheuristics inspired from ant colony optimization algorithm (ACO). For one metaheuristic, the solution is constructed completely. In the other, ants construct component solutions as pools that are later combined through an integer solver programme. Guo, Goncalves, and Hsu (Citation2012) have proposed an approach based on the transformation of ACO to a clustering approach. They named this approach the clustering ant colony (CAC). Each ant in the CAC constructs the pools guided by preference information during their tour. When all ants have accomplished their tours, the obtained solutions are improved by a variable neighborhood search (VNS) (Mladenovic and Hansen Citation1997). Guo, Goncalves, and Hsu (Citation2011) also developed an approach known as the guided genetic algorithm (GGA). In this algorithm, the initial population is generated by a sweep heuristic (Gillett and Miller Citation1974). The crossover and mutation operators are guided by preference information, which is constituted from the best fits, and the local search is performed by mutation. The preference information is updated at each iteration, and it accomplishes two important roles: it avoids infeasible solutions which helps repair them, and it guides crossover and mutation GGA operators. Mlayah, Boudali, and Tagina (Citation2018) have suggested an approach based on VNS hybridizing with Tabu search (TS) (Glover Citation1977) that they named HVNTS. In this approach, the initial population is generated by using a sweep heuristic. Then VNS is used as the diversification process, while TS acts as the intensification process. Su, Zhou, and Yu (Citation2019) have treated the LTCPP problem different from the one treated by the aforementioned authors. In the model of Su, Zhou, and Yu, not all users have cars. Additionally, the model considers other parameters, including the number of days and the number of servers for each day. The authors have suggested the hybrid metaheuristic approach of artificial bee colony (ABC) with a VNS TL (VNSTL). They named this approach the ABC-VNSTL. The VNSTL performs the employee and onlooker phases, while the scout phase is conducted through an approach known as the scout diversity protection. Instead of modifying one dimension at each step, as in classical ABC, the ABC-VNSTL modifies several dimensions at the same time. As a result, its convergence is accelerated.
This paper contributes to the field by proposing an efficient modified biogeography-based optimization (BBO) to resolve large-scale LTCPPs. The rest of this paper is organized in five sections. The problem is defined in the six section. The second section explains the mathematical model. The classical BBO metaheuristic (Simon Citation2008) is introduced in the third section. The new approach of a modified BBO is detailed in the fourth section. The fifth section provides a comparison of this approach with other efficient approaches, while, the sixth section presents the conclusion.
Problem Definition
In the LTCPP, users must reach their common destination by sharing their cars. Each user within a pool, in turn, picks up the other members of the same pool in route toward the common destination. Each user has the following specified constraints:
A limited car capacity when the user plays the server role
A maximum driving time when the user plays the server role
An earliest leaving time from home
A maximum arriving time at work
A penalty cost when a user travels alone
The LTCPP is a multi-objective problem that first clusters users in subgroups called pools such that the sum of traveled routes must be the shortest; second, the number of pools must be the fewest. The objective of the LTCPP is to minimize the total traveled distance by all users and to minimize the number of used cars under car capacities and time window constraints.
Mathematical Model
The mathematical model of the LTCPP is presented below (Guo, Goncalves, and Hsu Citation2012). The LTCPP can be modeled by means of a directed graph , where
is the set of users, {0} is the common destination, and
is the set of arcs between each user and the others and between each user and the common destination. The mean shortest paths of a pool
is defined by Equationequation (1)
(1)
(1) .
Where is the user that acts as a server,
is the cost of the shortest path starting from
and ending at
by connecting all users of the pool
,
is the size of the pool
,
is the cost of the direct travel of the server
to the common destination. When a user
travels alone, a penalty
is added to the travel cost.
Since an LTCPP solution is composed from pools, the total cost of a solution is the sum of the costs of
pools. The LTCPP mathematical model notations are defined as follows:
: A binary variable that equals 1 if the arc
is traveled by a server
of a pool
; it equals 0 otherwise.
: A binary variable that equals 1 if the user
belongs to a pool
; it equals 0 otherwise.
: A binary variable that equals 1 if a user
travels alone.
: A positive variable indicating the pickup time of a user
by a server
.
: A positive variable denoting the arrival time at the common destination of a user
when picked up by the server
.
: A positive variable indicating the travel cost between two users
and
.
: A positive variable indicating the travel time between two users
and
.
: A positive variable indicating the minimum car capacity of a pool
.
: A positive variable indicating the maximum driving time a user
can accept.
: A positive variable indicating the earliest leaving time accepted by a user
.
: A positive variable indicating the latest arriving time at the common destination for a user
.
: A positive variable indicating the penalty for a user
when traveling alone.
: Index set of pools.
: Index set of users.
A: Index set of arcs.
The objective function is:
Subject to the following constraints:
EquationEquations (3)(3)
(3) and (Equation4
(4)
(4) ) require user
to be affiliated with pool
, and if a path begins with user
, only one of the arcs
or
can be traveled. EquationEquation (5)
(5)
(5) guarantees the continuity constraint. EquationEquation (6)
(6)
(6) assumes that each user
traveling alone is penalized, thus privileging user
being pooled with other users. EquationEquations (7)
(7)
(7) and (Equation8
(8)
(8) ) are car capacity and maximum accepted travel time, respectively. The feasible pickup times are guaranteed by Equationequations (9)
(9)
(9) and (Equation10
(10)
(10) ), while the minimum and maximum values of arrival times are assured by Equationequations (11)
(11)
(11) and (Equation12
(12)
(12) ), respectively.
Biogeography-Based Optimization (BBO)
Biogeography is the study of the distribution of species on earth, their migrations between habitats, and their extinctions. Dan Simon (Citation2008) has proposed BBO as a population-based metaheuristic for global optimization based on this phenomenon. To carry out the equilibrium principal (MacArthur and Wilson Citation1967) and optimization process (Ma Citation2010; Volk Citation2003), BBO uses a mathematical model where:
Each habitat represents a solution;
Each habitat has a habitat suitability index (HSI) to represents its quality and, thus, the fitness of a solution;
Each habitat is characterized by
suitable index variables (SIV), which represent variables of the addressed problem;
Each habitat
has an immigration rate
and an emigration rate
;
The two migration rates are functions relevant to the number of species;
The species, which are SIV(s), migrate from one habitat to another according to migration rate probabilities;
Each habitat (solution) is subject to mutation on its SIV(s).
After generating an initial population of habitats, BBO uses three operators, migration, mutation, and elitism. The migration operator performs information exchange between habitats. Rather than producing new individuals as evolutionary algorithms with a crossover operator, BBO modifies the existing individuals by using a migration operator (Simon Citation2008). The mutation operator perturbs the individuals to diversify the population and escape the local optima traps. The elitism mechanism guides the intensification process. The pseudo code of the BBO algorithm is as follows:
Algorithm 1: BBO algorithm
Initialization
While stop criteria not verified
Evaluate the quality (HSI) of each solution
Memorize the K solutions having best quality (having the higher level of HSI)
Migration: migrate randomly the habitats (solutions) by using the rates λ and μ
Mutation: mutate the solutions which don’t belong to elite
Replace the population of solutions by the descendants
Implementing elitism: replace worst habitats by the bests known
End While
The BBO migration process is relevant to the immigration and emigration rates, which are computed by Equationequations (13)(13)
(13) and (Equation14
(14)
(14) ), respectively. These two equations define the linear model represented by .
Where and
are the initial immigration and emigration rates,
is the number of species of habitat
, and
is the maximum number of species. The linear model was compared with other models, including constant, trapezoidal migration models among others (Ma Citation2010).
Algorithm 2: BBO migration algorithm
Select with a probability
If is selected then
For do
Select with probability
If is selected then
Select randomly from
Replace a random SIV in by
End if
End for
End if
Where is a user parameter,
the probability that a habitat has
species, and
is the probability that a habitat has the maximum number of species.
Algorithm 3: BBO mutation algorithm
For i = 1 to N do
Compute from and
the probability
Compute the mutation rate with Equationequation (15)
(15)
(15)
// Browse SIV(s) of the solution to mutate
For do
If alors
Generate randomly a feasible
// Replace the SIV of the solution to mutate
End If
End for
End for
BBO is a performant metaheuristic. Therefore, it has been widely used in different areas of transport, such as VRP problems (Berghida Citation2015), image processing (Zheng et al. Citation2016), power and electricity (Chatterjee et al. Citation2012), robotics (Zhang, Wang, and Chen Citation2019), wireless networks (Zhang et al. Citation2015), data mining (Zhao et al. Citation2019), economics and social sciences (Du and Simon Citation2013), and the internet of things (Cao, Wang, and Li Citation2014), among other domains.
Hybrid Modified Mutation BBO
Solution Encoding
A habitat (solution) can be implemented by an indirect (binary) or direct (real) representation; in this case, the direct representation was chosen. The direct or real representation is advantageous given that it does not require an interpretation of intermediate solutions or a translation of the final solution. In addition, Guo, Goncalves, and Hsu (Citation2012) as well as Mlayah, Boudali, and Tagina (Citation2018) have used this representation.
Two levels of information emerge from the problem: the clustering of users into independent pools and within each pool, and the route that each user browses when they play the role of server. To address the LTCPP by using BBO, the following correspondences were conducted ():
A habitat represents a solution;
The total cost of a solution is equal to the HSI of a habitat;
A pool represents a species and, thus, an SIV;
In turn, each user in a pool plays the role of server, who picks up the rest of the pool users.
The Hybrid Modified Mutation BBO Algorithm
The difficulty of using any metaheuristic is balancing diversification and intensification; this balancing is an open problem (Yang Citation2014). Therefore, the BBO algorithm structure was modified to address the balance problem and the LTCPP problem. The new algorithm was named the hybrid modified mutation BBO (HMMBBO). The global idea of HMMBBO is to use as an intensification process migration combined with elitism and to allow a modified mutation operator to aid the diversification process. Instead of mutating a large number of species, as in the BBO, the mutation is applied to a reduced number of pools (species). The HMMBBO performs small and large mutations in the beginning of the process and only small mutations at the end. This strategy favors diversification at the beginning and intensification at the end. After the mutation, a migration combined with an improvement that is performed through a VNSTL of a randomly selected habitat. In VNSTL, two TLs were used. The first TL was used to avoid selecting the same solution twice, while the second was used to list the pools that could not be improved. As in nature, mutated species migrate, interact, and attempt to improve themselves; the latter phenomenon is simulated by implementing VNSTL. The HMMBBO algorithm is defined in algorithm (4).
Important differences exist between a classical BBO and the HMMBBO. First, elitism is not applied when a mutation is performed. In other words, elitism is only used in the intensification phase. The aim of this modification is to allow mutated individuals to interact among themselves and with the rest of the individuals. Another difference is the use of the mutation operator only after a number of fails and not at each iteration, as in classical BBO. The third difference is the use of migration as a propagator of new information provided by mutation in the diversification phase. The last difference is the hybridization with VNSTL to improve the new habitats and their interactions. In the next section, useful reduce functions are defined before detailing migration and mutation operations.
Algorithm 4: HMMBBO algorithm for LTCPP
Load instance data
Initiate the table of allowed and not allowed user pairs to be pooled one with each other
Initiate BBO parameters: population size N, migration rates λ and μ, elite size
Generate Initial population composed from structured and random
While stop criteria not verified
Evaluate the quality () of each solution
Memorize the K solutions having best quality (having the lowest HSI)
Compute the rates of immigration (λ) and emigration (μ) for each solution
Compute the probability for each number of species P
Migration satisfying problem constraints
If (nbfails > m and rand (0,1) < α)
If ((||/
) < ω) and (iter/nbTotIter) < r and nbMutation >
and nbRenew <
)
//Mutation: used as a renew of population (LM: Large Mutation)
Modified Mutation (minLM, maxLM)
nbRenew = nbRenew + 1
nbMutation = 0
Else
//Mutation: mutate a reduced number of species
Modified Mutation (minRM, maxRM)
nbMutation = nbMutation + 1
nbRenew = Max (0,nbRenew – 1)
End if
// Propagation of information
Migration
//Improve m solutions randomly
VNSTL
nbfails = 0
Else
Replace the worst solutions by the elite solutions of precedent generation
End if
If (||/
<ω)
nbfails = nbfails + 1
Else
nbfails = 0
End if
End While
Useful Reduce Functions
The search space of LTCPP is large and contains many infeasible solutions. Avoiding such solutions maximizes the amount of computing time spent exploring more feasible solutions. Therefore, useful reduce functions (Baldacci, Maniezzo, and Mingozzi Citation2004) were used. These functions were used for the following purposes:
To construct a table of potentially allowed users to be pooled together when Equationequation (16)
(16)
(16) is satisfied; they are not allowed to be pooled together otherwise;
To identify users that must be alone if Equationequation (17)
(17)
(17) is violated;
To control during the resolution process if the addition of a user to a pool violates time window constraints before controlling them for each route; this control is performed with Equationequations (18)
(18)
(18) and (Equation19
(19)
(19) ).
Where is the shortest time route from a user
to all users of the pool
, and
is the shortest time route between traveled routes by all users of pool
.
Where is the earliest leaving time of all users of pool
,
is the potential earliest leaving time of user
when playing the role of server and if added to pool
. Therefore, the first term of Equationequation (19)
(19)
(19) added to the shortest travel time of pool
must be less than or equal to the minimal last arrival time of user
and of all users of pool
.
Initial Population
An initial population of habitats is generated from structured and randomized individuals. The generation of the structured individuals is based on a modified version of the heuristic used by Guo (Citation2012). The heuristic has been modified by merging pools with one user when feasible. The goal of the modified heuristic is to provide, from the beginning of the research process, a heterogeneous population and hence a diversity in terms of pool composition.
Migration
The migration operator has an important function in BBO. It is the operator through which the exchange of information between habitats is performed. First, a habitat receiving species, which are pools containing information, is selected according to a probability based on the immigration rate
. Then, each habitat
from which a species or pool emigrates is selected according to a probability based on the emigration rate
. One pool emigrates from each selected habitat. This process does not create a new descendant but modifies existing ones, as illustrated in . The migration operator is implemented in algorithm (5).
The migration of a from a habitat
to a habitat
causes user redundancy in the pool of
. Therefore, the solution
becomes inconsistent. The response to this situation is to remove these users from their pools. After doing so, some affected pools may contain one user, which penalizes the pool cost and, consequently, the entire solution. As a result, the algorithm attempts to merge the penalized pools. provides an example of the migration of one pool according to the following description.
Step 1: Select a habitat
to receive a pool from a habitat
.
Step 2: Select the pool containing users 8, 12, 10, and 6 from the habitat
.
Step 3: Migrate the selected pool to habitat
and remove redundant users from other pools of
.
Step 4: Merge user 19, who is alone due to migration operation.
Algorithm 5: HMMBBO migration algorithm for LTCPP
Select with a probability
If is selected then
For do
Select with probability
If is selected then
Select randomly with a size greater than 1 from
If then
Add to
Remove from other pools of users having the same users of
Attempt to merge affected pools of which their sizes = 1
End if
End if
End for
End if
Mutation
In any metaheuristic the diversification process is an important process. On the one hand, it allows escape from local optima traps and encourages exploration of new areas. On the other hand, it could prevent the improvement of local optima if used prematurely or frequently. Therefore, the modified mutation operator is performed only under the conditions defined in algorithm (4). Moreover, in HMMBBO mutation is modified to control the size of mutation by two parameters that indicate the range of mutations by habitat. As a result, the number of species to mutate depends on the two parameters in a random manner. The aim of this modification is to define the move size to another search space and, therefore, attempt to escape local optima traps and to explore other areas.
In BBO, the mutation operator guaranteed the diversification process and had to be used for this purpose. In the modified mutation operator of HMMBBO, different operators were used to address the LTCPP. The operators ‘swap,’ ‘merge,’ ‘move,’ and ‘divide’ were used in the intensification process to improve the existing solutions in the CAC and GGA approaches of Guo, Goncalves, and Hsu (Citation2012, Citation2011) as well as the HVNTS approach of Mlayah, Boudali, and Tagina (Citation2018). In contrast, the operators in the proposed approach were used for diversification regardless of the improvement of existing solutions. The operators were defined and used as follows:
Swap: A number of pools with more than one user are randomly selected. For each selected pool, the swap is performed with another pool of the same habitat; the last pool is selected randomly and can have any size. This operation is repeated until all pools are visited or until a valid swap is identified.
Merge: A portion of unfilled pools are randomly selected. Each pool is merged with another of the same habitat, and the last pool is selected randomly. Similar to the swap operator, this operation ends at the first valid merge.
Move: A pool with more than one user is randomly selected. Then, another unfilled pool of the same habitat is randomly selected. The operator moves one user of the first pool into the second pool, and the operation is repeated until a valid move is reached or until all pools are visited. This operator is applied to a portion of pools.
Divide: A full pool is randomly selected and divided into two pools; each must contain more than two users. This condition avoids the penalty over cost in the case of a pool with one user.
Divide-Merge: This creates a new pool with two users from two different pools. First, one pool containing more than two users is randomly selected. Then, the pools of the same habitat are sorted according to the gravity center of the first selected pool. This operator associates one user from the first selected pool with another user of the other pools, in the above-mentioned order.
MoveAll: The goal of this operator is to move each user of a selected pool to another pool of the same habitat. If one user of the concerned pool is not successfully moved, the operation fails. This operator is applied to a portion of pools.
BrokeAloneUser: This operator is applied to pools with one user. It first attempts to merge the pool; if the merge fails, it attempts to move a user from another pool with more than one user. If both of these operations fail, a swap is attempted.
These neighborhood operators are used as described by algorithm (6). The operators ‘divide’ and ‘divide-merge’ are used less frequently than the others in the mutation. Their less-frequent use is attributed to the fact that these two operators increase the number of pools that can degrade a number of solutions. As such, they could result in the intensification process being penalized.
Algorithm 6: HMMBBO mutation algorithm for LTCPP
Mutation (int minMutations, int maxMutations)
For i = 1 to N do
Compute the mutation rate with Equationequation (15)
(15)
(15)
// define the max number of iterations between and
For do
If then
//
For do
//Select randomly m distinct pools between m1 and m2
// according operator
For do
// Apply a neighborhood operator on each selected pool
(
)
End for
End For
End If
End For
End for
Information contained in the mutated habitats is propagated by the migration operator and improved by the VNSTL, as described in the section dedicated to the HMMBBO algorithm. The VNSTL uses the same operators as mutation, although in this case they are used to improve and not to diversify. Therefore, each neighborhood operator succeeds if it enhances the quality of the habitat to which it is applied. Two user parameters are defined for VNSTL, the number of solutions for enhancement and the number of authorized successive fails for each neighborhood operator.
Results and Comparisons
Experiments have been conducted by using the new approach based on an improved BBO algorithm. The objects of these experiments have included those derived by Guo (Citation2012) and from VRP hard instances (Baldacci, Maniezzo, and Mingozzi Citation2004). The results of HMMBBO were compared to those obtained by Guo (Citation2012). The instances are composed from two types, clustered and randomized. Each type is then composed of nine instances divided into three groups of three instances of 100, 200, and 400 users. The HMMBBO was implemented in Java, and experiments were conducted on a laptop equipped with an Intel processor Core™ i5-4210 U 1.7 Mhz CPU. All results were obtained after 30 runs.
The results from the new approach were compared with those obtained by Guo (Citation2012) and the approaches multi-agent self-adaptive genetic algorithm (AGA), GGA, and CAC. Two versions of HMMBBO were performed, HMMBBO1 and HMMBBO2. These versions are different on the VNSTL parameters. For HMMBBO1, the number of modified solutions by VNTSL for each iteration is one, and the number of authorized fails for each neighborhood operator is one. The values of these two parameters for HMMBBO2 are a random number between one and two, and five respectively.
In addition, HMMBBO1 outperforms the three other approaches on five clustered instances, and it is outperformed only by AGA in the instances of C202, C203, and C402. In contrast, HMMBBO1 is outperformed by all the approaches in C201. With HMMBBO2, the obtained results from HMMBBO1 are improved in all clustered instances. In fact, HMMBBO2 outperforms AGA on C202 and C402. On the other hand, AGA outperforms HMMBBO2 in C201 and C203, yet the latter is closest to CAC for this instance. provides the results for clustered instances. Furthermore, HMMBBO1 and HMMBBO2 are more efficient for random instances, as HMMBBO1 outperforms AGA, GGA, and CAC in all instances except R402, for which HMMBBO1 and AGA demonstrate the best result. However, HMMBBO2 outperforms HMMBBO1, AGA, GGA, and CAC in all random instances. The result comparisons for randomized instances are reported in . On the other hand, HMMBBO1 and HMMBBO2 are less time consuming than the other approaches. While the CPU time increases quickly for the three other approaches, HMMBBO1 and HMMBBO2 are less time consuming. illustrate the CPU time progression for clustered and randomized instances.
Table 1. Results for clustered instances
Table 2. Results for randomized instances
Conclusion
This paper proposes the HMMBBO approach to address the LTCPP by using migration and elitism as intensification processes and performing the diversification process with a modified mutation operator. Moreover, the diversification phase has been combined with a propagation phase based on the use of a migration operator and an improvement with VNSTL, without using elitism. As a result of these two phases and the absence of elitism, HMMBBO avoids losing new information provided by the mutation operator. Consequently, HMMBBO has the advantages of BBO, thus escaping local optima traps by disabling the negative effects of elitism.
In fact, HMMBBO has been demonstrated to be more efficient than the well-known approaches of AGA, GGA, and CAC in 16 instances and in 18 for its second version, HMMBBO2. In the other instances, HMMBBO provides promising and competing results compared to those obtained by AGA, GGA, and CAC. These results have been achieved with the two HMMBBO versions in less time than with AGA, GGA, and CAC.
However, the HMMBBO results from two instances have been outperformed by the results provided by AGA. Therefore, the results for these two instances should be improved, in addition to improving HMMBBO in general. Any future research must be extended to include other metaheuristics that address the LTCPP.
Acknowledgments
Our sincere thanks to the Directorate General for Scientific Research and Technological Development (DGRSDT), Ministry of Higher Education and Scientific Research for its support of this work.
References
- Baldacci, R., V. Maniezzo, and A. Mingozzi. 2004. An exact method for the car pooling problem based on lagrangean column generation. Operations Research 52 (3):422–39. doi:10.1287/opre.1030.0106.
- Berghida, Meryem, and Abdelmadjid Boukra. 2015. EBBO: An enhanced biogeography-based optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows. The International Journal of Advanced Manufacturing Technology 77 (9–12): 1711–25.
- Cao, J., F. Wang, and P. Li. 2014. An improved biogeography-based optimization algorithm for optimal reactive power flow. International Journal of Control and Automation 7 (3):161–76. doi:10.14257/ijca.2014.7.3.16.
- Chatterjee, A., P. Siarry, A. Nakib, and R. Blanc. 2012. An improved biogeography-based optimization approach for segmentation of human head CT-scan images employing fuzzy entropy. Engineering Applications of Artificial Intelligence 25 (8):1698–709. doi:10.1016/j.engappai.2012.02.007.
- Correia, G., and J. M. Viegas. 2008. A structured simulation-based methodology for carpooling viability assessment. Transportation Research Board 87th Annual Meeting, Washington DC, USA.
- Du, D., and D. Simon. 2013. Complex system optimization using biogeography-based optimization. Mathematical Problems in Engineering 2013:1–17.
- Ferrari, E., R. Manzini, A. Pareschi, A. Persona, and A. Regattieri. 2003. The car pooling problem: Heuristic algorithms based on savings functions. Journal of Advanced Transportation 37 (3):243–72. doi:10.1002/atr.5670370302.
- Gillett, B., and L. Miller. 1974. A heuristic algorithm for the vehicle dispatch problem. Operations Research 22 (2):340–49. doi:10.1287/opre.22.2.340.
- Glover, F. 1977. Heuristics for integer programming using surrogate constraints. Decision Sciences 8 (1):156–66. doi:10.1111/j.1540-5915.1977.tb01074.x.
- Guo, Y. 2012. Metaheuristics for solving large size long-term car pooling problem and an extension. Ph.D. thesis, Universit´e Lille Nord de France
- Guo, Y., G. Goncalves, and T. Hsu. 2011. A guided genetic algorithm for solving the long-term car pooling problem,“ 2011 IEEE Workshop On Computational Intelligence In Production And Logistics Systems (CIPLS), pp. 1-7, doi: 10.1109/CIPLS.2011.5953357.
- Guo, Y., G. Goncalves, and T. Hsu. 2012. A clustering ant colony algorithm for the long-term car pooling problem International Journal of Swarm Intelligence Research. 3 (2):39–62.
- Ho, S. C., W. Y. Szeto, Y.-H. Kuo, J. M. Y. Leung, M. Petering, and T. W. H. Tou. 2018. A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological 111:395–421. doi:10.1016/j.trb.2018.02.001.
- Ma, H. 2010. An analysis of the equilibrium of migration models for biogeography-based optimization. Information Sciences 180 (18):3444–64. doi:10.1016/j.ins.2010.05.035.
- MacArthur, R., and E. Wilson. 1967. The theory of Island biogeography.Monographs in population biology. Princeton: Princeton UniversityPress.
- Maniezzo, V., C. Antonella, D. Vigo, and H. Hildmann. 2004. An ANTS heuristic for the long – Term car pooling problem. New Optimization Techniques in Engineering 15:411-430.
- Mladenovic, N., and P. Hansen. 1997. Variable neighborhood search. Computers & Operations Research 24 (11):1097–100. doi:10.1016/S0305-0548(97)00031-2.
- Mlayah, I., I. Boudali, and M. Tagina. 2018. A hybrid variable neighborhood tabu search for the long-term car pooling problem. In Hybrid intelligent systems. vol. 923, ed. A. M. Madureira, A. Abraham, N. Gandhi, and M. L. Varela, 481–90. Cham. Springer International Publishing.
- Simon, D. 2008. Biogeography-based optimization. IEEE Transactions on Evolutionary Computation 12 (6):702–13. doi:10.1109/TEVC.2008.919004.
- Su, S., F. Zhou, and H. Yu. 2019. An artificial bee colony algorithm with variable neighborhood search and tabu list for long-term carpooling problem with time window. Applied Soft Computing 85 (December):105814. doi:10.1016/j.asoc.2019.105814.
- Varrentrapp, K., V. Maniezzo, and T. Stützle. 2002. The long-term car-pooling problem: On the soundnessof the problem formulation and proof of NP-completeness. TechnischeUniversitatDarmstadt.
- Volk, T., Gaia’s Body. 2003. Toward a physiology of earth. Cambridge, MA: MIT Press.
- Yan, S., C.-Y. Chen, and Y.-F. Lin. 2011. A model with a heuristic algorithm for solving the long-term many-to-many car pooling problem. IEEE Transactions on Intelligent Transportation Systems 12 (4):1362–73. doi:10.1109/TITS.2011.2158209.
- Yang, X. S. 2014. Swarm intelligence based algorithms: A critical analysis, Evolutionary Intelligence. 7 (1):17–28.
- Zhang, X., D. Wang, and H. Chen. 2019. Improved biogeography-based optimization algorithm and its application to clustering optimization and medical image segmentation. IEEE Access 7:28810–25. doi:10.1109/ACCESS.2019.2901849.
- Zhang, Y., S. Wang, Z. Dong, P. Phillip, G. Ji, and J. Yang. 2015. Pathological brain detection magnetic resonance imaging scanning by wavelet entropy and hybridization of biogeography-based optimization and particle swarm optimization. Progress In Electromagnetics Research 152:41–58. doi:10.2528/PIER15040602.
- Zhao, F., S. Qin, Y. Zhang, W. Ma, C. Zhang, and H. Song. 2019. A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem. Expert Systems with Applications 126:321–39. doi:10.1016/j.eswa.2019.02.023.
- Zheng, Q., R. Li, X. Li, N. Shah, J. Zhang, F. Tian, J. Li, and J. Li. 2016. Virtual machine consolidated placement based on multi-objective biogeography-based optimization. Future Generation Computer Systems 54:95–122. doi:10.1016/j.future.2015.02.010.