A variable neighborhood search heuristic for periodic routing problems

The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon while there is some flexibility on the exact days of the visits. Hence, one has to choose the visit days for each customer and to solve a VRP for each day. Our method is based on Variable Neighborhood Search (VNS). Computational results are presented, that show that our approach is competitive and even outperforms existing solution procedures proposed in the literature. Also considered is the special case of a single vehicle, i.e. the Periodic Traveling Salesman Problem (PTSP). It is shown that slight changes of the proposed VNS procedure is also competitive for the PTSP.     

Some applications of the generalized vehicle routing problem

The Generalized Vehicle Routing Problem (GVRP) is an extension of the classical Vehicle Routing Problem (VRP) in which the vertex set is partitioned into clusters and vehicles must visit exactly one (or at least one)vertex per cluster. The GVRP provides a useful modelling framework for a wide variety of applications. The purpose of this paper is to provide such examples of applications and models. These include the Travelling Salesman with Profits, several VRP extensions, the Windy Routing Problem,and the design of tandem configurations for automated guided vehicles.     

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.     

A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.     

A Delay Dependent Queue without Pre-emption with General Linearly Increasing Priority Function

This paper considers the delay dependent priority queueing discipline with P non-preemptive priority classes. The priority at time t of a customer from the pth priority class, who arrives at time T_p, is given by q_p(t) = a _p + b _p (t - T _p ). The result has been derived for the expected waiting time of a customer from the pth priority class.     

Operations policy for a supply chain system with fixed-interval delivery and linear demand

This research addresses a production-supply problem for a supply-chain system with fixed-interval delivery. A strategy that determines the optimal batch sizes, cycle times, numbers of orders of raw materials, and production start times is prescribed to minimize the total costs for a given finite planning horizon. The external demands are time-dependent following a life-cycle pattern and the shipment quantities follow the demand pattern. The shipment quantities to buyers follow various phases of the demand pattern in the planning horizon where demand is represented by piecewise linear model. The problem is formulated as an integer, non-linear programming problem. The model also incorporates the constraint of inventory capacity. The problem is represented using the network model where an optimal characteristic has been analysed. To obtain an optimal solution with N shipments in a planning horizon, an algorithm is proposed that runs with the complexity of Θ(N²) for problems with a single-phase demand and O(N³) for problems with multi-phase demand.     

Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n ³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}{{\ln n}}\), respectively.     

On a two-phase solution approach for the bi-objective <Emphasis Type="Italic">k</Emphasis>-dissimilar vehicle routing problem

In the k-dissimilar vehicle routing problem, a set of k dissimilar alternatives for a Capacitated Vehicle Routing Problem (CVRP) has to be determined for a single instance. The tradeoff between minimizing the longest routing and maximizing the minimum dissimilarity between two routings is investigated. Here, spatial dissimilarity is considered. Since short routings tend to be similar to each other, an objective conflict arises. The developed heuristic approach approximates the Pareto-set with respect to this tradeoff. This paper focuses on the generation of a high-quality candidate set of routings from which k routings are extracted with respect to a spatial as well as to an edge-based dissimilarity metric. In particular two algorithmic variants are suggested which differ in generating dissimilar routings. They are further compared to each other as well as to a naive approach. The method is tested on benchmark instances of the CVRP and findings are reported for both metrics. Taking the hypervolume as a quality criterion, it could be shown that the approach provides a good approximation of the Pareto-set for both metrics. An additional comparison to the results of Talarico et al. (Eur J Oper Res 244(1):129–140, 2015) proves its competitive ability.     

Flexible aircraft fleeting and routing at <Emphasis Type="Italic">TunisAir</Emphasis>

This paper addresses a Flexible Aircraft Fleeting and Routing Problem, which is motivated by the Tunisian national carrier TunisAir. A solution to this problem specifies the departure time of each flight, the subset of aircraft to be chartered or rented out, the individual aircraft assigned to each flight, as well as the sequence of flights to be flown by each aircraft. The objective is to maximize the expected total net profit, while satisfying activity constraints and long-term maintenance requirements. Tailored optimization-based heuristics are developed for solving this complex integrated problem. Computational experiments conducted on real data demonstrate that the proposed procedures are effective and robust, and significantly improve upon TunisAir's solutions.     

Tensor products of tilting modules

We consider whether the tilting properties of a tilting A-module T and a tilting B-module T′ can convey to their tensor product T ? T′: The main result is that T ? T′ turns out to be an (n + m)-tilting A ? B-module, where T is an m-tilting A-module and T′ is an n-tilting B-module.     

Some Structure Theories of Leibniz Triple Systems

In this paper, we investigate the Leibniz triple system T and its universal Leibniz envelope U(T). The involutive automorphism of U(T) determining T is introduced, which gives a characterization of the \(\mathbb {Z}_{2}\)-grading of U(T). We show that the category of Leibniz triple systems is equivalent to a full subcategory of the category of \(\mathbb {Z}_{2}\)-graded Leibniz algebras. We give the relationship between the solvable radical R(T) of T and R a d(U(T)), the solvable radical of U(T). Further, Levi’s theorem for Leibniz triple systems is obtained. Moreover, the relationship between the nilpotent radical of T and that of U(T) is studied. Finally, we introduce the notion of representations of a Leibniz triple system, which can be described by using involutive representations of its universal Leibniz envelope.     

Determining supply requirement in the sales-and-operations-planning (S&amp;OP) process under demand uncertainty: a stochastic programming formulation and a spreadsheet implementation

We show how to extend the demand-planning stage of the sales-and-operations-planning (S&OP) process with a spreadsheet implementation of a stochastic programming model that determines the supply requirement while optimally trading off risks of unmet demand, excess inventory, and inadequate liquidity in the presence of demand uncertainty. We first present the model that minimizes the weighted sum of respective conditional value-at-risk (cVaR) metrics over demand scenarios in the form of a binomial tree. The output of this model is the supply requirement to be used in the supply-planning stage of the S&OP process. Next we show how row-and-column aggregation of the model reduces its size from exponential (2 ^T ) in the number of time periods T in the planning horizon to merely square (T²). Finally, we demonstrate the tractability of this aggregated model in an Excel spreadsheet implementation with a numerical example with 26 time periods.     

An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP is $\mathcal{NP}$ -hard since it is a generalization of the classical Vehicle Routing Problem (VRP), in which clients are served by a heterogeneous fleet of vehicles with distinct capacities and costs. The objective is to design a set of routes in such a way that the sum of the costs is minimized. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a random neighborhood ordering (RVND), in the local search phase. To the best of our knowledge, this is the first ILS approach for the HFVRP. The developed heuristic was tested on well-known benchmark instances involving 20, 50, 75 and 100 customers. These test-problems also include dependent and/or fixed costs according to the vehicle type. The results obtained are quite competitive when compared to other algorithms found in the literature.     

A comparison between the order and the volume fill rate for a base-stock inventory control system under a compound renewal demand process

The order fill rate (OFR) is sometimes suggested as an alternative to the volume fill rate (VFR) (most often just denoted fill rate) as a performance measure for inventory control systems. We consider a continuous review, base-stock policy, where replenishment orders have a constant lead time and unfilled demands are backordered. For this policy, we develop exact mathematical expressions for the two fill-rate measures when demand follows a compound renewal process. We also elaborate on when the OFR can be interpreted as the (extended) ready rate. For the case when customer orders are generated by a negative binomial distribution, we show that it is the size of the shape parameter of this distribution that determines the relative magnitude of the two fill rates. In particular, we show that when customer orders are generated by a geometric distribution, the OFR and the VFR are equal.     

Stability of capture into parametric autoresonance

We consider nonlinear elliptic second-order variational inequalities with degenerate (with respect to the spatial variable) and anisotropic coefficients and L ¹-data. We study the cases where the set of constraints belongs to a certain anisotropic weighted Sobolev space and to a larger function class. In the first case, some new properties of T-solutions and shift T-solutions of the investigated variational inequalities are established. Moreover, the notion of W ^1,1-regular T-solution is introduced, and a theorem of existence and uniqueness of such a solution is proved. In the second case, we introduce the notion of T-solution of the variational inequalities under consideration and establish conditions of existence and uniqueness of such a solution.     

Nonlinear trigonometric approximations of multivariate function classes

Order-sharp estimates are established for the best N-term approximations of functions from Nikol’skii–Besov type classes B_pq^sm(T^k) with respect to the multiple trigonometric system T^(k) in the metric of L_r(T^k) for a number of relations between the parameters s, p, q, r, and m (s = (s₁,..., s_n) ∈ R₊ⁿ, 1 ≤ p, q, r ≤ ∞, m = (m₁,..., m_n) ∈ Nⁿ, k = m₁ +... + m_n). Constructive methods of nonlinear trigonometric approximation—variants of the so-called greedy algorithms—are used in the proofs of upper estimates.     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

Rates of decay in the classical Katznelson-Tzafriri theorem

The Katznelson-Tzafriri Theorem states that, given a power-bounded operator T, ∥Tⁿ(I ? T)∥ → 0 as n → ∞ if and only if the spectrum σ(T) of T intersects the unit circle T in at most the point 1. This paper investigates the rate at which decay takes place when σ(T) ∩ T = {1}. The results obtained lead, in particular, to both upper and lower bounds on this rate of decay in terms of the growth of the resolvent operator R(e^iθ, T) as θ → 0. In the special case of polynomial resolvent growth, these bounds are then shown to be optimal for general Banach spaces but not in the Hilbert space case.     

Holomorphic maps preserving parts of the local spectrum

Let x ₀ be a nonzero vector in \({\mathbb{C}^{n}}\) , and let \({U\subseteq \mathcal{M}_{n}}\) be a domain containing the zero matrix. We prove that if φ is a holomorphic map from U into \({\mathcal{M}_{n}}\) such that the local spectrum of T ∈ U at x ₀ and the local spectrum of φ(T) at x ₀ have always a common value, then T and φ(T) have always the same spectrum, and they have the same local spectrum at x ₀ a.e. with respect to the Lebesgue measure on U. If \({\varphi \colon U\rightarrow \mathcal{M}_{n}}\) is holomorphic with φ(0) = 0 such that the local spectral radius of T at x ₀ equals the local spectral radius of φ(T) at x ₀ for all T ∈ U, there exists \({\xi \in \mathbb{C}}\) of modulus one such that ξT and φ(T) have the same spectrum for all T in U. We also prove that if for all T ∈ U the local spectral radius of φ(T) coincides with the local spectral radius of T at each vector x, there exists \({\xi \in \mathbb{C}}\) of modulus one such that φ(T) = ξT on U.     

Finitistic dimension and restricted injective dimension

We study the relations between finitistic dimensions and restricted injective dimensions. Let R be a ring and T a left R-module with A = End _R T. If _R T is selforthogonal, then we show that rid(T _A ) ? findim(A _A ) ? findim( _R T) + rid(T _A ). Moreover, if R is a left noetherian ring and T is a finitely generated left R-module with finite injective dimension, then rid(T _A ) ? findim(A _A ) ? fin.inj.dim( _R R)+rid(T _A ). Also we show by an example that the restricted injective dimensions of a module may be strictly smaller than the Gorenstein injective dimension.