A Paired-Vehicle Recourse Strategy for the Vehicle-Routing Problem with Stochastic Demands

Ak, Aykagan; Erera, Alan L.
May 2007
Transportation Science;May2007, Vol. 41 Issue 2, p222
Academic Journal
This paper presents a paired-vehicle recourse strategy for the vehicle routing problem with stochastic demands (VRPSD). In the VRPSD, a fleet of homogeneous capacitated vehicles is dispatched from a terminal to serve single-period customer demands, which are known in distribution when planning, but only revealed with certainty upon vehicle arrival. While most existing research for this problem focuses on recourse strategies where each vehicle operates independently, this paper alternatively considers a strategy in which vehicles may be coordinated in pairs. A tabu search heuristic is developed to find good solutions to VRPSD instances with homogeneous customer demand distributions given this alternative recourse strategy. Finally, a computational study on a set of test problems with a variety of demand distributions reveals that the paired-recourse strategy may lead to expected travel cost savings of 3% to 25% on problems with 50 or more customers.


Related Articles

  • Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers. Cohn, Amy; Root, Sarah; Wang, Alex; Mohr, Douglas // Transportation Science;May2007, Vol. 41 Issue 2, p238 

    Small package delivery is a multibillion dollar industry with complex planning decisions required to efficiently utilize costly resources and meet tight time requirements. The planning process is typically decomposed into sequential subproblems to establish tractability. This decomposition can...

  • DETERMINING OPTIMUM SHIP ROUTES. Faulkner, Frank D. // Operations Research;Nov/Dec62, Vol. 10 Issue 6, p799 

    A method is given for determining optimum ship routes on a digital computer A ship is assumed to be in a fallout field whose intensity is a known function f(x,y,t) of position and time A typical problem is that of choosing a route to a point where f≦fm, the maximum intensity that can be...

  • Cost functions and duality for stochastic technologies. Chambers, Robert G.; Quiggin, John // American Journal of Agricultural Economics;May98, Vol. 80 Issue 2, p288 

    Discusses the properties of cost functions dual to stochastic production technologies which are derived. Identification of various aspects of agricultural production; Requirements for the existence of cost functions; Consistency of cost functions.

  • A GAME THEORY MODEL OF CONVOY ROUTING. Danskin, J.M. // Operations Research;Nov/Dec62, Vol. 10 Issue 6, p774 

    This paper considers a nonlinear two-person zero-sum game in which one of the players plays over the direct product of two spaces In fact he allocates ships and escort vessels, separately, to various routes, and his antagonist allocates submarines to the various routes Its interest lies first in...

  • Trips for One, for Less.  // Arthur Frommer's Budget Travel (Newsweek LLC);Apr2011, Vol. 14 Issue 3, p33 

    The article offers six ideas for minimizing costs when travelling alone, which includes taking river cruises during the off-season as most cruise companies offer discounts or waive their single-supplement charges, staying at ryokans which are Japanese traditional inns as it always assess per...

  • THE BEST WAY TO GO? Huff, Aaron // Commercial Carrier Journal;Feb2007, Vol. 164 Issue 2, p62 

    The article highlights the adoption of advanced technology by several trucking companies in the U.S. to automate and optimize their routing options. Penske Logistics is using the CellComm propriety solution to increase the accuracy of its routes. Richard Falconio, director of technology at...

  • Modelling environmentally friendly fairways using Lagrangian trajectories: a case study for the Gulf of Finland, the Baltic Sea. Soomere, Tarmo; Berezovski, Mihhail; Quak, Ewald; Viikmäe, Bert // Ocean Dynamics;Oct2011, Vol. 61 Issue 10, p1669 

    We address possibilities of minimising environmental risks using statistical features of current-driven propagation of adverse impacts to the coast. The recently introduced method for finding the optimum locations of potentially dangerous activities (Soomere et al. in Proc Estonian Acad Sci...

  • Over the Top: Sailing the Northeast Passage. Walsh, Don // U.S. Naval Institute Proceedings;Jun2001, Vol. 127 Issue 6, p89 

    Relates the history of the establishment of the Northern Sea Route in the Arctic Regions. Economic and political reasons for establishing the route; Explorations to the Northward Passage; Closure of the region to all foreign ships by the Soviet Union.

  • A Discrete Lagrangian Algorithm for Optimal Routing Problems. Kosmas, O. T.; Vlachos, D. S.; Simos, T. E. // AIP Conference Proceedings;11/6/2008, Vol. 1060 Issue 1, p75 

    The ideas of discrete Lagrangian methods for conservative systems are exploited for the construction of algorithms applicable in optimal ship routing problems. The algorithm presented here is based on the discretisation of Hamilton’s principle of stationary action Lagrangian and...


Read the Article


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

Try another library?
Sign out of this library

Other Topics