A simulated annealing for multi-criteria network path problems
Introduction
The shortest path problem (SPP) is to find the least cost path between the predetermined origin and destination in a given network and is one of the oldest and widely used problems in network optimization [13], [16]. Meanwhile, the SPP is also one of the relatively few network optimization problems for which exact and polynomial time solution algorithms exist [14], [40]. Follows from practical point of view, the SPP is extended to various versions such as the dissimilar path problem [2], [43], the time-dependent SPP [11], the multi-modal SPP [55], the multi-criteria SPPs (MSPPs) [27], [29] and the constrained SPP (CSPP) [3], [18], [26], [50].
The MSPP is an extension of the traditional SPP and is concerned with finding a set of efficient paths with respect to two or more objectives which are usually in conflict with each other. The CSPP is another extended version of the traditional SPP by associating each of the network arcs with a special weight in the sense of resource and is to find the minimum cost path from predetermined origin to destination in the network such that the total resources along this path does not exceed a given bound. Unfortunately, the multi-criteria or the addition of such a resource constraint to the SPP generally results in the problems that belong to the set of problems known as NP-hard [23].
Furthermore, some of the extended versions of SPP are those with nonlinear (or nonadditive) or no-concave objective functions, for example, the dissimilar path problem (DPP) [43], the time-dependent SPP [11], the stochastic SPP [4], [15], [44], [48] and the path problem in traffic equilibrium assignment (TEA) [9], [28], [53]. Additionally, the optimal solution of some path related problems is a set of paths, for example, the DPP and the transit route problem [12], [19], [20]. In addition, from the practical point of view, some of the SPPs in real system have much higher requirements about runtime of the solution algorithm, for example, the SPPs in car navigation systems (CNS) of the urban traffic system (UTS) [31], [33], [41] and the application of the DPP in evacuation [43]. Generally, a path problem in real system (e.g., in the UTS) is the SPP which synthesizes a variety of characteristics such as nonlinear, time-dependent, stochastic, dynamic, constrained, multi-criteria and so on. From algorithmic point of view, because the evolutionary algorithm (EA) does not have much mathematical requirements about the optimization problems, the EA is one of the primary and efficient approaches to solve the SPP with such a variety of characteristics [25]. Among the EAs for various SPPs, the most widely adopted is the genetic algorithm (GA), for example, the GAs in [10], [15], [32], [33], [39], [42], [47], [54].
It is well known that, in contrast with the simulated annealing (SA), because of the larger population size and the crossover and selection operations, the runtime of GA is usually much longer than that of SA while the GA can obtain higher quality solutions than SA [21], [22]. In other words, if the problem has higher requirement about the runtime of solution algorithm, then the SA is more suitable; otherwise the GA is suitable. Though SA has been applied to a vast number of the optimization problems over the past years, however, there have been only a few attempts in extending SA to multi-criteria optimization (MO) primarily because of its “search from a point to point” and “converge to Pareto optimal set” of MO [5]. Such defects are also existed in applying SA for solving MSPPs.
Motivated by the attempts to improve the previously stated defects of the SA by Bandyopadhyay [5] such that SA can be further used to the MSPPs in special forms such as nonlinear, time-dependent, stochastic, dynamic and constrained, this paper investigates a SA for solving these special MSPPs with higher requirement about runtime of the solution algorithm. The primary contributions include following four aspects:
- •
Using an enlarging representation, a solution is represented as an oriented spanning tree (OST) which contains a path from origin O to destination D, where oriented means that if the network is directed, then all of directions of the arcs in a path in the OST are the same as the direction leaving from the root node.
- •
By combing such a representation with the network representation in [30], we propose a one-to-many decoding approach by which a set of feasible paths from origin to destination can be easily obtained with computing complex O(n), where n is the number of network nodes.
- •
Based on such a representation and the decoding approach, the mutation (i.e., the neighboring search) of the designed SA is performed by OST permutation. By this way, a “search from an OST (i.e., a paths set) to another OST (i.e., another paths set)” neighboring search is provided and, to some extent, the defect summarized by Bandyopadhyay [5] for applying SA to MSPPs is thus overcome. Furthermore, because of “search from a paths set to another paths set” the possibility of encountering a feasible solution of the MCSPPs is greatly increased and, to some extent, both of the local and global search capability of the designed SA are enhanced.
- •
Using the obtained paths set by decoding, an improved distance based evaluating approach is designed for computing the (i.e., the energy increment in terms of SA) between the test solution and the current solution.
This paper is organized as follows. Firstly, some of the research literatures with respect to EAs for solving MSPPs are surveyed in Section 2. Secondly, some mathematical terminologies are defined in Section 3.1 and the notations regarding multi-objective optimization are introduced in Section 3.2 and the related mathematical models are also introduced in Section 3.2. The SA for solving MSPP and MCSPP is investigated in Section 4. Finally, the designed SA is evaluated via some benchmarks in Section 5.
Section snippets
Literature review of the EAs for MSPP
As a valid tool for solving optimization problems in the set of NP-hard, the evolutionary algorithm (EA), particularly, the genetic algorithm, has also been extended to find an approximate Pareto optimal set of the MSPPs. According to the adopted representation approach, the existing EAs for SPP can be categorized into four types, i.e., the nodes series based GA (NSBGA) by Ahn and Ramakrishna [1], the 0-1 string based GA (0-1-SBGA) by Mohamed et al. [45], the priority based GA (PBGA) by Gen and
Preliminaries
In this section, some mathematical notations are introduced in Section 3.1, the notations with respect to multi-criteria optimization and the related mathematical models are introduced in Section 3.2.
The OST based simulated annealing
This section will elaborate the details of the proposed SA for solving the MSPP (3.3a), (3.3b) and MCSPP (3.4a), (3.4b), (3.4c). Simulated annealing (SA) as a popular search algorithm is an approach which can provide near-optimal solutions to combinatorial optimization problems though Geman and Geman [24] provided proof that SA, if annealed sufficiently slow, converges to the global optimum. Kirkpatrick et al. [34] and Eglese [17] do provide fundamental descriptions of SA. The SA is guided by
Numerical experiments and discussion
In this section, the designed SA is numerically tested. Experiments include those in Section 5.1 for sensitivity analysis of the parameters and those in 5.2 Experiments for small scale examples, 5.3 Experiments for large scale examples, 5.4 Experiments for MCSPP, 5.5 The application in solving the nonlinear and stochastic MSPP for small scale MSPPs, relatively large scale MSPPs, constrained MSPPs and stochastic MSPP, respectively.
The SA has been widely applied in solving some route related
Conclusions
The test results show that the adopted representing and decoding methods as well as the mutation operator in the designed SA can really improve both of the local search and the global search capability of the designed SA. Therefore, the designed SA is available to solve the bi-criteria SPPs and CSPPs.
In recent years, there has been a growing interest in studying evolutionary algorithms for different path problems, particularly the simulated annealing and genetic algorithm. The ideas such as the
Acknowledgements
This research is supported by National Natural Science Foundation of China (No. 60174049).
References (55)
- et al.
On finding dissimilar paths
European Journal of Operational Research
(2000) - et al.
A penalty function heuristic for the resource constrained shortest path problem
European Journal of Operational Research
(2002) - et al.
Dynamic shortest path in stochastic dynamic networks: ship routing problem
European Journal of Operational Research
(2003) - et al.
The shortest route through a network with time-dependent internodal transit times
Journal of Mathematical Analysis and Applications
(1966) - et al.
The transit route arc-node service maximization problem
European Journal of Operational Research
(2011) - et al.
Genetic algorithms for routing shortest paths in dynamic and stochastic networks
European Journal of Operational Research
(2003) Simulated annealing: a tool for operational research
European Journal of Operational Research
(1990)- et al.
An improved FPTAS for restricted shortest path
Information Processing Letters
(2002) - et al.
An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems
Applied Soft Computing
(2012) - et al.
Heuristics for the bi-objective path dissimilarity problem
Computers & Operations Research
(2009)
Least possible time paths in stochastic time-varying networks
Computer Operational Research
A genetic algorithms to solve the bicriteria shortest path problem
Electronic Notes in Discrete Mathematics
Fuzzy shortest path problems incorporating interactivity among paths
Fuzzy Sets and Systems
An effective genetic algorithm approach to multiobjective routing problems
Applied Mathematics and Computation
Dynamic and stochastic shortest path in transportation networks with two components of travel time uncertainty
Transportation Research Part C
A comparison of solution strategies for biobjective shortest path problems
Computers & Operations Research
An improved solution algorithm for the constrained shortest path problem
Transportation Research Part B
A label correcting approach for solving bicriterion shortest-path problems
Computers & Operations Research
User equilibrium in traffic assignment problem with fuzzy N-A incidence matrix
Fuzzy Sets and Systems
A genetic algorithm for shortest path routing problem and the sizing of populations
IEEE Transaction on Evolutionary Computation
A simulated annealing-based multiobjective optimization algorithm: AMOSA
IEEE Transactions on Evolutionary Computation
Graph theory with application
Near-shortest and k-shortest simple paths
Networks
Chance-constrained programming
Management Science
Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs
Applied Mathematics and Computation
On the shortest route through a network
Management Science
Cited by (22)
Planning efficient 4D trajectories in Air Traffic Flow Management.
2019, European Journal of Operational ResearchCitation Excerpt :To overcome this issue, we here present a multi-objective simulated annealing algorithm to solve the ATFM problem and thus computing a good approximation of the Pareto frontier in a reasonable amount of time. The motivations for implementing a simulated annealing algorithm are: (i) its effectiveness in finding good solutions in a short amount of time; (ii) the robustness, meaning that its performance is not negatively influenced by peculiarities of problem instances, as observed for example in Knust and Xie (2017); (iii) its applicability to a number of optimization problems, see, e.g., Aarts, Korst, and Michiels (2005); (iv) its successful implementation for problems with similar features, e.g., the multi-criteria path problems (Liu, Mu, Luo, & Li, 2012). Before describing the local search in detail, we introduce the concept of dominance in multi-objective optimization, which is used to compare two solutions, say xA and xB.
A simulated annealing heuristic for the multiconstraint team orienteering problem with multiple time windows
2015, Applied Soft Computing JournalCitation Excerpt :Simulated annealing is a local search-based meta-heuristic capable of escaping from local optimum by accepting, with small probability, worse solutions during the search process. SA has been successfully applied to many hard combinatorial optimization problems [21–30], multi-criteria decision making problems [31–34], and various real-world applications [35–40]. Because of its simplicity and flexibility, SA has also been hybridized with other meta-heuristics [40–46] or mathematical programming techniques [47–50] for solving difficult optimization problems.
Generic constraints handling techniques in constrained multi-criteria optimization and its application
2015, European Journal of Operational ResearchCitation 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 ModellingCitation Excerpt :Because of the characteristic of such representing of path, there are some weakness in those evolution operators and, consequently, the efficiency of the EAs for SPP is seriously affected [21]. 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].
A conflict-congestion model for pedestrian-vehicle mixed evacuation based on discrete particle swarm optimization algorithm
2014, Computers and Operations ResearchCitation Excerpt :Zong et al. [17] studied the mixed evacuation problem and proposed model considering the factors such as congestion and the interaction between pedestrians and vehicles, but the model has not taken the potential conflict between pedestrians and vehicles into account, which is crucial to evacuation efficiency. Currently, multi-objective optimization algorithms and swarm intelligence have been used to simulate and solve evacuation problems for making evacuation plans which satisfy more than one objective [18–20]. A number of optimization algorithms or techniques, including the ant colony optimization algorithm [21,22], the particle swarm optimization algorithm [23,24], game theory [25], agent theory [26,27], non-dominated sorting genetic algorithm [28], and genetic algorithm [29] in general, have been used to solve evacuation problems.
Graph Traversal-based Solutions for Trip Planning in Public Transportation Graph
2021, 2021 International Conference on Information Technology, ICIT 2021 - Proceedings