toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) Lagos, F.; Klapp, M.A.; Toriello, A. doi  openurl
  Title Branch-and-price for routing with probabilistic customers Type
  Year 2023 Publication Computers & Industrial Engineering Abbreviated Journal Comput. Ind. Eng.  
  Volume 183 Issue Pages 109429  
  Keywords Vehicle routing; Probabilistic routing; Column generation  
  Abstract We study the Vehicle Routing Problem with Probabilistic Customers (VRP-PC), a two-stage optimization model, which is a fundamental building block within the broad family of stochastic routing problems. This problem is mainly motivated by logistics distribution networks in which customers receive frequent delivery services, and by the last mile problem faced by companies such as UPS and FedEx. In a first stage before customer service requests realize, a dispatcher determines a set of vehicle routes serving all potential customer locations. In a second stage occurring after observing all customer requests, vehicles execute planned routes skipping all locations of customers not requiring service. The objective is to minimize the expected vehicle travel cost assuming known customer realization probabilities. We propose a column generation framework to solve the VRP-PC to a given optimality tolerance. Specifically, we present two novel algorithms, one that under -approximates a solution's expected cost, and another that uses its exact expected cost. Each algorithm is equipped with a route pricing mechanism that iteratively improves the approximation precision of a route's reduced cost; this produces fast route insertions at the start of the algorithm and reaches termination conditions at the end of the execution. Compared to branch-and-cut algorithms for arc-based formulations, our framework can more readily incorporate sequence-dependent constraints, which are typically required in routing problems. We provide a priori and a posteriori performance guarantees for these algorithms, and demonstrate their effectiveness via a computational study on instances with realization probabilities ranging from 0.5 to 0.9.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0360-8352 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:001047678500001 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1858  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: