Probabilistic analysis of a capactiated vehicle routing problem—I

A fleet of vehicles located at a service center must serve the demands of a set of customers. The amount delivered by each vehicle cannot exceed its capacity and a customer’s demand may not be split over more than one vehicle. In our model, customers locations, as well as their demands are independent identically distributed. Simchi-Levi and Bramel [10] determined the asymptotic value of the optimal solution in this model. We prove here a sharp rate of convergence to the asymptotic value     

The close–open mixed vehicle routing problem

We consider the Close–Open Mixed Vehicle Routing Problem (COMVRP) in this paper. The COMVRP differs from the classical vehicle routing problems because simultaneously considering open and close routes in the solution of the problem. The objective of the problem is to minimize the fixed and variable costs for operating the open and close routes. No attention was devoted to this problem. A mix integer programming (MIP) model and an effective metheuristic, i.e., memetic algorithm, are established for the COMVRP. Computational experiments are conducted. The results of experiments show that the proposed metheuristic algorithm is able to produce satisfied solutions within an acceptable running time, and outperforms the robust MIP solver CPLEX.     

A min–max vehicle routing problem with split delivery and heterogeneous demand

In this article, we introduce a new variant of min–max vehicle routing problem, where various types of customer demands are satisfied by heterogeneous fleet of vehicles and split delivery of services is allowed. We assume that vehicles may serve one or more types of service with unlimited service capacity, and varying service and transfer speed. A heuristic solution approach is proposed. We report the solutions for several test problems.     

Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

Painlevé’s paradox and dynamic jamming in simple models of passive dynamic walking

Painlevé’s paradox occurs in the rigid-body dynamics of mechanical systems with frictional contacts at configurations where the instantaneous solution is either indeterminate or inconsistent. Dynamic jamming is a scenario where the solution starts with consistent slippage and then converges in finite time to a configuration of inconsistency, while the contact force grows unbounded. The goal of this paper is to demonstrate that these two phenomena are also relevant to the field of robotic walking, and can occur in two classical theoretical models of passive dynamic walking — the rimless wheel and the compass biped. These models typically assume sticking contact and ignore the possibility of foot slippage, an assumption which requires sufficiently large ground friction. Nevertheless, even for large friction, a perturbation that involves foot slippage can be kinematically enforced due to external forces, vibrations, or loose gravel on the surface. In this work, the rimless wheel and compass biped models are revisited, and it is shown that the periodic solutions under sticking contact can suffer from both Painlevé’s paradox and dynamic jamming when given a perturbation of foot slippage. Thus, avoidance of these phenomena and analysis of orbital stability with respect to perturbations that include slippage are of crucial importance for robotic legged locomotion.     

Maximum utility product pricing models and algorithms based on reservation price

We consider a revenue management model for pricing a product line with several customer segments under the assumption that customers’ product choices are determined entirely by their reservation prices. We highlight key mathematical properties of the maximum utility model and formulate it as a mixed-integer programming problem, design heuristics and valid cuts. We further present extensions of the models to deal with various practical issues arising in applications. Our computational experiments with real data from the tourism sector as well as with the randomly generated data show the effectiveness of our approach.     

Evolutional computations and neuronet and genetic algorithms — formal statements

We try to formalize the definition of some problems that deal with the application of evolutional and neuronet algorithms. One of our goals is to discuss the correctness of solutions obtained with the application of evolutional methods.     

Graph algorithms for DNA sequencing – origins,current models and the future

With the ubiquitous presence of next-generation sequencing in modern biological, genetic, pharmaceutical and medical research, not everyone pays attention to the underlying computational methods. Even fewer researchers know what were the origins of the current models for DNA assembly. We present original graph models used in DNA sequencing by hybridization, discuss their properties and connections between them. We also explain how these graph models evolved to adapt to the characteristics of next-generation sequencing. Moreover, we present a practical comparison of state-of-the-art DNA de novo assembly tools representing these transformed models, i.e. overlap and decomposition-based graphs. Even though the competition is tough, some assemblers perform better and certainly large differences may be observed in hardware resources utilization. Finally, we outline the most important trends in the sequencing field, and try to predict their impact on the computational models in the future.     

The rollon–rolloff waste collection vehicle routing problem with time windows

This study introduces a rollon–rolloff waste collection vehicle routing problem involving large containers that accumulate huge amounts of garbage at construction sites and shopping districts. In this problem, tractors move one container at a time between customer locations, a depot, disposal facilities, and container storage yards. The complicated constraints discussed in this study arise from having multiple disposal facilities, multiple container storage yards, seven service types of customer demands, different time windows for customer demands and facilities, various types and sizes of containers, and the lunch break of tractor drivers. In addition, real-world issues, such as changing service types, multiple demands at a customer’s location, and tractors with different work schedules, are dealt with. This study proposes a large neighborhood search based iterative heuristic approach consisting of several algorithms for the problem. The effectiveness of the proposed methods is demonstrated by computational experiments using benchmark data, some instances of which are derived from real-world problems.     

A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products

This paper considers a practical variant of the Vehicle Routing Problem (VRP) known as the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products (HVRPTWMP). As the problem is NP-hard, the resolution approach proposed here is a sequential Ant Colony System (ACS)—Tabu Search algorithm. The approach introduces a two pheromone trail strategy to accelerate agents’ (ants) learning process. Its convergence to good solutions is given in terms of fleet size and travel time while completing tours and service to all customers. The proposed procedure uses regency and frequency memories form Tabu Search to further improve the quality of solutions. Experiments are carried out using instances from literature and show the effectiveness of this procedure.     

The single vehicle pickup and delivery problem with time windows: intelligent operators for heuristic and metaheuristic algorithms

The single vehicle pickup and delivery problem with time windows is an important practical problem, yet only a few researchers have tackled it. In this research, we compare three different approaches to the problem: a genetic algorithm, a simulated annealing approach, and a hill climbing algorithm. In all cases, we adopt a solution representation that depends on a duplicate code for both the pickup request and its delivery. We also present an intelligent neighborhood move, that is guided by the time window, aiming to overcome the difficult problem constraints efficiently. Results presented herein improve upon those that have been previously published.     

Stochastic investment models—theory and applications

The paper discusses a stochastic model for investment variables, involving four series: the Retail Prices Index, an index of share dividend yields, an index of share yields, and the yield on ‘consols’. Section 2 describes the model and explains its derivation on the basis of historical data. Section 3 shows how the model can be used for forecasting the distributions of the variables. Section 4 discusses possible applications, and describes two in detail, relating to the expense charges of unit trusts and to guarantees incorporated in index linked life annuities.     

Optimal dynamic control of predator–prey models

Central European Journal of Operations Research - This paper combines work to use a decision support tool for sustainable economic development, while acknowledging interdependent dynamics of...     

From vehicle–driver behaviors to first order traffic flow macroscopic models

This paper proposes a two scale modeling approach to vehicular traffic, where macroscopic conservation equations are closed by models at the microscopic scale obtained by a mathematical interpretation of driver behaviors to local flow conditions. The paper focuses on the closure of the mass conservation equations by phenomenological models derived by a detailed analysis at the scale of individual vehicles.     

To run or not?: Some dynamic programming models in cricket

In cricket, particularly near the end of an innings, batsmen of different abilities need to manage the rate at which they score runs. Either batsman can choose to bat aggressively or defensively, which alters their chances of scoring runs or being dismissed. Since they change ends when they score a run and at the end of an over, by scoring an odd or even number of runs the two batsmen also determine which of them will face the next ball. It may be worthwhile to refuse a run to keep the slower or lower scoring batsman from the strike. Some dynamic programming models are developed which could be used to maximise the total number of runs scored.     

Factorization algorithms and non‐stationary wiener filtering

An algorithm for the linear least squares prediction of some classes of non‐stationary processes is obtained. The non‐stationary models under study recover and unify, in a single framework, the Kolmogorov‐Wiener and the Kalman theory of prediction, and also contain other non-stationary classes such as second order martingale difference processes.     

2-D finite element analysis of rigid pavement considering dynamic vehicle–pavement interaction effects

In the present study, an improved solution algorithm based on Finite Element Method for dynamic analysis of rigid pavements under moving loads is presented incorporating vehicle–pavement interaction which is having significant effect on the response. The concrete pavement is discretized by finite and infinite plate elements. The underlying soil medium is modeled by Pasternak model. An attempt is made to consider the infinite extent of the pavement with introduction of infinite elements at both ends. A detailed study is carried out for the range of velocities for pavements of finite and infinite lengths resting on two parameter soil medium. The effect of soil modulus, shear modulus, pavement thickness and the vehicle–pavement interaction on the response of pavement is presented. Relationships are suggested in non-dimensional form to predict critical velocity and maximum deflection for three prominent peaks in case of analysis without VPI and first critical velocity range of analysis with VPI. Predicted values using these relationships are in good agreement with the actual values. The comparison between the response of finite and infinite pavement lengths revealed that the deflections are decreased and the critical velocity range is narrowed in case of pavements of infinite length.