Constructive Heuristics for the Multicompartment Vehicle Routing Problem with Stochastic Demands

Mendoza, Jorge E.; Castanier, Bruno; Guéret, Christelle; Medaglia, Andrés L.; Velasco, Nubia
August 2011
Transportation Science;Aug2011, Vol. 45 Issue 3, p346
Academic Journal
The vehicle routing problem with stochastic demands (VRPSD) consists of designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distribution. This paper tackles a generalization of the VRPSD known as the multicompartment VRPSD (MC-VRPSD), a problem in which each customer demands several products that, because of incompatibility constraints, must be loaded in independent vehicle compartments. To solve the problem, we propose three simple and effective constructive heuristics based on a stochastic programming with recourse formulation. One of the heuristics is an extension to the multicompartment scenario of a savings-based algorithm for the VRPSD; the other two are different versions of a novel look-ahead heuristic that follows a route-first, cluster-second approach. In addition, to enhance the performance of the heuristics these are coupled with a post-optimization procedure based on the classical 2-Opt heuristic. The three algorithms were tested on instances of up to 200 customers from the MC-VRPSD and VRPSD literature. The proposed heuristics unveiled 26 and 12 new best known solutions for a set of 180 MC-VRPSD problems and a 40-instance testbed for the VRPSD, respectively.


Related Articles

  • ON ADAPTIVE-STEP PRIMAL-DUAL INTERIOR-POINT ALGORITHMS FOR LINEAR PROGRAMMING. Mizuno, Shinji; Todd, Michael J.; Ye, Yinyu // Mathematics of Operations Research;Nov93, Vol. 18 Issue 4, p964 

    We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic reasoning for expecting that the algorithms will perform much better in practice...

  • A Parametric Linear Complementarity Technique for Optimal Portfolio Selection with a Risk-free Asset. Pang, Jong-shi // Operations Research;Jul/Aug80, Vol. 28 Issue 4, p927 

    The general single-period optimal portfolio selection problem with a risk-free asset can be solved by a two-stage approach In the first stage, one solves a certain fractional program, and in the second, a simple stochastic program with one single variable. This paper proposes a parametric...

  • Stochastic Heuristic Optimization based Multi-Query Processing in Wireless Sensor Network using Genetic Algorithm. Jeya Bharathi, S. Antony Alice; lagarsamy, K. // International Journal of Computer Applications;Jul2014, Vol. 97, p9 

    Wireless Sensor Network is an infrastructure comprising of sensing, and computing. The communication elements in sensor network give capability to instrument, watch, and respond to events and phenomenon in a particular situation. Query processing in sensor network first transfers the query...

  • Stochastic Operating Room Scheduling for High-Volume Specialties Under Block Booking. Shylo, Oleg V.; Prokopyev, Oleg A.; Schaefer, Andrew J. // INFORMS Journal on Computing;Fall2013, Vol. 25 Issue 4, p682 

    Scheduling elective procedures in an operating suite is a formidable task because of competing performance metrics and uncertain surgery durations. In this paper, we present an optimization framework for batch scheduling within a block booking system that maximizes the expected utilization of...

  • A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs. Akbari Torkestani, Javad; Meybodi, Mohammad // Journal of Supercomputing;Feb2012, Vol. 59 Issue 2, p1035 

    During the last decades, a host of efficient algorithms have been developed for solving the minimum spanning tree problem in deterministic graphs, where the weight associated with the graph edges is assumed to be fixed. Though it is clear that the edge weight varies with time in realistic...

  • Stochastic Programs with Incomplete Information. Ben-Tal, Aharon; Hochman, Eithan // Operations Research;Mar/Apr76, Vol. 24 Issue 2, p336 

    This paper treats a simple recourse problem. We consider the problem of reducing the feasible set into a smaller efficient set when partial information about the random parameters is known. We analyze some examples and give applications to stochastic programs with compete information.

  • A Parallel,Linear Programming- based Heuristic for Large-Scale Set Partitioning Problems. Linderoth, Jeff T.; Lee, Eva K.; Savelsbergh, Martin W.P. // INFORMS Journal on Computing;Summer2001, Vol. 13 Issue 3, p191 

    Examines the parallel, linear programming and implication-based heuristic for solving set partitioning problems (SPP). Procedure for solving the SPP; Separation problem for odd-cycle inequalities; Main computing tasks of algorithm.

  • The Express heuristic for probabilistically constrained integer problems. Bruni, Maria; Beraldi, Patrizia; Laganà, Demetrio // Journal of Heuristics;Jun2013, Vol. 19 Issue 3, p423 

    Integer problems under joint probabilistic constraints with random coefficients in both sides of the constraints are extremely hard from a computational standpoint since two different sources of complexity are merged. The first one is related to the challenging presence of probabilistic...

  • EFFICIENT HEURISTIC ALGORITHMS FOR POSITIVE 0-1 POLYNOMIAL PROGRAMMING PROBLEMS. Granot, Frieda // Management Science;Jul1982, Vol. 28 Issue 7, p829 

    We develop in this paper two types of heuristic methods for solving the positive 0-1 polynomial programming (PP) problem of finding a 0-1 vector x that maximizes c[SUPT]x subject to f(x) ⩽ b where c, b ⩾ 0 and f is an m-vector of polynomials with non-negative coefficients. The...


Read the Article


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

Try another library?
Sign out of this library

Other Topics