Catálogo de publicaciones - libros

In this paper the first results on the Online Dial-A-Ride Problem with Time-Windows (ODARPTW for short) are presented. Requests for rides appearing over time consist of two points in a metric space, a and a . Servers transport objects of requests from sources to destinations. Each request specifies a deadline. If a request is not be served by its deadline, it will be called off. The goal is to plan the motion of servers in an online way so that the maximum number of requests is met by their deadlines. We perform competitive analysis of two deterministic strategies for the problem with a single server in two cases separately, where the server has unit capacity and where the server has infinite capacity. The competitive ratios of the strategies are obtained. We also prove a lower bound on the competitive ratio of any deterministic algorithm of for a server with unit capacity and of for a server with infinite capacity, where denotes the diameter of the metric space.

For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance. We propose a technique to transform the problem to MIN RES CUT . We apply Goemans and Williamson’s 0.878-approximation algorithm for MAX RES CUT, which is based on a positive semidefinite programming relaxation,to the obtained MIN RES CUT instances. Computational experiments show that our approach quickly generates solutions of good approximation ratios.

Coopetition has become the current trend of economic activities. Coopetitive game is introduced through the comparison of the characteristics of noncooperative game and cooperative game. Furthermore, the coopetitive game is solved adopting one kind of Minimax theorem. Finally, the Cournot coopetition model is presented as an example, and the equilibrium is compared with Nash equilibrium.

This paper deals with the riding behavior of commuters who take trains from a living place to a work place during morning rush hours. The total travel cost include early and late arrival penalties as well as carriage body capacity. An equivalent mathematical programming model which generates equilibrium riding behavior is presented. The number of actually chosen transit runs, passenger flow distributions, and fares resulted from three system configurations namely social optimum, monopoly by one company and duopoly competition, are investigated by numerical examples.

In a real options and game-theoretic framework, this paper investigates the optimal timing of two asymmetric firms’ R&D investment under uncertainty. There exist three types of equilibria that can occur in the choice of the R&D investment strategies, i.e. the preemptive, sequential and simultaneous equilibrium. The occurrence of a particular type of equilibrium is determined by the firms’ relative payoff, which mainly depends on the level of operating cost asymmetry and first-mover advantage and the operating cost itself. We show that when the cost asymmetry and the first-mover advantage among firms are relatively small, two firms invest simultaneously. When the first-mover advantage is significant, the low-cost firm preempts the high-cost firm. In the situation where the asymmetry between firms becomes large enough, two firms invest sequentially. We also show that the lower the operating cost is, the more the incentive to become the leader has. So, with the operating cost decreasing, the possibility of simultaneous equilibrium and sequential equilibrium decreases, but that of preemptive equilibrium increases.

For the complex and time-varying traffic flow, single-strategy based fuzzy traffic control algorithms are not very ideal. In order to further improve the capacity of isolated intersection, we propose a multi-strategy fuzzy control algorithm to adapt to the variation of urban traffic flow, and then optimize its control rules and membership functions by using improved genetic algorithm. The simulation result shows that compared with traditional genetic algorithm, the efficiency of improved genetic algorithm is higher, and its performance is more stable. The multi-strategy fuzzy control model possesses the stronger self-adaptive competence and performance.

Facility Location Problems have always been studied with the assumption that the environment in the network is static and does not change over time. In practice, however, the environment is usually dynamic and we must consider the facility location in a global view. In this paper, we impose the following additional constraints on input facilities: the total number of facilities to be placed is not known in advance and a facility cannot be removed once it is placed. We solve this problem by presenting an algorithm to find a facility permutation such that any prefix of the permutation of facilities is near-optimal over any other facility subset.

In this paper, we introduce a class of stochastic age-dependent population dynamic system. Applying the theory of stochastic functional differential equation, using Gronwall’s lemma and Barkholder-Davis-Gundy’s lemma, Existence and uniqueness of strong solution are proved for a class of stochastic age-dependent population dynamic system on Hilbert space. In particular, as a direct consequence our main results extend some of those from ordinary age-dependent population dynamic system.

We consider the scheduling problem | , | under the assumption of , i.e., for some implies for all 1 ≤ ≤ , where and denote the processing times on machine of jobs and , respectively. For the special case when the number of distinct release times is constant and all processing times and release times integral, we propose a pseudo-polynomial time algorithm by approach of dynamic programming. Without the integral restriction, an FPTAS is provided. And for the general case with arbitrary , we establish a PTAS.

This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes , and are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems. The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof method is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.