Recovery management for a dial-a-ride system with real-time disruptions

The problem considered in this work stems from a non-profit organization in charge of door-to-door passenger transportation for medical appointments. Patients are picked up at home by a driver and are then dropped at their appointment location. They may also be driven back home at the end of their appointment. Some patients have specific requirements, e.g., they may require an accompanying person or a wheelchair. Planning such activities gives rise to a so-called dial-a-ride problem. In the present work, it is assumed that the requests assigned to the drivers have been selected, and the transportation plan has been established for the next day. However, in practice, appointment durations may vary due to unforeseen circumstances, and some transportation requests may be modified, delayed or canceled during the day. The aim of this work is to propose a reactive algorithm which can adapt the initial plan in order to manage the disruptions and to take care of as many patients as possible in real-time. The plan should be modified quickly when a perturbation is observed, without resorting to major changes which may confuse the drivers and the patients. Several recourse procedures are defined for this purpose. They allow the dispatcher to temporarily delete a request, to insert a previously deleted request, or to permanently cancel a request. Simulation techniques are used to test the approach on randomly generated scenarios. Several key performance indicators are introduced in order to measure the impact of the disruptions and the quality of the solutions.     

A dynamic vehicle routing problem with multiple delivery routes

This paper considers a vehicle routing problem where each vehicle performs delivery operations over multiple routes during its workday and where new customer requests occur dynamically. The proposed methodology for addressing the problem is based on an adaptive large neighborhood search heuristic, previously developed for the static version of the problem. In the dynamic case, multiple possible scenarios for the occurrence of future requests are considered to decide about the opportunity to include a new request into the current solution. It is worth noting that the real-time decision is about the acceptance of the new request, not about its service which can only take place in some future routes (a delivery route being closed as soon as a vehicle departs from the depot). In the computational results, a comparison is provided with a myopic approach which does not consider scenarios of future requests.     

Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system

This paper presents the first application of prepositioning in the context of the dynamic stochastic on-demand bus routing problem (DODBRP). The DODBRP is a large-scale dial-a-ride problem that involves bus station assignment and aims to minimize the total user ride time (URT) by simultaneously assigning passengers to alternative stations and determining optimal bus routes.In the DODBRP, transportation requests are introduced dynamically, and buses are dispatched to stations with known requests. This paper investigates the concept of prepositioning, which involves sending buses not only to currently known requests but also to requests that are likely to appear in the future, based on a given probability.To solve this dynamic and stochastic ODBRP, the paper proposes a heuristic algorithm based on variable neighborhood search (VNS). The algorithm considers multiple scenarios to represent different realizations of the stochastic requests.Experimental results demonstrate the superiority of the prepositioning approach over the DODBRP across various levels of forecast accuracy, lengths of time bucket, and probabilities of realization. Furthermore, the paper shows that removing empty stations as a recourse action can further enhance solution quality. Additionally, in situations with low prediction accuracy, increasing the number of scenarios can lead to improved solutions. Finally, a combination of prepositioning, empty station removal, and the insertion of dynamic requests proves to be effective.Overall, the findings of this paper provide valuable insights into the application of prepositioning in the dynamic stochastic on-demand bus routing problem, highlighting its potential for addressing real-world transportation challenges.     

Fair resource allocation for different scenarios of demands

This paper considers a resource allocation problem, which objective is to treat fairly all the system users. Usually the requests cannot be entirely predicted, but the manager can forecast the request evolution, this leading to a set of possible scenarios. Such a problem arises for instance in network bandwidth allocation as well as in storage space management. It also appears in the management of computer systems, such as computational grids or in cloud computing, when teams share a common pool of machines. Problems of fair resource sharing arise among users with equal access right but with different needs.Here the problem is tackled by a multi-criteria model, where one criterion is associated to one scenario. A solution is a policy, which provides an allocation for each scenario. An algorithm is proposed and analysed that lists all solutions which are Pareto optimal with regard to the different possible user request scenarios. The algorithm is used offline, but can be adapted, with some additional hypothesis, to be used online.     

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.     

Modeling uncertain passenger arrivals in the elevator dispatching problem with destination control

An Elevator Group Control System (EGCS) assigns an elevator of a group to each passenger transportation request by solving a snapshot optimization problem, the Elevator Dispatching Problem (EDP). In the destination control, passengers register their destination floors in the elevator lobbies, after which the EGCS completes the assignment at once and is not allowed to change it later. Therefore, the EDP is formulated as a stochastic optimal control problem, where uncertain future passenger arrivals are modeled by a Poisson and a geometric Poisson process. The EDP is considered as a certainty equivalent controller in which the uncertain quantities are replaced by their expected values, and as a robust controller in which they take multiple values according to risk scenarios. Numerical experiments show that the expectations do not accurately predict EDP variables. The modeling with the geometric Poisson process results in better forecasting accuracy than with the Poisson process and many scenarios that closely match the realizations of the variables. Hence, the scenarios can be used as a basis for a robust EDP which simultaneously minimizes a passenger service quality criterion and its variation due to uncertain demand.     

A novel approach using parallel Kalman filters in time and frequency estimation

In the present information based knowledge society, accurate knowledge of time and frequency plays a fundamental role. For many applications, real time estimates of the clocks time and frequency error are required. We have developed a novel approach for estimating time and frequency errors based on an assembly of clocks of varying quality. By using parallel Kalman filters we utilize all available measurements in the estimation. As these measurements are available with different delays, the Kalman filter produces estimates of different quality. One filtermay produce real-time estimates while another filter waits for delayed measurements. When new information becomes available, the parallel Kalman filters exchange information in order to keep the state matrices updated with the most recent information. In Kalman filtering, accurate modelling of the measurement system is fundamental. All the contributing clocks, as well as the time transfer methods, are modelled as stochastic processes. By using this methodology and by correctly modelling the contributing clocks, we obtain minimum mean square error estimators (MMSE) of the time and frequency errors of a specific clock at every epoch. In addition, we also determine the uncertainty of each time and frequency error estimate. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A robust approach for scheduling in hospitals using multiple objectives

Scheduling in hospitals is a challenging task and stochastic influences have a major impact on the final schedule. Therefore, uncertainties of treatment durations and of emergency arrivals have to be taken into account explicitly. In order to avoid re-scheduling we integrate information on stochastic parameters into a scenario-based mixed-integer optimization model. Besides, we focus on different stakeholders’ objectives that are simultaneously considered within a multi-criteria optimization model. Individually optimal solutions are likely to differ and the overall aim is to identify a good and acceptable compromise solution. The presented approach is based on fuzzy sets and merges the interests of several stakeholders. Different schedules are calculated and later on evaluated with randomly generated scenarios for surgery times and emergencies. The resulting objective function values are close to the individually optimal solutions. Finally, the schedules lead to a high rate of utilization and a low amount of overtime.     

Numerical evaluation of approximation methods in stochastic programming

We study an approach for the evaluation of approximation and solution methods for multistage linear stochastic programmes by measuring the performance of the obtained solutions on a set of out-of-sample scenarios. The main point of the approach is to restore the feasibility of solutions to an approximate problem along the out-of-sample scenarios. For this purpose, we consider and compare different feasibility and optimality based projection methods. With this at hand, we study the quality of solutions to different test models based on classical as well as recombining scenario trees.     

Non-linear filtering and optimal investment under partial information for stochastic volatility models

This paper studies the question of filtering and maximizing terminal wealth from expected utility in partial information stochastic volatility models. The special feature is that the only information available to the investor is the one generated by the asset prices, and the unobservable processes will be modeled by stochastic differential equations. Using the change of measure techniques, the partial observation context can be transformed into a full information context such that coefficients depend only on past history of observed prices (filter processes). Adapting the stochastic non-linear filtering, we show that under some assumptions on the model coefficients, the estimation of the filters depend on a priori models for the trend and the stochastic volatility. Moreover, these filters satisfy a stochastic partial differential equations named “Kushner–Stratonovich equations”. Using the martingale duality approach in this partially observed incomplete model, we can characterize the value function and the optimal portfolio. The main result here is that, for power and logarithmic utility, the dual value function associated to the martingale approach can be expressed, via the dynamic programming approach, in terms of the solution to a semilinear partial differential equation which depends on the filters estimate and the volatility. We illustrate our results with some examples of stochastic volatility models popular in the financial literature.     

Robustness in stochastic programs with risk constraints

This paper is a contribution to the robustness analysis for stochastic programs whose set of feasible solutions depends on the probability distribution?P. For various reasons, probability distribution P may not be precisely specified and we study robustness of results with respect to perturbations of?P. The main tool is the contamination technique. For the optimal value, local contamination bounds are derived and applied to robustness analysis of the optimal value of a portfolio performance under risk-shaping CVaR constraints. A?new robust portfolio efficiency test with respect to the second order stochastic dominance criterion is suggested and the contamination methodology is exploited to analyze its resistance with respect to additional scenarios.     

A differentiated service scheme to optimize website revenues

We consider a website host server with web quality of service (QoS) capabilities to offer differentiated services. A quantitative modelling framework is set up to analyse the economic benefits of differentiated services and to build optimization models for managing the website host's connection bandwidth to the Internet (which is assumed to be the bottleneck factor determining the QoS). Three models are formulated corresponding to three operational scenarios to provide differentiated services. The first is for the marketing manager to classify visit requests as premium or basic when the information technology (IT) manager has already reserved bandwidths for the two classes, and the second is for the IT manager to allocate the total available bandwidth to each class when the marketing manager has already designated which visit requests are premium and which are basic. The third is for the joint optimization of request classification and bandwidth allocation when centralized coordination is possible. Analytic results are obtained for a special case that corresponds to very impatient customers requesting large amounts of data. Qualitative insights gained and numerical results obtained strongly support the implementation of differentiated services. More interestingly, the decentralized models that use simple and rough-cut rules yield solutions almost as good as the joint optimization model.     

A heuristic approach for airport gate assignments for stochastic flight delays

To make good flight to gate assignments, not only do all the relevant constraints have to be considered, but stochastic flight delays that occur in actual operations also have to be taken into account. In past research, airport gate assignments and stochastic disturbances have often been handled in the planning and the real-time stages separately, meaning that the interrelationship between these stages, as affected by such delays, has been neglected. In this research, we develop a heuristic approach embedded in a framework designed to help the airport authorities make airport gate assignments that are sensitive to stochastic flight delays. The framework includes three components, a stochastic gate assignment model, a real-time assignment rule, and two penalty adjustment methods. The test results are based on data supplied by a Taiwan international airport, and show that the proposed framework performs better than the current manual assignment process and the traditional deterministic model.     

A two-stage stochastic programming framework for transportation planning in disaster response

This study proposes a two-stage stochastic programming model to plan the transportation of vital first-aid commodities to disaster-affected areas during emergency response. A multi-commodity, multi-modal network flow formulation is developed to describe the flow of material over an urban transportation network. Since it is difficult to predict the timing and magnitude of any disaster and its impact on the urban system, resource mobilization is treated in a random manner, and the resource requirements are represented as random variables. Furthermore, uncertainty arising from the vulnerability of the transportation system leads to random arc capacities and supply amounts. Randomness is represented by a finite sample of scenarios for capacity, supply and demand triplet. The two stages are defined with respect to information asymmetry, which discloses uncertainty during the progress of the response. The approach is validated by quantifying the expected value of perfect and stochastic information in problem instances generated out of actual data.     

Parametric modeling of protein–DNA binding kinetics: A discrete event based simulation approach

To understand the stochastic behavior of biological systems, we adopt an “in silico” stochastic event based simulation methodology that can determine the temporal dynamics of different molecules. The main requirement for this technique is the event execution time models for the different biological functions of the system. This paper presents a parametric model to determine the execution time of one such biological function: protein–DNA binding. This biological function is modeled as a combination of microlevel biological events using a coarse-grained probability measure to estimate the stochastic parameters of the function. Our model considers the actual binding mechanism along with some approximated protein and DNA structural information. We use a collision theory based approach to transform the thermal and concentration gradients of this biological function into their corresponding probability measure. This information theoretic approach significantly removes the complexity of the classical protein sliding along the DNA model, improves the speed of computation and can bypass the speed-stability paradox. This model can produce acceptable estimates of DNA–protein binding time necessary for our event based stochastic system simulator where the higher order (more than second order statistics) uncertainties can be ignored. The results show good correspondence with available experimental estimates. The model depends very little on experimentally generated rate constants and brings the important biological parameters and functions into consideration. We also present some “in silico” results showing the effects of protein–DNA binding on gene expression in prokaryotic cells.     

Real-time control of freight forwarder transportation networks by integrating multimodal transport chains

Western European freight forwarders are continually being forced to increase the efficiency of their transportation processes because of the liberalization and deregulation of the European transport market. This paper proposes a new real-time-oriented control approach in order to expand load consolidation, reduce empty vehicle trips, and handle dynamic disturbances. This approach integrates multimodal transportation and multiple transshipments for the first time. Thus, it enables the flexible generation and adaptation of transportation processes. In order to be able to handle occurring disturbances, an optimization procedure that adapts the transportation processes is continually applied. Vehicle breakdowns or deceleration of vehicles, traffic congestion, and street blockages are integrated as possible disturbance scenarios. At the same time, dynamically incoming transportation requests are also dealt with. Moreover, cooperative agreements between freight forwarders, which are gaining increasing importance, are integrated by mapping hubs and external services. The efficiency of the new real-time approach is validated by several computational experiments. In particular, the use of the entire execution time for plan adaptation as well as the integration of multiple transshipments has shown promising results.     

A Lagrangean relaxation and decomposition algorithm for the video placement and routing problem

Video on demand (VoD) is a technology used to provide a number of programs to a number of users on request. In developing a VoD system, a fundamental problem is load balancing, which is further characterized by optimally placing videos to a number of predefined servers and routing the user program requests to available resources. In this paper, an exact solution algorithm is described to solve the video placement and routing problem. The algorithm is based on Lagrangean relaxation and decomposition. The novelty of the approach can be described as the use of integer programs to obtain feasible solutions in the algorithm. Computational experimentation reveals that for randomly generated problems with up to 100 nodes and 250 videos, the use of such integer programs help greatly in obtaining good quality solutions (typically within 5% of the optimal solution), even in the very early iterations of the algorithm.     

Real-time order tracking for supply systems with multiple transportation stages

This paper presents a stochastic model that evaluates the value of real-time shipment tracking information for supply systems that consist of a retailer, a manufacturer, and multiple stages of transportation. The retailer aggregates demand for a single product from end customers and places orders on the manufacturer. Orders received by the manufacturer may take several time periods before they are fulfilled. Shipments dispatched by the manufacturer move through multiple stages before they reach the retailer, where each stage represents a physical location or a step in the replenishment process. The lead time for a new order depends on the number of unshipped orders at the manufacturer’s site and the number and location of all shipments in transportation. The analytic model uses real-time information on the number of orders unfulfilled at the manufacturer’s site, as well as the location of shipments to the retailer, to determine the ordering policy that minimizes the long-run average cost for the retailer. It is shown that the long-run average cost is lower with real-time tracking information, and that the cost savings are substantial for a number of situations. The model also provides some guidelines for operating this supply system under various scenarios. Numerical examples demonstrate that when there is a lack of information it is better for the retailer to order every time period, but with full information on the status in the supply system it is not always necessary for the retailer to order every time period to lower the long-run average cost.     

A two-echelon stochastic facility location model for humanitarian relief logistics

We develop a two-stage stochastic programming model for a humanitarian relief logistics problem where decisions are made for pre- and post-disaster rescue centers, the amount of relief items to be stocked at the pre-disaster rescue centers, the amount of relief item flows at each echelon, and the amount of relief item shortage. The objective is to minimize the total cost of facility location, inventory holding, transportation and shortage. The deterministic equivalent of the model is formulated as a mixed-integer linear programming model and solved by a heuristic method based on Lagrangean relaxation. Results on randomly generated test instances show that the proposed solution method exhibits good performance up to 25 scenarios. We also validate our model by calculating the value of the stochastic solution and the expected value of perfect information.     

Evolutionary multiobjective optimization in noisy problem environments

This paper presents a multiobjective evolutionary algorithm (MOEA) capable of handling stochastic objective functions. We extend a previously developed approach to solve multiple objective optimization problems in deterministic environments by incorporating a stochastic nondomination-based solution ranking procedure. In this study, concepts of stochastic dominance and significant dominance are introduced in order to better discriminate among competing solutions. The MOEA is applied to a number of published test problems to assess its robustness and to evaluate its performance relative to NSGA-II. Moreover, a new stopping criterion is proposed, which is based on the convergence velocity of any MOEA to the true Pareto optimal front, even if the exact location of the true front is unknown. This stopping criterion is especially useful in real-world problems, where finding an appropriate point to terminate the search is crucial.