Optimization Online


Vehicle Routing Problems with Time Windows and Convex Node Costs

Qie He(qhe***at***umn.edu)
Yongjia Song(ysong3***at***vcu.edu)

Abstract: We consider a variant of the vehicle routing problems with time windows, where the objective includes the inconvenience cost modeled by a convex function on each node. We formulate this mixed integer convex program using a novel set partitioning formulation, by considering all combinations of routes and block structures over the routes. We apply a branch-and-price framework to solve this formulation. To solve the pricing problem, we leverage a recursive algorithm that solves the optimal service time scheduling problem given a fixed route, and develop a labeling algorithm with a dominance rule that is easy to check. In our computational study, we show the effectiveness of the labeling algorithm compared to state-of-the-art mixed integer convex programming solvers on an extensive set of vehicle routing problems with time windows and quadratic inconvenience costs.

Keywords: Vehicle routing problem, Branch-and-price, Labeling algorithm, Convex node cost

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

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 08/30/2016
Entry Accepted: 08/30/2016
Entry Last Modified: 08/30/2016

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