Search

We consider a capacity expansion problem for a railway network under uncertainty. In our approach, integer and stochastic programming provide a basic framework. We develop a multistage stochastic programming model in which some of the variables are restricted to integer values. Given the distribution of the number of customers in a scenario, the problem of minimizing the expected value of the total investment cost is considered. The problem is reformulated as a problem with first stage integer variables and continuous second stage variables. An L-shaped algorithm is proposed to solve this problem.

We consider the allocation of a running time supplement to a railway timetable. Previously, Vekas et al. examined the optimal way to allocate the running time supplement. The uncertain disturbances in a railway were modeled using random variables. In their model, it was assumed that there was an upper limit to the total supplement, but its allocation was not restricted. In this paper, we suggest an improvement to the previous model and present a new stochastic programming model in which there is a constraint on the running time supplement allocated to each trip to minimize the expected delay. Then a solution algorithm to solve the problem is developed. In the previous model, allocation of the running time supplement was biased because it was not allocated to all trips. We balance the amounts of supplements for trips by adding upper and lower bounds. The uctuations of the supplements for trips become small, and the probability of a delay decreases using our new model. Then the calculation times using the L-shaped algorithm and the former method solving a deterministic equivalent of large-scale problems are compared. It is shown that the large-scale problems can be solved effectively by using the L-shaped method.

Optimization of daily vehicle routes with deliveries and pickups as well as multiple use of vehicles for a rental business is considered. The problem is formulated as a variant of generalized set covering problems in which variables correspond to workdays of vehicles. Two variants of column generation heuristic algorithms are developed: one to obtain near-optimal solutions with moderate amount of CPU time together with the associated lower bound, and the other to get solutions with maximum of 8% GAP within 30 CPU seconds. The speed-up of the algorithm is achieved by approximately solving subproblems which exploits information of optimal dual prices associated with the restricted LP master problem. The column generation heuristic algorithms are applied successfully not only to single-depot problems but also to multi-depot problems.