Optimization Online


Robust Optimization for the Vehicle Routing Problem with Multiple Deliverymen

Jonathan De La Vega (jdlvmartinez***at***gmail.com)
Pedro Munari (munari***at***dep.ufscar.br)
Reinaldo Morabito (morabito***at***dep.ufscar.br)

Abstract: This paper studies the vehicle routing problem with time windows and multiple deliverymen in which customer demands are uncertain and belong to a predetermined polytope. In addition to the routing decisions, this problem aims to define the number of deliverymen used to provide the service to the customers on each route. A new mathematical formulation is presented for the deterministic counterpart based on auxiliary variables that define the assignment of customers to routes. Building on this formulation, we apply a static robust optimization approach to obtain a robust counterpart formulation that captures the random nature of customer demand. Due to the difficulty of solving this formulation, we propose a constructive heuristic to generate a robust solution that is used as an initial solution for solving the robust counterpart formulation. The heuristic is an extension of Solomonís heuristic I1. Computational results using problem instances from the literature and risk analysis via Monte-Carlo simulation indicate the potential of this static robust optimization to deal with trade-off between cost and risk. The results also reveal that the proposed approach provides good results even without having exact knowledge of some probabilistic measure of the customer demand.

Keywords: Vehicle Routing Problem with Multiple Deliverymen, Static Robust Linear Optimiza- tion, Uncertain Demand, Heuristics.

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

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

Citation: De La Vega, J.; Munari, P.; Morabito, R. Robust Optimization for the Vehicle Routing Problem with Multiple Deliverymen. Central European Journal of Operations Research, v. 27 (4), p. 905-936, 2019. (https://link.springer.com/article/10.1007/s10100-017-0511-x)

Download: [PDF]

Entry Submitted: 06/06/2017
Entry Accepted: 06/07/2017
Entry Last Modified: 05/23/2020

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