CONSTRUCTIVE HEURISTICS FOR THE MULTI-COMPARTMENT VEHICLE ROUTING PROBLEM WITH STOCHASTIC DEMANDS

J. MENDOZA, B. CASTANIER, C. GUÉRET, A. MEDAGLIA, N. VELASCO

TRANSPORTATION SCIENCE, 2011

Abstract

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.

CONTACT

Addrs. Cra. 1 E No. 19A - 40. Mario Laserna Building - School of Engineering, Bogotá, Colombia, Zip 111711, Ph. +(571) 332 4327, 332 4328, 332 4329

Universidad de los Andes | Monitored by Mineducación
Recognition as University: Decree 1297 of May 30th, 1964.
Recognition as legal entity: Resolution 28 of February 23, 1949 Minjusticia.

© Universidad de los Andes. All rights reserved.