A simulated annealing for multi-criteria network path problems

Abstract

This paper investigates an oriented spanning tree (OST) based simulated annealing (SA) for solving the multi-criteria shortest path problem (MSPP) as well as the multi-criteria constrained shortest path problem (MCSPP), especially for those with nonlinear objectives. As a popular search algorithm, because of “search-from-a-point” searching mechanism, there have been only a few attempts in extending SA to multi-criteria optimization, particularly, for various MSPPs. In contrast with the existing evolutionary algorithms (EAs), by representing a path as an OST, the designed SA provides an entirely new searching mechanism in sense of “search from a paths set to another paths set” such that both of its local and global search capabilities are greatly improved. Because the possibility of existing a feasible path in a paths set is usually larger than that of one path being feasible, the designed SA has much predominance for solving MCSPPs. Some computational comparisons are discussed and the test results are compared with those obtained by a recent EA of which the representing approach and the ideas of evolution operators such as mutation and crossover are adopted in most of the existing EAs for the shortest path problems. The test results indicate that the new algorithm is available for both of MSPPs and MCSPPs.

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 $\mathrm{\Delta }E$ (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.