Search

This paper investigates the solution algorithms for the multi-criteria multi-modal shortest path problem (M-SPP), which belongs to the set of problems known as NP-hard, in urban transit network (UTN). The related M-SPP is one of the important and practical problems in several fields such as urban transportation system and freight transportation. The UTN is composed of multiple modes (e.g., automobile, bus, subway, light rail, pedestrian and so on). To get their destination, the passengers can alternate between different modes. As a special demand, the time-window is usually associated with the M-SPP. Because of the service time-limit of modes, the available modes at a stop are varied with the time. So the optimal M-SPP with arriving time-window cannot be simply obtained by finding the optimal M-SPP firstly and then reversely deducing the leaving time-window of the origin according to the arriving time-window of destination. In this paper, the M-SPP with arriving time-window is firstly proposed. To solve the multi-criteria M-SPPs (MM-SPP) with transfer delaying, an improved exact label correcting algorithm (LCA) is designed and, to solve the proposed MM-SPPs with both of transfer delaying and arriving time-window, an exact reverse LCA is designed. Finally, some computing examples are given to test the effectiveness of the designed algorithms.

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.

In this paper, the equilibrium optimization problem is proposed and the assignment problem is extended to the equilibrium multi-job assignment problem, equilibrium multi-job quadratic assignment problem and the minimum cost and equilibrium multi-job assignment problem. Furthermore, the mathematical models of the equilibrium multi-job assignment problem and the equilibrium multi-job quadratic assignment problem with fuzzy parameters are formulated. Finally, a genetic algorithm is designed for solving the proposed programming models and some numerical examples are given to verify the efficiency of the designed algorithm.

A matching of a graph is an independent subset of the edges set and a maximum matching is a matching with as many edges in it as possible. The maximum weighted matching problem is to find a maximum matching in a given graph such that the sum of the weights of the edges in it is maximum. In this paper, the concepts of expected maximum fuzzy weighted matching, the α-maximum fuzzy weighted matching and the most maximum fuzzy weighted matching are initialized. According to various decision criteria, the maximum fuzzy weighted matching problem is formulated as expected value model, chance-constrained programming and dependent-chance programming by using the credibility theory, and the crisp equivalents are also given. Furthermore, a hybrid genetic algorithm is designed for solving the proposed fuzzy programming models. Finally, a numerical example is given.

The assignment problem is to find the total costs optimal jobs assignment schedule where n jobs are allocated to n workers, and each worker receives exactly just one job, such that the total cost is optimal. The quadratic assignment problem with penalty takes three types of costs into consideration: direct cost, interactive cost an penalty. In this paper, the fuzzy quadratic assignment problem with penalty is formulated as expected value model, chance-constrained programming and dependent-chance programming according to various decision criteria, and the crisp equivalents are given. Furthermore, hybrid genetic algorithm is designed for solving the proposed fuzzy programming models.

In this paper, some properties of Ramsey numbers are studied, and the following results are presented. 1. (1) For any positive integers k1, k2, …, km l1, l2, …, lm (m > 1), we have r ∏i=1m ki + 1, ∏i=1m li + 1 ≥ ∏i=1m [ r (ki + 1,li + 1) − 1] + 1 . 2. (2) For any positive integers k1, k2, …, km, l1, l2, …, ln , we have r ∑i=1m ki + 1, ∑j=1n lj + 1 ≥ ∑i=1m∑j=1n r (ki + 1,lj + 1) − mn + 1 . Based on the known results of Ramsey numbers, some results of upper bounds and lower bounds of Ramsey numbers can be directly derived by those properties.

In this paper, we prove that χT ( G ) = 5 for any Halin graph G with Δ ( G ) = 4, where Δ ( G ) and χT ( G ) denote the maximal degree and the total chromatic number of G , respectively.

LetG be a planar graph with δ(G)≥3,f 0 be a face ofG. In this paper it is proved that for any Halin graph with Δ(G)≥6,x c (G)=Δ(G)+1, where Δ(G),x c (G) denote the maximum degree and the complete chromatic number ofG, respectively.

In this paper, the following results are obtained: a(G) + β(G) ⩽ p + 1, ⌈p2⌉ ⩽ a(G)β(G), ⌈p2⌉ ⩽ a′(G) + gb′(Ḡ) ⩽ pa′(G) + α′(Ḡ) ⩽ 2⌈p2⌉ (δ ⩽ 1) and all bounds are sharp, where p = ¦V(G)¦, ⌈x⌉ denotes the smallest integer greater than or equal to x, a(G) is the vertex arboricity, a′(G) is the edge arboricity, α′(G) is the edge covering number, β(G) is the vertex independent number, β′(G) is the edge independent number, and δ is the minimum degree of G.

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where C(u) = {ƒ(uv) | uv ∈ E} , then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′as(G), and obtain the χ′as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.