Elsevier

Applied Soft Computing

Volume 12, Issue 1, January 2012, Pages 506-515
Applied Soft Computing

An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems

https://doi.org/10.1016/j.asoc.2011.08.015Get rights and content

Abstract

This paper investigates an oriented spanning tree (OST) based genetic algorithm (GA) for the multi-criteria shortest path problem (MSPP) as well as the multi-criteria constrained shortest path problem (MCSPP). By encoding a path as an OST, in contrast with the existing evolutionary algorithms (EA) for shortest path problem (SPP), the designed GA provides a “search from a paths set to another paths set” mutation mechanism such that both of its local search and global search capabilities are greatly improved. Because the possibility to find a feasible path in a paths set is usually larger than that of only one path is feasible, the designed GA has more predominance for solving MCSPPs. Some computational tests are presented and the test results are compared with those obtained by a recent EA of which the encoding approach and the ideas of evolution operators such as mutation and crossover are adopted in most of the existing EAs for shortest path problems. The test results indicate that the new algorithm is available for both of MSPP and MCSPP.

Graphical abstract

The proposed PS-ABC algorithm inherits the bright sides of other relevant methods, and simultaneously has the abilities of prediction and selection. Results show that PS-ABC has an extremely fast convergence speed like I-ABC and good search ability.

  1. Download : Download full-size image

Highlights

► We design an oriented spanning tree (OST) based genetic algorithm (GA) for the multi-criteria shortest path problem (SPP). ► By encoding a path as an OST, the designed GA provides a search from a paths set to another paths set ± mutation mechanism such that both of its local search and global search capabilities are greatly improved. ► The designed GA has more predominance for solving multi-criteria constrained SPPs as well as the non-additive SPPs.

Introduction

As a classic network problems, the shortest path problem (SPP) is one of the relatively few network optimization problems for which exact and polynomial time solution algorithms exist[1], [2], [3], [4]. The objective of the SPP is to find the least cost path through a network from a predetermined origin to a predetermined destination. Since the SPP was proposed by Dijkstra in 1959 [1], it has been widely applied in real life. For example, in traffic system, there are many path problems such as transport path (dissimilar path) of hazardous materials [5], [6], the transit path of passenger [7], [8], [9] and the path in car navigation system (CNS) [10] and so on.

Numerous extensions of the basic SPP exist. In general, these extended versions are more difficult to solve. Two of these extended versions are the multi-criteria SPP (MSPP) and the SPP with some additional constraints, say constrained SPP (CSPP). The CSPP is an extended SPP in which the path may be constrained to include a specific number of nodes [11], or include nodes within a pre-specified “covering” distance of every node in the network [12], [13] or include one additional constraint that establishes an upper limiting on the sum of some other arc cost for the path [14]. Unfortunately, the addition of such constraints to the SPP [15] or the multi-criteria [15] generally results in a problem that belongs to the set of problems known as NP-hard.

Though the MSPP and CSPP are widely studied over recent years and the evolutionary algorithms (EA) are adopted for solving MSPP[16], [17], [18], [19], [20], [21], however there have been only a few attempts in applying EA for CSPP and multi-criteria CSPP (MCSPP), particulary, for those for MCSPP. At a guess, the primary reason maybe is the difficulty to deal with the infeasibility of a path. In this paper, an oriented spanning tree (OST) based GA which provides a “searching from a paths set to another paths set” mutation operator is introduced for solving the MSPP as well as the MCSPP. By this mutation operator, to great extent, the difficulty to handle the infeasible path for the CSPPs is decreased.

The encode method and evolution operator are the key issues in the evolutionary algorithm (EA) for the path problems [17]. In most of the existing EA for solving the SPPs, particularly the SA and GA, a path is usually encoded as an arcs or edges series. Because different paths from the origin to the destination includes a variable number of nodes and a random arcs or edges series usually does not correspond to a path [17], so the mutation operation is implemented by regenerating some path segments in current path, for example the encode approach and evolution operator in the EAs in [16], [17], [18], [19], [20], [21]. The primary issues in these EAs are summarized as follows:

Firstly, that two paths may not have any common node except the origin and destination of the paths lead to the crossover can not be efficiently performed[17]. Moreover, the regenerating path segment mutation operation will lead to the difference between the current solution and its neighboring solution obtained by mutation is too large to hold the stability of the solution [17]. On the other hand, the obtained neighboring path may be infeasible when the related problem is CSPP. Generally, an infeasible path is usually handled in EA by repairing it to feasible or adding some penalty value to the value of its objective function such that it cannot be selected in next generation as far as possible. This repairing approach results in a further damage of solution and the penalty approach results in the decreasing of global search capability of GA. These are undesirable when design an evolutionary algorithm.

Note that the mutation of GA serves as the role of local search or neighbor search while the crossover operator serves as the role of global search. Generally, the mutation in GA is “search from a point to another point”. It is well known that in contrast with simulated annealing (SA) the local search capability of GA is lower than that of SA while the global search capability of SA is lower than that of GA.

In this paper a solution or a path is encoded as an oriented spanning tree (OST) rooted at the origin of the path and the neighboring searching is performed by OST permutation, where oriented means that if the network is directed, then all of directions of the arcs in a path in the OST are same and along with the direction leaving from the root node. We can easily obtain a paths set consists of the neighboring paths of the unique path from the origin to destination in the OST by using information in the encoded OST of a solution. This implies that a solution is decoded as a paths set and the neighbor searching is thus moved from an OST (or from a paths set) to another OST (or another paths set). By this way, the possibility of encountering a feasible solution is greatly increased and to some extent, from another point of view, because of searching from a paths set to another paths set, both of the local and the global search capability of the designed GA is also greatly enhanced. In addition, because the mutation and crossover are performed by OST permutation, so the designed GA overcome the mentioned defects of the mutation and crossover in existing EA for path problems.

This paper is organized as follows. Firstly, some terminologies and the related MSPP and MCSPP models are introduced in Sections 2.1 and 2.2, respectively, and some applications of the extended SPPs, which can be solved by the designed GA, in urban traffic system are introduced in Section 3. Then an OST based GA is given in Section 4. Finally, some numerical experiments are tested in Section 5.

Section snippets

Preliminaries

In this section, some mathematical terminologies and the related mathematical model are introduced in Section 2.1, and the notations with respect to multi-criteria optimization are introduced in Section 2.2.

The SPPs in urban traffic system

As stated previously, the SPP and its extended versions have been widely applied in urban traffic system (UTS). However, all of its extensions in UTS are almost those of NP-hard. Futhermore, there are many indices to measure a path in UTS, for example, path length, traffic time, costs, environmental measure, dissimilar measure [10], the measures in [23] and many other measures. Consequently, some of these extended SPPs in UTS are those of multi-criteria, for example, the bi-criteria dissimilar

The oriented spanning tree based genetic algorithm

Genetic algorithm (GA), as powerful and broadly applicable stochastic search and optimization techniques based on the mechanism of natural selection and natural genetic, is an approach which can provide near-optimal solutions to combinatorial optimization problems [24]. Holland [24] provided fundamental descriptions of GA. The GA has been applied to a vast number of optimization problems over the past few years. The GA starts with an initial set of randomly generated solutions, say population.

Numerical experiments

In this section, some numerical examples are designed. To evaluate the designed GA, the statistical analysis method is adopted. As stated previously the ideas of evolution operators in Gen and Cheng's GA [17] are widely employed in most of recent EAs for different extended SPPs, for example those in [16], [17], [18], [19], [20], [21], so the behavior of the designed GA and that of Gen and Cheng's GA [17] are compared with some statistical indices such as the average values of objective

Conclusion

In this research a new GA for determining optimal pathes of MSPPs and MCSPPs has been presented. By encoding a path as an OST, an OST permutation based mutation and crossover operators were developed and by decoding an encoded solution, namely an OST, into a set of paths, this GA provided a “search from a paths set to another paths set” mutation mechanism such that both of capabilities of the local search and global search of the designed GA were clearly improved. And once again, by decoding an

Acknowledgement

This research is supported by National Natural Science Foundation of China (no. 60870008).

References (35)

  • AifadopoulouG. et al.

    Multiobjective optimum path algorithm for passenger pretrip planning in multimodal transportation networks

    Journal of the Transportation Research Board

    (2008)
  • KimB.K. et al.

    Optimal route search in car navigation systems by multi-objective genetic algorithms

    International Journal of Information Systems for Logistics and Management

    (2009)
  • DeoN. et al.

    Shortest-path algorithms: taxonomy and annotation

    Networks

    (1984)
  • CurrentJ.R. et al.

    The shortest covering path problem: an application of locational constraints to network design

    Journal of Regional Science

    (1984)
  • CurrentJ.R. et al.

    Efficient algorithms for solving the shortest covering path problem

    Transportation Science

    (1994)
  • HandlerG.Y. et al.

    A dual algorithm for the constrained shortest path problem

    Networks

    (1980)
  • GareyM.R. et al.

    Computers and Intractability: A Guide to the Theory of NP-Completeness

    (1979)
  • Cited by (33)

    • Model and algorithm for 4PLRP with uncertain delivery time

      2016, Information Sciences
      Citation Excerpt :

      GA [22] is one of the most widely used EAs in recent decades to solve constrained optimization problems [42]. Because of the strong search capability, controllable search process and easy improvability, many scholars [37,39] use GA to solve the CSPP. In this research, several improved GAs are designed to solve our problem.

    • Generic constraints handling techniques in constrained multi-criteria optimization and its application

      2015, European Journal of Operational Research
      Citation Excerpt :

      However, for the DOPs having an eligible solution based algorithm, their constraints can be handled by a more efficient approach in Section 4.2, where the eligible solution based algorithm implies that in each of iterations an eligible solution is found. As was known to us that the EAs have been applied in the solution algorithms of MSPP, for example, the SA (Liu, Mu, Luo, and Li, 2012) and GA (Liu and Mu, 2012). All of these EAs are also that of the eligible solution based.

    • Exact algorithms for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network

      2014, Applied Mathematical Modelling
      Citation Excerpt :

      The recent researches of applying EA to bi-criteria SPP are the oriented spanning tree (OST) based genetic algorithm (GA) [22] and the simulated annealing (SA) [23]. Numerical test shows that convergence behaviors of EAs in [22,23] are predominance over that in [21]. In recent, some of the research topics are focused on the dynamic multi-modal SPPs.

    View all citing articles on Scopus
    View full text