Optimization Online


Improving Column-Generation for Vehicle Routing Problems via Random Coloring and Parallelization

Miao Yu (miaoyu***at***umich.edu)
Viswanath Nagarajan (viswa***at***umich.edu)
Siqian Shen (siqian***at***umich.edu)

Abstract: We consider a variant of the Vehicle Routing Problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the ``pricing problem'' which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm by Lozano et al. (2015), for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity (Alon et al. (1995)), which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50--957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2\% optimality gaps for most VRP benchmark instances, and less than 1\% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the runtime.

Keywords: vehicle routing problem (VRP), elementary shortest path, random coloring, column generation, parallel computing

Category 1: Network Optimization

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

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


Download: [PDF]

Entry Submitted: 03/11/2021
Entry Accepted: 03/11/2021
Entry Last Modified: 05/25/2021

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