1,720,983 research outputs found
Dynamic programming algorithms for the elementary shortest path problem with resource constraints
No full textWhen vehicle routing problems with additional constraints (e.g. capacities or time windows) are solved via column generation and branch-and-price, it is common that the pricing problem requires
the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the nodes. The pricing problem is usually solved via dynamic programming in two possible ways: requiring elementary paths or allowing paths with cycles. We experimentally compare these two strategies and we evaluate the effectiveness of some algorithmic ideas to improve their performance
A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection
No full textThe vehicle routing problem with simultaneous distribution and collection (VRPSDC) is the variation of the capacitated vehicle routing problem that arises when the distribution of goods from a depot to a set of customers and the collection of waste from the customers to the depot must be performed by the same vehiclesof limited capacity and the customers can be visited in any order. We study how the branch-and-price technique can be applied to the solution of this problem and in particular we compare two different ways of solving the pricing subproblem: exact dynamic programming and state space relaxation. By applying a bidirectional search we experimentally prove its effectiveness in solving the subproblem. We also devise suitable branching strategies for both the exact and the relaxed approach and we report on an extensive set of computational experiments on benchmark instances with both simple and composite demands
Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
No full textAbstractWhen vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows
New dynamic programming algorithms for the resource constrained shortest path problem.
No full textThe resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch-and-price algorithms for vehicle-routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare three methods. The first method is a well-known exact dynamic-programming algorithm improved by new ideas, such as bidirectional search with resource-based bounding. The second method consists in a branch-and-bound algorithm, where lower bounds are computed by dynamic-programming with state-space relaxation; we show how bounded bidirectional search can be adapted to state-space relaxation and we present different branching strategies and their hybridization. The third method, called decremental state-space relaxation, is a new one; exact dynamic-programming and state-space relaxation are two special cases of this new method. The experimental comparison of the three methods is definitely favorable to decrement state-space relaxation. Computational results are given for different kinds of resources, arising from the capacitated vehicle-routing problem, the vehicle-routing problem with distribution and collection, and the vehicle-routing problem with capacities and time windows.TRANSP-O
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
A column generation algorithm for a vehicle routing problem with economies of scale and additional constraints
No full textWe present an optimization algorithm developed for a provider of software planning tools for distribution logistics companies. The algorithm computes a daily plan for a heterogeneous fleet of vehicles, that can depart from different depots and must visit a set of customers for delivery operations. Besides multiple capacities and time windows associated with depots and customers, the problem also considers incompatibility constraints between goods, depots, vehicles and customers, maximum route length and durations, upper limits on the number of consecutive driving hours and compulsory drivers' rest periods, the possibility to skip some customers and to use express courier services instead of the given fleet to fulfill some orders, the option of splitting up the orders, and the possibility of open routes that do not terminate at the depots. Moreover, the cost of each vehicle route is computed through a system of fares, depending on the locations visited by the vehicle, the distance traveled, the vehicle load and the number of stops along the route. We developed a column generation algorithm, where the pricing problem is a particular resource constrained elementary shortest path problem, solved through a bounded bi-directional dynamic programming algorithm. We describe how to encode the cost function and the complicating constraints by an appropriate use of resources and we present computational results on real instances obtained from the software company.TRANSP-O
A decision support tool to plan shifts in a home for the aged
No full textIn this work we devise and implement a decision support system for a service company, managing the personnel shifts in a hospital for aged persons. In particular, we formulate a mathematical model that embeds labour regulations, trade union agreements and operational customs in terms of hard and soft constraints. Soft constraints and costs are treated in a multi-objective fashion by a preference modeling module exploiting the Analytic Hierarchy Process. Finally, we present a tabu-search algorithm used to initialize an open source linear programming solver and we compare the results obtained by the optimization algorithm with the manual planning
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
