Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

Compact formulations of the Steiner Traveling Salesman Problem and related problems

The Steiner Traveling Salesman Problem (STSP) is a variant of the TSP that is particularly suitable when routing on real-life road networks. The standard integer programming formulations of both the TSP and STSP have an exponential number of constraints. On the other hand, several compact formulations of the TSP, i.e., formulations of polynomial size, are known. In this paper, we adapt some of them to the STSP, and compare them both theoretically and computationally. It turns out that, just by putting the best of the formulations into the CPLEX branch-and-bound solver, one can solve instances with over 200 nodes. We also briefly discuss the adaptation of our formulations to some related problems.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.     

New mixed integer-programming model for the pickup-and-delivery problem with transshipment

In recent years, many important real-world applications are studied as “rich” vehicle routing problems that are variants and generalizations of the well-known vehicle routing problem. In this paper we address the pickup-and-delivery version of this problem and consider further generalization by allowing transshipment in the network. Moreover, we allow heterogenous vehicles and flexible fleet size. We describe mixed integer-programming formulations for the problem with and without time windows for services. The number of constraints and variables in the models are bounded by polynomial size of the problem. We discuss several problem variants that are either captured by our models or can be easily captured through simple modifications. Computational work gave promising results and confirms that transshipment in network can indeed enhance optimization.     

New mathematical models of the generalized vehicle routing problem and extensions

The generalized vehicle routing problem (GVRP) is an extension of the vehicle routing problem (VRP) and was introduced by Ghiani and Improta [1]. The GVRP is the problem of designing optimal delivery or collection routes from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets (clusters) which includes exactly one node from each cluster, subject to capacity restrictions. The aim of this paper is to provide two new models of the GVRP based on integer programming. The first model, called the node formulation is similar to the Kara-Bekta? formulation [2], but produces a stronger lower bound. The second one, called the flow formulation, is completely new. We show as well that under specific circumstances the proposed models of the GVRP reduces to the well known routing problems. Finally, the GVRP is extended for the case in which the vertices of any cluster of each tour are contiguous. This case is defined as the clustered generalized vehicle routing problem and both of the proposed formulations of GVRP are adapted to clustered case.     

The maximum covering/shortest path problem: A multiobjective network design and routing formulation

In this paper the authors introduce the maximum covering/shortest path problem and the maximum population/shortest path problem, a special case of the former model. Both models are formulated as two objective integer programs. A summary of the results of a sample problem for the latter formulation is given. Possible modifications to, and extensions and applications of both models are also presented. With these formulations the authors extend the concept of ‘coverage’ from facility location analysis to network design and routing analysis.     

Multi-objective vehicle routing problems

Routing problems, such as the traveling salesman problem and the vehicle routing problem, are widely studied both because of their classic academic appeal and their numerous real-life applications. Similarly, the field of multi-objective optimization is attracting more and more attention, notably because it offers new opportunities for defining problems. This article surveys the existing research related to multi-objective optimization in routing problems. It examines routing problems in terms of their definitions, their objectives, and the multi-objective algorithms proposed for solving them.     

The steiner tree packing problem in VLSI design

In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.     

Vehicle routing problems with multiple trips

This paper presents a survey on the multi-trip vehicle routing problem (MTVRP) and on related routing problems where vehicles are allowed to perform multiple trips. The first part of the paper focuses on the MTVRP. It gives an unified view on mathematical formulations and surveys exact and heuristic approaches. The paper continues with variants of the MTVRP and other families of routing problems where multiple trips are sometimes allowed. For the latter, it specially insists on the motivations for having multiple trips and the algorithmic consequences. The expected contribution of the survey is to give a comprehensive overview on a structural property of routing problems that has seen a strongly growing interest in the last few years and that has been investigated in very different areas of the routing literature.     

Comparison of wavelength requirements between two wavelength assignment methods in survivable WDM networks

We consider the routing and wavelength assignment (RWA) in survivable WDM network. A path protection scheme assumed and two different wavelength assignment methods for protection paths are considered. Integer programming formulations of RWA under two wavelength assignment methods are proposed and we devised algorithms to solve them. Test results show that the difference of wavelength requirements between two wavelength assignment methods is 5–30–     

Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing

The lift-gas allocation problem with well-separator routing constraints is a mixed-integer nonlinear program of considerable complexity. To this end, a mixed-integer linear formulation (compact) is obtained by piecewise-linearizing the nonlinear curves, using binary variables to express the linearization and routing decisions. A new formulation (integrated) combining the decisions on linearization and routing is developed by using a single binary variable. The structures of both formulations are explored to generate lifted cover cuts. Numerical tests show that the solution of the integrated formulation using cutting-plane generation is faster in spite of having more variables than the compact formulation.     

The many-to-many location-routing problem

In this paper the many to many location routing problem is introduced, and its relationship to various problems in distribution management is emphasised. Useful mathematical formulations which can be easily extended to cater for other related problems are produced. Techniques for tackling this complex distribution problem are also outlined.     

The Transit Route Arc-Node Service Maximization problem

This article presents a new method for determining optimal transit routes. The Transit Route Arc-Node Service Maximization model is a mathematical model that maximizes the service value of a route, rather than minimizing cost. Cost (distance) is considered as a budget constraint on the extent of the route. The mathematical formulation modifies and exploits the structure of linear programming problems designed for the traveling salesman problem. An innovative divide-and-conquer solution procedure is presented that not only makes the transit routing problem tractable, but also provides a range of high-quality alternate routes for consideration, some of which have substantially varying geometries. Variant formulations are provided for several common transit route types. The model is tested through its application to an existing street network in Richardson, TX. Optimal numeric results are obtained for several problem instances, and these results demonstrate that increased route cost is not correlated with increased service provision.     

Evaluation of mathematical models for flexible job-shop scheduling problems

With the rapid development in computer technologies, mathematical programming-based technique to solve scheduling problems is significantly receiving attention from researchers. Although, it is not efficient solution method due to the NP-hard structure of these problems, mathematical programming formulation is the first step to develop an effective heuristic. Numerous comparative studies for variety scheduling problems have appeared over the years. But in our search in literature there is not an entirely review for mathematical formulations of flexible job shop scheduling problems (FJSP). In this paper, four the most widely used formulations of the FJSP are compiled from literature and a time-indexed model for FJSP is proposed. These formulations are evaluated under three categories that are distinguished by the type of binary variable that they rely on for using of sequencing operations on machines. All five formulations compared and results are presented.     

Extended formulations for stochastic lot-sizing problems

In this paper, extended formulations for stochastic uncapacitated lot-sizing problems with and without backlogging are developed in higher dimensional spaces that provide integral solutions. Moreover, physical meanings of the decision variables in the extended formulations are explored and special cases with more efficient formulations are studied.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When 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.     

Robust delay-constrained routing in telecommunications

In telecommunications, operators usually use market surveys and statistical models to estimate traffic evolution in networks or to approximate queuing delay functions in routing strategies. Many research activities concentrated on handling traffic uncertainty in network design. Measurements on real world networks have shown significant errors in delay approximations, leading to weak management decisions in network planning. In this work, we introduce elements of robust optimization theory for delay modeling in routing problems. Different types of data uncertainty are considered and linked to corresponding robust models. We study a special case of constraints featuring separable additive functions. Specifically, we consider that each term of the sum is disturbed by a random parameter. These constraints are frequent in network based problems, where functions reflecting real world measurements on links are summed up over end-to-end paths. While classical robust formulations have to deal with the introduction of new variables, we show that, under specific hypotheses, the deterministic robust counterpart can be formulated in the space of original variables. This offers the possibility of constructing tractable robust models. Starting from Soyster’s conservative model, we write and compare different uncertainty sets and formulations offering each a different protection level for the delay constrained routing problem. Computational experiments are developed in order to evaluate the “price of robustness” and to assess the quality of the new formulations.     

A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization

Production optimization of gas-lifted oil wells under facility, routing and pressure constraints is a challenging problem, which has attracted the interest of operations engineers aiming to drive economic gains and scientists for its inherent complexity. The hardness of this problem rests on the non-linear characteristics of the multidimensional well-production and pressure-drop functions, as well as the discrete routing decisions. To this end, this work develops several formulations in Mixed-Integer Linear Programming (MILP) using multidimensional piecewise-linear models to approximate the non-linear functions with domains spliced in hypercubes and simplexes. Computational and simulation analyses were performed considering a synthetic but realistic oil field modeled with a multiphase-flow simulator. The purpose of the analyses was to assess the relative performance of the MILP formulations and their impact on the simulated oil production.     

Implementations of special ordered sets in MP software

Special ordered sets (SOS) have been introduced as a practical device for efficiently handling special classes of nonconvex optimization problems. They are now implemented in most commercial codes for mathematical programming (MP software). The paper gives a survey of possible applications as multiple choice restrictions, conditional multiple choice restrictions, discrete variables, discontinuous variables and piecewise linear functions, global optimization of separable programming problems, alternative right-hand sides, overlapping special ordered sets and the solution of quadratic programming problems. Alternative problem formulations are discussed. Since special ordered sets are not defined uniquely modelling facilities depend on the definition of a special orderedset in a code. The paper demonstrates the superiority of SOS to the application of binary variables if they are treated judiciously.     

Coefficient strengthening: a tool for reformulating mixed-integer programs

Providing a good formulation is an important part of solving a mixed-integer program.We suggest measuring the quality of a formulation by whether it is possible to strengthen the coefficients of the formulation. Sequentially strengthening coefficients can then be used as a tool for improving formulations.We believe this method could be useful for analyzing and producing tight formulations of problems that arise in practice.We illustrate the use of the approach on a problem in production scheduling. We also prove that coefficient strengthening leads to formulations with a desirable property: if no coefficient can be strengthened, then no constraint can be replaced by an inequality that dominates it. The effect of coefficient strengthening is tested on a number of problems in computational experiments. The strengthened formulations are compared to reformulations obtained by the preprocessor of a commercial software package. For several test problems, the formulations obtained by coefficient strengthening are substantially stronger than the formulations obtained by the preprocessor. In particular, we use coefficient strengthening to solve two difficult problems to optimality that have only recently been solved. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.