The Vehicle Routing Problem with Stochastic Two-Dimensional Items

Jean-François Côté (), Michel Gendreau () and Jean-Yves Potvin ()
Additional contact information
Jean-François Côté: Département d'opérations et systèmes de décision and Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport, Université Laval, Québec G1V 0A6, Canada
Michel Gendreau: Département de mathématiques et de génie industriel, École Polytechnique de Montréal, Montréal H3C 3A7, Canada; Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport, Montréal H3C 3J7, Canada
Jean-Yves Potvin: Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport, Montréal H3C 3J7, Canada; Département d’informatique et de recherche opérationnelle, Université de Montréal, Montréal H3T 1J4, Canada

Transportation Science, 2020, vol. 54, issue 2, 453-469

Abstract: We consider a stochastic vehicle routing problem where a discrete probability distribution characterizes the two-dimensional size (height and width) as well as the weight of a subset of items to be delivered to customers. Although some item sizes and weights are not known with certainty when the routes are planned, they become known when it is time to load the vehicles, just before their departure. If it happens that not all items can be loaded in a vehicle, the items of one or more customers are put aside at a penalty or recourse cost. The objective is to minimize the sum of the routing and expected recourse costs. The problem is modeled as a two-stage stochastic program and solved with the integer L-shaped method. Some new inequalities and lower bounds are proposed. Computational results are reported on test instances specifically generated for this problem, as well as on classical instances for the deterministic case.

Keywords: vehicle routing problem; stochastic two-dimensional items; loading constraints; L-shaped method (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0904 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:54:y:2020:i:2:p:453-469

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().