Optimization Online


Robust Multi-Period Vehicle Routing under Customer Order Uncertainty

Anirudh Subramanyam (asubramanyam***at***cmu.edu)
Frank Mufalli (Frank_Mufalli***at***praxair.com)
Jose M. Lainez-Aguirre (jose_lainez-aguirre***at***praxair.com)
Jose M. Pinto (Jose_M_Pinto***at***praxair.com)
Chrysanthos E. Gounaris (gounaris***at***cmu.edu)

Abstract: In this paper, we study multi-period vehicle routing problems where the aim is to determine a minimum cost visit schedule and associated routing plan for each period using capacity-constrained vehicles. In our setting, we allow for customer service requests that are received dynamically over the planning horizon. In order to guarantee the generation of routing plans that can flexibly accommodate potential customers who have not yet called in to request service, we model future potential customers as binary random variables, and we seek to determine a visit schedule that remains feasible for all anticipated realizations of service requests. To that end, the decision-making process can be viewed as a multi-stage robust optimization problem with binary recourse decisions. We approximate the multi-stage problem via a non-anticipative two-stage model for which we propose a novel integer programming formulation and a branch-and-cut solution approach. In order to investigate the quality of the solutions we obtain, we also derive a valid lower bound on the multi-stage problem and present numerical schemes for its computation. Computational experiments on instances derived from standard literature benchmark datasets show that our approach is practically tractable and generates high quality robust plans at marginal cost increases above nominal plans.

Keywords: robust optimization, vehicle routing, uncertain customer orders

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )

Citation: Carnegie Mellon University, Pittsburgh, PA, April 2017.

Download: [PDF]

Entry Submitted: 04/06/2017
Entry Accepted: 04/06/2017
Entry Last Modified: 11/15/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society