Linear programming based decomposition methods for inventory distribution systems

We consider an inventory distribution system consisting of one warehouse and multiple retailers. The retailers face random demand and are supplied by the warehouse. The warehouse replenishes its stock from an external supplier. The objective is to minimize the total expected replenishment, holding and backlogging cost over a finite planning horizon. The problem can be formulated as a dynamic program, but this dynamic program is difficult to solve due to its high dimensional state variable. It has been observed in the earlier literature that if the warehouse is allowed to ship negative quantities to the retailers, then the problem decomposes by the locations. One way to exploit this observation is to relax the constraints that ensure the nonnegativity of the shipments to the retailers by associating Lagrange multipliers with them, which naturally raises the question of how to choose a good set of Lagrange multipliers. In this paper, we propose efficient methods that choose a good set of Lagrange multipliers by solving linear programming approximations to the inventory distribution problem. Computational experiments indicate that the inventory replenishment policies obtained by our approach can outperform several standard benchmarks by significant margins.     

Production and payment policies for an imperfect manufacturing system with discount cash flows analysis in fuzzy random environments

ABSTRACT

This paper considers an imperfect manufacturing system with credit policies in fuzzy random environments. The supplier simultaneously offers the retailer either a permissible delay in payments or a cash discount and retailer in turn provides its customer a permissible delay period. We used an alternate approach – discount cash flow analysis to establish an inventory problem. It is assumed that the elapsed time until the machine shifts from ‘in-control’ state to ‘out-of-control’ state is characterized as a fuzzy random variable. As a function of this parameter, the profit function is also a random fuzzy variable. Based on the credibility measure of fuzzy event, the model with fuzzy random elapsed time can be transformed into a crisp model . We establish several theoretical results to obtain the solution that provides the largest present value of all future cash flows. Finally, numerical example is given to illustrate the results and obtain some managerial insights.     

基于鲁棒优化的随机时变网络最优路径研究

交通事故、恶劣天气以及偶发的交通拥堵等都会导致道路交通网络中行程时间的不确定性,极大地影响了道路交通系统的可靠性,同时给日常生活中出行计划的制定以及出行路径的选择带来了不便。因此,本次研究将综合考虑道路交通网络中由于交通流量的全天变化所导致的路径行程时间的时变特征,以及由于事故、天气等不确定因素所导致的路径行程时间的随机特征,并以此作为路网环境的假设条件,对出行路径选择问题进行研究。具体地,首先建立行程时间的动态随机变量,并在此基础上模拟构建了随机时变网络。随后,定义了该网络环境下路径选择过程中所考虑的成本费用,并通过鲁棒优化的方法,将成本费用鲁棒性最强的路径视为最优路径。随后,在随机一致性条件下,通过数学推导证明了该模型可以简化为解决一个确定性时变网络中的最短路径问题。最终,具有多项式时间计算复杂度的改进Dijkstra算法被应用到模型的求解中,并通过小型算例验证模型及算法的有效性。结果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依赖于先验行程时间概率分布的获取,因此对后续的大规模实际城市道路网络应用提供了良好的理论基础。此外,由于具有行程时间随机时变特征的交通网络更接近实际道路情况,因此本次研究的研究成果具有较高的实际意义和应用价值。     

A continuous whole-link travel time model with occupancy constraint

The continuous dynamic network loading problem (CDNLP) aims to compute link travel times and path travel times on a congested network, given time-dependent path flow rates for a given time period. A crucial element of CDNLP is a model of the link performance. Two main modeling frameworks have been used in link loading models: The so-called whole-link travel time (WTT) models and the kinematic wave model of Lighthill–Whitham–Richards (LWR) for traffic flow.In this paper, we reformulate a well-known whole-link model in which the link travel time, for traffic entering a time t, is a function of the number of vehicles on link. This formulation does not require the satisfying of the FIFO (first in, first out) condition. An extension of the basic WTT model is proposed in order to take explicitly into account the maximum number of vehicles that the link can accommodate (occupancy constraint). A solution scheme for the proposed WTT model is derived.Several numerical examples are given to illustrate that the FIFO condition is not respected for the WTT model and to compare the travel time predictions effected by LWR and WTT models.     

Algorithms for a stochastic selective travelling salesperson problem

In this paper, the selective travelling salesperson problem with stochastic service times, travel times, and travel costs (SSTSP) is addressed. In the SSTSP, service times, travel times and travel costs are known a priori only probabilistically. A non-negative value of reward for providing service is associated with each customer and there is a pre-specified limit on the duration of the solution tour. It is assumed that not all potential customers can be visited within this tour duration limit, even under the best circumstances. And, thus, a subset of customers must be selected. The objective of the SSTSP is to design an a priori tour that visits each chosen customer once such that the total profit (total reward collected by servicing customers minus travel costs) is maximized and the probability that the total actual tour duration exceeds a given threshold is no larger than a chosen probability value. We formulate the SSTSP as a chance-constrained stochastic program and propose both exact and heuristic approaches for solving it. Computational experiments indicate that the exact algorithm is able to solve small- and moderate-size problems to optimality and the heuristic can provide near-optimal solutions in significantly reduced computing time.     

Bi-criteria dynamic location-routing problem for patrol coverage

In this paper, we address the problem of dynamic patrol routing for state troopers for effective coverage of highways. Specifically, a number of state troopers start their routes at temporary stations (TS), patrol critical locations with high crash frequencies, and end their shifts at other (or the same) TS so the starting points for the next period are also optimized. We determine the number of state troopers, their assigned routes, and the locations of the TS where they start and end their routes. The TS are selected from a given set of potential locations. The problem, therefore, is a multi-period dynamic location-routing problem in the context of public service. Our objective is to maximize the critical location coverage benefit while minimizing the costs of TS selections, vehicle utilizations, and routing/travel. The multi-objective nature of the problem is handled using an ?-constraint approach. We formulate the problem as a mixed integer linear programming model and solve it using both off-the-shelf optimization software and a custom-built, efficient heuristic algorithm. The heuristic, utilizing the hierarchical structure of the problem, is built on the decomposition of location and routing problems. By allowing routing to start from multiple locations, our model improves the coverage by as much as 12% compared with the single-depot coverage model.     

A branch-and-bound algorithm for instrumental variable quantile regression

This paper studies a statistical problem called instrumental variable quantile regression (IVQR). We model IVQR as a convex quadratic program with complementarity constraints and—although this type of program is generally NP-hard—we develop a branch-and-bound algorithm to solve it globally. We also derive bounds on key variables in the problem, which are valid asymptotically for increasing sample size. We compare our method with two well known global solvers, one of which requires the computed bounds. On random instances, our algorithm performs well in terms of both speed and robustness.     

The finite multiple lot sizing problem with interrupted geometric yield and holding costs

We consider the multiple lot sizing problem in production systems with random process yield losses governed by the interrupted geometric (IG) distribution. Our model differs from those of previous researchers which focused on the IG yield in that we consider a finite number of setups and inventory holding costs. This model particularly arises in systems with large demand sizes. The resulting dynamic programming model contains a stage variable (remaining time till due) and a state variable (remaining demand to be filled) and therefore gives considerable difficulty in the derivation of the optimal policy structure and in numerical computation to solve real application problems. We shall investigate the properties of the optimal lot sizes. In particular, we shall show that the optimal lot size is bounded. Furthermore, a dynamic upper bound on the optimal lot size is derived. An O(nD) algorithm for solving the proposed model is provided, where n and D are the two-state variables. Numerical results show that the optimal lot size, as a function of the demand, is not necessarily monotone.     

Formulation and a two-phase matheuristic for the roaming salesman problem: Application to election logistics

In this paper we investigate a novel logistical problem. The goal is to determine daily tours for a traveling salesperson who collects rewards from activities in cities during a fixed campaign period. We refer to this problem as the Roaming Salesman Problem (RSP) motivated by real-world applications including election logistics, touristic trip planning and marketing campaigns. RSP can be characterized as a combination of the traditional Periodic TSP and the Prize-Collecting TSP with static arc costs and time-dependent node rewards. Commercial solvers are capable of solving small-size instances of the RSP to near optimality in a reasonable time. To tackle large-size instances we propose a two-phase matheuristic where the first phase deals with city selection while the second phase focuses on route generation. The latter capitalizes on an integer program to construct an optimal route among selected cities on a given day. The proposed matheuristic decomposes the RSP into as many subproblems as the number of campaign days. Computational results show that our approach provides near-optimal solutions in significantly shorter times compared to commercial solvers.     

Forecasting using belief functions: An application to marketing econometrics

A method is proposed to quantify uncertainty on statistical forecasts using the formalism of belief functions. The approach is based on two steps. In the estimation step, a belief function on the parameter space is constructed from the normalized likelihood given the observed data. In the prediction step, the variable Y to be forecasted is written as a function of the parameter θ and an auxiliary random variable Z with known distribution not depending on the parameter, a model initially proposed by Dempster for statistical inference. Propagating beliefs about θ and Z through this model yields a predictive belief function on Y. The method is demonstrated on the problem of forecasting innovation diffusion using the Bass model, yielding a belief function on the number of adopters of an innovation in some future time period, based on past adoption data.     

A Queueing Framework for Routing Problems with Time-dependent Travel Times

Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability (obtained via the queueing approach) is quantified for the different datasets.      

Asymptotics of random contractions

In this paper we discuss the asymptotic behaviour of random contractions X=RS, where R, with distribution function F, is a positive random variable independent of S∈(0,1). Random contractions appear naturally in insurance and finance. Our principal contribution is the derivation of the tail asymptotics of X assuming that F is in the max-domain of attraction of an extreme value distribution and the distribution function of S satisfies a regular variation property. We apply our result to derive the asymptotics of the probability of ruin for a particular discrete-time risk model. Further we quantify in our asymptotic setting the effect of the random scaling on the Conditional Tail Expectations, risk aggregation, and derive the joint asymptotic distribution of linear combinations of random contractions.     

Viability with Probabilistic Knowledge of Initial Condition, Application to Optimal Control

In this paper we provide an extension of the Viability and Invariance Theorems in the Wasserstein metric space of probability measures with finite quadratic moments in ? ^d for controlled systems of which the dynamic is bounded and Lipschitz. Then we characterize the viability and invariance kernels as the largest viability (resp. invariance) domains. As application of our result we consider an optimal control problem of Mayer type with lower semicontinuous cost function for the same controlled system with uncertainty on the initial state modeled by a probability measure. Following Frankowska, we prove using the epigraphical viability approach that the value function is the unique lower semicontinuous proximal episolution of a suitable Hamilton Jacobi equation.     

Implementation of sensitivity calculations on a monte carlo experiment

A new approach to the optimization of discrete-event dynamic systems has recently been developed (Refs. 1–4). The implementation of this approach requires answering the following question: given an observed value of the outcome of a random variable, what would have been the outcome if the parameters of the random variable had been different? The answer to this question would traditionally involve the value of an outcome in an underlying sample space. However, this underlying value cannot normally be observed. In this note, we give a framework for answering this question, in terms of the observed value alone. This point had not been considered rigorously in the new approach of Refs. 1–4, and our note derives a basic equation required for that approach.     

Two approximations of the present value distribution of a disability annuity

The distribution function of the present value of a cash flow can be approximated by means of a distribution function of a random variable, which is also the present value of a sequence of payments, but with a simpler structure. The corresponding random variable has the same expectation as the random variable corresponding to the original distribution function and is a stochastic upper bound of convex order. A sharper upper bound can be obtained if more information about the risk is available. In this paper, it will be shown that such an approach can be adopted for disability annuities (also known as income protection policies) in a three state model under Markov assumptions. Benefits are payable during any spell of disability whilst premiums are only due whenever the insured is healthy. The quality of the two approximations is investigated by comparing the distributions obtained with the one derived from the algorithm presented in the paper by Hesselager and Norberg [Insurance Math. Econom. 18 (1996) 35–42].     

基于航段需求计算网络竞价的近似动态规划方法

竞价控制是收益管理中广泛应用的一种存量控制方法.将网络存量控制问题描述为一个动态规划模型,通过状态向量的一个仿射函数近似动态规划的最优值函数,并且在航段水平上考虑随机需求,最终得到一个计算网络竞价所需的确定性线性规划(DLP),相对于标准的DLP,这个DLP得到了更接近于动态规划最优值的上界.给出了一个列生成算法用于求解这个DLP,并提供了模拟算例,计算结果表明可获得比标准的DLP方法更好的收益.     

Alternative formulations of a combined trip generation,trip distribution,modal split,and trip assignment model

The traditional four-step model has been widely used in travel demand forecasting by considering trip generation, trip distribution, modal split and traffic assignment sequentially in a fixed order. However, this sequential approach suffers from the inconsistency among the level-of-service and flow values in each step of the procedure. In the last two decades, this problem has been addressed by many researchers who have sought to develop combined (or integrated) models that can consider travelers’ choice on different stages simultaneously and give consistent results. In this paper, alternative formulations, including mathematical programming (MP) formulation and variational inequality (VI) formulations, are provided for a combined travel demand model that integrates trip generation, trip distribution, modal split, and traffic assignment using the random utility theory framework. Thus, the proposed alternative formulations not only allow a systematic and consistent treatment of travel choice over different dimensions but also have behavioral richness. Qualitative properties of the formulations are also given to ensure the existence and uniqueness of the solution. Particularly, the model is analyzed for a special but useful case where the probabilistic travel choices are assumed to be a hierarchical logit model. Furthermore, a self-adaptive Goldstein–Levitin–Polyak (GLP) projection algorithm is adopted for solving this special case.     

Fluid dynamics models and their applications in transportation and pricing

Fluid dynamics models provide a powerful deterministic technique to approximate stochasticity in a variety of application areas. In this paper, we study two classes of fluid models, investigate their relationship as well as some of their applications. This analysis allows us to provide analytical models of travel times as they arise in dynamically evolving environments, such as transportation networks as well as supply chains. In particular, using the laws of hydrodynamic theory, we first propose and examine a general second-order fluid model. We consider a first-order approximation of this model and show how it is helpful in analyzing the dynamic traffic equilibrium problem. Furthermore, we present an alternate class of fluid models that are traditionally used in the context of dynamic traffic assignment. By interpreting travel times as price/inventory–sojourn-time relationships, we are also able to connect this approach with a tractable fluid model in the context of dynamic pricing and inventory management.     

Scheduling trams in the morning

In this note, we prove —›-completeness of the following problem: Given a set of trams of different types, which are stacked on sidings in their depot and an order in which trams of specified types are supposed to leave. Is there an assignment of trams to departure times without any shunting movements? In the particular case where the number of sidings is fixed, the problem is solvable in polynomial time. We derive a dynamic program and improve its performance by a state elimination scheme. We implemented three variants of the dynamic program and applied them to random data as well as to real-world data.     

Exact computational approaches to a stochastic uncapacitated single allocation p-hub center problem

The stochastic uncapacitated single allocation p-hub center problem is an extension of the deterministic version which aims to minimize the longest origin-destination path in a hub and spoke network. Considering the stochastic nature of travel times on links is important when designing a network to guarantee the quality of service measured by a maximum delivery time for a proportion of all deliveries. We propose an efficient reformulation for a stochastic p-hub center problem and develop exact solution approaches based on variable reduction and a separation algorithm. We report numerical results to show effectiveness of our new reformulations and approaches by finding global solutions of small-medium sized problems. The combination of model reformulation and a separation algorithm is particularly noteworthy in terms of computational speed.