Packing two copies of a sparse graph into a graph with restrained maximum degree

We show that if a tree T is not a star, then there is an embedding σ of T in the complement of T such that the maximum degree of T∪σ(T) is at most Δ(T)+2. We also show that if G is a graph of order n with n?1 edges, then with several exceptions, there exists an embedding σ of G in the complement of G such that the maximum degree of G∪σ(G) is at most Δ(G)+3. Both results are sharp in the sense that neither of Δ(T)+2 and Δ(G)+3 can be reduced. From these two results, we deduce two corollaries on packings of three graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 178–187, 2009     

Vehicle routing with cross-docking

Over the past decade, cross-docking has emerged as an important material handling technology in transportation. A variation of the well-known Vehicle Routing Problem (VRP), the VRP with Cross-Docking (VRPCD) arises in a number of logistics planning contexts. This paper addresses the VRPCD, where a set of homogeneous vehicles are used to transport orders from the suppliers to the corresponding customers via a cross-dock. The orders can be consolidated at the cross-dock but cannot be stored for very long because the cross-dock does not have long-term inventory-holding capabilities. The objective of the VRPCD is to minimize the total travel time while respecting time window constraints at the nodes and a time horizon for the whole transportation operation. In this paper, a mixed integer programming formulation for the VRPCD is proposed. A tabu search heuristic is embedded within an adaptive memory procedure to solve the problem. The proposed algorithm is implemented and tested on data sets provided by the Danish consultancy Transvision, and involving up to 200 pairs of nodes. Experimental results show that this algorithm can produce high-quality solutions (less than 5% away from optimal solution values) within very short computational time.     

Vehicle routing with split deliveries

This paper considers a relaxation of the classical vehicle routing problem (VRP), in which split deliveries are allowed. As the classical VRP, this problem is NP-hard, but nonetheless it seems more difficult to solve exactly. It is first formulated as an integer linear program. Several new classes of valid constraints are derived, and a hierarchy between these is established. A constraint relaxation branch and bound algorithm for the problem is then described. Computational results indicate that by using an appropriate combination of constraints, the gap between the lower and upper bounds at the root of the search tree can be reduced considerably. These results also confirm the quality of a previously published heuristic for this problem.     

Semidefinite programming approach for the quadratic assignment problem with a sparse graph

The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but such SDPs typically scale badly, involving matrix variables of dimension \(n^2\) where n is the number of nodes. To achieve a speed up, we propose a further relaxation of the SDP involving a number of positive semidefinite matrices of dimension \(\mathcal {O}(n)\) no greater than the number of edges in one of the graphs. The relaxation can be further strengthened by considering cliques in the graph, instead of edges. The dual problem of this novel relaxation has a natural three-block structure that can be solved via a convergent Alternating Direction Method of Multipliers in a distributed manner, where the most expensive step per iteration is computing the eigendecomposition of matrices of dimension \(\mathcal {O}(n)\). The new SDP relaxation produces strong bounds on quadratic assignment problems where one of the graphs is sparse with reduced computational complexity and running times, and can be used in the context of nuclear magnetic resonance spectroscopy to tackle the assignment problem.     

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.     

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 and corresponds to the article by Cattaruzza et al. (4OR 14(3):223–259, 2016). 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.     

Fluctuations in the Ising model on a sparse random graph

We compute the fluctuations of the magnetization and of the multi-overlaps for the dilute mean field ferromagnet, in the high temperature region. The rescaled magnetization tends to a centered Gaussian variable with variance diverging at the critical line. The rescaled multi-overlaps also tend to centered independent Gaussian variables, but their covariances remain finite at the critical line.     

Vehicle routing with stochastic time-dependent travel times

Assigning and scheduling vehicle routes in a stochastic time-dependent environment is a crucial management problem. The assumption that in a real-life environment everything goes according to an a priori determined static schedule is unrealistic. Our methodology builds on earlier work in which the traffic congestion is captured in an analytical way using queueing theory. The congestion is then applied to the VRP problem. In this paper, we introduce the variability in traffic flows into the model. This allows for an evaluation of the routes based on the uncertainty involved. Different experiments show that the risk taking behavior of the planner can be taken into account during optimization. As more weight is given to the variability component, the resulting optimal route will take a slightly longer travel time, but will be more reliable. We propose a powerful objective function that is easily implemented and that captures the trade-off between the average travel time and its variance. The evaluation of the solution is done in terms of the 95th-percentile of the travel time distribution (assumed to be lognormal), which reflects well the quality of the solution in this stochastic time-dependent environment.     

Vehicle routing problems on a line-shaped network with release time constraints

This work considers the vehicle routing problem on a line with the constraint that each customer is visited after its release time. It is already known that the single-vehicle case is polynomially solvable. We present polynomial time algorithms for two variants of the multi-vehicle case.     

Vehicle routing problem with simultaneous deliveries and pickups

The vehicle routing problem with backhauls involves the delivery and pickup of goods at different customer locations. In many practical situations, however, the same customer may require both a delivery of goods from the distribution centre and a pickup of recycled items simultaneously. In this paper, an insertion-based procedure to generate good initial solutions and a heuristic based on the record-to-record travel, tabu lists, and route improvement procedures are proposed to resolve the vehicle routing problems with simultaneous deliveries and pickups. Computational characteristics of the insertion-based procedure and the hybrid heuristic are evaluated through computational experiments. Computational results show that the insertion-based procedure obtained better solutions than those found in the literature. Computational experiments also show that the proposed hybrid heuristic is able to reduce the gap between initial solutions and optimal solutions effectively and is capable of obtaining optimal solutions very efficiently for small-sized problems.     

Vehicle routing with stochastic demands and restricted failures

This paper considers a class of stochastic vehicle routing problems (SVRPs) with random demands, in which the number of potential failures per route is restricted either by the data or the problem constraints. These are realistic cases as it makes little sense to plan vehicle routes that systematically fail a large number of times. First, a chance constrained version of the problem is considered which can be solved to optimality by algorithms similar to those developed for the deterministic vehicle routing problem (VRP). Three classes of SVRP with recourse are then analyzed. In all cases, route failures can only occur at one of the lastk customers of the planned route. Since in general, SVRPs are considerably more intractable than the deterministic VRPs, it is interesting to note that these realistic stochastic problems can be solved as a sequence of deterministic traveling salesman problems (TSPs). In particular, whenk=1 the SVRP with recourse reduces to a single TSP.     

Homomorphisms from sparse graphs to the Petersen graph

Let G be a graph and let c: be an assignment of 2-elements subsets of the set {1,…,5} to the vertices of G such that for any two adjacent vertices u and v,c(u) and c(v) are disjoint. Call such a coloring c a (5, 2)-coloring of G. A graph is (5,2)-colorable if and only if it has a homomorphism to the Petersen graph.The maximum average degree of G is defined as . In this paper, we prove that every triangle-free graph with is homomorphic to the Petersen graph. In other words, such a graph is (5, 2)-colorable. Moreover, we show that the bound on the maximum average degree in our result is best possible.     

Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

This paper considers the problem of finding a minimal triangulation of an undirected graph G = (V, E), where a triangulation is a set T such that every cycle in G = (V, E ∪ T) has a chord. A triangulation T is minimal (minimum) if no triangulation F exists such that F is a proper subset of $\text{T (¦F¦ < ¦T¦)}$, and an ordering α is optimal (optimum) if a minimal (minimum) triangulation is generated by α. A minimum triangulation (optimum ordering) is necessarily minimal (optimal), but the converse is not necessarily true. A necessary and sufficient condition for a triangulation to be minimal is presented. This leads to an algorithm for finding an optimal ordering α which produces a minimal set of “fill-in” when the process is viewed as triangular factorization of a sparse matrix.     

Vehicle routing via column generation

This paper explores an approximate method for solving a routing problem in a four-level distribution which has “double-ended” demand. Routes are represented as columns in a linear program and column generation is used to improve the solution by generating new routes. The generation of new routes is based on an LP sub-problem. Its solution is rounded down to integer values to insure its feasibility as a route for inclusion in the restricted master problem. Finally, an illustrative problem is solved.     

A note on a mixed routing and scheduling problem on a grid graph

We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.