A stochastic model for a vehicle in a dial-a-ride system

We consider a stochastic model for a system which can serve n customers concurrently, and each accepted and departing customer generates a service interruption. The proposed model describes a single vehicle in a dial-a-ride transport system and is closely related to Erlang’s loss system. We give closed-form expressions for the blocking probability, the acceptance rate, and the mean sojourn time, which are all shown to be insensitive with respect to the forms of the distributions defining the workload and interruption durations.     

A periodic-review inventory system with a capacitated backup supplier for mitigating supply disruptions

We consider a periodic-review inventory system with two suppliers: an unreliable regular supplier that may be disrupted for a random duration, and a reliable backup supplier that can be used during a disruption. The backup supplier charges higher unit purchasing cost and fixed order cost when compared to the regular supplier. Because the backup supplier is used at unplanned moments, its capacity to replenish inventory is considered limited. Analytical results partially characterize the structure of the optimal order policy: a state-dependent (X(i), Y(i)) band structure (with corresponding bounds of X(i) and Y(i) to be given), where i represents the status of the regular supplier. Numerical studies illustrate the structure of the optimal policy and investigate the impacts of major parameters on optimal order decisions and system costs.     

On the use of phase‐type distributions for inventory management with supply disruptions

Maintaining the continuity of operations becomes increasingly important for systems that are subject to disruptions due to various reasons. In this paper, we study an inventory system operating under a (q, r) policy, where the supply can become inaccessible for random durations. The availability of the supply is modeled by assuming a single supplier that goes through ON and OFF periods of stochastic duration, both of which are modeled by phase‐type distributions (PTD). We provide two alternative representations of the state transition probabilities of the system, one with integral and the other employing Kolmogorov differential equations. We then use an efficient formulation for the analytical model that gives the optimal policy parameters and the long‐run average cost. An extensive numerical study is conducted, which shows that OFF time characteristics have a bigger impact on optimal policy parameters. The ON time characteristics are also important for critical goods if disasters can happen. Copyright © 2011 John Wiley & Sons, Ltd.     

Dynamic programming based metaheuristics for the dial-a-ride problem

The organization of a specialized transportation system to perform transports for elderly and handicapped people is usually modeled as dial-a-ride problem. Users place transportation requests with specified pickup and delivery locations and times. The requests have to be completed under user inconvenience considerations by a specified fleet of vehicles. In the dial-a-ride problem, the aim is to minimize the total travel times respecting the given time windows, the maximum user ride times, and the vehicle restrictions. This paper introduces a dynamic programming algorithm for the dial-a-ride problem and demonstrates its effective application in (hybrid) metaheuristic approaches. Compared to most of the works presented in literature, this approach does not make use of any (commercial) solver. We present an exact dynamic programming algorithm and a dynamic programming based metaheuristic, which restricts the considered solution space. Then, we propose a hybrid metaheuristic algorithm which integrates the dynamic programming based algorithms into a large neighborhood framework. The algorithms are tested on a given set of benchmark instances from the literature and compared to a state-of-the-art hybrid large neighborhood search approach.     

An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows

The dial-a-ride problem (DARP) is a widely studied theoretical challenge related to dispatching vehicles in demand-responsive transport services, in which customers contact a vehicle operator requesting to be carried from specified origins to specified destinations. An important subproblem arising in dynamic dial-a-ride services can be identified as the single-vehicle DARP, in which the goal is to determine the optimal route for a single vehicle with respect to a generalized objective function. The main result of this work is an adaptive insertion algorithm capable of producing optimal solutions for a time constrained version of this problem, which was first studied by Psaraftis in the early 1980s. The complexity of the algorithm is analyzed and evaluated by means of computational experiments, implying that a significant advantage of the proposed method can be identified as the possibility of controlling computational work smoothly, making the algorithm applicable to any problem size.     

A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem

This work deals with a dynamic dial-a-ride problem with time window constraints. In particular, new unplanned requests for service may arise at a vehicle stop and the driver must decide in real-time whether to accept or reject them.For this problem, we have developed a two-phase insertion algorithm based on route perturbations: the first phase, which is run off-line when the vehicle moves between two successive stops, aims at creating a feasible neighborhood of the current route; while the second phase, which is run in real-time every time a new request occurs, inserts, when possible, the delivery stop of the new customer in the current route.     

A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints

This paper presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints. In this heuristic, a properly organized local search strategy and a diversification strategy are used to improve initial solutions. Then the improved solutions can be refined further by an intensification strategy. The performance of this heuristic was evaluated by intensive computational tests on some randomly generated instances. Small gaps to the lower bounds from the column generation method were obtained in very short time for instances with no more than 200 requests. Although the result is not sensitive to the initial solution, the computational time can be greatly reduced if some effort is spent to construct a good initial solution. With this good initial solution, larger instances up to 2000 requests were solved in less than 10 hours on a popular personal computer.     

A heuristic algorithm for a dial-a-ride problem with time windows,multiple capacities,and multiple objectives

The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface.     

Analysis of a two-party supply chain with random disruptions

We study a continuous-review inventory problem of a two-echelon supply chain with random disruptions, identify properties of the optimal cost function, compare the optimal order quantity with the classical economic order quantity, analyze the sensitivity of the optimal solution, and explore the conditions under which zero-inventory ordering policy is preferred.     

Operational effects of service level variations for the dial-a-ride problem

The dial-a-ride problem consists of designing a number of minimum-cost vehicle routes in a system of demand-dependent, collective people transportation. Quality is ensured by taking into account service level requirements. However, little research has been conducted into the effect of service level variations on operational costs incurred by service providers. This study investigates the evolution of operational costs for 78 combinations of two service level parameters, being the maximum deviation from a user’s preference time and the relative maximum exceedance of a user’s direct ride time. A distinction is made between various operating circumstances, including the size of the service provider, the traffic conditions in the service area and the heterogeneity of the customers. The resulting tradeoffs between quality and costs should encourage service providers to make informed decisions regarding potential changes in the service level they offer. The sensitivity analysis in this paper is performed on well-known benchmark data from literature and applies a state-of-the-art deterministic annealing metaheuristic to compute operational costs.     

A knowledge-based system for cash management with management science expertise

A PC based system called CASH MANAGER is presented. It is a knowledge-based decision support system designed for financial managers. The system contains financial manager knowledge and management science expertise. It is designed to support decisions made by financial managers, who are not management science experts, yet desire to employ the capabilities of management science tools. CASH MANAGER can formulate a cash management problem as an embedded network problem, solve the problem, ensure its feasibility, interpret the output of the solution and recommend alternative courses of action.     

Topics in real-time fleet management

This is a summary of the author’s Ph.D. thesis, supervised by Gianpaolo Ghiani and Barrett W. Thomas and defended on 21 February 2008, at the Università degli Studi della Calabria. The thesis is written in English and is available from the author upon request. In this work, various tactical and operational issues concerning real-time fleet management are studied. First, we introduce the Dynamic and Stochastic Traveling Salesman Problem and propose an optimal policy through a Markov Decision Process as well as develop lower and upper bounds on the optimal policy cost. Then, we present several strategies for implementing a priori routes, and we identify situations in which the use of more involved a priori strategies can give some benefit. Next, we consider the Dynamic and Stochastic Vehicle Dispatching Problem with Pickups and Deliveries, for which we develop anticipatory algorithms that evaluate alternative solutions through a short-term demand sampling and a fully sequential procedure for indifference zone selection. Finally, we propose Approximated Neighborhood Evaluation procedures for the same-day Courier Shift Scheduling Problem, a tactical problem which amounts to minimizing the staffing cost subject to probabilistic service level requirements.      

The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments

This paper studies a dynamic dial-a-ride problem bearing complex constraints on a time-dependent network. A flexible scheduling scheme is proposed to dynamically cope with different stochastic events, such as the travelling time fluctuation, new requests, absences of customers, vehicle breakdowns, cancellations of requests, traffic jams and so on. A fast heuristic is proposed to re-optimize the schedule when a new event occurs. This heuristic consists of a properly organized local search strategy and uses a secondary objective function to drive the search out of local optima. Intensive computational simulations were carried out to evaluate the performance of this scheduling scheme and the influence of different stochastic factors. The simulation results of different scenarios with different percentage of dynamic requests reveal that this scheduling scheme can generate high quality schedules and is capable of coping with various stochastic events.     

Initiating a state of the art system for real-time supply chain coordination

Intelligent Wireless Web (IWW) employs the capabilities of high speed wireless networks and exploits the parallel advancements in Internet-based technologies such as the Semantic Web, Web Services, Agent-based Technologies, and context awareness. Considering its great potentials to be applied in business systems, we have devised an innovative model, based on the IWW services, for a typical mobile real-time supply chain coordination system which has been developed and tested in a real operational environment. Our article investigates the proposed system in this way: at the start, the building blocks of the IWW are discussed in detail. Then, we fully explain the basic concepts of mobile real-time supply chain coordination and concentrate on the motivations to implement such a modern system. The vision of intelligent wireless web services, as discussed in this paper, centers on the need to provide mobile supply chain members highly specific data and services in real-time on an as-needed basis, with the flexibility of use for the user. In this regard, we investigate nine enabling technologies of the IWW for our system and discuss how, by exploiting the convergence and synergy between different technologies, it has become possible to deliver intelligent wireless web support to mobile real-time supply chain coordination. Afterwards, a practical framework is clearly established in four phases. This initiative system has been implemented in the laboratory and has passed the evaluation processes successfully. Further details will be announced in near future in another research article.     

A note on “Efficient feasibility testing for dial-a-ride problems”

Hunsaker and Savelsbergh [B. Hunsaker, M.W.P. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169-173.] developed a linear-time algorithm to verify the feasibility for dial-a-ride problems. However, this algorithm may incorrectly declare infeasibility due to ride time constraints in some cases. We propose a revised procedure to address this flaw, but in an O(n²) worst-case time.     

Rescheduling problems with deteriorating jobs under disruptions

In this paper, we consider two single-machine rescheduling problems with linear deteriorating jobs under disruption. By a deteriorating jobs, we mean that the actual processing time of the job is an increasing function of its starting time. The two problems correspond to two different increasing linear function. Rescheduling means a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. We consider the rescheduling problem to minimize the total completion time under a limit of the disruption from the original scheduling. For each problem, we consider two versions. For each version, the polynomial algorithms are proposed, respectively.     

A method of optimal real-time computation of a linear system with retarded control

A new method of solving time-optimal control problems in real time is developed. The method is based on the following: 1) approximating the attainability sets with a family of hyperplanes; 2) subdividing the whole computational process into the computations performed beforehand and those that are carried out while the control takes place; 3) integrating the differential equations only over the displacement intervals of the final time point and the switching time points. The computational cost of the method is evaluated. The peculiarities of calculating the optimal control of a linear system with retarded control in real time are considered. The results of simulation and numerical calculations are presented.     

Perishable inventory management system with a minimum volume constraint

The federal government maintains large quantities of medical supplies in stock as part of its Strategic National Stockpile (SNS) to protect the American public in case of a public health emergency. Managing these large perishable inventories effectively can help reduce the cost of the SNS and improves national security. In this paper, we propose a modified Economic Manufacturing Quantity (EMQ) model for perishable inventory with a minimum volume constraint, which is applicable to managing the inventory of medicines for the Strategic National Stockpile. We demonstrate that minimizing the cost of maintaining such a system can be formulated as a non-convex non-smooth unconstrained optimization problem. The property of this model is analysed and an efficient exact algorithm is presented to solve this problem. In the numerical experiment part, we perform sensitivity analysis on several government-controlled system parameters to illustrate how the government can obtain lower costs or a larger stockpile at the same cost by allowing more freedom in the management of the stocks.     

Optimal memory management in a system with garbage collection

This paper discusses the problem of determining cost-saving policies for obtaining memory in systems with garbage collection, in particular the run time system of DEC-10 Simula. A mathematical model of the problem is defined and a policy is obtained from the model and a certain amount of heuristic reasoning. The implementation and validation of the policy is also described.     

Optimal impulse control for a multidimensional cash management system with generalized cost functions

We consider the optimal control of a multidimensional cash management system where the cash balances fluctuate as a homogeneous diffusion process in Rⁿ${\mathbb{R}}^n$. We formulate the model as an impulse control problem on an unbounded domain with unbounded cost functions. Under general assumptions we characterize the value function as a weak solution of a quasi-variational inequality in a weighted Sobolev space and we show the existence of an optimal policy. Moreover we prove the local uniform convergence of a finite element scheme to compute numerically the value function and the optimal cost. We compute the solution of the model in two-dimensions with linear and distance cost functions, showing what are the shapes of the optimal policies in these two simple cases. Finally our third numerical experiment computes the solution in the realistic case of the cash concentration of two bank accounts made by a centralized treasury.