TITLE

An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers

AUTHOR(S)
Gendreau, Michel; Laporte, Gilbert; Séguin, René
PUB. DATE
May 1995
SOURCE
Transportation Science;May95, Vol. 29 Issue 2, p143
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
In this article, the following stochastic vehicle routing problem is considered. Each customer has a known probability of presence and a random demand. This problem arises in several contexts, e.g., in the design of less-than-truckload collection routes. Because of uncertainty, it may not be possible to follow vehicle routes as planned. Using a stochastic programming framework, the problem is solved in two stages. In a first stage, planned collection routes are designed. In a second stage, when the set of present customers is known, these routes are followed as planned by skipping the absent customers. Whenever the vehicle capacity is attained or exceeded, the vehicle returns to the depot and resumes its collections along the planned route. This generates a penalty. The problem is to design a first stage solution in order to minimize the expected total cost of the second state solution. This is formulated as a stochastic integer program, and solved for the first time to optimality by means of an integer L-shaped method.
ACCESSION #
4454105

 

Related Articles

  • Saliency-Guided Detection of Unknown Objects in RGB-D Indoor Scenes. Jiatong Bao; Yunyi Jia; Yu Cheng; Ning Xi // Sensors (14248220);Sep2015, Vol. 15 Issue 9, p21054 

    This paper studies the problem of detecting unknown objects within indoor environments in an active and natural manner. The visual saliency scheme utilizing both color and depth cues is proposed to arouse the interests of the machine system for detecting unknown objects at salient positions in a...

  • ON THE STOCHASTIC EUCLIDEAN TRAVELLING SALESPERSON PROBLEM FOR DISTRIBUTIONS WITH UNBOUNDED SUPPORT. Rhee, Wansoo T. // Mathematics of Operations Research;May93, Vol. 18 Issue 2, p292 

    We study the asymptotic behavior of the shortest tour Tn through n points X1,…, Xn in Rd (d ≥ 2), where (Xt)t≥ are i.i.d. random variables, whose density f(x) has an unbounded support. Beardwood et at. [2] conjectured that Tn/n1-1/d converges a.s. if and only if ∫f(x)1-1/d...

  • On the Computation and Application of Prototype Point Patterns. Freier, Katherine E. Tranbarger; Schoenberg, Frederic Paik // Open Applied Informatics Journal;2010, Vol. 4, p1 

    This work addresses computational problems related to the implementation of Victor and Purpura's spike-time distance metric for temporal point process data. Three computational algorithms are presented that facilitate the calculation of spike-time distance. In addition, recommendations for...

  • On stochastic sensitivity control in discrete systems. Bashkirtseva, I.; Ryashko, L. // Automation & Remote Control;Sep2010, Vol. 71 Issue 9, p1833 

    For a discrete nonlinear controlled stochastic system, we consider the scatter range of random states around the equilibrium. We consider the problem of designing a regulator that would allow to form a stable stationary probability distribution with a given covariance around this equilibrium....

  • Virtual Slow Manifolds: The Fast Stochastic Case. Gear, C. W.; Givon, D.; Kevrekidis, I. G. // AIP Conference Proceedings;9/9/2009, Vol. 1168 Issue 1, p17 

    The persistently fast evolutionary behavior of certain differential systems may have intrinsically slow features. We consider fast stochastic systems whose solution trajectories are slowly changing distributions and assume that we do not have access to the equations of the system, only to a...

  • Generalized stochastic dominance and bad outcome aversion. Peters, Hans; Schulteis, Tim; Vermeulen, Dries // Social Choice & Welfare;Jul2010, Vol. 35 Issue 2, p285 

    Incomplete preferences over lotteries on a finite set of alternatives satisfying, besides independence and continuity, a property called bad outcome aversion are considered. These preferences are characterized in terms of their specific multi-expected utility representations (cf. Dubra et al., J...

  • A COST-BASED METHODOLOGY FOR STOCHASTIC LINE BALANCING WITH INTERMITTENT LINE STOPPAGES. Silverman, Fred N.; Carter, John C. // Management Science;Apr1986, Vol. 32 Issue 4, p455 

    This paper examines the effect of stochastic task times on the total operating costs of a continuously paced assembly line under the assumption that the line is stopped whenever at least one work station requires more time than allotted. A comprehensive stochastic cost function is integrated...

  • THE RESEARCH OF QUANTUM PHASE ESTIMATION ALGORITHM. Zhuang Jiayu; Zhao Junsuo; Xu Fanjiang; Qiao Peng; Hu Haiying // International Journal of Computer Science, Engineering & Applica;Jun2013, Vol. 3 Issue 3, p61 

    A quantum computation problem is discussed in this paper. Many new features that make quantum computation superior to classical computation can be attributed to quantum coherence effect, which depends on the phase of quantum coherent state. Quantum Fourier transform algorithm, the most commonly...

  • IMPORTANCE SAMPLING AND THE CYCLIC APPROACH. Juneja, Sandeep // Operations Research;Nov/Dec2001, Vol. 49 Issue 6, p900 

    The method of importance sampling is widely used for efficient rare-event simulation of stochastic systems. This method involves simulating the system under a new distribution that accentuates the probability along the most likely paths to the rare event. Traditionally, insights from large...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics