Search

This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows (TDVRPTW). We capture road congestion by considering time-dependent travel times, i.e., depending on the departure time to a customer, a different travel time is incurred. We consider the variant of the TDVRPTW where the objective is to minimize total route duration and denote this variant the duration minimizing TDVRPTW (DM-TDVRPTW). Because of time dependency, vehicles' dispatch times at the depot are crucial as road congestion might be avoided. Because of its complexity, all known solution methods to the DM-TDVRPTW are based on (meta-)heuristics. The decomposition of an arc-based formulation leads to a set-partitioning problem as the master problem, and a time-dependent shortest path problem with resource constraints as the pricing problem. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. We introduce new dominance criteria that allow more label dominance. For our numerical results, we modified Solomon's data sets by adding time dependency. Our algorithm is able to solve about 63% of the instances with 25 customers, 38% of the instances with 50 customers, and 15% of the instances with 100 customers.

Authors are in long term developing e-learning supports for some parts of Operation Research course. The original purpose was to prepare e-learning supports for students of FBE Mendelu, mainly for part-time form students, who have subscribed Economic mathematical methods course (EMM). Considering decreasing number of lessons on part-time form of study (16 hours in a semester, in comparison to 56 hours in full-time form of study), was for part-time form students even more difficult to fulfill exam requirements. As a help for students there was stage by stage prepared several of programs, they allow self-contained practicing of some linear programming methods. Programs did allow to users step-by-step verify their solution, i.e. whether their calculation are in accordance with algorithm described in lectures. Advantage for the students consists in fact, that each mistake (numerical or algorithmic) they were able to uncover, what contributes to increase of self-study effectiveness and from that resulting higher study motivation. Resulting from existing experience, authors decided to request for a new FRVS grant for academic year 2012, focused on e-learning support of selected graph theory problems. Within this project there was developed a tool allowing to make and according to the user needs interactively modify created graphs. On this graph it is possible individually, step by step (in compliance with on lectures presented algorithm) to practice solving of selected graph theory and network analysis problems (e.g. minimal spanning tree, shortest path in a graph, testing for cycles in a graph, critical path method etc.). Project is realized as modular and was realized in Delphi developing tool. Described algorithms are saved in dynamic linked libraries. There for it is very easy to add here new (newly programmed) algorithms. Project results (i.e. project experience obtained from e-learning supports) will be available for all FBE Mendelu members interested in this problematic.

We are living in the 21st century in which technological advances have greatly improved the quality of human lives. However nature keeps presenting its challenges in the form of tsunamis, floods, wild fires, hurricanes, volcanoes, etc. Excellent evacuation route planning is of paramount importance to reduce loss of lives during such disasters. The parameters of finite time lined capacity of evacuation paths and thousands to millions of evacuees for the problem of evacuation route planning makes it more complex than the problem of finding the shortest path which has been studied extensively in graph theory. Computation time (execution time hereafter) and evacuation time are two key properties which determine the efficiency and effectiveness of evacuation routing algorithms. This paper proposes a graph theory based evacuation routing algorithm called Forward Backward Shortest Path (FBSP). FBSP uses a novel idea to determine multiple routes by combining multiple paths at a time unlike other evacuation routing algorithms such as Shortest Multiple Path (SMP) that uses just the shortest paths between the source nodes and destination nodes. The experimental analysis on simulated graphs showed that FBSP improves evacuation time over SMP without significantly increasing execution time.

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issue of network vulnerability by prescribing alternate routes for traffic flows. Applications include the dispatching of duplicate packets of data to improve the reliability in communication networks and the diverting of traffic during congestion to reduce the chances of bottlenecks in transportation networks, in the presence of time-dependent variations in travel delays in the network. We prove that this problem, and many variations of it, are NP-hard and we develop a 0-1 linear programming model that can be used to solve this problem. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. We also present some computational results obtained by solving the above models using CPLEX-MIP.

Dynamic programming has been used to find the optimal solution for one-dimensional slitting problems in which the value of a piece is nonlinearly dependent on both the width of the piece and the number of defects on it. In this paper, linear programming is proposed to solve this problem. Additionally, it is shown that this problem can be converted to be a shortest path problem and can be solved easily by an acyclic algorithm. Either a linear programming approach or a shortest path approach are both simpler and faster than the use of dynamic programming.

It is well known that linear programming provides, computationally, the only solution to the optimal plastic design of plane frames. It is also known that the formulation of the problem by the force method, using kinematic variables, requires for its solution, by the simplex method, much less computation than the corresponding program which uses for its formulation the displacement method. However, the force method is not easily automated. This problem is circumvented in the paper by presenting a new algorithm which automatically selects a subminimal cycle base in any planar graph. Based on a shortest path technique between two points of a connected graph, the algorithm forms cycles by finding the shortest paths between the end nodes of members of the graph. The check for independence is done by fictitiously increasing the lengths of the members that form the cycle. This leads to an easy computer implementation of the algorithm. The algorithm is then used to provide a statical basis for any plane frame. Equilibrium with applied loads is satisfied by the use of cantilevers that follow the shortest load path of each load to the ground. The whole process automates the data generation of the force method and makes possible to use, in a computer program, the same input data as in the displacement method. A few examples of applications are given.

For a given graph G with distinct vertices s, t and a given delay constraint D ∈ R+, the k-disjoint restricted shortest path (kRSP) problem of computing k-disjoint minimum cost stpaths with total delay restrained by D, is known to be NP-hard. Bifactor approximation algorithms have been developed for its special case when k = 2, while no approximation algorithm with constant single factor or bifactor ratio has been developed for general k. This paper firstly presents a (k, (1 + e)H(k))-approximation algorithm for the kRSP problem by extending Orda's factor(1.5, 1.5) approximation algorithm [9]. Secondly, this paper gives a novel linear programming (LP) formula for the kRSP problem. Based on LP rounding technology, this paper rounds an optimal solution of this formula and obtains an approximation algorithm within a bifactor ratio of (2, 2). To the best of our knowledge, it is the first approximation algorithm with constant bifactor ratio for the kRSP problem. Our results can be applied to serve applications in networks which require quality of service and robustness simultaneously, and also have broad applications in construction of survivable networks and fault tolerance systems.

In this paper, we consider two interdiction problems for a linear program. These generalize the problems proposed by Fulkerson and Harding and by Golden for the shortest path problem. These problems also provide equilibrium analysis for a system in which some kind of resource can be used to change the original equilibrium. We show that these two problems can be solved simultaneously by performing parametric analysis of a linear program with bounded variables. We also consider their applications for the interdiction of flow networks. In particular, we propose an algorithm for solving the related parametric network flow problem.

In this paper we deal with a generalization of the Chinese Postman Problem with Time Windows involving the added complexity of time dependent service times and travel times, which is motivated from hybrid system testing. In the literatures, several linear integer programs for this new problem have been studied intensively. However, there exists a “large” number B in the timing constraints, which always leads to a very weak linear relaxation. In order to avoid this drawback, this paper presents a graph transformation method with pseudo-polynomially bounded, through which the problem can be reformulated as a new 0/1 integer linear programming without any timing constraint. Computational results reported on 32 randomly generated instances show that medium-sized problems can be solved optimally by the graph transformation algorithm and CPLEX 12.0 within a reasonable time.

Many interesting combinatorial problems can be optimized efficiently using recursive computations often termed discrete dynamic programming. In this paper, we develop a paradigm for a general class of such optimizations that yields a polyhedral description for each model in the class. The elementary concept of dynamic programs as shortest path problems in acyclic graphs is generalized to one seeking a least cost solution in a directed hypergraph. Sufficient conditions are then provided for binary integrality of the associated hyperflow problem. Given a polynomially solvable dynamic program, the result is a linear program, in polynomially many variables and constraints, having the solution vectors of the dynamic program as its extreme-point optima. That is, the linear program provides a succinct characterization of the solutions to the underlying optimization problem expressed through an appropriate change of variables. We also discuss projecting this formulation to recover constraints on the original variables and illustrate how some important dynamic programming solvable models fit easily into our paradigm. A classic multiechelon lot sizing problem in production and a host of optimization problems on recursively defined classes of graphs are included.

Intensity-modulated radiation therapy (IMRT) is a modern cancer treatment technique that delivers prescribed radiation dose distributions, called intensity maps (IMs), to target tumors via the help of a device called the multileaf collimator (MLC). Due to the maximum leaf spread constraint of the MLCs, IMs whose widths exceed a given threshold cannot be delivered as a whole, and thus must be split into multiple subfields. Field splitting problems in IMRTnormally aim to minimize the total beam-on time (i.e., the total time when a patient is exposed to actual radiation during the delivery) of the resulting subfields. In this paper, we present efficient polynomial time algorithms for two general field splitting problems with guaranteed output optimality. Our algorithms are based on interesting observations and analysis, as well as new techniques and modelings. We formulate the first field splitting problem as a special integer linear programming (ILP) problem that can be solved optimally by linear programming due to its geometry; from an optimal integer solution for the ILP, we compute an optimal field splitting by solving a set of shortest path problems on graphs. We tackle the second field splitting problem by using a novel path-sweeping technique on IMs.

Software pipelining is an instruction-level loop scheduling method for achieving high performance fine-grain parallelism on VLIW (very long instruction word) processors. This paper presents a novel software pipelining method for non-pipelining parallel processors based on integer scaling and retiming transformations. This approach generalises and simplifies the analogous extended retiming model of T.W. O'Neil et al. (see Proc. ISCA 12th Int. Conf. Parallel & Distributed Computing Syst., p.292-7, 1999; Proc. of ICASSP'99 Conf., vol.4 p.2001-4, 1999). Matrix techniques are used in order to simplify the corresponding graph transformations. Some general properties taken from algebraic graph theory are applied in order to obtain general scheduling techniques: node and cycle methods. The two-phase scheduling method considered is first defined by means of two standard linear programming problems. We transform the corresponding problems into some variants of the maximum cost-to-time ratio problem and shortest path problem, in order to obtain efficient polynomial time algorithms. An example of software pipelining optimization of a digital correlator is also given.