1,721,140 research outputs found
Branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs
No full textWe consider the asymmetric capacitated vehicle routing problem (CVRP), a particular case of the standard asymmetric vehicle routing problem in which only the vehicle capacity constraints are imposed. CVRP is known to be NP-hard and finds practical applications in distribution and scheduling. We describe two new bounding procedures for CVRP, based on the so-called additive approach. Each procedure computes a sequence of nondecreasing lower bounds, obtained by solving different relaxations of CVRP. Effective implementation of the procedures are also outlined which considerably reduce the computational effort. The two procedures are combined into an overall bounding algorithm. A branch-and-bound exact algorithm is then proposed, whose performance is enhanced by means of reduction procedures, dominance criteria, and feasibility checks. Extensive computational results on both real-world and random test problems are presented, showing that the proposed approach favorably compares with previous algorithms from the literature
Robust Train Timetabling
No full textNowadays railway systems are highly affected by disturbances, occurring in daily operations, and causing train delays and passenger inconvenience. Not only they negatively affect the passengers satisfaction, but they also cause additional operational costs, since the planned schedule needs to be modified in real-time. Train timetabling is a particularly critical phase in railway system management, since, in real-time operations, all the changes applied to the planned timetable impact on platform assignment, rolling stock circulation and crew scheduling. Therefore, in the strategic planning, it is an important issue to determine robust timetables, i.e., timetables that “perform well” under disturbances, avoiding delay propagation as much as possible. In this chapter, we present state-of-the-art methods that achieve robust timetables, and discuss their advantages and drawbacks
Timetable Optimization for High-Speed Trains at Chinese Railways
No full textWe study the Train Timetabling Problem (TTP) of the high-speed trains at the Chinese railways. TTP calls for determining, in the planning phase, an optimal schedule for a given set of trains, while satisfying track capacity occupation constraints. In this work, we are given on input a set of feasible timetables for the trains already planned along a double-track high-speed line, and the main goal consists of scheduling as many additional trains as possible. Beside the main goal, a second objective is to obtain a regular schedule, i.e. a schedule showing regularity in the train frequency. We model TTP on a time-space graph and propose a heuristic algorithm for it. Preliminary computational results on real-world instances of the high-speed line from Beijing to Shanghai in China are reported
An Effective Peak Period Heuristic for Railway Rolling Stock Planning
No full textIn this work we tackle a real-world application of railway rolling stock planning, known as the train unit assignment problem (TUAP), arising for a regional train operator in the North of Italy. Given a set of timetabled train trips, each with a demand of passenger seats, as well as a set of train units, each with a cost and a number of available passenger seats, the goal is to determine the minimum cost daily assignment of the train units to the trips, satisfying a set of operational constraints. The context we focus on is that of a competitive bid process whereby a train operator competes to win a contract for providing rolling stock circulation in a regional railway network. From a theoretical perspective, we prove that even a relaxation of the TUAP is NP-hard. To solve the TUAP, we propose a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period (i.e., a period of the day in which many trips overlapping in time must be performed). The heuristic algorithm is tested on real-world instances provided by the regional train operator and on larger realistic instances of TUAP. The obtained results are compared with those of previously developed methods, showing the effectiveness of the new algorithm that finds optimal or near-optimal solutions and outperforms, for what concerns both the solution quality and the computing time, the considered methods from the literature
A metaheuristic framework for Nonlinear Capacitated Covering Problems
No full textSeveral relevant optimization problems can be formulated as generalizations of Capacitated Covering Problems, by considering a cost function that combines a linear term with a nonlinear one. In this paper we introduce the Staircase Capacitated Covering Problem, where the nonlinear term has a staircase shape, and we propose a framework based on a Metaheuristic algorithm for solving problems having this formulation. The performance of the Metaheuristic algorithm in solving the Staircase Capacitated Covering Problem is evaluated on a set of instances derived from an industrial application, and it is compared with a linearized formulation of the problem solved by CPLEX. In particular, the experiments show that the former produces better solutions in the same computing time
Fixed job schedule problem with working-time constraints
No full textWe considere a generalization of the fixed job schedule problem where a bound is imposed on the total working time of each processor. It is shown that the problem is NP-hard but polynomially solvable in the preemptive case. We introduce several lower bounds. One is determined through definition of a special class of graphs, for which the maximum clique problem is shown to be polynomial. Lower bounds and dominance criteria are exploited in a brach-and-bound algorithm for optimal solution of the problem. The effectiveness of the algorithm is analyzed through computational experiments
FIXED JOB SCHEDULE PROBLEM WITH SPREAD-TIME CONSTRAINTS
No full textWe consider a generalization of the fixed job schedule problem in which each processor is available only for a prefixed time interval from the release time of the earliest task assigned to it. The problem can arise in bus driver scheduling. We show that the problem is NP-hard, and introduce polynomial procedures to determine lower bounds, dominance criteria and reductions. We also develop a branch-and-bound algorithm for obtaining the optimal solution of the problem and analyze the algorithm's average performance in a series of computational experiments. Finally, we investigate the preemptive case and other polynomial special cases
A tutorial on non-periodic train timetabling and platforming problems
No full textIn this tutorial, we give an overview of two fundamental problems arising in the optimization of a railway system: the train timetabling problem (TTP), in its non-periodic version, and the train platforming problem (TPP). We consider for both problems the planning stage, i.e. we face them from a tactical point of view. These problems correspond to two main phases that are usually optimized in close sequence by the railway infrastructure manager. First, in the TTP phase, a schedule of the trains in a railway network is determined. A schedule consists of the arrival and departure times of each train at each (visited) station. Second, in the TPP phase, one needs to determine a stopping platform and a routing for each train inside each (visited) station, according to the schedule found in the TTP phase. Due to the complexity of the two problems, an integrated approach is generally hopeless for real-world instances. Hence, the two phases are considered separately and optimized in sequence. Although there exist several versions for both problems, depending on the infrastructure manager and train operators requirements, we do not aim at presenting all of them, but rather at introducing the reader to the topic using small examples. We present models and solution approaches for the two problems in a didactic way and always refer the reader to the corresponding papers for technical details
Vehicle Routing: Problems, Methods, and Applications
No full textVehicle routing problems, among the most studied in combinatorial optimization, arise in many practical contexts (freight distribution and collection, transportation, garbage collection, newspaper delivery, etc.). Operations researchers have made significant developments in the algorithms for their solution, and Vehicle Routing: Problems, Methods, and Applications, Second Edition reflects these advances. The text of the new edition is either completely new or significantly revised and
provides extensive and complete state-of-the-art coverage of vehicle routing by those who have done most of the innovative research in the area;
emphasizes methodology related to specific classes of vehicle routing problems and, since vehicle routing is used as a benchmark for all new solution techniques, contains a complete overview of current solutions to combinatorial optimization problems;
includes several chapters on important and emerging applications, such as disaster relief and green vehicle routing
- …
